Vecino uniéndose - Neighbor joining

En bioinformática , la unión de vecinos es un método de agrupamiento de abajo hacia arriba (aglomerativo) para la creación de árboles filogenéticos , creado por Naruya Saitou y Masatoshi Nei en 1987. Usualmente utilizado para árboles basados ​​en datos de secuencias de ADN o proteínas , el algoritmo requiere conocimiento de la distancia entre cada par de taxones (por ejemplo, especies o secuencias) para formar el árbol.

El algoritmo

Comenzando con un árbol de estrellas (A), la matriz Q se calcula y se usa para elegir un par de nodos para unir, 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 continuas ahora está fija y no se cambiará en los siguientes pasos de unión. Las distancias desde el nodo u a los nodos ae se calculan a partir de la ecuación ( 3 ). Luego, este proceso se repite, utilizando una matriz de solo las distancias entre los nodos, a, b, c, d, e y u, y una matriz Q derivada de ella. En este caso, uye se unen a la v recién creada, como se muestra en (C). Dos iteraciones más conducen primero a (D) y luego a (E), momento en el que se realiza el algoritmo, ya que el árbol está completamente resuelto.

La unión de vecinos toma como entrada una matriz de distancias que especifica 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 , e itera sobre los siguientes pasos hasta que el árbol está completamente resuelto y se conocen todas las longitudes de las ramas:

1. Basándose en la matriz de distancia actual, calcule la matriz (definida a continuación).${\ displaystyle Q}$
2. Encuentre el par de taxones distintos iyj (es decir, con ) para el que tiene su valor más bajo. Estos taxones se unen a un nodo recién creado, que está conectado al nodo central. En la figura de la derecha, fyg se unen al nuevo nodo u.${\ Displaystyle i \ neq j}$${\ Displaystyle Q (i, j)}$
3. Calcule la distancia desde cada uno de los taxones del par hasta este nuevo nodo.
4. Calcule la distancia desde cada uno de los taxones fuera de este par al nuevo nodo.
5. Inicie el algoritmo nuevamente, reemplazando el par de vecinos unidos con el nuevo nodo y usando las distancias calculadas en el paso anterior.

La matriz Q

Con base en una matriz de distancias que relaciona los taxones, calcule de la siguiente manera: ${\ Displaystyle n}$${\ displaystyle Q}$

${\ Displaystyle Q (i, j) = (n-2) re (i, j) - \ sum _ {k = 1} ^ {n} re (i, k) - \ sum _ {k = 1} ^ {n} d (j, k)}$

( 1 )

donde es la distancia entre taxones y . ${\ Displaystyle d (i, j)}$${\ Displaystyle i}$${\ Displaystyle j}$

Distancia de los miembros de la pareja al nuevo nodo

Para cada uno de los taxones del par que se está uniendo, use la siguiente fórmula para calcular la distancia al nuevo nodo:

${\ Displaystyle \ delta (f, u) = {\ frac {1} {2}} d (f, g) + {\ frac {1} {2 (n-2)}} \ left [\ sum _ { k = 1} ^ {n} d (f, k) - \ sum _ {k = 1} ^ {n} d (g, k) \ right] \ quad}$

( 2 )

y:

${\ Displaystyle \ delta (g, u) = re (f, g) - \ delta (f, u) \ quad}$

Taxa y son los taxones emparejados y es el nodo recién creado. Las ramas que unen y y y , y sus longitudes, y son parte del árbol que se está creando gradualmente; no afectan ni se ven afectados por los pasos posteriores de unión de vecinos. ${\ Displaystyle f}$${\ Displaystyle g}$${\ Displaystyle u}$${\ Displaystyle f}$${\ Displaystyle u}$${\ Displaystyle g}$${\ Displaystyle u}$${\ Displaystyle \ delta (f, u)}$${\ Displaystyle \ delta (g, u)}$

Distancia de los otros taxones del nuevo nodo

Para cada taxón no considerado en el paso anterior, calculamos la distancia al nuevo nodo de la siguiente manera:

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

