Fixed-parameter algorithms for maximum agreement forests
From MaRDI portal
Abstract: We present new and improved fixed-parameter algorithms for computing maximum agreement forests (MAFs) of pairs of rooted binary phylogenetic trees. The size of such a forest for two trees corresponds to their subtree prune-and-regraft distance and, if the agreement forest is acyclic, to their hybridization number. These distance measures are essential tools for understanding reticulate evolution. Our algorithm for computing maximum acyclic agreement forests is the first depth-bounded search algorithm for this problem. Our algorithms substantially outperform the best previous algorithms for these problems.
Recommendations
- Fixed-parameter and approximation algorithms for maximum agreement forests of multifurcating trees
- Algorithms for parameterized maximum agreement forest problem on multiple trees
- Parameterized algorithms for maximum agreement forest on multiple trees
- Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees
- On the fixed parameter tractability of agreement-based phylogenetic distances
Cited in
(44)- TBRDist
- A parameterized algorithm for the maximum agreement forest problem on multiple rooted multifurcating trees
- Ricci-Ollivier curvature of the rooted phylogenetic subtree-prune-regraft graph
- Deciding the existence of a cherry-picking sequence is hard on two trees
- On unrooted and root-uncertain variants of several well-known phylogenetic network problems
- Reflections on kernelizing and computing unrooted agreement forests
- A practical fixed-parameter algorithm for constructing tree-child networks from multiple binary trees
- New reduction rules for the tree bisection and reconnection distance
- Maximum parsimony distance on phylogenetic trees: a linear kernel and constant factor approximation algorithm
- Not all phylogenetic networks are leaf-reconstructible
- Reconciliation of a gene network and species tree
- A quadratic kernel for computing the hybridization number of multiple trees
- A faster FPT algorithm for the maximum agreement forest problem
- rSPR
- On the maximum parsimony distance between phylogenetic trees
- Cyclic generators and an improved linear kernel for the rooted subtree prune and regraft distance
- A duality based 2-approximation algorithm for maximum agreement forest
- Fixed-parameter and approximation algorithms for maximum agreement forests of multifurcating trees
- Hybridization number on three rooted binary trees is EPT
- Kernelizations for the hybridization number problem on multiple nonbinary trees
- Improved approximation algorithm for maximum agreement forest of two rooted binary phylogenetic trees
- Scanning phylogenetic networks is NP-hard
- The agreement distance of unrooted phylogenetic networks
- Cherry picking: a characterization of the temporal hybridization number for a set of phylogenies
- Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable
- Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees
- On the fixed parameter tractability of agreement-based phylogenetic distances
- Combining Networks Using Cherry Picking Sequences
- Better practical algorithms for rSPR distance and hybridization number
- Computing maximum agreement forests without cluster partitioning is folly
- A tight kernel for computing the tree bisection and reconnection distance between two phylogenetic trees
- Fixed-Parameter Algorithms for Finding Agreement Supertrees
- Convex Characters, Algorithms, and Matchings
- Deep kernelization for the tree bisection and reconnection (TBR) distance in phylogenetics
- Ranked subtree prune and regraft
- Vector encoding of phylogenetic trees by ordered leaf attachment
- Cherry picking in forests: a new characterization for the unrooted hybrid number of two phylogenetic trees
- A branch-\&-price approach to the unrooted maximum agreement forest problem
- Bounding the SNPR distance between two tree-child networks using generalised agreement forests
- A simple 4-approximation algorithm for maximum agreement forests on multiple unrooted binary trees
- Bounding the number of reticulation events for displaying multiple trees in a phylogenetic network
- Split-or-decompose: improved FPT branching algorithms for maximum agreement forests
- Approximating maximum agreement forest on multiple binary trees
- Algorithms for parameterized maximum agreement forest problem on multiple trees
This page was built for publication: Fixed-parameter algorithms for maximum agreement forests
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2862198)
