Orientabilidad de redes filogenéticas no dirigidas a una clase deseada: algoritmos prácticos y aplicación a la...

Área de la Ciencia:

• Biología computacional
• Teoría de grafos
• Filogenética

Sus antecedentes:

• El problema C-ORIENTATION es vital para convertir grafos no dirigidos de métodos basados en distancias (por ejemplo, Neighbor-Net) en redes filogenéticas dirigidas.
• Su complejidad es desconocida para muchas clases de redes, incluidas las redes binarias hijo-árbol, y las soluciones prácticas son limitadas.

Objetivo del estudio:

• Abordar el problema C-ORIENTATION proponiendo un algoritmo exacto de Tratabilidad Fija de Parámetros (FPT) y un heurístico rápido.
• Mejorar los algoritmos existentes de tiempo exponencial reduciendo el espacio de búsqueda para la colocación de vértices de reticulación.

Principales métodos:

• Desarrollamos un algoritmo FPT exacto para C-ORIENTATION, parametrizado por el número de reticulación y el tamaño mínimo del ciclo básico.
• Creamos un algoritmo heurístico rápido específicamente para la ORIENTACIÓN HIJO-ARBOL.

Principales resultados:

• El algoritmo FPT supera significativamente el estado actual del arte, a pesar de seguir siendo exponencial.
• El algoritmo heurístico es considerablemente más rápido, pero puede generar más falsos negativos a medida que aumentan los números de reticulación.

Conclusiones:

• El algoritmo FPT propuesto ofrece una mejora sustancial para C-ORIENTATION.
• El heurístico proporciona una alternativa rápida para la ORIENTACIÓN HIJO-ARBOL, con una compensación entre velocidad y precisión que justifica una mayor investigación para aplicaciones biológicas.