Professor Magnus Bordewich m.j.r.bordewich@durham.ac.uk
Professor
A 3-approximation algorithm for the subtree distance between phylogenies
Bordewich, M.; McCartin, C.; Semple, C.
Authors
C. McCartin
C. Semple
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 |
You might also like
Quantifying the difference between phylogenetic diversity and diversity indices
(2024)
Journal Article
Evaluating Gaussian Grasp Maps for Generative Grasping Models
(2022)
Presentation / Conference Contribution
On the Complexity of Optimising Variants of Phylogenetic Diversity on Phylogenetic Networks
(2022)
Journal Article
On the Maximum Agreement Subtree Conjecture for Balanced Trees
(2022)
Journal Article
Autoencoders Without Reconstruction for Textural Anomaly Detection
(2021)
Presentation / Conference Contribution
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search