<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume8 Issue4" %>
On the Computational Complexity of the Rooted Subtree Prune and Regraft Distance
Magnus Bordewich1,2 and Charles Semple2
1School of Computing, University of Leeds, Leeds LS2 9JT, United Kingdom
2Biomathematics Research Centre, Department of Mathematics and Statistics, University of Canterbury, Christchurch, New Zealand
Annals of Combinatorics 8 (4) p.409-423 December, 2006
AMS Subject Classification: 05C05, 92D15
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.
Keywords: rooted phylogenetic tree, rooted subtree prune and regraft


1. B.L. Allen and M. Steel, Subtree transfer operations and their induced metrics on evolutionary trees, Ann. Comb. 5 (2001) 1--13.

2. M. Baroni, C. Semple, and M. Steel, A framework for representing reticulate evolution, Ann. Comb., in press.

3. M. Baroni and M. Steel, Private communication.

4. B. DasGupta, X. He, T. Jiang, M. Li, J. Tromp, and L. Zhang, On distances between phylogenetic trees, In: Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1997, pp. 427--436.

5. R. Downey and M. Fellows, Parameterized Complexity (Monographs in Computer Science), Springer Verlag, 1998.

6. M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NPCompleteness, Freeman, San Francisco, 1979.

7. J. Hein, Reconstructing evolution of sequences subject to recombination using parsimony, Math. Biosci. 98 (1990) 185--200.

8. J. Hein, T. Jing, L.Wang, and K. Zhang, On the complexity of comparing evolutionary trees, Discrete Appl. Math. 71 (1996) 153--169.

9. M. Li, J. Tromp, and L. Zhang, On the nearest neighbour interchange distance between evolutionary trees, J. Theoret. Biol. 182 (1996) 463--467.

10. W. Maddison, Gene trees in species trees, Syst. Biol. 46 (1997) 523--536.

11. G.W. Moore, M. Goodman, and J. Barnabas, An iterative approach from the standpoint of the additive hypothesis to the dendrogram problem posted by molecular data sets, J. Theoret. Biol. 38 (1973) 423--457.

12. L. Nakhleh, T. Warnow, and C.R. Linder, Reconstructing reticulate evolution in species - theory and practice, In: Proceedings of the 8th Annual International Conference on Research in Computational Molecular Biology (RECOMB), 2004, pp. 337--46.

13. D. Robinson, Comparison of labelled trees with valency three, J. Combin. Theory 11 (1971) 105--119.

14. C. Semple and M. Steel, Phylogenetics, Oxford University Press, 2003.

15. Y. Song and J. Hein, Parsimonious reconstruction of sequence evolution and haplotyde blocks: finding the minimum number of recombination events, In: Algorithms in Bioinformatics (WABI), G. Benson and R. Page, Eds., Lecture Notes in Bioinformatics, vol. 2812, 2003, pp. 287--302.