There are many different methods for constructing phylogenetic trees from biological data. To either compare one such algorithm with another, or to find the likelihood of a certain tree generated from the data, researchers often compute a distance between trees. In this talk, we present a practical algorithm for computing the geodesic distance, as well as the geodesic path, between two phylogenetic trees in the tree space introduced by Billera, Holmes, and Vogtmann(2001). In doing so, we show that the possible shortest paths between two trees can be represented as chains in a partially ordered set, whose elements are the sets formed by a closure relation on the incompatible edges between the trees. Furthermore, we give a linear time algorithm for computing the geodesic candidate corresponding to each maximal chain in this partially ordered set. Dynamic programming techniques can be used to further prune the search of the partially ordered set for the shortest path
view more