Approximation algorithms for nonbinary agreement forests

DOI10.1137/120903567zbMATH Open1311.68193arXiv1210.3211OpenAlexW1634898999MaRDI QIDQ4979822FDOQ4979822

Authors: Leo Van Iersel, Steven Kelk, Nela Lekić, L. Stougie 

Publication date: 19 June 2014

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: Given two rooted phylogenetic trees on the same set of taxa X, the Maximum Agreement Forest problem (MAF) asks to find a forest that is, in a certain sense, common to both trees and has a minimum number of components. The Maximum Acyclic Agreement Forest problem (MAAF) has the additional restriction that the components of the forest cannot have conflicting ancestral relations in the input trees. There has been considerable interest in the special cases of these problems in which the input trees are required to be binary. However, in practice, phylogenetic trees are rarely binary, due to uncertainty about the precise order of speciation events. Here, we show that the general, nonbinary version of MAF has a polynomial-time 4-approximation and a fixed-parameter tractable (exact) algorithm that runs in O(4^k poly(n)) time, where n = |X| and k is the number of components of the agreement forest minus one. Moreover, we show that a c-approximation algorithm for nonbinary MAF and a d-approximation algorithm for the classical problem Directed Feedback Vertex Set (DFVS) can be combined to yield a d(c+3)-approximation for nonbinary MAAF. The algorithms for MAF have been implemented and made publicly available.

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

Recommendations

• Approximating maximum agreement forest on multiple binary trees
• Improved approximation algorithm for maximum agreement forest of two rooted binary phylogenetic trees
• Approximation algorithms for maximum agreement forest on multiple trees
• Improved approximation algorithm for maximum agreement forest of two trees
• Parameterized and approximation algorithms for the MAF problem in multifurcating trees

zbMATH Keywords

phylogenetic treeapproximation algorithmfixed-parameter tractabilityphylogenetic networkagreement forests

Mathematics Subject Classification ID

Problems related to evolution (92D15) Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Cited In (10)

• On the maximum parsimony distance between phylogenetic trees
• Fixed-parameter and approximation algorithms for maximum agreement forests of multifurcating trees
• Computing Maximum Agreement Forests without Cluster Partitioning is Folly
• Kernelizations for the hybridization number problem on multiple nonbinary trees
• Algorithms and Data Structures
• Hybridization number on three rooted binary trees is EPT
• 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
• LSH Forest: Practical Algorithms Made Theoretical
• A duality based 2-approximation algorithm for maximum agreement forest

This page was built for publication: Approximation algorithms for nonbinary agreement forests

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