Computing Geodesic Distances in Tree Space
Megan Owen · SIAM Journal on Discrete Mathematics · 2011
We present two algorithms for computing the geodesic distance between phylogenetic trees in tree space, as introduced by Billera, Holmes, and Vogtmann [Adv. Appl. Math., 27 (2001), pp. 733–767]. We show that the possible combinatorial types of shortest paths between two trees can be compactly represented by a partially ordered set. We calculate the shortest distance along each candidate path by converting the problem into one of finding the shortest path through a certain region of Euclidean space. In particular, we show there is a linear time algorithm for finding the shortest path between a point in the all-positive orthant and a point in the all-negative orthant of $\mathbb{R}^k$ contained in the subspace of $\mathbb{R}^k$ consisting of all orthants with the first i coordinates nonpositive and the remaining coordinates nonnegative for $0 \leq i \leq k$.