Ricci-Ollivier curvature of the rooted phylogenetic subtree-prune-regraft graph

DOI10.1016/j.tcs.2017.02.006zbMath1380.92048OpenAlexW2962693999WikidataQ125709094 ScholiaQ125709094MaRDI QIDQ1675925

Chris Whidden, Frederick A. IV Matsen

Publication date: 3 November 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2017.02.006

zbMATH Keywords

Markov chain Monte CarlophylogeneticsRicci-Ollivier curvaturesubtree-prune-regraft

Mathematics Subject Classification ID

Problems related to evolution (92D15) Applications of graph theory (05C90) Monte Carlo methods (65C05)

Related Items (10)

Transforming phylogenetic networks: moving beyond tree space ⋮ Improved approximation algorithm for maximum agreement forest of two rooted binary phylogenetic trees ⋮ The Graph Curvature Calculator and the Curvatures of Cubic Graphs ⋮ Gene tree reconciliation including transfers with replacement is NP-hard and FPT ⋮ Ranked subtree prune and regraft ⋮ Emergence of the circle in a statistical model of random cubic graphs ⋮ Computing nearest neighbour interchange distances between ranked phylogenetic trees ⋮ The combinatorics of discrete time-trees: theory and open problems ⋮ Long-scale ollivier Ricci curvature of graphs ⋮ Consistency of a phylogenetic tree maximum likelihood estimator

Uses Software

• GAP
• SageMath
• GLPK
• fastDNAml
• MrBayes
• BEAST
• BEAUti
• rSPR
• EMD
• spr_neighbors

Cites Work

• Unnamed Item
• Unnamed Item
• MrBayes
• On the enumeration of tanglegrams and tangled chains
• On agreement forests
• Curvature, concentration and error estimates for Markov chain Monte Carlo
• Ricci curvature of graphs
• Limitations of Markov chain Monte Carlo algorithms for Bayesian inference of phylogeny
• Ricci curvature of Markov chains on metric spaces
• On the combinatorics of rooted binary phylogenetic trees
• Partition-distance: A problem and class of perfect graphs arising in clustering
• On the computational complexity of the rooted subtree prune and regraft distance
• Random walks on trees and matchings
• The earth mover's distance as a metric for image retrieval
• Ollivier's Ricci curvature, local clustering and curvature-dimension inequalities on graphs
• Ricci curvature on polyhedral surfaces via optimal transportation
• Invariance principle for variable speed random walks on trees
• Extremal distances for subtree transfer operations in binary trees
• A note on the relaxation time of two Markov chains on rooted phylogenetic tree spaces
• Properties of subtree-prune-and-regraft operations on totally-ordered phylogenetic trees
• Subtree prune and regraft: a reversible real tree-valued Markov process
• Fixed-Parameter Algorithms for Maximum Agreement Forests
• Fast Convergence of Markov Chain Monte Carlo Algorithms for Phylogenetic Reconstruction with Homogeneous Data on Closely Related Species
• Mixing Time for a Markov Chain on Cladograms
• Efficiently Inferring Pairwise Subtree Prune-and-Regraft Adjacencies between Phylogenetic Trees
• Comparison of labeled trees with valency three
• SAGE

This page was built for publication: Ricci-Ollivier curvature of the rooted phylogenetic subtree-prune-regraft graph