skip to content

Practical distance computation in the space of phylogenetic trees

Tuesday 18th December 2007 - 10:20 to 10:40
INI Seminar Room 1
Session Chair: 
Stephen Willson

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.

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons