Extremal distances for subtree transfer operations in binary trees

DOI10.1007/S00026-018-0410-4MaRDI QIDQ2421307zbMATH OpenOpenAlexWikidataFDO

Authors Ross Atkins, Colin McDiarmid

Publication date 14 June 2019

Published in Annals of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

phylogenetic treesubtree prune and regraftbinary treeagreement forestaverage distancetree rearrangementextremal distancetree bisection and reconnection

Mathematics Subject Classification ID

Problems related to evolution (92D15) Trees (05C05) Extremal problems in graph theory (05C35) Distance in graphs (05C12) Graph operations (line graphs, products, etc.) (05C76)

Abstract: Three standard subtree transfer operations for binary trees, used in particular for phylogenetic trees, are: tree bisection and reconnection ($TBR$), subtree prune and regraft ($SPR$) and rooted subtree prune and regraft ($rSPR$). For a pair of leaf-labelled binary trees with $n$ leaves, the maximum number of such moves required to transform one into the other is $n-Theta(sqrtn)$, extending a result of Ding, Grunewald and Humphries. We show that if the pair is chosen uniformly at random, then the expected number of moves required to transfer one into the other is $n-Theta(n^{2/3})$. These results may be phrased in terms of agreement forests: we also give extensions for more than two binary trees.

Recommendations

• Some extremal ratios of the distance and subtree problems in binary trees
• Extremal values of ratios: distance problems vs. subtree problems in trees. II
• Extremal values of ratios: distance problems vs. subtree problems in trees
• A distance metric on binary trees using lattice-theoretic measures
• scientific article; zbMATH DE number 1161281
• Extremal values for ratios of distances in trees
• On the rotation distance between binary trees
• Lower bounds on the rotation distance of binary trees
• Distance Approximating Trees: Complexity and Algorithms
• Distance preserving subtrees in minimum average distance spanning trees

Cites work

• scientific article; zbMATH DE number 4170917 (Why is no real title available?)
• scientific article; zbMATH DE number 1974592 (Why is no real title available?)
• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• scientific article; zbMATH DE number 850224 (Why is no real title available?)
• scientific article; zbMATH DE number 3019031 (Why is no real title available?)
• Bounds on the expected size of the maximum agreement subtree
• Does random tree puzzle produce Yule-Harding trees in the many-taxon limit?
• Note on the hybridization number and subtree distance in phylogenetics
• On agreement forests
• On the complexity of comparing evolutionary trees
• On the computational complexity of the rooted subtree prune and regraft distance
• Reconstructing evolution of sequences subject to recombination using parsimony
• Subtree transfer operations and their induced metrics on evolutionary trees
• The maximum agreement subtree problem

Cited in

(9)

• Ricci-Ollivier curvature of the rooted phylogenetic subtree-prune-regraft graph
• Maximum parsimony distance on phylogenetic trees: a linear kernel and constant factor approximation algorithm
• Exploring the tiers of rooted phylogenetic network space using tail moves
• Deep kernelization for the tree bisection and reconnection (TBR) distance in phylogenetics
• Lagged couplings diagnose Markov chain Monte Carlo phylogenetic inference
• Ranked subtree prune and regraft
• Properties of subtree-prune-and-regraft operations on totally-ordered phylogenetic trees
• Reflections on kernelizing and computing unrooted agreement forests
• New reduction rules for the tree bisection and reconnection distance

This page was built for publication: Extremal distances for subtree transfer operations in binary trees

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