====== Megan Owen (Cornell) ======

====== Practical Distance Computation in the Space of Phylogenetic Trees ======

===== Abstract for the Combinatorics Seminar 2008 March 11 =====

What is the distance between two phylogenetic (evolutionary) trees and how can we efficiently compute it? In a 2001 paper, Billera, Holmes and Vogtmann constructed a space containing all phylogenetic trees, and showed the distance between the points corresponding to trees in this space is a reasonable inter-tree distance measure. I present a practical algorithm to compute this distance, showing that the possible shortest paths between two trees can be represented as a partially ordered set, and giving a linear time algorithm for computing the shortest path through a certain Euclidean subspace. Dynamic programming techniques can be used to further prune the search of the partially ordered set for the shortest path.


----