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

DOI10.1016/J.JCSS.2018.03.002zbMATH Open1400.92379arXiv1608.02709OpenAlexW2963660191WikidataQ129925128 ScholiaQ129925128MaRDI QIDQ1671997FDOQ1671997

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)

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.

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

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

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)

Cites Work

• Fixed-parameter algorithms for maximum agreement forests
• Comparison of phylogenetic trees
• On the computational complexity of the rooted subtree prune and regraft distance
• 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
• Fixed-parameter and approximation algorithms for maximum agreement forests of multifurcating trees
• Title not available (Why is that?)
• A quadratic kernel for computing the hybridization number of multiple trees
• Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees
• A faster FPT algorithm for the maximum agreement forest problem
• Improved approximation algorithm for maximum agreement forest of two rooted binary phylogenetic trees
• Title not available (Why is that?)
• Approximating the maximum agreement forest on \(k\) trees
• Vertex cover: Further observations and further improvements
• Faster exact computation of rSPR distance
• Algorithms for parameterized maximum agreement forest problem on multiple trees
• An improved approximation algorithm for rSPR distance
• A duality based 2-approximation algorithm for maximum agreement forest

Cited In (13)

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

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)