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

Abstract

O cálculo de distâncias evolutivas, como as distâncias de reversão e double cut and join, entre a ordem dos genes de dois organismos e um problema combinatório complexo. Este cenário pode ficar ainda mais complicado se quisermos construir árvores filogenéticas, visto que a maioria das abordagens da literatura primeiro solucionam o problema da mediana de três genomas, o qual foi demonstrado ser NP-Difícil para vários modelos evolutivos. Neste trabalho propomos vários algoritmos evolutivos para o problema de ordenação de permutações (sem sinal) por reversões, cuja saída e a distancia de reversão. Estes algoritmos são baseados em um algoritmo genético simples, sobre o qual foram incorporados varias heurísticas como busca local, busca por oposição, e eliminação de pontos de quebra. Experimentos foram realizados usando diferentes dados (permutações) baseados na ordem dos genes, os quais foram gerados artificialmente (de forma aleatória) e também a partir de dados biológicos. Dentre estes algoritmos os que melhores resultados tem para casos práticos, ou seja, permutações de comprimento ate 120, são os chamados AMBO e AMBO-Híbrido. Estes resultados foram validados usando testes estatísticos como Friedman e Holm. Adicionalmente, foi implementado um software para construir arvores filogenéticas chamado de HELPHY, que toma como entrada dados baseados na ordem dos genes (permutações com sinal). Primeiro foi proposto um algoritmo guloso para o problema da pequena filogenia, cujo objetivo e calcular o custo de uma determinada árvore. Logo, para o problema da grande filogenia foi proposta uma abordagem baseada em busca em vizinhança variável, cujo objetivo e explorar o espaço de soluções de estruturas de árvores. Experimentos mostraram que HELPHY conseguiu melhorar o tempo de execução para encontrar árvores com bons escores (distância de reversão) para o dataset Campanulaceae; além disso, uma nova árvore tendo o melhor escore (distância double cut and join) na literatura foi encontrado para o dataset Hemiascomycetes.