FenixEdu™

Dissertação

{en_GB=Large scale and dynamic phylogenetic inference from epidemic data} {} EVALUATED

Detalhes: {pt=Os métodos de tipagem são vastamente utilizados uma vez que fornecem conhecimento importante na vigilância de doenças infecciosas, investigação de surtos e na história natural de uma infecção. O seu uso está-se a tornar bastante comum, em particular com a introdução de High Throughput Sequencing (HTS). Por outro lado, a quantidade de dados que é gerada é enorme e muitos algoritmos têm sido propostos para realizarem a análise filogenética desses dados, abordando problemas de correção e escalabilidade, como é o caso do algoritmo goeBURST. Grande parte dos algoritmos baseados em distâncias que inferem árvores filogenéticas seguem um esquema de junção do par mais próximo. Esta é uma das abordagens utilizadas em clustering hierárquico. Apesar dos algoritmos de inferência filogenética parecerem bastante diferentes, a principal diferença reside no facto de como cada um define a proximidade a um cluster e que critério é que usam. O objetivo principal desta tese é o estudo dos métodos mais utilizados que permitem realizar inferência filogenética, focando no algoritmo goeBURST e os problemas computacionais que advém da sua utilização a grande escala. Além disso, este deve ser executado sempre que novos dados fiquem disponíveis e a partir do zero. Este problema é abordado através da proposta de dois algoritmos dinâmicos que permitem que os dados sejam continuamente integrados e atualizados. Os resultados experimentais mostram que esses algoritmos são eficientes na integração de novos dados e na atualização dos padrões evolutivos inferidos, melhorando o tempo de execução das atualizações em pelo menos uma ordem de grandeza., en=Typing methods are widely used in the surveillance of infectious diseases, outbreak investigation and studies of the natural history of an infection. Their use is becoming standard, in particular with the introduction of High Throughput Sequencing (HTS). On the other hand, the data being generated is massive and many algorithms have been proposed for phylogenetic analysis of typing data, addressing both correctness and scalability issues, such as the goeBURST algorithm. Most of the distance based algorithms for inferring phylogenetic trees follow the closest-pair joining scheme. This is one of the approaches used in hierarchical clustering. Although phylogenetic inference algorithms may seem rather different, the main difference among them resides on how one defines cluster proximity and on which optimization criterion is used. The main goal of this thesis is the study of the most well known phylogenetic inference methods suitable for processing typing data, focusing mostly on the goeBURST algorithm and its computational problems that appear when dealing with large datasets. Moreover, this algorithm must however be run whenever new data becomes available starting from scratch. We address this issue by proposing two dynamic algorithms allowing data to be continuously integrated and updated. Experimental results show that these algorithms are efficient on integrating new data and updating inferred evolutionary patterns, improving the update running time by at least one order of magnitude.}
Keywords: {pt=Inferência filogenética, Árvores filogenéticas, Algoritmos dinâmicos, Dados de tipagem baseados em sequências., en=Phylogenetic inference, Phylogenetic trees, Dynamic algorithms, Sequence-based typing data.}

Discussão: novembro 9, 2017, 13:0