Hispanopedia WikiLos reordenamientos de árboles son algoritmos deterministas dedicados a la búsqueda de la estructura óptima de un árbol filogenético . Se pueden aplicar a cualquier conjunto de datos que se ordenan de forma natural en un árbol, pero tienen más aplicaciones en la filogenética computacional , especialmente en búsquedas de máxima parsimonia y máxima verosimilitud de árboles filogenéticos , que buscan identificar uno entre muchos árboles posibles que explique mejor la historia evolutiva de un gen o especie en particular .
Reordenamientos básicos de árboles
-
Intercambio de vecinos más cercanos (NNI) -
Poda y re-injerto de subárboles (SPR) -
Bisección y reconexión de árboles (TBR)
El reordenamiento de árboles más simple, conocido como intercambio de vecinos más cercanos , intercambia la conectividad de cuatro subárboles dentro del árbol principal. Debido a que hay tres formas posibles de conectar cuatro subárboles, [1] y una es la conectividad original, cada intercambio crea dos árboles nuevos. La búsqueda exhaustiva de los posibles vecinos más cercanos para cada conjunto posible de subárboles es la forma más lenta pero optimizadora de realizar esta búsqueda. Una búsqueda alternativa, de mayor alcance, la poda y reinjerto de subárboles (SPR), selecciona y elimina un subárbol del árbol principal y lo vuelve a insertar en otra parte del árbol principal para crear un nuevo nodo. Finalmente, la bisección y reconexión de árboles (TBR) separa un subárbol del árbol principal en un nodo interior y luego intenta todas las conexiones posibles entre los bordes de los dos árboles así creados. La creciente complejidad de la técnica de reordenamiento de árboles se correlaciona con el aumento del tiempo computacional requerido para la búsqueda, aunque no necesariamente con su rendimiento. [2]
El SPR se puede dividir en uSPR: SPR sin raíz, rSPR: SPR con raíz. uSPR se aplica a árboles sin raíz y funciona de la siguiente manera: rompe cualquier borde. Une un extremo del borde (seleccionado arbitrariamente) a cualquier otro borde del árbol. rSPR se aplica a árboles con raíz* y funciona de la siguiente manera: rompe cualquier borde excepto el borde que conduce al nodo raíz. Une un extremo del borde (específicamente: el extremo del borde que está MÁS ALEJADO de la raíz) y únelo a cualquier otro borde del árbol. [3]
* En este ejemplo, la raíz del árbol está marcada por un nodo de grado uno, lo que significa que todos los nodos del árbol tienen grado 1 o grado 3. Un enfoque alternativo, utilizado en Bordewich y Semple, es considerar que el nodo raíz tiene grado 2 y tener una regla especial para rSPR.
La cantidad de movimientos SPR [4] o TBR [5] necesarios para pasar de un árbol a otro se puede calcular generando un bosque de máxima concordancia que comprenda (respectivamente) árboles con raíces o sin raíces. Este problema es complejo en términos de NP pero manejable con parámetros fijos.
Fusión de árboles
El tipo más simple de fusión de árboles comienza con dos árboles ya identificados como casi óptimos; por lo tanto, es muy probable que tengan la mayoría de sus nodos correctos, pero pueden fallar en la resolución de las "hojas" individuales del árbol de manera adecuada; por ejemplo, la separación ((A,B),(C,D)) en la punta de una rama versus ((A,C),(B,D)) puede no estar resuelta. [1] La fusión de árboles intercambia estas dos soluciones entre dos árboles que de otra manera serían casi óptimos. Las variantes del método utilizan algoritmos genéticos estándar con una función objetivo definida para intercambiar subárboles de alto puntaje en árboles principales que tienen un puntaje alto en general. [6]
Búsqueda sectorial
Una estrategia alternativa es separar una parte del árbol (que puede seleccionarse al azar o utilizando un enfoque más estratégico) y realizar TBR/SPR/NNI en este subárbol. Este subárbol optimizado puede luego reemplazarse en el árbol principal, con lo que se espera mejorar el puntaje p. [7]
Árbol a la deriva
Para evitar quedar atrapado en óptimos locales, se puede utilizar un enfoque de "recocido simulado", mediante el cual ocasionalmente se permite que el algoritmo considere árboles candidatos subóptimos, con una probabilidad relacionada con qué tan lejos están del óptimo. [7]
Fusión de árboles
Una vez que se ha reunido una serie de árboles igualmente óptimos, a menudo es posible encontrar un árbol mejor combinando las "partes buenas" de árboles separados. Se pueden intercambiar los subgrupos con una composición idéntica pero con una topología diferente y evaluar los árboles resultantes. [7]
Referencias
- ^ ab Felsenstein, José (2004). Inferir filogenias . Asociados de Sinauer: Sunderland, MA. ISBN 9780878931774.
- ^ Takahashi, Kei; Nei, Masatoshi (agosto de 2000). "Eficiencias de algoritmos rápidos de inferencia filogenética bajo los criterios de máxima parsimonia, mínima evolución y máxima verosimilitud cuando se utiliza un gran número de secuencias". Biología molecular y evolución . 17 (8): 1251–1258. doi : 10.1093/oxfordjournals.molbev.a026408 . PMID 10908645.
- ^ Bordewich, Magnus; Semple, Charles (2005). "Sobre la complejidad computacional de la distancia de poda y reinjerto de subárboles enraizados". Anales de Combinatoria . 8 (4): 409–423. doi :10.1007/s00026-004-0229-z. S2CID 13002129.
- ^ Whidden, Chris; Beiko, Robert G.; Zeh, Norbert (2016). "Algoritmos de parámetros fijos y de aproximación para bosques de acuerdo máximo de árboles multifurcantes". Algorithmica . 74 (3): 1019–1054. arXiv : 1305.0512 . doi :10.1007/s00453-015-9983-z. S2CID 14297537.
- ^ Chen, Jianer; Fan, Jia-Hao; Sze, Sing-Hoi (2015). "Algoritmos parametrizados y de aproximación para bosques de máxima concordancia en árboles multifurcantes". Ciencias Informáticas Teóricas . 562 : 496–512. doi : 10.1016/j.tcs.2014.10.031 .
- ^ Matsuda, H. (1996). "Inferencia filogenética de proteínas utilizando máxima verosimilitud con un algoritmo genético" (PDF) . Simposio del Pacífico sobre Bioinformática 1996. págs. 512–523.
- ^ abc Goloboff, Pablo A. (1999). "Análisis de grandes conjuntos de datos en tiempos razonables: soluciones para óptimos compuestos". Cladistics . 15 (4): 415–428. doi : 10.1006/clad.1999.0122 . PMID 34902941.