Speaker:  Megan Owen
Title:   Practical Distance Computation in the Space of Phylogenetic Trees
Time: 4:30 PM, Monday, February 18, 2008
Place:  Malott 205

Abstract:  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 metric space containing all phylogenetic trees, and showed that the geodesic distance between the points corresponding to trees in this space is a reasonable inter-tree distance measure.  Furthermore, the metric on this tree space has nonpositive curvature, giving several biologically and statistically interesting implications. In this talk, I will introduce the tree space and its geometry, before presenting a practical algorithm to compute the geodesic distance.  The possible shortest paths between two trees can be represented as a partially ordered set, and part of this algorithm solves a special case of the shortest Euclidean path problem in R^n with obstacles in linear time.

February 15, 2008