FenixEdu™

Dissertação

Library of efficient algorithms for phylogenic analysis EVALUATED

Detalhes: As relações evolucionárias entre diferentes espécies são geralmente inferidas através de análise filogenética, que fornece árvores filogenéticas, que podem ser computadas através de perfis alélicos construídos sequenciando regiões específicas das sequências e abstraíndo-as em índices categóricos. Com o aumento de trocas de pessoas e mercadorias, as epidemias têm-se tornado muito importantes, e combinar informações de datasets específicos por país pode agora revelar padrões de propagação desconhecidos. O fluxo de análise filogenética é composto principalmente por quatro passos consecutivos, o cálculo de distâncias, a correção de distâncias, o algoritmo de inferência, e a otimização local. Existem muitas ferramentas de filogenia, porém muitas implementam apenas alguns destes passos e servem apenas um propósito, por exemplo um tipo de algoritmos. Outro problema é serem muitas vezes difíceis de usar e integrar, porque cada uma tem a sua API. Este projeto resultou numa biblioteca que implementa os quatro passos do fluxo, é eficiente, extensível, reutilizável, e portável, e fornece APIs comuns e documentação. Esta difere das outras no sentido em que, é capaz de parar e resumir o fluxo em qualquer passo, e foi construída para ser continuamente estendida e não servir apenas um propósito. Os benchmarks de tempo conduzidos sobre esta biblioteca mostram que as suas implementações dos algoritmos estão conforme as suas complexidades de tempo teóricas. Os benchmarks de memória demonstram que as implementações dos algoritmos de NJ seguem uma complexidade de memória linear, enquanto que as implementações dos algoritmos de MST e GCP seguem uma complexidade de memória quadrática.
Keywords: filogenia, inferência, algoritmos, árvores

Discussão: janeiro 13, 2021, 16:30