An algorithmic approach to the comparison of phylogenetic trees

by António Pedro Branco

MSc thesis presentation and discussion.

Date: 2023-Nov-21   Time: 09:00
Room: 0.19

Abstract: 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 it is proposed an efficient implementation
of the Robinson Foulds and Triplet comparison metrics over trees succinct
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.