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. Basándose en la matriz de distancias actual calcula la matriz Q (definida abajo).
  2. A continuación, busca el par de taxones para los que Q(i,j) tiene su valor más bajo. Estos taxones se unen para formar un nuevo nodo que se une al resto del árbol. En la figura de la derecha, «F» y «G» se unen al árbol por el nodo nuevo «U».
  3. Se calcula la distancia desde cada uno de los taxones del par a este nodo nuevo.
  4. Se calcula la distancia desde cada uno de los taxones que no pertenecen a este nuevo par al nodo nuevo.
  5. Se ejecuta el algoritmo otra vez, sustituyendo el par de taxones recién unidos por el nodo nuevo utilizando las distancias calculadas en el paso anterior.

La matriz Q[editar]

Basado en una matriz de distancia en relación al taxón r, se calcula 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 del par que 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 analizado en el paso 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]

El cálculo del método de Unión de vecinos para un conjunto de r taxones requiere r-3 iteraciones. En cada paso hay que construir y buscar una matriz Q.

Inicialmente la matriz Q tiene un tamaño r\times r, de manera que el siguiente paso 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 paso del algoritmo. Se sigue el ejemplo, en el supuesto de que unimos 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 necesita ser calculada ni es necesario buscar nuevos nodos. 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 15 de diciembre de 2013. 
  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.