Computing Geodesic Distances in Tree Space

Details Computing Geodesic Distances in Tree Space Computing Geodesic Distances in Tree Space

2009-03-04

arxiv.org/abs/0903.0696v2

Mathematics

Combinatorics

24 pages, 7 figures; v2: substantially revised for clarity

Scientific paper

We present two algorithms for computing the geodesic distance between phylogenetic trees in tree space, as introduced by Billera, Holmes, and Vogtmann (2001). 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 R^k contained in the subspace of R^k consisting of all orthants with the first i coordinates non-positive and the remaining coordinates non-negative for 0 <= i <= k.

Affiliated with

Also associated with

No associations

Rating

Computing Geodesic Distances in Tree Space does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Computing Geodesic Distances in Tree Space, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing Geodesic Distances in Tree Space will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-368783