Vecino uniéndose

Método de agrupamiento de abajo hacia arriba para crear árboles filogenéticos

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. ^[1] Generalmente basado 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 crear el árbol filogenético. ^[2]

El algoritmo

Partiendo de un árbol en estrella (A), se calcula la matriz Q y se utiliza 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 sólidas ahora está fija y no se modificará en los pasos de unión posteriores. 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, u y e se unen al nodo recién creado v, como se muestra en (C). Dos iteraciones más conducen primero a (D) y luego a (E), momento en el que el algoritmo finaliza, 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 , y repite los siguientes pasos hasta que el árbol se resuelve por completo y se conocen todas las longitudes de las ramas:

1. Basándose en la matriz de distancia actual, calcule una matriz (definida a continuación). ${\displaystyle Q}$
2. Encuentre el par de taxones distintos i y j (es decir, con ) para el cual es más pequeño. Haga un nuevo nodo que una los taxones i y j, y conecte el nuevo nodo al nodo central. Por ejemplo, en la parte (B) de la figura de la derecha, se crea el nodo u para unir f y g. ${\displaystyle i\neq j}$ ${\displaystyle Q(i,j)}$
3. Calcula la distancia desde cada uno de los taxones del par hasta este nuevo nodo.
4. Calcula la distancia desde cada uno de los taxones fuera de este par hasta el nuevo nodo.
5. Inicie el algoritmo nuevamente, reemplazando el par de vecinos unidos con el nuevo nodo y utilizando las distancias calculadas en el paso anterior.

La matriz Q

A partir de una matriz de distancias que relaciona los taxones, calcule la matriz x de la siguiente manera: ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle Q}$

¿Dónde está la distancia entre taxones y ? ${\displaystyle d(i,j)}$ ${\displaystyle i}$ ${\displaystyle j}$

Distancia de los miembros del par al nuevo nodo

Para cada uno de los taxones del par que se va a unir, utilice la siguiente fórmula para calcular la distancia al nuevo nodo:

y:

${\displaystyle \delta (g,u)=d(f,g)-\delta (f,u)\quad }$

Los taxones 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 son afectadas 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 desde el nuevo nodo

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

donde está el nuevo nodo, es el nodo al que queremos calcular la distancia y y son los miembros del par recién unido. ${\displaystyle u}$ ${\displaystyle k}$ ${\displaystyle f}$ ${\displaystyle g}$

Complejidad

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

Ejemplo

Unión de vecinos con 5 taxones. En este caso, 2 pasos de unión de vecinos dan como resultado 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 incorporación

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

${\displaystyle Q_{1}(a,b)=(n-2)d(a,b)-\sum _{k=1}^{5}d(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 se omiten aquí): ${\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

Sea el nuevo nodo el que se indica. Por la ecuación ( 2 ), arriba, las ramas que se unen a y tienen entonces 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)=d(a,b)-\delta (a,u)\quad =5-2=3}$

Primera actualización de la matriz de distancias

Luego procedemos a actualizar la matriz de distancia inicial en una nueva matriz de distancia (ver abajo), reducida en tamaño en una fila y una columna debido a la unión de con en su vecino . Usando la ecuación ( 3 ) anterior, calculamos la distancia desde a 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 d(u,d)={\frac {1}{2}}[d(a,d)+d(b,d)-d(a,b)]={\frac {9+10-5}{2}}=7}$

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

La matriz de distancia 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 unir y , o unir y ; ambos pares tienen el valor mínimo de , y cualquiera de las dos opciones conduce al mismo resultado. Para ser más concretos, unamos y y llamemos 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 que unen a y se pueden calcular: ${\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 de vecinos como se muestra en la figura.

Segunda actualización de la matriz de distancias

Ahora se calcula la matriz de distancia actualizada para los 3 nodos restantes, , , y : ${\displaystyle D_{2}}$ ${\displaystyle v}$ ${\displaystyle d}$ ${\displaystyle e}$

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

${\displaystyle d(v,e)={\frac {1}{2}}[d(u,e)+d(c,e)-d(u,c)]={\frac {6+7-7}{2}}=3}$

Paso final

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,e)=(3-2)d(v,e)-\sum _{k=1}^{3}d(v,k)-\sum _{k=1}^{3}d(e,k)=3-7-6=-10}$

