Fixed-parameter and approximation algorithms for maximum agreement forests of multifurcating trees
From MaRDI portal
Publication:270010
DOI10.1007/S00453-015-9983-ZzbMATH Open1333.68297arXiv1305.0512OpenAlexW2002094114MaRDI QIDQ270010FDOQ270010
Robert G. Beiko, Chris Whidden, Norbert Zeh
Publication date: 6 April 2016
Published in: Algorithmica (Search for Journal in Brave)
Abstract: We present efficient algorithms for computing a maximum agreement forest (MAF) of a pair of multifurcating (nonbinary) rooted trees. Our algorithms match the running times of the currently best algorithms for the binary case. The size of an MAF corresponds to the subtree prune-and-regraft (SPR) distance of the two trees and is intimately connected to their hybridization number. These distance measures are essential tools for understanding reticulate evolution, such as lateral gene transfer, recombination, and hybridization. Multifurcating trees arise naturally as a result of statistical uncertainty in current tree construction methods.
Full work available at URL: https://arxiv.org/abs/1305.0512
Recommendations
- Parameterized and approximation algorithms for the MAF problem in multifurcating trees
- Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees
- Fixed-parameter algorithms for maximum agreement forests
- Parameterized algorithms for maximum agreement forest on multiple trees
- Algorithms for parameterized maximum agreement forest problem on multiple trees
Cites Work
- Fixed-parameter algorithms for maximum agreement forests
- On the computational complexity of the rooted subtree prune and regraft distance
- Introduction to algorithms
- Subtree transfer operations and their induced metrics on evolutionary trees
- On the complexity of comparing evolutionary trees
- The maximum agreement forest problem: Approximation algorithms and computational experiments
- Approximation Algorithms for Nonbinary Agreement Forests
- A 3-approximation algorithm for the subtree distance between phylogenies
- Bounding the number of hybridisation events for a consistent evolutionary history
- Faster Exact Computation of rSPR Distance
- Computing the minimum number of hybridization events for a consistent evolutionary history
Cited In (11)
- New Gromov-inspired metrics on phylogenetic tree space
- On the subnet prune and regraft distance
- Computing Maximum Agreement Forests without Cluster Partitioning is Folly
- Approximating maximum agreement forest on multiple binary trees
- Improved approximation algorithm for maximum agreement forest of two rooted binary phylogenetic trees
- A parameterized algorithm for the maximum agreement forest problem on multiple rooted multifurcating trees
- Gene tree reconciliation including transfers with replacement is NP-hard and FPT
- On the fixed parameter tractability of agreement-based phylogenetic distances
- Fixed-Parameter Algorithms for Finding Agreement Supertrees
- MUL-tree pruning for consistency and optimal reconciliation -- complexity and algorithms
- A faster FPT algorithm for the maximum agreement forest problem
Uses Software
This page was built for publication: Fixed-parameter and approximation algorithms for maximum agreement forests of multifurcating trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q270010)
