A tight kernel for computing the tree bisection and reconnection distance between two phylogenetic trees
From MaRDI portal
Publication:5233752
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.
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
Cites work
- A note on convex characters, Fibonacci numbers and exponential-time algorithms
- A parameterized algorithm for the maximum agreement forest problem on multiple rooted multifurcating trees
- A parsimony-based metric for phylogenetic trees
- A quadratic kernel for computing the hybridization number of multiple trees
- Computing the minimum number of hybridization events for a consistent evolutionary history
- 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
- Fixed-parameter algorithms for maximum agreement forests
- Hybridization number on three rooted binary trees is EPT
- Kernelization Lower Bounds by Cross-Composition
- Kernelizations for the hybridization number problem on multiple nonbinary trees
- On the complexity of comparing evolutionary trees
- On the computational complexity of the rooted subtree prune and regraft distance
- On the fixed parameter tractability of agreement-based phylogenetic distances
- On the maximum parsimony distance between phylogenetic trees
- On unrooted and root-uncertain variants of several well-known phylogenetic network problems
- Parameterized algorithms
- Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees
- Phylogeny. Discrete and random processes in evolution
- Reduction rules for the maximum parsimony distance on phylogenetic trees
- Subtree transfer operations and their induced metrics on evolutionary trees
Cited in
(8)- Maximum parsimony distance on phylogenetic trees: a linear kernel and constant factor approximation algorithm
- A near-linear kernel for bounded-state parsimony distance
- Deep kernelization for the tree bisection and reconnection (TBR) distance in phylogenetics
- Kernelizations for the hybridization number problem on multiple nonbinary trees
- Treewidth distance on phylogenetic trees
- 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)
