<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 5 Issue 1" %>
Subtree Transfer Operations and Their Induced Metrics on Evolutionary Trees
Benjamin L. Allen, and Mike Steel1
Biomathematics Research Centre, University of Canterbury, Private Bag 4800, Christchurch, New Zealand
Annals of Combinatorics 5(1) p.1-15 March, 2001
AMS Subject Classification: 05C05, 92D15, 68R10, 68Q25
Leaf-labelled trees are widely used to describe evolutionary relationships, particularly in biology. In this setting, extant species label the leaves of the tree, while the internal vertices correspond to ancestral species. Various techniques exist for reconstructing these evolutionary trees from data, and an important problem is to determine how "far apart" two such reconstructed trees are from each other, or indeed from the  true historical tree. To investigate this question requires tree metrics, and these can be induced by operations that rearrange trees locally. Here we investigate three such operations: nearest neighbour interchange (NNI), subtree prune and regraft (SPR), and tree bisection and reconnection (TBR). The SPR operation is of particular interest as it can be used to model biological processes such as horizontal gene transfer and recombination. We count the number of unrooted binary trees one SPR from any given unrooted binary tree, as well as providing new upper and lower bounds for the diameter of the adjacency graph of trees under SPR and TBR. We also show that the problem of computing the minimum number of TBR operations required to transform one tree to another can be reduced to a problem whose size is a function just of the distance between the trees (and not of the size of the two trees), and thereby establish that the problem is fixed-parameter tractable
Keywords: trees, metrics, subtree transfer, fixed parameter tractability


1.  B. Allen, Subtree transfer operations and their induced metrics on evolutionary trees, MSc Thesis, University of Canterbury, Christchurch, New Zealand, 1998.

2.  R. Downey and M.R. Fellows, Parameterized Complexity, Springer-Verlag, New York, 1999.

3.  P. Gilson and G. McFadden, Something borrowed, something green: lateral transfer of chloroplasts by secondary endosymbiosis, Trends Ecol. Evol. 10 (1995) 12每17.

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

5.  J. Hein, A heuristic method to reconstruct the history of sequences subject to recombination, J. Mol. Evol. 36 (1993) 369每405.

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

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

8.  W.H. Li and D. Graur, Fundamentals of Molecular Evolution, Sinauer Associates, Inc., 1991.

9.  D.R. Maddison, The discovery and importance of multiple islands of most-parsimonious trees, Syst. Zool. 43 (3) (1991) 315每328.

10.  R.D.M. Page, On islands of trees and the efficacy of different methods of branch swapping in finding most-parsimonious trees, Syst. Biol. 42 (2) (1993) 200每210.

11.  D.F. Robinson, Comparison of labeled trees with valency three, J. Combin. Theory 11 (1971) 105每119.

12.  D.L. Swofford, G.J. Olsen, P.J. Waddell, and D.M. Hillis, Phylogenetic Inference in Molecular Systematics, Sinauer Associates, second Edition, 1996.