A duality based 2-approximation algorithm for maximum agreement forest

DOI10.4230/LIPICS.ICALP.2016.70MaRDI QIDQ4598209zbMATH OpenOpenAlexFDO

Authors Frans Schalekamp, Anke van Zuylen, Suzanne Van der Ster

Publication date 19 December 2017

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

zbMATH Keywords

computational biologymaximum agreement forestphylogenetic treeSPR distancesubtree prune-and-regraft distance

Mathematics Subject Classification ID

Approximation algorithms (68W25) Approximation methods and heuristics in mathematical programming (90C59) Problems related to evolution (92D15)

Abstract: We give a 2-approximation algorithm for the Maximum Agreement Forest problem on two rooted binary trees. This NP-hard problem has been studied extensively in the past two decades, since it can be used to compute the Subtree Prune-and-Regraft (SPR) distance between two phylogenetic trees. Our result improves on the very recent 2.5-approximation algorithm due to Shi, Feng, You and Wang (2015). Our algorithm is the first approximation algorithm for this problem that uses LP duality in its analysis.

Recommendations

• A duality based 2-approximation algorithm for maximum agreement forest
• scientific article; zbMATH DE number 1833410
• Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees
• Improved approximation algorithm for maximum agreement forest of two trees
• Improved approximation algorithm for maximum agreement forest of two rooted binary phylogenetic trees

Cited in

(4)

• A parameterized algorithm for the maximum agreement forest problem on multiple rooted multifurcating trees
• A duality based 2-approximation algorithm for maximum agreement forest
• scientific article; zbMATH DE number 1833410 (Why is no real title available?)
• Better practical algorithms for rSPR distance and hybridization number

This page was built for publication: A duality based 2-approximation algorithm for maximum agreement forest

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