Polyhedral computational geometry for averaging metric phylogenetic trees
From MaRDI portal
Publication:2348943
Trees (05C05) Computational aspects related to convexity (52B55) Global geometric and topological methods (à la Gromov); differential geometric analysis on metric spaces (53C23) Probability measures on topological spaces (60B05) Applications of statistics to biology and medical sciences; meta analysis (62P10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Problems related to evolution (92D15)
Abstract: This paper investigates the computational geometry relevant to calculations of the Frechet mean and variance for probability distributions on the phylogenetic tree space of Billera, Holmes and Vogtmann, using the theory of probability measures on spaces of nonpositive curvature developed by Sturm. We show that the combinatorics of geodesics with a specified fixed endpoint in tree space are determined by the location of the varying endpoint in a certain polyhedral subdivision of tree space. The variance function associated to a finite subset of tree space has a fixed algebraic formula within each cell of the corresponding subdivision, and is continuously differentiable in the interior of each orthant of tree space. We use this subdivision to establish two iterative methods for producing sequences that converge to the Frechet mean: one based on Sturm's Law of Large Numbers, and another based on descent algorithms for finding optima of smooth functions on convex polyhedra. We present properties and biological applications of Frechet means and extend our main results to more general globally nonpositively curved spaces composed of Euclidean orthants.
Recommendations
- Geometry of the space of phylogenetic trees
- An algebraic metric for phylogenetic trees
- Phylogenetic tree reconstruction: geometric approaches
- On geometry of binary symmetric models of phylogenetic trees
- Phylogenetic trees and Euclidean embeddings
- A novel approach to phylogenetic trees: d‐Dimensional geometric Steiner trees
- Polyhedral geometry of phylogenetic rogue taxa
- Geometric medians in reconciliation spaces of phylogenetic trees
- Geometry of phylogenetic group-based models
- New Gromov-inspired metrics on phylogenetic tree space
Cites work
- Computing geodesic distances in tree space
- Computing medians and means in Hadamard spaces
- Consensus n-trees
- Geodesics in CAT(0) cubical complexes
- Geometry of the space of phylogenetic trees
- scientific article; zbMATH DE number 4031953 (Why is no real title available?)
- scientific article; zbMATH DE number 4102053 (Why is no real title available?)
- scientific article; zbMATH DE number 1974599 (Why is no real title available?)
- scientific article; zbMATH DE number 2051142 (Why is no real title available?)
- scientific article; zbMATH DE number 1385418 (Why is no real title available?)
- scientific article; zbMATH DE number 1865935 (Why is no real title available?)
- scientific article; zbMATH DE number 1424303 (Why is no real title available?)
- Lectures on Polytopes
- Limit Theorems for the Inductive Mean on Metric Trees
- Metric combinatorics of convex polyhedra: cut loci and nonoverlapping unfoldings
- Network flows. Theory, algorithms, and applications.
- On the structure of all minimum cuts in a network and applications
- Principal components analysis in the space of phylogenetic trees
- Statistical approach to tests involving phylogenies
- Statistics for phylogenetic trees
- Sticky central limit theorems on open books
- Tree-oriented analysis of brain artery structure
Cited in
(47)- Geometry of the space of phylogenetic trees
- The topology and geometry of automorphism groups of free groups
- A consensus algorithm in CAT(0) space and its application to distributed fusion of phylogenetic trees
- Limiting behaviour of Fréchet means in the space of phylogenetic trees
- Geometric medians in reconciliation spaces of phylogenetic trees
- Random walks and Brownian motion on cubical complexes
- The Stein effect for Fréchet means
- Information metrics for phylogenetic trees via distributions of discrete and continuous characters
- Wald space for phylogenetic trees
- Properties for the Fréchet mean in Billera-Holmes-Vogtmann treespace
- Shortest paths and convex hulls in 2D complexes with non-positive curvature
- A nonpositive curvature property of modular semilattices
- Multilocus phylogenetic analysis with gene tree clustering
- Geometry and statistics: manifolds and stratified spaces
- Tree-oriented analysis of brain artery structure
- Information geometry for phylogenetic trees
- A polynomial time algorithm to compute geodesics in CAT(0) cubical complexes
- Computing medians and means in Hadamard spaces
- The space of ultrametric phylogenetic trees
- Uncertainty in Phylogenetic Tree Estimates
- Central limit theorems for Fréchet means in the space of phylogenetic trees
- Sticky central limit theorems on open books
- A space of phylogenetic networks
- Relative Optimality Conditions and Algorithms for Treespace Fréchet Means
- A polynomial time algorithm to compute geodesics in CAT(0) cubical complexes
- A novel approach to phylogenetic trees: d‐Dimensional geometric Steiner trees
- Representations of partial leaf sets in phylogenetic tree space
- How to calculate the barycenter of a weighted graph
- Confidence Sets for Phylogenetic Trees
- Convexity in tree spaces
- Old and new challenges in Hadamard spaces
- Mean ergodic theorems for a sequence of nonexpansive mappings in complete \(\mathrm{CAT}(0)\) spaces and its applications
- The space of equidistant phylogenetic cactuses
- Foundations of the Wald Space for Phylogenetic Trees
- Geodesics in CAT(0) cubical complexes
- Maximum likelihood estimation of log-concave densities on tree space
- Tropical convexity in location problems
- Tropical consensus trees
- Hypothesis testing for two sample comparison of non Euclidean network data
- Spaces of ranked tree-child networks
- Intrinsic interleaving distance for merge trees
- Convex optimization on \(\mathrm{CAT}(0)\) cubical complexes
- Consistency of nonparametric density estimators in CAT(0) orthant space
- Tropical Fréchet means: a polyhedral approach to exact optimization
- Geometry of the space of phylogenetic trees with non-identical leaves
- Tropical Fréchet means
- Discrete coalescent trees
This page was built for publication: Polyhedral computational geometry for averaging metric phylogenetic trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2348943)
