Computing Geodesic Tree Distances with the GTP Algorithm

by Miguel António Gomes Caires

MSc thesis presentation and discussion.

Date: 2021-Dec-21   Time: 14:00
Room: Zoom

Abstract: The geometry of tree space $\mathcal{T}_n$ introduced by Billera,
Holmes, and Vogtmann provides an effective way of comparing phylogenetic trees
in the form of the geodesic distance, i.e. the length of the shortest path
from one tree to another. We study and implement the first polynomial-time
algorithm for finding geodesic paths in tree space $\mathcal{T}_n$, proposed
by Owen and Provan. We focus on other graph problems and algorithms related to
the Geodesic Treepath Problem, namely the maximum flow problem. Our results
show that the geodesic distance can be efficiently computed in practice with
the correct choice of algorithms and data structures, confirming the
theoretical results we derived.