Para ser más concretos, uniremos y y llamaremos al último nodo . Las longitudes de las tres ramas restantes se pueden calcular: ${\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)=d(v,d)-\delta (v,w)=4-2=2}$

${\displaystyle \delta (w,e)=d(v,e)-\delta (v,w)=3-2=1}$

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

Conclusión: distancias aditivas

Este ejemplo representa un caso idealizado: nótese 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 recorridas, el resultado es igual a la distancia entre esos taxones en la matriz de distancias de entrada. Por ejemplo, al pasar 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 notar que, dada una matriz de distancias aditiva como entrada, la unión vecinal garantiza encontrar el árbol cuyas distancias entre taxones concuerdan con ella. ${\displaystyle d}$ ${\displaystyle b}$ ${\displaystyle 2+2+3+3=10}$

Vecino que se incorpora como evolución mínima

La unión de vecinos puede considerarse una heurística voraz para el criterio de evolución mínima equilibrada ^[5] (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 pesos que dependen de la topología. La topología óptima de BME es la que minimiza esta longitud del árbol. NJ en cada paso une vorazmente ese par de taxones que dará 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 ser bastante cercano. ^[5]

Ventajas y desventajas

La principal virtud de NJ es que es rápido ^{[6] : 466} en comparación con los métodos de mínimos cuadrados , máxima parsimonia y máxima verosimilitud . ^[6] Esto lo hace práctico para analizar grandes conjuntos de datos (cientos o miles de taxones) y para el bootstrap , para cuyos fines otros medios de análisis (por ejemplo, máxima parsimonia , máxima verosimilitud ) pueden ser computacionalmente prohibitivos.

La unión de vecinos tiene la propiedad de que si la matriz de distancia de entrada es correcta, entonces el árbol de salida será correcto. Además, la corrección 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 verdadera en menos de la mitad de la longitud de la rama más corta en el árbol. ^[7] En la práctica, la matriz de distancia rara vez satisface esta condición, pero la unión de vecinos a menudo construye la topología de árbol correcta de todos modos. ^[8] La corrección de la unión de vecinos para matrices de distancia casi aditivas implica que es estadísticamente consistente bajo muchos modelos de evolución; dados datos de longitud suficiente, 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. ^{[ cita requerida ]} 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. Entre las implementaciones de NJ canónica (es decir, que utilizan los criterios de optimización de NJ clásicos, por lo que dan los mismos resultados), RapidNJ (iniciado en 2003, actualización importante en 2011, aún actualizado en 2023) ^[9] y NINJA (iniciado en 2009, última actualización en 2013) ^[10] se consideran de última generación. Tienen tiempos de ejecución típicos proporcionales a aproximadamente el cuadrado del número de taxones.

Las variantes que se desvían del canónico incluyen:

• BIONJ (1997) ^[11] y Weighbor (2000), ^[12] mejoraron la precisión aprovechando el hecho de que las distancias más cortas en la matriz de distancias generalmente se conocen mejor que las distancias más largas. Los dos métodos se han ampliado para que funcionen en matrices de distancias incompletas. ^[13]
• "Fast NJ" recuerda el mejor nodo y siempre es O(n^2); "relax NJ" realiza una búsqueda de ascenso de colina y conserva la complejidad del peor caso de O(n^3). Rapid NJ es más rápido que el simple NJ relajado. ^[14]
• FastME es una implementación del método de evolución mínima equilibrada (BME), estrechamente relacionado (véase § Unión de vecinos como evolución mínima). Es casi tan rápido como NJ y más preciso que éste. Comienza con un árbol aproximado y luego lo mejora utilizando un conjunto de movimientos topológicos como los intercambios de vecinos más cercanos (NNI). ^[15] FastTree es un método relacionado. Funciona en "perfiles" de secuencia en lugar de una matriz. Comienza con un árbol aproximado a NJ, lo reorganiza en BME y luego lo reorganiza en un árbol de máxima verosimilitud aproximado. ^[16]

Véase también

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

Referencias

1. Saitou, N.; Nei, M. (1 de julio de 1987). "El método de unión vecinal: un nuevo método para reconstruir árboles filogenéticos". Biología molecular y evolución . 4 (4): 406–425. doi : 10.1093/oxfordjournals.molbev.a040454 . PMID  3447015.
2. Xavier Didelot (2010). "Análisis basado en secuencias de estructuras de poblaciones bacterianas". En D. Ashley Robinson; Daniel Falush; Edward J. Feil (eds.). Genética de poblaciones bacterianas en enfermedades infecciosas . John Wiley and Sons. págs. 46–47. ISBN 978-0-470-42474-2.
3. Studier, JA; Keppler, KJ (noviembre de 1988). "Una nota sobre el algoritmo de unión vecinal de Saitou y Nei". Biología molecular y evolución . 5 (6): 729–31. doi : 10.1093/oxfordjournals.molbev.a040527 . ISSN  1537-1719. PMID  3221794.
4. Mailund, Thomas; Brodal, GerthS; Fagerberg, Rolf; Pedersen, ChristianNS; Phillips, Derek (2006). "Remodelación del método de unión vecinal". BMC Bioinformatics . 7 (1): 29. doi : 10.1186/1471-2105-7-29 . PMC 3271233 . PMID  16423304. 
5. Gascuel O, Steel M (2006). "Neighbor-joining revealed" (Se revela la unión de vecinos). Mol Biol Evol . 23 (11): 1997–2000. doi : 10.1093/molbev/msl072 . PMID:  16877499.
6. Kuhner, MK; Felsenstein, J. (1994-05-01). "Una comparación de simulación de algoritmos de filogenia bajo tasas evolutivas iguales y desiguales". Biología molecular y evolución . 11 (3): 459–468. doi : 10.1093/oxfordjournals.molbev.a040126 . ISSN  0737-4038. PMID  8015439.
7. Atteson K (1997). "El rendimiento de los algoritmos de unión de vecinos en la reconstrucción de filogenia", págs. 101-110. En Jiang, T. y Lee, D., eds., Lecture Notes in Computer Science, 1276 , Springer-Verlag, Berlín. COCOON '97.
8. Mihaescu R, Levy D, Pachter L (2009). "Por qué funciona la unión de vecinos". Algorithmica . 54 (1): 1–24. arXiv : cs/0602041 . doi :10.1007/s00453-007-9116-4. S2CID  2462145.{{cite journal}}: CS1 maint: multiple names: authors list (link)
9. "RapidNJ". birc.au.dk .
10. "NINJA: una herramienta para la inferencia de filogenia mediante unión de vecinos a gran escala - Inicio". wheelerlab.org .
11. "ATGC: BioNJ". www.atgc-montpellier.fr .
12. "Página de inicio de WEIGHBOR". 5 de marzo de 2015. Archivado desde el original el 5 de marzo de 2015.
13. Criscuolo, Alexis; Gascuel, Olivier (diciembre de 2008). "Algoritmos rápidos tipo NJ para tratar con matrices de distancia incompletas". BMC Bioinformatics . 9 (1): 166. doi : 10.1186/1471-2105-9-166 . PMC 2335114 . PMID  18366787. 
14. Simonsen, Martin; Mailund, Thomas; Pedersen, Christian NS (2008). "Unión rápida de vecinos" (PDF) . Algoritmos en bioinformática . Apuntes de clase en informática. Vol. 5251. págs. 113-122. doi :10.1007/978-3-540-87361-7_10. ISBN 978-3-540-87360-0.
15. "ATGC: FastME". www.atgc-montpellier.fr .
16. "FastTree 2.1: Árboles de verosimilitud aproximada máxima para alineaciones grandes". www.microbesonline.org .

Otras fuentes

• Studier JA, Keppler KJ (1988). "Una nota sobre el algoritmo Neighbor-Joining de Saitou y Nei". Mol Biol Evol . 5 (6): 729–731. doi : 10.1093/oxfordjournals.molbev.a040527 . PMID  3221794.
• Martin Simonsen; Thomas Mailund; Christian NS Pedersen (2008). "Unión rápida de vecinos". Algoritmos en bioinformática . Apuntes de clase en informática. Vol. 5251. págs. 113–122. CiteSeerX  10.1.1.218.2078 . doi :10.1007/978-3-540-87361-7_10. ISBN . 978-3-540-87360-0.

Enlaces externos

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