Problem of the Week
BUGCAT
Zassenhaus Conference
Hilton Memorial Lecture
BingAWM
Math Club
Actuarial Association
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.