Subtree Transfer Operations and their Application to Evolutionary Biology
by
Benjamin Allen
University of Canterbury
Coauthors: Mike Steel

Unrooted binary trees are often used to describe evolutionary events. Extant species make up the leaves of such trees, while the internal vertices correspond to extinct species ancestral to the extant species. Once biological data is collected, for example DNA sequences, various techniques exist for determining the topology (shape) of corresponding evolutionary trees. Parsimony and Neighbour-Joining are the two common techniques. Techniques can produce several trees, and different techniques can produce different sets of trees. Questions arise, such as, how far are such trees from each other with respect to a given tree metric? How far are such trees from the true tree? Tree metrics can be induced by tree operations, where a series of such operations can be carried out to transform an tree to another. This talk will investigate three such operations on unrooted binary trees, nearest neighbour interchanges, subtree prune and regrafts and tree bisection and reconnections. The subtree prune and regraft operation is of particular interest as it can be used to model biological processes such as horizontal gene transfer and recombination, as well as in optimiztion heuristics, when searching for good trees. We will present new theorems that count the number of unrooted binary trees one subtree prune and regraft from any given unrooted binary tree, as well as new upper and lower bounds for the diameter of the baumraum, or tree space, with respect to the subtree prune and regraft operation. We shall also show that the problem of computing the minimum number of subtree prune and regrafts require to transform one tree to another can be kernalized to a problem whose size is a function 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.

Date received: June 11, 1998