Improved approximation algorithm for maximum agreement forest of two rooted binary phylogenetic trees

DOI10.1007/S10878-015-9921-7MaRDI QIDQ328699zbMATH OpenOpenAlexFDO

Authors Feng Shi, Qilong Feng, Jie You, Jianxin Wang

Publication date 20 October 2016

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-015-9921-7

zbMATH Keywords

phylogenetic treeapproximation algorithmmaximum agreement forestSPR distance

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Problems related to evolution (92D15) Approximation algorithms (68W25)

Recommendations

• Improved approximation algorithm for maximum agreement forest of two trees
• Approximating maximum agreement forest on multiple binary trees
• Approximation algorithms for maximum agreement forest on multiple trees
• Approximation algorithms for nonbinary agreement forests
• A faster FPT algorithm for the maximum agreement forest problem

Cites work

• scientific article; zbMATH DE number 1833410 (Why is no real title available?)
• A 3-approximation algorithm for the subtree distance between phylogenies
• A faster FPT algorithm for the maximum agreement forest problem
• Approximating the maximum agreement forest on \(k\) trees
• Approximation algorithms for maximum agreement forest on multiple trees
• Approximation algorithms for nonbinary agreement forests
• Bounding the number of hybridisation events for a consistent evolutionary history
• Comparison of phylogenetic trees
• Fixed-parameter algorithms for maximum agreement forests
• Fixed-parameter and approximation algorithms for maximum agreement forests of multifurcating trees
• On the complexity of comparing evolutionary trees
• On the computational complexity of the rooted subtree prune and regraft distance
• Ricci-Ollivier curvature of the rooted phylogenetic subtree-prune-regraft graph
• Subtree transfer operations and their induced metrics on evolutionary trees
• The maximum agreement forest problem: Approximation algorithms and computational experiments

Cited in

(12)

• An improved approximation algorithm for rSPR distance
• A duality based 2-approximation algorithm for maximum agreement forest
• Approximating the maximum agreement forest on \(k\) trees
• Approximation algorithms for nonbinary agreement forests
• Gene tree reconciliation including transfers with replacement is NP-hard and FPT
• A duality based 2-approximation algorithm for maximum agreement forest
• Approximating maximum agreement forest on multiple binary trees
• A parameterized algorithm for the maximum agreement forest problem on multiple rooted multifurcating trees
• Approximation algorithms for maximum agreement forest on multiple trees
• Improved approximation algorithm for maximum agreement forest of two trees
• scientific article; zbMATH DE number 1833410 (Why is no real title available?)
• The maximum agreement forest problem: Approximation algorithms and computational experiments

Describes a project that uses

Uses Software

• rSPR
• SPRSupertrees

This page was built for publication: Improved approximation algorithm for maximum agreement forest of two rooted binary phylogenetic trees

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