An algorithmic approach to the comparison of phylogenetic trees

11/21/2023

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.

Authors in the community:

• 

  A

  António Pedro Paredes Silva Branco

  ist192426

Supervisors of this institution:

• 

  A

  A P Francisco

  ist14152

electrical-engineering-electronic-engineering-information-engineering - Electrical engineering, electronic engineering, information engineering

eng - English

Instituto Superior Técnico