( 3 )

donde está el nuevo nodo, es el nodo al que queremos calcular la distancia y son los miembros del par que se acaba de unir. ${\ Displaystyle u}$${\ Displaystyle k}$${\ Displaystyle f}$${\ Displaystyle g}$

Complejidad

La unión de vecinos en un conjunto de taxones requiere iteraciones. En cada paso uno tiene que construir y buscar una matriz. Inicialmente, la matriz es el tamaño , luego el siguiente paso es , etc. Implementar esto de una manera sencilla conduce a un algoritmo con una complejidad de tiempo de ; Existen implementaciones que usan heurística para hacerlo mucho mejor que esto en promedio. ${\ Displaystyle n}$${\ Displaystyle n-3}$${\ displaystyle Q}$${\ displaystyle Q}$${\ Displaystyle n \ times n}$${\ Displaystyle (n-1) \ times (n-1)}$${\ Displaystyle O (n ^ {3})}$

Ejemplo

Vecino que se une con 5 taxones. En este caso, 2 pasos de unión de vecinos dan un árbol con topología completamente resuelta. Las ramas del árbol resultante están etiquetadas con sus longitudes.

Supongamos que tenemos cinco taxones y la siguiente matriz de distancias : ${\ Displaystyle (a, b, c, d, e)}$${\ Displaystyle D}$

Primer paso

Primera unión

Calculamos los valores mediante la ecuación ( 1 ). Por ejemplo: ${\ Displaystyle Q_ {1}}$

${\ Displaystyle Q_ {1} (a, b) = (n-2) re (a, b) - \ sum _ {k = 1} ^ {5} re (a, k) - \ sum _ {k = 1} ^ {5} d (b, k)}$

${\ Displaystyle = (5-2) \ times 5- (5 + 9 + 9 + 8) - (5 + 10 + 10 + 9) = 15-31-34 = -50}$

Obtenemos los siguientes valores para la matriz (los elementos diagonales de la matriz no se utilizan y aquí se omiten): ${\ Displaystyle Q_ {1}}$

En el ejemplo anterior ,. Este es el valor más pequeño de , por lo que unimos los elementos y . ${\ Displaystyle Q_ {1} (a, b) = - 50}$${\ Displaystyle Q_ {1}}$${\ Displaystyle a}$${\ Displaystyle b}$

Estimación de la longitud de la primera rama

Dejar que denotan el nuevo nodo. Por la ecuación ( 2 ), arriba, las ramas de unión y a continuación, tienen longitudes: ${\ Displaystyle u}$${\ Displaystyle a}$${\ Displaystyle b}$${\ Displaystyle u}$

${\ Displaystyle \ delta (a, u) = {\ frac {1} {2}} d (a, b) + {\ frac {1} {2 (5-2)}} \ left [\ sum _ { k = 1} ^ {5} d (a, k) - \ sum _ {k = 1} ^ {5} d (b, k) \ right] \ quad = {\ frac {5} {2}} + {\ frac {31-34} {6}} = 2}$

${\ Displaystyle \ delta (b, u) = re (a, b) - \ delta (a, u) \ quad = 5-2 = 3}$

Actualización de la primera matriz de distancias

Luego procedemos a actualizar la matriz de distancia inicial en una nueva matriz de distancia (ver más abajo), reducida en tamaño en una fila y una columna debido a la unión de with con su vecino . Usando la ecuación ( 3 ) anterior, calculamos la distancia desde cada uno de los otros nodos además de y . En este caso obtenemos: ${\ Displaystyle D}$${\ Displaystyle D_ {1}}$${\ Displaystyle a}$${\ Displaystyle b}$${\ Displaystyle u}$${\ Displaystyle u}$${\ Displaystyle a}$${\ Displaystyle b}$

${\ Displaystyle d (u, c) = {\ frac {1} {2}} [d (a, c) + d (b, c) -d (a, b)] = {\ frac {9 + 10 -5} {2}} = 7}$

