Reorganización del árbol

Los 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 estén organizados naturalmente en un árbol, pero tienen la mayoría de sus aplicaciones en la filogenética computacional , especialmente en las búsquedas de máxima parsimonia y máxima verosimilitud de árboles filogenéticos , que buscan identificar uno entre muchos árboles posibles que mejor explique la historia evolutiva de un gen o especie en particular .

• 
  Intercambio del vecino más cercano (NNI)
• 
  Poda y reinjerto de subárboles (SPR)
• 
  Bisección y reconexión de árboles (TBR)

La reorganización de árboles más simple, conocida como intercambio de vecinos más cercanos , intercambia la conectividad de cuatro subárboles dentro del árbol principal. Dado que existen tres formas posibles de conectar cuatro subárboles, ^{[ 1 ]} y una de ellas 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 también la más 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 reinserta en otro lugar 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 las aristas de los dos árboles así creados. La creciente complejidad de la técnica de reorganización de árboles se correlaciona con el aumento del tiempo de cálculo requerido para la búsqueda, aunque no necesariamente con su rendimiento. ^{[ 2 ]}

SPR se puede subdividir en uSPR: SPR sin raíz, rSPR: SPR con raíz. uSPR se aplica a árboles sin raíz y funciona así: se rompe cualquier arista. Se une un extremo de la arista (seleccionado arbitrariamente) a cualquier otra arista del árbol. rSPR se aplica a árboles con raíz* y funciona así: se rompe cualquier arista excepto la que conduce al nodo raíz. Se une un extremo de la arista (específicamente: el extremo de la arista que está MÁS LEJOS de la raíz) y se adjunta a cualquier otra arista 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, consiste en considerar que el nodo raíz tiene grado 2 y aplicar una regla especial para rSPR.

El número de movimientos SPR ^{[ 4 ]} o TBR ^{[ 5 ]} necesarios para pasar de un árbol a otro se puede calcular generando un Bosque de Máximo Acuerdo compuesto por árboles enraizados o no enraizados, respectivamente. Este problema es NP-difícil, pero tratable con Parámetros Fijos.

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 al resolver adecuadamente las "hojas" individuales del árbol; por ejemplo, la separación ((A,B),(C,D)) en la punta de una rama frente a ((A,C),(B,D)) puede quedar sin resolver. ^{[ 1 ]} La fusión de árboles intercambia estas dos soluciones entre dos árboles que, de otro modo, 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 alta puntuación en árboles principales que, en general, tienen una alta puntuación. ^{[ 6 ]}

Una estrategia alternativa consiste en separar una parte del árbol (que puede seleccionarse al azar o mediante un enfoque más estratégico) y aplicar TBR/SPR/NNI a este subárbol. Este subárbol optimizado puede luego reemplazarse en el árbol principal, con la esperanza de mejorar la puntuación p. ^{[ 7 ]}

Para evitar quedar atrapado en óptimos locales, se puede utilizar un enfoque de "recocido simulado", mediante el cual se permite ocasionalmente que el algoritmo considere árboles candidatos subóptimos, con una probabilidad relacionada con qué tan lejos están del óptimo. ^{[ 7 ]}

Una vez que se ha reunido una serie de árboles igualmente óptimos, a menudo es posible encontrar un árbol mejor combinando las partes más valiosas de árboles individuales. Se pueden intercambiar subgrupos con una composición idéntica pero topología diferente y evaluar los árboles resultantes. ^{[ 7 ]}