<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
A Cluster Reduction for Computing the Subtree Distance Between Phylogenies
Simone Linz1 and Charles Semple2
1Center for Bioinformatics (ZBIT), University of Tübingen, Sand 14, 72076 Tübingen, Germany
2Biomathematics Research Centre, Department of Mathematics and Statistics, University of Canterbury, Private Bag 4800, Christchurch 8140, New Zealand
Annals of Combinatorics 15 (3) pp.465-484 July, 2011
AMS Subject Classification: 05C05; 92D15
Calculating the rooted subtree prune and regraft (rSPR) distance between two rooted binary phylogenetic trees is a frequently applied process in various areas of molecular evolution. However, computing this distance is an NP-hard problem and practical algorithms for computing it exactly are rare. In this paper, a divide-and-conquer approach to calculating the rSPR distance is established. This approach breaks the problem instance into a number of smaller and more tractable subproblems. Two reduction rules which were previously used to show that computing the rSPR distance is fixed-parameter tractable can easily be used to complement this new theoretical result, and so a significant positive impact on the running time of calculating this distance in practice is likely.
Keywords: phylogenetic tree, subtree prune and regraft, cluster reduction


1. Allen, B.L., Steel,M.: Subtree transfer operations and their induced metrics on evolutionary trees. Ann. Combin. 5(1), 1–15 (2001)

2. Ávila, L.F., García, G., Serna, M., Thilikos, D.M.: A list of parameterized problems in bioinformatics. Technical report LSI-06-24-R. Technical University of Catalonia, Catalonia (2006)

3. Baroni, M., Semple, C., Steel, M.: A framework for representing reticulate evolution. Ann. Combin. 8(4), 391–408 (2004)

4. Baroni, M., Grünewald, S., Moulton, V., Semple, C.: Bounding the number of hybridization events for a consistent evolutionary history. J. Math. Biol. 51(2), 171–182 (2005)

5. Baroni, M., Semple, C., Steel, M.: Hybrids in real time. Syst. Biol. 55(1), 46–56 (2006)

6. Beiko, R., Hamilton, N.: Phylogenetic identification of lateral genetic transfer events. BMC Evol. Biol. 6, #15 (2006)

7. Bordewich, M., Semple, C.: On the computational complexity of the rooted subtree prune and regraft distance. Ann. Combin. 8(4), 409–423 (2004)

8. Bordewich, M., Linz, S., John, K.St., Semple, C.: A reduction algorithm for computing the hybridization number of two trees. Evol. Bioinform. Online 3, 86–98 (2007)

9. Downey, R., Fellows,M.: Parameterized Complexity (Monographs in Computer Science), Springer Verlag, New York (1999)

10. Gramm, J., Nickelsen, A., Tantau, T.: Fixed-parameter algorithms in phylogenetics. Comput. J. 51(1), 79–101 (2008)

11. Hillis, D.M., Moritz, C., Mable, B.K.,: Molecular Systematics. Sinauer Associates, Massachusetts (1996)

12. Maddison, W.: Gene trees in species trees. Syst. Biol. 46(3), 523–536 (1997)

13. Nakhleh, L.,Warnow, T., Linder, C.R., John, K.St.: Reconstructing reticulate evolution in species —theory and practice. J. Comput. Biol. 12(6), 796–811 (2005)]

14. Semple, C., Steel, M.: Phylogenetics. Oxford University Press, Oxford (2003)

15. Song, Y., Hein, J.: Parsimonious reconstruction of sequence evolution and haplotype blocks: finding the minimum number of recombination events. In: Algorithms in Bioinformatics, Lecture Notes in Bioinformatics, Vol. 2812, pp. 287–302. Third International Workshop, Budapest (2003)