Método de uniéndose de vecinos

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
Este mapa de distancia genética hecho en 2002 es una estimación de los 18 grupos humanos del mundo por un método de uniéndose de vecinos basó de 23 tipos de información genética. Fue hecho por Saitou Naruya (japonés:斎藤成也), profesor del Instituto Nacional (Japonés) de Genética[1] Este árbol se muestra ramas para negroides, mongoloides de Asia, caucasoides, australoides y «amerindiodes».

En bioinformática, el método de unión de vecinos es un método de agrupación de abajo hacia arriba para la creación de árboles fenéticos (fenogramas), creado por Naruya Saitou y Masatoshi Nei en 1987.[2] Por lo general, se utiliza para árboles de secuencias de ADN o de proteína, para lo cual, el algoritmo requiere del conocimiento de la distancia que existe entre cada par de taxones (por ejemplo, especies o secuencias) para formar el árbol.[3]

El algoritmo[editar]

Archivo:Neighbor-joining 7 taxa start to finish.png
A partir de un árbol de la estrella (A), la matriz Q se calcula y se utiliza para elegir un par de nodos para unirse, en este caso, «f» y «g». Estos se unen a un nodo recién creado, «u», como se muestra en (B). La parte del árbol que se muestra como líneas de puntos ha sido arreglado y no se cambiará en medidas de unirse posteriores. Las distancias de nodo «U» a los nodos «a» y «e» se calculan a partir de la fórmula que figura en el texto. A continuación, este proceso se repite, utilizando una matriz de sólo las distancias entre los nodos, «a», «b», «c», «d», «e», «y» y «u», y una matriz «Q» derivada de ella. En este caso «u» y «e» son unidos a la «v» recién creado, como se muestra en (C). Dos iteraciones más conducen primero a (D), y luego a (E), momento en el que el algoritmo se realiza, como el árbol está completamente resuelto.

El método de "Unión de vecinos" parte de una matriz de distancias, que indica la distancia entre cada par de taxones. El algoritmo comienza con un árbol completamente sin resolver, cuya topología corresponde a la de una red en estrella, y aplica los siguientes pasos hasta que el árbol está completamente resuelto y las longitudes de sus ramas se conocen:

  1. Basado en la matriz de distancias actual calcular el matriz Q (definindo abajo)
  2. Encontrar el par de taxones para los que Q(i,j) tiene su valor más bajo. Añadir un nuevo nodo al árbol, uniéndose estos taxones para el resto del árbol. En la figura de la derecha, «F» y «G» se unen al árbol por el nodo nuevo «U».
  3. Calcular la distancia desde cada uno de los taxones en el par a este nodo nuevo.
  4. Calcular la distancia desde cada uno de los taxones fuera de este par al nodo nuevo.
  5. Comenzar el algoritmo otra vez, sustituyendo el par de vecinos unidos con el nodo nuevo y usando las distancias calculadas en la medida anterior.

La matriz Q[editar]

Basado en una matriz de distancia en relación al taxón r, calcular Q como sigue:

Q(i,j)=(r-2)d(i,j)-\sum_{k=1}^r d(i,k) - \sum_{k=1}^r d(j,k)

donde d(i,j) es la distancia entre taxones i y j, y k es cualquier otro nodo no i ni j respectivamente.

Distancia de los miembros del par al nodo nuevo[editar]

Para cada vecino en el par acaba de unirse, utilice la siguiente fórmula para calcular la distancia al nodo nuevo. (Taxones f y g son los taxones emparejado y u es el nodo recién generado):

d(f,u)=\frac{1}{2}d(f,g)+\frac{1}{2(r-2)} \left [ \sum_{k=1}^r d(f,k) - \sum_{k=1}^r d(g,k) \right ] \quad

y, por la reflexión:

d(g,u)=d(f,g)-d(f,u) \quad

Distancia de los otros taxones al nuevo nodo[editar]

Para cada taxón no se considera en la medida anterior, se calcula la distancia hasta el nodo nuevo como sigue:

d(u,k)=\frac{1}{2} [d(f,k)+d(g,k)-d(f,g)]

donde u es el nodo nuevo, k es el nodo para el que se desea calcular la distancia y f y g son los miembros del par acaba de unirse.

Complejidad[editar]

Uniéndose de vecinos en un conjunto de r taxones se requiere r-3 iteraciones. En cada medida hay que construir y buscar una matriz Q.

Inicialmente la matriz Q es tamaño r\times r, entonces la siguiente medida es (r-1)\times(r-1), etcétera. Esto conduce a un algoritmo con una complejidad de tiempo de O(r^3).

Ejemplo[editar]

Se supone que tenga cuatro taxones (A, B, C, D) y la matriz de distancias como sigue:

A B C D
A 0 7 11 14
B 7 0 6 9
C 11 6 0 7
D 14 9 7 0

Se obtenía los siguientes valores para la matriz Q:

A B C D
A 0 −40 −34 −34
B −40 0 −34 −34
C −34 −34 0 −40
D −34 −34 −40 0

En el ejemplo anterior, dos pares de taxones tienen el valor más bajo de −40. Se puede seleccionar cualquiera de ellos para la segunda medida del algoritmo. Se sigue el ejemplo, en el supuesto de que nos unimos a los taxones A y B juntos. Si u indique el nodo nuevo, entonces las longitudes de las ramas de los bordes de la \{A, u\} y de la \{B, u\} serían, respectivamente, 6 y 1, por la fórmula anterior.

Se procede a la actualización de la matriz de distancias, calculando d(u,k) de acuerdo con la fórmula anterior para cada nodo k. En este caso se obtiene d(u,C)=5 y d(u,D)=8. La matriz de distancias resultante es:

u C D
u 0 5 8
C 5 0 7
D 8 7 0

La topología del árbol se resuelve completamente en este punto, así que Q no se necesita ser calculada y los vecinos no se necesitan ser unidos. Sin embargo, estas distancias pueden ser utilizadas para obtener las longitudes restantes de las 3 ramas, como se muestra en la figura.

Referencias[editar]

  1. «斎藤成也 Naruya, S. Kyushu Museum. 2002. February 2, 2007». Museum.kyushu-u.ac.jp. Consultado el 2013-12-15.
  2. Saitou N, Nei M. "The neighbor-joining method: a new method for reconstructing phylogenetic trees." Molecular Biology and Evolution, volumen 4, expedición 4, pp. 406-425, julio 1987.
  3. Xavier Didelot (2010). «Sequence-Based Analysis of Bacterial Population Structures». En D. Ashley Robinson, Daniel Falush, Edward J. Feil. Bacterial Population Genetics in Infectious Disease. John Wiley and Sons. pp. 46–47. ISBN 978-0-470-42474-2.