A Fast Algorithm for Computing Geodesic Distances in Tree Space

Details A Fast Algorithm for Computing Geodesic Distances in Tree Space A Fast Algorithm for Computing Geodesic Distances in Tree Space

2009-07-23

arxiv.org/abs/0907.3942v2

Biology

Quantitative Biology

Populations and Evolution

20 pages, 5 figures. Added new section on including common edges and leaf edge-lengths in the algorithm, clarified starting po

Scientific paper

Comparing and computing distances between phylogenetic trees are important biological problems, especially for models where edge lengths play an important role. The geodesic distance measure between two phylogenetic trees with edge lengths is the length of the shortest path between them in the continuous tree space introduced by Billera, Holmes, and Vogtmann. This tree space provides a powerful tool for studying and comparing phylogenetic trees, both in exhibiting a natural distance measure and in providing a Euclidean-like structure for solving optimization problems on trees. An important open problem is to find a polynomial time algorithm for finding geodesics in tree space. This paper gives such an algorithm, which starts with a simple initial path and moves through a series of successively shorter paths until the geodesic is attained.

Affiliated with

Also associated with

No associations

Rating

A Fast Algorithm for 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 A Fast Algorithm for Computing Geodesic Distances in Tree Space, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Fast Algorithm for Computing Geodesic Distances in Tree Space will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-354229