${\ Displaystyle re (u, re) = {\ frac {1} {2}} [re (a, re) + re (b, re) -d (a, segundo)] = {\ frac {9 + 10 -5} {2}} = 7}$

${\ Displaystyle re (u, e) = {\ frac {1} {2}} [re (a, e) + re (b, e) -d (a, b)] = {\ frac {8 + 9 -5} {2}} = 6}$

La matriz de distancias resultante es: ${\ Displaystyle D_ {1}}$

Los valores en negrita corresponden a las distancias recién calculadas, mientras que los valores en cursiva no se ven afectados por la actualización de la matriz, ya que corresponden a distancias entre elementos no involucrados en la primera unión de taxones. ${\ Displaystyle D_ {1}}$

Segundo paso

Segunda unión

La matriz correspondiente es: ${\ Displaystyle Q_ {2}}$

Podemos elegir entre unirnos y , o unirnos y ; ambos pares tienen el valor mínimo de , y cualquiera de las opciones conduce al mismo resultado. Para ser concretos, vamos a unir y y llamar al nuevo nodo . ${\ Displaystyle u}$${\ Displaystyle c}$${\ Displaystyle d}$${\ Displaystyle e}$${\ Displaystyle Q_ {2}}$${\ displaystyle -28}$${\ Displaystyle u}$${\ Displaystyle c}$${\ Displaystyle v}$

Estimación de la longitud de la segunda rama

Las longitudes de las ramas de unión y a puede ser calculada: ${\ Displaystyle u}$${\ Displaystyle c}$${\ Displaystyle v}$

${\ Displaystyle \ delta (u, v) = {\ frac {1} {2}} d (u, c) + {\ frac {1} {2 (4-2)}} \ left [\ sum _ { k = 1} ^ {4} d (u, k) - \ sum _ {k = 1} ^ {4} d (c, k) \ right] \ quad = {\ frac {7} {2}} + {\ frac {20-22} {4}} = 3}$

${\ Displaystyle \ delta (c, v) = d (u, c) - \ delta (u, v) \ quad = 7-3 = 4}$

La unión de los elementos y el cálculo de la longitud de la rama ayudan a dibujar el árbol de unión vecino como se muestra en la figura .

Actualización de la segunda matriz de distancia

La matriz de distancia actualizado para los 3 nodos restantes, , , y , ahora se calcula: ${\ Displaystyle D_ {2}}$${\ Displaystyle v}$${\ Displaystyle d}$${\ Displaystyle e}$

${\ Displaystyle re (v, re) = {\ frac {1} {2}} [re (u, re) + re (do, re) -d (u, do)] = {\ frac {7 + 8 -7} {2}} = 4}$

${\ Displaystyle re (v, mi) = {\ frac {1} {2}} [re (u, mi) + re (do, mi) -d (u, do)] = {\ frac {6 + 7 -7} {2}} = 3}$

Último paso

La topología del árbol está completamente resuelta en este punto. Sin embargo, para mayor claridad, podemos calcular la matriz. Por ejemplo: ${\ Displaystyle Q_ {3}}$

${\ Displaystyle Q_ {3} (v, mi) = (3-2) re (v, mi) - \ sum _ {k = 1} ^ {3} re (v, k) - \ sum _ {k = 1} ^ {3} d (e, k) = 3-7-6 = -10}$

Para ser más concretos, unámonos y y llamemos al último nodo . Se pueden calcular las longitudes de las tres ramas restantes: ${\ Displaystyle v}$${\ Displaystyle d}$${\ Displaystyle w}$

${\ Displaystyle \ delta (v, w) = {\ frac {1} {2}} d (v, d) + {\ frac {1} {2 (3-2)}} \ left [\ sum _ { k = 1} ^ {3} d (v, k) - \ sum _ {k = 1} ^ {3} d (d, k) \ right] \ quad = {\ frac {4} {2}} + {\ frac {7-7} {2}} = 2}$

${\ Displaystyle \ delta (w, d) = re (v, d) - \ delta (v, w) = 4-2 = 2}$

${\ Displaystyle \ delta (w, mi) = re (v, mi) - \ delta (v, w) = 3-2 = 1}$

