FenixEdu™

Dissertação

{en_GB=Large scale phylogenetic inference from noisy data based on minimum weight spanning arborescences} {} EVALUATED

Detalhes: {pt=A complexidade dos métodos actuais representa uma barreira para a reconstrução de relações filogenéticas e de padrões evolutivos de bactérias com alguns milhares de genomas. O cálculo de árvores de abrangência de custo mínimo a partir de sequências multilocus é uma forma rápida e eficiente de reconstruir essas relações. Nas sequências multilocus não é admitida a falta de informação. Recentemente, foi demonstrado que ao considerar grafos direccionados em vez de não direccionados e ao calcular arborescências de custo mínimo em vez de árvores este problema pode ser mitigado. Actualmente, esta abordagem depende de grafos fortemente ligados e a complexidade da implementação do algoritmo de Edmonds, que permite determinar arborescências de custo mínimo, é pelo menos quadrática. Nesta tese foram estudadas e avaliadas técnicas para acelerar o cálculo de arborescências de custo mínimo, resultando numa implementação do algoritmo de Edmonds com a complexidade temporal de O(|E| log |V|), onde E denota o conjunto de arestas e V representa o conjunto de vértices de um grafo direccionado G=(V,E). Também utilizámos técnicas a fim de manter arborescências de custo mínimo associadas a um grafo que sofre alterações repetidamente ao ter uma aresta removida ou adicionada. A nossa implementação da manutenção de arborescências de custo mínimo dinâmicas demonstrou ser em média duas vezes mais rápida ao realizar m operações consecutivas do que executar o algoritmo de Edmonds por m operações consecutivas., en=Current methods struggle to reconstruct phylogenetic relationships and evolution patterns of more than a few thousands of bacterial genomes. Calculating minimum spanning trees from legacy MLST is quick and efficient since legacy MLST is based on only seven loci and there is no missing data. Recently, it was shown that finding minimum spanning arborescences can help with this problem by considering directed graphs instead of undirected ones. The present approach depends on a fully connected graph. The running time complexity of algorithms for finding spanning arborescences of minimum weight such as Edmonds' algorithm, for example, is at least quadratic therefore the running time may still be problematic for analyzing large data sets. The aim of this thesis was to study and evaluate strategies to speed up the calculation of minimum spanning arborescences in phylogenetic context. Here we present an implementation of Edmonds' algorithm that runs in O(|E| log |V|) time, where V denotes the set of vertices and E denotes the set of edges of a directed graph G=(V,E). Furthermore, we applied techniques in order to maintain a minimum spanning arborescence for an underlying graph which is modified repeatedly by having an edge removed or added. Our implementation of the dynamic minimum spanning arborescence proved to be two times faster than calculating Edmonds' algorithm over a sequence of m operations.}
Keywords: {pt=Inferência Filogenética, Árvores de Abrangência de Custo Mínimo, Arborescências de Custo Mínimo, Arborescências de Custo Mínimo Dinâmicas, Falta de Informação, en=Phylogenetic Inference, Minimum Spanning Trees, Minimum Spanning Forests, Minimum Spanning Arborescences, Dynamic Minimum Spanning Arborescences, Missing Data}

Discussão: outubro 25, 2019, 11:0