Subtree Transfer Operations and Their Induced Metrics
on Evolutionary Trees

Benjamin L. Allen, and Mike Steel^{1}

Biomathematics Research Centre,
University of Canterbury, Private Bag 4800, Christchurch, New Zealand
^{1}m.steel@math.canterbury.ac.nz

Annals of Combinatorics 5(1) p.1-15 March, 2001

Abstract:

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*

References:

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.