Reflections on kernelizing and computing unrooted agreement forests
From MaRDI portal
Publication:2069261
DOI10.1007/S10479-021-04352-1zbMATH Open1480.92156arXiv2012.07354OpenAlexW4287553373MaRDI QIDQ2069261FDOQ2069261
Authors: Rim van Wersch, Steven Kelk, Simone Linz, Georgios Stamoulis 
Publication date: 20 January 2022
Published in: Annals of Operations Research (Search for Journal in Brave)
Abstract: Phylogenetic trees are leaf-labelled trees used to model the evolution of species. Here we explore the practical impact of kernelization (i.e. data reduction) on the NP-hard problem of computing the TBR distance between two unrooted binary phylogenetic trees. This problem is better-known in the literature as the maximum agreement forest problem, where the goal is to partition the two trees into a minimum number of common, non-overlapping subtrees. We have implemented two well-known reduction rules, the subtree and chain reduction, and five more recent, theoretically stronger reduction rules, and compare the reduction achieved with and without the stronger rules. We find that the new rules yield smaller reduced instances and thus have clear practical added value. In many cases they also cause the TBR distance to decrease in a controlled fashion. Next, we compare the achieved reduction to the known worst-case theoretical bounds of 15k-9 and 11k-9 respectively, on the number of leaves of the two reduced trees, where k is the TBR distance, observing in both cases a far larger reduction in practice. As a by-product of our experimental framework we obtain a number of new insights into the actual computation of TBR distance. We find, for example, that very strong lower bounds on TBR distance can be obtained efficiently by randomly sampling certain carefully constructed partitions of the leaf labels, and identify instances which seem particularly challenging to solve exactly. The reduction rules have been implemented within our new solver Tubro which combines kernelization with an Integer Linear Programming (ILP) approach. Tubro also incorporates a number of additional features, such as a cluster reduction and a practical upper-bounding heuristic, and it can leverage combinatorial insights emerging from the proofs of correctness of the reduction rules to simplify the ILP.
Full work available at URL: https://arxiv.org/abs/2012.07354
Recommendations
- New reduction rules for the tree bisection and reconnection distance
- A tight kernel for computing the tree bisection and reconnection distance between two phylogenetic trees
- On the fixed parameter tractability of agreement-based phylogenetic distances
- A cluster reduction for computing the subtree distance between phylogenies
- On agreement forests
Problems related to evolution (92D15) Trees (05C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Integer programming (90C10) Distance in graphs (05C12)
Cites Work
- Fixed-parameter algorithms for maximum agreement forests
- A parsimony-based metric for phylogenetic trees
- Fundamentals of parameterized complexity
- Title not available (Why is that?)
- Subtree transfer operations and their induced metrics on evolutionary trees
- On the complexity of comparing evolutionary trees
- A Greedy Heuristic for the Set-Covering Problem
- On the maximum parsimony distance between phylogenetic trees
- Parameterized algorithms
- Kernelizations for the hybridization number problem on multiple nonbinary trees
- Reduction rules for the maximum parsimony distance on phylogenetic trees
- Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees
- The probabilities of rooted tree-shapes generated by random bifurcation
- Experiments on data reduction for optimal domination in networks
- On the fixed parameter tractability of agreement-based phylogenetic distances
- On the complexity of computing MP distance between binary phylogenetic trees
- A note on convex characters, Fibonacci numbers and exponential-time algorithms
- Kernelization. Theory of parameterized preprocessing
- Extremal distances for subtree transfer operations in binary trees
- The power of linear-time data reduction for maximum matching
- New reduction rules for the tree bisection and reconnection distance
- Multilocus phylogenetic analysis with gene tree clustering
- Computing maximum agreement forests without cluster partitioning is folly
- Engineering Kernelization for Maximum Cut
- Shared-Memory Branch-and-Reduce for Multiterminal Cuts
- A tight kernel for computing the tree bisection and reconnection distance between two phylogenetic trees
- What Is Known About Vertex Cover Kernelization?
Cited In (6)
- Convex Characters, Algorithms, and Matchings
- A near-linear kernel for bounded-state parsimony distance
- Deep kernelization for the tree bisection and reconnection (TBR) distance in phylogenetics
- Sharp upper and lower bounds on a restricted class of convex characters
- A tight kernel for computing the tree bisection and reconnection distance between two phylogenetic trees
- New reduction rules for the tree bisection and reconnection distance
Uses Software
This page was built for publication: Reflections on kernelizing and computing unrooted agreement forests
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2069261)
