Computing geodesic distances in tree space

DOI10.1137/090751396MaRDI QIDQ3225136zbMATH OpenOpenAlexFDO

Authors Megan Owen

Publication date 15 March 2012

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

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

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)

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.

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

Cited in

(21)

• The space of ultrametric phylogenetic trees
• Isometric embeddings in trees and their use in distance problems
• Shortest paths and convex hulls in 2D complexes with non-positive curvature
• Convexity in tree spaces
• A nonpositive curvature property of modular semilattices
• Fixed gate point location problems
• Polyhedral computational geometry for averaging metric phylogenetic trees
• A polynomial time algorithm to compute geodesics in CAT(0) cubical complexes
• Wald space for phylogenetic trees
• Limiting behaviour of Fréchet means in the space of phylogenetic trees
• Computing medians and means in Hadamard spaces
• 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
• Melzak algorithm for phylogenetic spaces
• A polynomial time algorithm to compute geodesics in CAT(0) cubical complexes
• Approximating geodesic tree distance
• A space of phylogenetic networks
• Computing the nc-Rank via Discrete Convex Optimization on CAT(0) Spaces
• Representations of partial leaf sets in phylogenetic tree space
• 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)