Fixed-parameter and approximation algorithms for maximum agreement forests of multifurcating trees
From MaRDI portal
(Redirected from Publication:270010)
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.
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
- A 3-approximation algorithm for the subtree distance between phylogenies
- Approximation algorithms for nonbinary agreement forests
- Bounding the number of hybridisation events for a consistent evolutionary history
- Computing the minimum number of hybridization events for a consistent evolutionary history
- Faster exact computation of rSPR distance
- Fixed-parameter algorithms for maximum agreement forests
- Introduction to algorithms
- On the complexity of comparing evolutionary trees
- On the computational complexity of the rooted subtree prune and regraft distance
- Subtree transfer operations and their induced metrics on evolutionary trees
- The maximum agreement forest problem: Approximation algorithms and computational experiments
Cited in
(14)- A faster FPT algorithm for the maximum agreement forest problem
- New Gromov-inspired metrics on phylogenetic tree space
- Parameterized and approximation algorithms for the MAF problem in multifurcating trees
- On the subnet prune and regraft distance
- Fixed-parameter algorithms for maximum agreement forests
- Approximating maximum agreement forest on multiple binary trees
- Parameterized and approximation algorithms for maximum agreement forest in multifurcating 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
- Computing maximum agreement forests without cluster partitioning is folly
- 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
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)
