Hispanopedia Wiki
Articulo de referencia

Un vecino se une

En bioinformática , el método de unión de vecinos es un método de agrupamiento ascendente (aglomerativo) para la creación de árboles filogenéticos , creado por Naruya Saitou y M...

Hispanopedia WikiContenido en espanolLectura gratuita

En bioinformática , el método de unión de vecinos es un método de agrupamiento ascendente (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 conocer 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 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 mostrada con líneas continuas queda fija y no se modificará en los pasos de unión posteriores. Las distancias del nodo u a los nodos ae se calculan a partir de la ecuación ( 3 ). Este proceso se repite, utilizando una matriz que contiene únicamente 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 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 finaliza el algoritmo, ya que el árbol está completamente resuelto.

El algoritmo de 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 conozcan todas las longitudes de las ramas:

  1. Basándose en la matriz de distancias actual, calcule una matrizQ{\displaystyle Q}(definido a continuación).
  2. Encuentra el par de taxones distintos i y j (es decir, coni≠j{\displaystyle i\neq j}) para el cualQ(i,j){\displaystyle Q(i,j)}es el más pequeño. Crea un nuevo nodo que una los taxones i y j, y conecta 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.
  3. Calcula la distancia de cada uno de los taxones del par a este nuevo nodo.
  4. Calcula la distancia desde cada uno de los taxones que se encuentran fuera de este par hasta el nuevo nodo.
  5. Vuelva a iniciar el algoritmo, reemplazando el par de vecinos unidos con el nuevo nodo y utilizando las distancias calculadas en el paso anterior.

La matriz Q

Basado en una matriz de distancias que relaciona lanorte{\displaystyle n}taxones, calcular elnorte{\displaystyle n}incógnitanorte{\displaystyle n}matrizQ{\displaystyle Q}como sigue:

dónded(i,j){\displaystyle d(i,j)}es la distancia entre taxonesi{\displaystyle i}yj{\displaystyle j}.

Distancia de los miembros del par al nuevo nodo

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

y:

δ(gramo,tú)=d(F,gramo)−δ(F,tú){\displaystyle \delta (g,u)=d(f,g)-\delta (f,u)\quad }

TaxonesF{\displaystyle f}ygramo{\displaystyle g}son los taxones emparejados ytú{\displaystyle u}es el nodo recién creado. Las ramas que se unenF{\displaystyle f}ytú{\displaystyle u}ygramo{\displaystyle g}ytú{\displaystyle u}y sus longitudes,δ(F,tú){\displaystyle \delta (f,u)}yδ(gramo,tú){\displaystyle \delta (g,u)}forman parte del árbol que se va creando gradualmente; no afectan ni se ven afectadas por los pasos posteriores de unión de vecinos.

Distancia de los demás taxones al nuevo nodo

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

dóndetú{\displaystyle u}es el nuevo nodo,k{\displaystyle k}es el nodo al que queremos calcular la distancia yF{\displaystyle f}ygramo{\displaystyle g}son los miembros de la pareja que se acaban de unir.

Complejidad

Vecino se une a un conjunto de norte{\displaystyle n}Los taxones requierennorte−3{\displaystyle n-3}iteraciones. En cada paso hay que construir y buscar unQ{\displaystyle Q}matriz. Inicialmente elQ{\displaystyle Q}La matriz es de tamañonorte×norte{\displaystyle n\times n}, entonces el siguiente paso es(norte−1)×(norte−1){\displaystyle (n-1)\times (n-1)}, etc. Implementar esto de forma directa conduce a un algoritmo con una complejidad temporal deO(norte3){\displaystyle O(n^{3})}; [ 3 ] existen implementaciones que utilizan heurísticas para obtener resultados mucho mejores que este en promedio. [ 4 ]

Ejemplo

Unión de vecinos con 5 taxones. En este caso, dos 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(a,b,do,d,mi){\displaystyle (a,b,c,d,e)}y la siguiente matriz de distanciasD{\displaystyle D}:

Primer paso

Primero unirse

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

Q1(a,b)=(norte−2)d(a,b)−∑k=15d(a,k)−∑k=15d(b,k){\displaystyle Q_{1}(a,b)=(n-2)d(a,b)-\sum _{k=1}^{5}d(a,k)-\sum _{k=1}^{5}d(b,k)}
=(5−2)×5−(5+9+9+8)−(5+10+10+9)=15−31−34=−50{\displaystyle =(5-2)\times 5-(5+9+9+8)-(5+10+10+9)=15-31-34=-50}

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

En el ejemplo anterior,Q1(a,b)=−50{\displaystyle Q_{1}(a,b)=-50}Este es el valor más pequeño deQ1{\displaystyle Q_{1}}, por lo que unimos elementosa{\displaystyle a}yb{\displaystyle b}.

Estimación de la longitud de la primera rama

Dejartú{\displaystyle u}denotamos el nuevo nodo. Por la ecuación ( 2 ), arriba, las ramas que se unen a{\displaystyle a}yb{\displaystyle b}atú{\displaystyle u}entonces tienen longitudes:

δ(a,tú)=12d(a,b)+12(5−2)[∑k=15d(a,k)−∑k=15d(b,k)]=52+31−346=2{\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}
δ(b,tú)=d(a,b)−δ(a,tú)=5−2=3{\displaystyle \delta (b,u)=d(a,b)-\delta (a,u)\quad =5-2=3}

Primera actualización de la matriz de distancias

A continuación, procedemos a actualizar la matriz de distancias inicial.D{\displaystyle D}en una nueva matriz de distanciasD1{\displaystyle D_{1}}(ver abajo), reducido en tamaño por una fila y una columna debido a la unión dea{\displaystyle a}conb{\displaystyle b}en su vecinotú{\displaystyle u}. Usando la ecuación ( 3 ) anterior, calculamos la distancia desdetú{\displaystyle u}a cada uno de los demás nodos, además dea{\displaystyle a}yb{\displaystyle b}En este caso, obtenemos:

d(tú,do)=12[d(a,do)+d(b,do)−d(a,b)]=9+10−52=7{\displaystyle d(u,c)={\frac {1}{2}}[d(a,c)+d(b,c)-d(a,b)]={\frac {9+10-5}{2}}=7}
d(tú,d)=12[d(a,d)+d(b,d)−d(a,b)]=9+10−52=7{\displaystyle d(u,d)={\frac {1}{2}}[d(a,d)+d(b,d)-d(a,b)]={\frac {9+10-5}{2}}=7}
d(tú,mi)=12[d(a,mi)+d(b,mi)−d(a,b)]=8+9−52=6{\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 distancias resultanteD1{\displaystyle D_{1}}es:

Valores audaces enD1{\displaystyle D_{1}}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 que no participan en la primera unión de taxones.

Segundo paso

Segunda unión

El correspondienteQ2{\displaystyle Q_{2}}La matriz es:

Podemos optar por unirnostú{\displaystyle u}ydo{\displaystyle c}o unirsed{\displaystyle d}ymi{\displaystyle e}; ambos pares tienen el mínimoQ2{\displaystyle Q_{2}}valor de−28{\displaystyle -28}y cualquiera de las dos opciones conduce al mismo resultado. Para mayor concreción, unamostú{\displaystyle u}ydo{\displaystyle c}y llamar al nuevo nodov{\displaystyle v}.

Estimación de la longitud de la segunda rama

Las longitudes de las ramas que se unen tú{\displaystyle u}ydo{\displaystyle c}av{\displaystyle v}se puede calcular:

δ(tú,v)=12d(tú,do)+12(4−2)[∑k=14d(tú,k)−∑k=14d(do,k)]=72+20−224=3{\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}
δ(do,v)=d(tú,do)−δ(tú,v)=7−3=4{\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 las ramas ayudan a dibujar el árbol de unión de vecinos como se muestra en la figura .

Actualización de la segunda matriz de distancias

La matriz de distancias actualizadaD2{\displaystyle D_{2}}para los 3 nodos restantes,v{\displaystyle v},d{\displaystyle d}, ymi{\displaystyle e}, ahora se calcula:

d(v,d)=12[d(tú,d)+d(do,d)−d(tú,do)]=7+8−72=4{\displaystyle d(v,d)={\frac {1}{2}}[d(u,d)+d(c,d)-d(u,c)]={\frac {7+8-7}{2}}=4}
d(v,mi)=12[d(tú,mi)+d(do,mi)−d(tú,do)]=6+7−72=3{\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 laQ3{\displaystyle Q_{3}}matriz. Por ejemplo:

Q3(v,mi)=(3−2)d(v,mi)−∑k=13d(v,k)−∑k=13d(mi,k)=3−7−6=−10{\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, unámonos.v{\displaystyle v}yd{\displaystyle d}y llamar al último nodow{\displaystyle w}. Se pueden calcular las longitudes de las tres ramas restantes:

δ(v,w)=12d(v,d)+12(3−2)[∑k=13d(v,k)−∑k=13d(d,k)]=42+7−72=2{\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}
δ(w,d)=d(v,d)−δ(v,w)=4−2=2{\displaystyle \delta (w,d)=d(v,d)-\delta (v,w)=4-2=2}
δ(w,mi)=d(v,mi)−δ(v,w)=3−2=1{\displaystyle \delta (w,e)=d(v,e)-\delta (v,w)=3-2=1}

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

Conclusión: distancias aditivas

Este ejemplo representa un caso idealizado: observe que si nos movemos de cualquier taxón a cualquier 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 ded{\displaystyle d}ab{\displaystyle b}tenemos2+2+3+3=10{\displaystyle 2+2+3+3=10}Una matriz de distancias cuyas distancias coinciden de esta manera con algún árbol se denomina «aditiva», una propiedad poco común en la práctica. Dada una matriz de distancias aditiva como entrada, el algoritmo de unión de vecinos garantiza encontrar el árbol cuyas distancias entre taxones coinciden con ella.

Unicidad

La matriz Q utilizada en Neighbor-joining es única: cualquier criterio de selección que sea

  • una función lineal de las distancias de entrada
  • siempre selecciona un par adyacente cuando se aplica a distancias aditivas, y
  • es invariable al reetiquetado

siempre elegirá el mismo par que al elegir el valor más pequeño en la matriz Q. [ 5 ]

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

El método de unión de vecinos (NJ) puede considerarse una heurística voraz para el criterio de evolución mínima equilibrada [ 6 ] (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 ponderaciones que dependen de la topología. La topología óptima de BME es la que minimiza esta longitud del árbol. En cada paso, NJ une de forma voraz el par de taxones que producirá la mayor disminución en la longitud estimada del árbol. Este procedimiento no garantiza encontrar el óptimo para el criterio BME, aunque a menudo lo hace y suele estar bastante cerca. [ 6 ]

Ventajas y desventajas

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

El método de unión de vecinos tiene la propiedad de que si la matriz de distancias de entrada es correcta, entonces el árbol de salida también lo será. Además, la corrección de la topología del árbol de salida está garantizada siempre que la matriz de distancias sea "casi aditiva", específicamente si cada entrada en la matriz de distancias difiere de la distancia verdadera en menos de la mitad de la longitud de la rama más corta en el árbol. [ 8 ] 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 correcta del árbol de todos modos. [ 9 ] La corrección de la unión de vecinos para matrices de distancias 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, el método de unión de vecinos ha sido ampliamente reemplazado por métodos filogenéticos que no dependen de medidas de distancia y ofrecen mayor precisión en la mayoría de las condiciones. El método de unión de vecinos tiene la desventaja de que a menudo asigna longitudes negativas a algunas ramas.

Implementaciones y variantes

Existen numerosos programas que implementan el método de unión de vecinos (NJ). Entre las implementaciones del método NJ canónico (que utiliza los criterios de optimización clásicos de NJ, lo que da los mismos resultados), RapidNJ (iniciado en 2003, con una actualización importante en 2011 y que aún se actualiza en 2023) [ 10 ] y NINJA (iniciado en 2009, con la última actualización en 2013) [ 11 ] se consideran de última generación. Sus tiempos de ejecución suelen ser aproximadamente proporcionales al cuadrado del número de taxones.

Las variantes que se desvían de la versión canónica incluyen:

  • BIONJ (1997) [ 12 ] y Weighbor (2000), [ 13 ] 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. Ambos métodos se han extendido para funcionar con matrices de distancias incompletas. [ 14 ]
  • El algoritmo "Fast NJ" recuerda el mejor nodo y siempre tiene una complejidad de O(n^2); el algoritmo "relax NJ" realiza una búsqueda de ascenso de colina y mantiene una complejidad en el peor de los casos de O(n^3). Rapid NJ es más rápido que el algoritmo "relax NJ" simple. [ 15 ]
  • 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 y más preciso que NJ. Comienza con un árbol aproximado y luego lo mejora utilizando un conjunto de movimientos topológicos como Intercambios de Vecinos Más Cercanos (NNI). [ 16 ] FastTree es un método relacionado. Trabaja con "perfiles" de secuencia en lugar de una matriz. Comienza con un árbol NJ aproximado, lo reorganiza en BME y luego lo reorganiza en máxima verosimilitud aproximada. [ 17 ]
  • NeighborNet [ 18 ] utiliza la matriz Q y una variante del paso de reducción para crear redes filogenéticas, en lugar de árboles filogenéticos.

Véase también

Referencias

  1. ↑ Saitou, N.; Nei, M. (1 de julio de 1987). "El método de unión de vecinos: 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 de vecinos 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, Christian NS; Phillips, Derek (2006). " Remodelando el método de unión de vecinos" . BMC Bioinformatics . 7 (1): 29. doi : 10.1186/1471-2105-7-29 . PMC 3271233. PMID 16423304 .  
  5. ↑ Bryant, David (junio de 2005). "Sobre la unicidad del criterio de selección en Neighbor-Joining" . Journal of Classification . 22 (1): 3– 15. doi : 10.1007/s00357-005-0003-x . ISSN 0176-4268 . 
  6. 1 2 Gascuel O, Steel M (2006). "Neighbor-joining revealed" . Mol Biol Evol . 23 (11): 1997– 2000. doi : 10.1093/molbev/msl072 . PMID 16877499 . 
  7. 1 2 Kuhner, MK; Felsenstein, J. (1994-05-01). "Una comparación de simulación de algoritmos filogenéticos 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 .  
  8. ↑ Atteson K (1997). "El rendimiento de losalgoritmos de unión de vecinos para la reconstrucción filogenética", págs. 101-110 . En Jiang, T., y Lee, D., eds., Lecture Notes in Computer Science, 1276 , Springer-Verlag, Berlín. COCOON '97.
  9. ↑ Mihaescu R, Levy D, Pachter L (2009). "Por qué funciona el método neighbor-joining". Algorithmica . 54 (1): 1– 24. arXiv : cs/0602041 . doi : 10.1007/s00453-007-9116-4 . S2CID 2462145 . {{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )
  10. ↑ "RapidNJ" . birc.au.dk .
  11. ↑ "NINJA: una herramienta para la inferencia filogenética de unión de vecinos a gran escala - Inicio" . wheelerlab.org .
  12. ↑ «ATGC: BioNJ» . www.atgc-montpellier.fr .
  13. ↑ "Página principal de WEIGHBOR" . 5 de marzo de 2015. Archivado del original el 5 de marzo de 2015.
  14. ↑ 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 .  
  15. ↑ Simonsen, Martin; Mailund, Thomas; Pedersen, Christian NS (2008). "Rapid Neighbour-Joining" (PDF) . Algorithms in Bioinformatics . Lecture Notes in Computer Science. Vol. 5251. pp. 113–122 . doi : 10.1007/978-3-540-87361-7_10 . ISBN   978-3-540-87360-0.
  16. ↑ «ATGC: FastME» . www.atgc-montpellier.fr .
  17. ↑ "FastTree 2.1: Árboles de máxima verosimilitud aproximada para alineamientos grandes" . www.microbesonline.org .
  18. ↑ Bryant, D. (2003-08-29). "Neighbor-Net: Un método aglomerativo para la construcción de redes filogenéticas" . Biología molecular y evolución . 21 (2): 255– 265. doi : 10.1093/molbev/msh018 . ISSN 0737-4038 . 

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). "Rapid Neighbour-Joining". Algorithms in Bioinformatics . Lecture Notes in Computer Science. Vol.  5251. pp. 113–122 . CiteSeerX 10.1.1.218.2078 . doi : 10.1007/978-3-540-87361-7_10 . ISBN   978-3-540-87360-0.
  • El método Neighbor-Joining se archivó el 9 de julio de 2021 en Wayback Machine : un tutorial.
Lecturas relacionadas
6 articulos
iconoBioinformáticaBioinformática temprana: alineamiento computacional de secuencias determinadas experimentalmente de una clase de proteínas relacionadas; consulte §...Análisis de conglomeradosAnálisis de conglomeradosEl análisis de conglomerados o clustering es la tarea de agrupar un conjunto de objetos de tal manera que los objetos del mismo grupo (llamado clus...Árbol filogenéticoÁrbol filogenéticoUn árbol filogenético , filogenia o árbol evolutivo es una representación gráfica que muestra la historia evolutiva entre un conjunto de especies o...Masatoshi NaiMasatoshi Nei ( 根井正利 , Nei Masatoshi , 2 de enero de 1931 - 18 de mayo de 2023) fue un biólogo evolutivo estadounidense nacido en Japón . Vida prof...Estructura primaria de la proteínaEstructura primaria de la proteínaLa estructura primaria de una proteína es la secuencia lineal de aminoácidos en un péptido o proteína . [1] Por convención, la estructura primaria ...ADNADNEstructura de la doble hélice del ADN (ADN tipo B ). Los átomos de la estructura están codificados por colores según el elemento y las estructuras ...