User Tools

Site Tools


seminars:comb:abstract.200803owe

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.


seminars/comb/abstract.200803owe.txt · Last modified: 2020/01/29 14:03 (external edit)