A inferência filogenética busca reconstruir uma árvore que represente a história evolutiva de um conjunto de espécies ou grupos de espécies dados como entrada. O método de inferência filogenética mais utilizado atualmente é o da máxima verossimilhança, pois se baseia em todas as informações disponíveis nas sequências, possui um modelo estatístico bem fundamentado, e atinge um grau de precisão mais elevado que outros métodos conhecidos. O problema da inferência filogenética é do tipo NP-Completo, ou seja, é de ordem N!. Sendo assim, aplicar um método exaustivo de busca em árvores seria inviável, se levarmos em consideração o tempo de processamento que essa operação levaria, pois a quantidade de árvores testadas seria muito grande. Com base no método da máxima verossimilhança e no estudo de outros algoritmos que fazem essa mesma tarefa, foram desenvolvidos até o momento dois novos métodos heurísticos para busca de árvores e inferência filogenética. A implementação dessas duas heurísticas deu origem ao programa GrafuMV.

Para o desenvolvimento das heurísticas para reconstrução de árvores filogenéticas, fez-se necessário o estudo de outras ferramentas de domínio público de mesmo propósito, e assim foi feita a análise das heurísticas utilizadas por ferramentas bastante conhecidas, como o Phyml e o fastDNAml. Para implementação do GrafuMV, foi utilizado o ambiente de desenvolvimento integrado Kdevelop, disponível para o KDE, sistema de ambiente gráfico do Linux. A linguagem de programação utilizada foi a C++, por apresentar um excelente desempenho e possuir recursos avançados de orientação a objeto. Para a realização dos testes, foram utilizados conjuntos de dados, executados nos programas GrafuMV, Phyml e fastDNAml. Todos os programas foram configurados para rodar utilizando o modelo de Jukes-Cantor. O computador utilizado para os testes foi um Athlon XP 2400+, placa-mãe ASUS A7V600-X e 256 MB RAM. O ambiente utilizado foi o Fedora Core 4 e o compilador GCC 4.0.

A partir dos testes, notamos que o tempo de execução do GrafuMV esteve mais próximo ao tempo do fastDNAml do que do Phyml. Para a Heurística 1, o tempo do GrafuMV foi 26.3% mais eficiente que o tempo do fastDNAml para conjuntos com mais de 40 sequências e 44,34% para mais de 60 sequências. Para conjuntos com menos de 20 sequências, o fastDNAml apresentou desempenho 80,43% superior à Heurística 1 do GrafuMV. Comparado ao Phyml, os tempos do GrafuMV são muito maiores (85,5% para mais de 40 sequências e 71% para menos de 20 sequências) e este será o grande desafio para o desenvolvimento do mesmo, visto que o Phyml é um dos programas mais eficientes conhecidos. Quanto às árvores, há algumas diferenças nas geradas por todos os programas, mas pelo fato de reconstruírem árvores sem raiz, o Phyml e fastDNAml apresentaram resultados mais próximos entre si do que o GrafuMV. A pesquisa e o desenvolvimento do GrafuMV ainda se encontram em estágio inicial, mas os resultados já nos dão idéia de que este pode ser ainda bastante otimizado e, à medida que outros modelos evolucionários forem adicionados, a inferência pode ser melhorada substancialmente. Além disso, a necessidade de uso de um método de comparação de árvores é evidente e está em estudo. Comparando as Heurísticas 1 e 2, vimos que a Heurística 1 é indiscutivelmente mais rápida. Isso se deve ao fato de que são realizados cálculos extras em todas as iterações na fase de agrupamento na Heurística 2. Ainda não é possível medir o impacto real desses cálculos a mais na inferência e somente a continuação do trabalho poderá comprovar ou não sua importância.

Neste trabalho são apresentadas duas novas heurísticas para realizar a reconstrução de árvores filogenéticas baseadas no método da máxima verossimilhança. O GrafuMV, que compreende as duas heurísticas, foi implementado utilizando a linguagem C++ e foi validado utilizando dados de teste dos programas utilizados na comparação. O valor deste trabalho é, principalmente, a sua contribuição com duas novas heurísticas para resolver um problema que atualmente continua em aberto quando se utilizam conjuntos de dados com um número muito grande de sequências (várias centenas). Pretende-se continuar o desenvolvimento do programa para permitir a inclusão de mais modelos de substituição e também incluir no cálculo da máxima verossimilhança a mudança de taxas entre sítios. Outro trabalho que dará seguimento ao desenvolvimento da ferramenta é a proposta de uma solução paralela para melhorar a eficiência.

Instituição de fomento: FAPESB

Trabalho de Iniciação Científica