<%@ 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
linz@informatik.uni-tuebingen.de
2Biomathematics Research Centre, Department of Mathematics and Statistics, University of Canterbury, Private Bag 4800, Christchurch 8140, New Zealand
c.semple@math.canterbury.ac.nz
Annals of Combinatorics 15 (3) pp.465-484 July, 2011
AMS Subject Classification: 05C05; 92D15
Abstract:
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

References:

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)