Cálculo da distância de reversão e construção de árvores filogenéticas usando a ordem dos genes

Abstract

Calcular distancias evolutivas, como la distancia de inversión o la distancia de doble corte y unión, entre las órdenes del gen de dos organismos es un problema combinatorio complejo. Este escenario puede ser aún más complicado si queremos construir árboles filogenéticos, ya que la mayoría de los enfoques en la literatura primero resuelve el problema mediano para tres genomas, que se demostró que es NP-Hard para varios modelos evolutivos. En este trabajo, proponemos varios algoritmos evolutivos para el problema de ordenar permutaciones (sin signo) por inversiones, cuya salida es la distancia de inversión. Estos algoritmos se basan en un algoritmo genético simple, en el que se integraron diferentes heurísticas, como la búsqueda local, el aprendizaje basado en la oposición y la eliminación de puntos de interrupción. Los experimentos se realizaron utilizando diferentes tipos de datos (permutaciones) basados ​​en órdenes de genes que se generaron artificialmente (de forma aleatoria) y también a partir de datos biológicos. A partir de estos algoritmos, los que tienen los mejores resultados para casos prácticos, es decir, permutaciones de longitud de hasta 120, se denominan AMBO y AMBO-Hibrido. Estos resultados fueron validados aplicando las pruebas estadísticas de Friedman y Holm. Además, se implementó un software llamado HELPHY para construir árboles filogenéticos, que toma como datos de entrada basados ​​en el orden de los genes (permutaciones firmadas). Primero, se propuso un algoritmo ambicioso para el pequeño problema de filogenia, cuyo objetivo es calcular el costo (puntaje) de una estructura de árbol dada. Luego, se propuso un enfoque basado en la búsqueda de vecindad variable para el gran problema de filogenia, cuyo objetivo es explorar el espacio de búsqueda de las estructuras de los árboles. Los resultados de los experimentos mostraron que HELPHY mejoró el tiempo de ejecución para encontrar buenos puntajes (distancia de inversión) para el conjunto de datos Campanulaceae; además, se encontró una nueva estructura de árbol con el mejor puntaje (doble corte y distancia de unión) en la literatura para el conjunto de datos de Hemiascomycetes.