A tight kernel for computing the tree bisection and reconnection distance between two phylogenetic trees
From MaRDI portal
Publication:5233752
DOI10.1137/18M122724XzbMATH Open1430.68130arXiv1811.06892OpenAlexW2901518681WikidataQ127291120 ScholiaQ127291120MaRDI QIDQ5233752FDOQ5233752
Publication date: 6 September 2019
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Abstract: In 2001 Allen and Steel showed that, if subtree and chain reduction rules have been applied to two unrooted phylogenetic trees, the reduced trees will have at most 28k taxa where k is the TBR (Tree Bisection and Reconnection) distance between the two trees. Here we reanalyse Allen and Steel's kernelization algorithm and prove that the reduced instances will in fact have at most 15k-9 taxa. Moreover we show, by describing a family of instances which have exactly 15k-9 taxa after reduction, that this new bound is tight. These instances also have no common clusters, showing that a third commonly-encountered reduction rule, the cluster reduction, cannot further reduce the size of the kernel in the worst case. To achieve these results we introduce and use "unrooted generators" which are analogues of rooted structures that have appeared earlier in the phylogenetic networks literature. Using similar argumentation we show that, for the minimum hybridization problem on two rooted trees, 9k-2 is a tight bound (when subtree and chain reduction rules have been applied) and 9k-4 is a tight bound (when, additionally, the cluster reduction has been applied) on the number of taxa, where k is the hybridization number of the two trees.
Full work available at URL: https://arxiv.org/abs/1811.06892
Recommendations
- New reduction rules for the tree bisection and reconnection distance
- Reflections on kernelizing and computing unrooted agreement forests
- On the fixed parameter tractability of agreement-based phylogenetic distances
- Kernelizations for the hybridization number problem on multiple nonbinary trees
- Treewidth distance on phylogenetic trees
phylogenetic treegeneratorfixed-parameter tractabilityphylogenetic networkkernelizationhybridization numbertree bisection and reconnection
Problems related to evolution (92D15) Trees (05C05) Analysis of algorithms (68W40) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- Fixed-parameter algorithms for maximum agreement forests
- A parsimony-based metric for phylogenetic trees
- On the computational complexity of the rooted subtree prune and regraft distance
- Phylogeny. Discrete and random processes in evolution
- Subtree transfer operations and their induced metrics on evolutionary trees
- On the complexity of comparing evolutionary trees
- On the maximum parsimony distance between phylogenetic trees
- Parameterized Algorithms
- Kernelization Lower Bounds by Cross-Composition
- Computing the minimum number of hybridization events for a consistent evolutionary history
- A quadratic kernel for computing the hybridization number of multiple trees
- Kernelizations for the hybridization number problem on multiple nonbinary trees
- Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable
- Cycle Killer...Qu'est-ce que c'est? On the Comparative Approximability of Hybridization Number and Directed Feedback Vertex Set
- Reduction rules for the maximum parsimony distance on phylogenetic trees
- Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees
- On unrooted and root-uncertain variants of several well-known phylogenetic network problems
- On the fixed parameter tractability of agreement-based phylogenetic distances
- A parameterized algorithm for the maximum agreement forest problem on multiple rooted multifurcating trees
- A note on convex characters, Fibonacci numbers and exponential-time algorithms
- Hybridization number on three rooted binary trees is EPT
Cited In (6)
- A near-linear kernel for bounded-state parsimony distance
- Maximum parsimony distance on phylogenetic trees: a linear kernel and constant factor approximation algorithm
- Deep kernelization for the tree bisection and reconnection (TBR) distance in phylogenetics
- Cyclic generators and an improved linear kernel for the rooted subtree prune and regraft distance
- Reflections on kernelizing and computing unrooted agreement forests
- New reduction rules for the tree bisection and reconnection distance
This page was built for publication: A tight kernel for computing the tree bisection and reconnection distance between two phylogenetic trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5233752)
