A 3-approximation algorithm for the subtree distance between phylogenies

Bordewich, M.; McCartin, C.; Semple, C.

Abstract

In this paper, we give a (polynomial-time) 3-approximation algorithm for the rooted subtree prune and regraft distance between two phylogenetic trees. This problem is known to be NP-complete and the best previously known approximation algorithm is a 5-approximation. We also give a faster fixed-parameter algorithm for the rooted subtree prune and regraft distance than was previously known.

Citation

Bordewich, M., McCartin, C., & Semple, C. (2008). A 3-approximation algorithm for the subtree distance between phylogenies. Journal of discrete algorithms, 6(3), 458-471. https://doi.org/10.1016/j.jda.2007.10.002

• Journal Article Type: Article
• Publication Date: Sep 1, 2008
• Deposit Date: Dec 21, 2009
• Journal: Journal of Discrete Algorithms
• Print ISSN: 1570-8667
• Electronic ISSN: 1570-8675
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 6
• Issue: 3
• Pages: 458-471
• DOI: https://doi.org/10.1016/j.jda.2007.10.002
• Keywords: Rooted subtree prune and regraft, Agreement forest.
• Public URL: https://durham-repository.worktribe.com/output/1522652
• Publisher URL: http://www.sciencedirect.com/science/article/B758J-4RHFVH5-1/2/6d4695ca376998bd5098624f1a4250d9