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

DOI10.1007/s10878-015-9921-7zbMath1378.90085OpenAlexW798279669MaRDI QIDQ328699

Qilong Feng, Feng Shi, Jianxin Wang, Jie You

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

approximation algorithmphylogenetic treemaximum agreement forestSPR distance

Mathematics Subject Classification ID

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

Related Items (5)

A parameterized algorithm for the maximum agreement forest problem on multiple rooted multifurcating trees ⋮ 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 ⋮ An Improved Approximation Algorithm for rSPR Distance

Uses Software

• rSPR
• SPRSupertrees

Cites Work

• Unnamed Item
• Fixed-parameter and approximation algorithms for maximum agreement forests of multifurcating trees
• Approximating the maximum agreement forest on \(k\) trees
• A 3-approximation algorithm for the subtree distance between phylogenies
• The maximum agreement forest problem: Approximation algorithms and computational experiments
• Comparison of phylogenetic trees
• Ricci-Ollivier curvature of the rooted phylogenetic subtree-prune-regraft graph
• On the computational complexity of the rooted subtree prune and regraft distance
• Bounding the number of hybridisation events for a consistent evolutionary history
• A faster FPT algorithm for the maximum agreement forest problem
• Fixed-Parameter Algorithms for Maximum Agreement Forests
• Approximation Algorithms for Maximum Agreement Forest on Multiple Trees
• Approximation Algorithms for Nonbinary Agreement Forests
• Subtree transfer operations and their induced metrics on evolutionary trees
• On the complexity of comparing evolutionary trees

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