On the Computational Complexity of the Rooted Subtree
Prune and Regraft Distance

Magnus Bordewich^{1,2} and Charles Semple^{2}

magnusb@comp.leeds.ac.uk

c.semple@math.canterbury.ac.nz

Annals of Combinatorics 8 (4) p.409-423 December, 2006

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.

References:

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.