A parameterized algorithm for the maximum agreement forest problem on multiple rooted multifurcating trees

DOI10.1016/J.JCSS.2018.03.002MaRDI QIDQ1671997zbMATHzbMATHOpenAlexWikidataFDO

Authors Feng Shi, Qilong Feng, Jianxin Wang, Jianer Chen

Publication date 7 September 2018

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.02709

zbMATH Keywords

phylogenetic treealgorithmmaximum agreement forest

Mathematics Subject Classification ID

Problems related to evolution (92D15) Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40)

Abstract: The Maximum Agreement Forest problem has been extensively studied in phylogenetics. Most previous work is on two binary phylogenetic trees. In this paper, we study a generalized version of the problem: the Maximum Agreement Forest problem on multiple rooted multifurcating phylogenetic trees, from the perspective of fixed-parameter algorithms. By taking advantage of a new branch-and-bound strategy, two parameterized algorithms, with running times $O(2.42^k{m}^3{n}^4)$ and $O(2.74^k{m}^3{n}^5)$, respectively, are presented for the hard version and the soft version of the problem, which correspond to two different biological meanings to the polytomies in multifurcating phylogenetic trees.

Recommendations

• Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees
• Parameterized and approximation algorithms for the MAF problem in multifurcating trees
• Algorithms for parameterized maximum agreement forest problem on multiple trees
• Parameterized algorithms for maximum agreement forest on multiple trees
• Fixed-parameter and approximation algorithms for maximum agreement forests of multifurcating trees

Cites work

• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 1833410 (Why is no real title available?)
• A 3-approximation algorithm for the subtree distance between phylogenies
• A duality based 2-approximation algorithm for maximum agreement forest
• A faster FPT algorithm for the maximum agreement forest problem
• A quadratic kernel for computing the hybridization number of multiple trees
• Algorithms for parameterized maximum agreement forest problem on multiple trees
• An improved approximation algorithm for rSPR distance
• Approximating the maximum agreement forest on \(k\) trees
• Approximation algorithms for nonbinary agreement forests
• Bounding the number of hybridisation events for a consistent evolutionary history
• Comparison of phylogenetic trees
• Faster exact computation of rSPR distance
• Fixed-parameter algorithms for maximum agreement forests
• Fixed-parameter and approximation algorithms for maximum agreement forests of multifurcating trees
• Improved approximation algorithm for maximum agreement forest of two rooted binary phylogenetic trees
• On the complexity of comparing evolutionary trees
• On the computational complexity of the rooted subtree prune and regraft distance
• Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees
• Subtree transfer operations and their induced metrics on evolutionary trees
• The maximum agreement forest problem: Approximation algorithms and computational experiments
• Vertex cover: Further observations and further improvements

Cited in

(13)

• New reduction rules for the tree bisection and reconnection distance
• Parameterized and approximation algorithms for the MAF problem in multifurcating trees
• Fixed-parameter tractability for minimum tree cut/paste distance and minimum common integer partition
• Maximum parsimony distance on phylogenetic trees: a linear kernel and constant factor approximation algorithm
• A tight kernel for computing the tree bisection and reconnection distance between two phylogenetic trees
• Approximating maximum agreement forest on multiple binary trees
• Parameterized algorithms for maximum agreement forest on multiple trees
• Algorithms for parameterized maximum agreement forest problem on multiple trees
• Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees
• Improved approximation algorithms for two-stage flowshops scheduling problem
• An approximation algorithm for the \(l\)-pseudoforest deletion problem
• New kernels for several problems on planar graphs
• A faster FPT algorithm for the maximum agreement forest problem

Describes a project that uses

Uses Software

• rSPR
• SPRSupertrees

This page was built for publication: A parameterized algorithm for the maximum agreement forest problem on multiple rooted multifurcating trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1671997)