We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
On the Computational Complexity of the Rooted Subtree Prune and Regraft Distance.
- Authors
Bordewich, Magnus; Semple, Charles
- Abstract
The graph-theoretic operation of rooted subtree prune and regraft is increasingly being used as a tool for understanding and modelling reticulation events in evolutionary biology. In this paper, we show that computing the rooted subtree prune and regraft distance between two rooted binary phylogenetic trees on the same label set is NP-hard. This resolves a longstanding open problem. Furthermore, we show that this distance is fixed parameter tractable when parameterised by the distance between the two trees.
- Subjects
COMPUTATIONAL complexity; GRAPHIC methods; BIOLOGY; PARAMETER estimation; PRUNE
- Publication
Annals of Combinatorics, 2005, Vol 8, Issue 4, p409
- ISSN
0218-0006
- Publication type
Article
- DOI
10.1007/s00026-004-0229-z