El árbol de unión vecino ahora está completo, como se muestra en la figura .

Conclusión: distancias aditivas

Este ejemplo representa un caso idealizado: observe que si nos movemos de un taxón a otro a lo largo de las ramas del árbol y sumamos las longitudes de las ramas atravesadas, el resultado es igual a la distancia entre esos taxones en la matriz de distancia de entrada. Por ejemplo, pasando de a tenemos . Una matriz de distancias cuyas distancias concuerdan de esta manera con algún árbol se dice que es "aditiva", una propiedad que es rara en la práctica. No obstante, es importante señalar que, dada una matriz de distancias aditiva como entrada, la unión de vecinos está garantizada para encontrar el árbol cuyas distancias entre taxones concuerden con ella. ${\ Displaystyle d}$${\ Displaystyle b}$${\ Displaystyle 2 + 2 + 3 + 3 = 10}$

Unión de vecinos como evolución mínima

La unión de vecinos puede verse como una heurística codiciosa para el criterio de Evolución Mínima Equilibrada (BME). Para cada topología, BME define la longitud del árbol (suma de las longitudes de las ramas) como una suma ponderada particular de las distancias en la matriz de distancias, con los pesos dependiendo de la topología. La topología óptima de BME es la que minimiza esta longitud de árbol. El vecino que se une en cada paso se une con avidez a ese par de taxones que darán la mayor disminución en la longitud estimada del árbol. Este procedimiento no garantiza encontrar el óptimo para el criterio de BME, aunque a menudo lo hace y suele estar bastante cerca.

Ventajas y desventajas

La principal virtud de NJ es que es rápido en comparación con los métodos de mínimos cuadrados , máxima parsimonia y máxima verosimilitud . Esto lo hace práctico para analizar grandes conjuntos de datos (cientos o miles de taxones) y para bootstrapping , para lo cual otros medios de análisis (por ejemplo, máxima parsimonia , máxima probabilidad ) pueden resultar prohibitivos desde el punto de vista computacional .

La unión de vecinos tiene la propiedad de que si la matriz de distancias de entrada es correcta, el árbol de salida será correcto. Además, la exactitud de la topología del árbol de salida está garantizada siempre que la matriz de distancia sea 'casi aditiva', específicamente si cada entrada en la matriz de distancia difiere de la distancia real en menos de la mitad de la longitud de la rama más corta del árbol. En la práctica, la matriz de distancias rara vez satisface esta condición, pero la unión de vecinos a menudo construye la topología de árbol correcta de todos modos. La exactitud de la unión de vecinos para matrices de distancias casi aditivas implica que es estadísticamente consistente en muchos modelos de evolución; dados datos de suficiente longitud, la unión de vecinos reconstruirá el árbol verdadero con alta probabilidad. En comparación con UPGMA y WPGMA , la unión de vecinos tiene la ventaja de que no asume que todos los linajes evolucionan al mismo ritmo ( hipótesis del reloj molecular ).

Sin embargo, la unión de vecinos ha sido reemplazada en gran medida por métodos filogenéticos que no se basan en medidas de distancia y ofrecen una precisión superior en la mayoría de las condiciones. La unión de vecinos tiene la característica indeseable de que a menudo asigna longitudes negativas a algunas de las ramas.

Implementaciones y variantes

Hay muchos programas disponibles que implementan la unión de vecinos. RapidNJ y NINJA son implementaciones rápidas con tiempos de ejecución típicos proporcionales a aproximadamente el cuadrado del número de taxones. BIONJ y Weighbor son variantes de uniones vecinas que mejoran su precisión al hacer uso del hecho de que las distancias más cortas en la matriz de distancias son generalmente más conocidas que las distancias más largas. FastME es una implementación del método de evolución mínima equilibrada estrechamente relacionado.

Ver también

• Búsqueda de vecino más cercano
• UPGMA y WPGMA
• Evolución mínima

Referencias

Otras fuentes

enlaces externos

• El método de unión de vecinos : un tutorial