An algorithmic approach to the comparison of phylogenetic trees

António Pedro Paredes Silva Branco

Key information

Authors:

António Pedro Paredes Silva Branco (António Pedro Paredes Silva Branco)

Supervisors:

Catia Raquel Jesus Vaz (Cátia Raquel Jesus Vaz); Alexandre Paulo Lourenço Francisco (A P Francisco)

Published in

11/21/2023

Abstract

Existem várias ferramentas disponíveis para inferir árvores filogenéticas, que descrevem as relações evolutivas entre entidades biológicas, como estirpes virais e bacterianas em surtos infecciosos, ou células cancerosas em árvores de progressão tumoral. Estas ferramentas baseiam-se em vários métodos de inferência disponíveis para produzir árvores filogenéticas, sendo que as árvores resultantes não são únicas. Assim, são necessários métodos de comparação de filogenias que sejam capazes de revelar onde duas árvores filogenéticas concordam ou diferem. Existem várias abordagens para calcular uma medida de similaridade ou dissimilaridade entre árvores. No entanto, dado o grande e crescente volume de dados filogenéticos, as árvores filogenéticas estão a tornar-se muito grandes, com centenas de milhares de folhas. Neste contexto, os requisitos de espaço tornam-se um problema, tanto no cálculo das distâncias entre árvores como no seu armazenamento. Nesta tese é proposta uma implementação eficiente das métricas de comparação Robinson Foulds e Triplet sobre representações sucintas de árvores. Também é demonstrado como estas implementações estendem as métricas para comparar árvores com informação em todos os nós. A implementação de Robinson Foulds também estende a métrica para calcular a métrica de Robinson Foulds para árvores com pesos e obter informações adicionais que podem ajudar a avaliar as dissimilaridades entre árvores. Os resultados experimentais mostram que as implementações atingem um ótimo desempenho com uma utilização de memória muito inferior. Estas implementações estão disponíveis como uma ferramenta de código aberto para análise filogenética no repositório git em https://github.com/pedroparedesbranco/TreeDiff. There are several tools available to infer phylogenetic trees, which depict the evolutionary relationships among biological entities such as viral and bacterial strains in infectious outbreaks, or cancerous cells in tumor progression trees. These tools rely on several inference methods available to produce phylogenetic trees, with resulting trees not being unique. Thus, methods for comparing phylogenies that are capable of revealing where two phylogenetic trees agree or differ are required. There are several approaches to compute a similarity or dissimilarity measure between trees. Nevertheless, given the large and increasing volume of phylogenetic data, phylogenetic trees are becoming very large with hundreds of thousands of leafs. In this context, space requirements become an issue both while computing tree distances and while storing trees. In this thesis we propose an efficient implementation of the Robinson Foulds and Triplet comparison metrics over trees with succint representations. It is also demonstrated how these implementations extend the metrics to compare fully labeled trees. The Robinson Foulds implementation also extends the metric to compute the Weighted Robinson Foulds metric and to obtain additional information that can help evaluate the dissimilarities between trees. Experimental results show that the implementations achieves great performance with much lower memory usage. These implementations are available as an open-source tool for phylogenetic analysis in the git repository at https://github.com/pedroparedesbranco/TreeDiff.