Computing geodesic distances in tree space

DOI10.1137/090751396zbMATH Open1237.05045arXiv0903.0696OpenAlexW2964075524MaRDI QIDQ3225136FDOQ3225136

Authors: Megan Owen 

Publication date: 15 March 2012

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/0903.0696

Recommendations

• Approximating geodesic tree distance
• Geometry of the space of phylogenetic trees
• New Gromov-inspired metrics on phylogenetic tree space
• An \(O(n \log n)\) time algorithm for computing the path-length distance between trees
• Convexity in tree spaces

zbMATH Keywords

tree spacecomputational geometryphylogenyshortest pathgeodesic distance

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Taxonomy, cladistics, statistics in mathematical biology (92B10) Distance in graphs (05C12) Paths and cycles (05C38)

Cited In (20)

• A polynomial time algorithm to compute geodesics in CAT(0) cubical complexes
• Melzak algorithm for phylogenetic spaces
• Isometric embeddings in trees and their use in distance problems
• A nonpositive curvature property of modular semilattices
• Representations of Partial Leaf Sets in Phylogenetic Tree Space
• Polyhedral computational geometry for averaging metric phylogenetic trees
• Computing the nc-Rank via Discrete Convex Optimization on CAT(0) Spaces
• Approximating geodesic tree distance
• A polynomial time algorithm to compute geodesics in CAT(0) cubical complexes
• Old and new challenges in Hadamard spaces
• A consensus algorithm in CAT(0) space and its application to distributed fusion of phylogenetic trees
• Properties for the Fréchet mean in Billera-Holmes-Vogtmann treespace
• A Space of Phylogenetic Networks
• The space of ultrametric phylogenetic trees
• Limiting behaviour of Fréchet means in the space of phylogenetic trees
• Computing the Gromov-Hausdorff Distance for Metric Trees
• Wald space for phylogenetic trees
• Shortest paths and convex hulls in 2D complexes with non-positive curvature
• Fixed gate point location problems
• Consistency of a phylogenetic tree maximum likelihood estimator

This page was built for publication: Computing geodesic distances in tree space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3225136)