Abstract
In phylogenetics, a common strategy used to construct an evolutionary tree for a set of species X is to search in the space of all such trees for one that optimizes some given score function (such as the minimum evolution, parsimony or likelihood score). As this can be computationally intensive, it was recently proposed to restrict such searches to the set of all those trees that are compatible with some circular ordering of the set X. To inform the design of efficient algorithms to perform such searches, it is therefore of interest to find bounds for the number of trees compatible with a fixed ordering in the neighborhood of a tree that is determined by certain tree operations commonly used to search for trees: the nearest neighbor interchange (nni), the subtree prune and regraft (spr) and the tree bisection and reconnection (tbr) operations. We show that the size of such a neighborhood of a binary tree associated with the nni operation is independent of the tree’s topology, but that this is not the case for the spr and tbr operations. We also give tight upper and lower bounds for the size of the neighborhood of a binary tree for the spr and tbr operations and characterize those trees for which these bounds are attained.
Original language  English 

Pages (fromto)  4670 
Journal  Bulletin of Mathematical Biology 
Volume  77 
Issue number  1 
Early online date  5 Dec 2014 
DOIs  
Publication status  Published  Jan 2015 
Keywords
 Phylogenetic tree
 Nearest neighbor interchange
 Subtree prune and regraft
 Tree bisection and reconnection
 NeighborNet
 Circular ordering
Profiles

Vincent Moulton
 School of Computing Sciences  Professor in Computational Biology
 Norwich Epidemiology Centre  Member
 Computational Biology  Member
Person: Research Group Member, Academic, Teaching & Research

Taoyang Wu
 School of Computing Sciences  Lecturer in Computing Sciences
 Computational Biology  Member
Person: Research Group Member, Academic, Teaching & Research