European collaboration explores neighbourhoods of trees in circular ordering

Dr Sarah Bastkowski, Biomathematician at The Genome Analysis Centre (TGAC) leads a study examining the restriction of tree space, providing new insights into the design of effective algorithms for tree construction.

Phylogenetic trees are graphical representations of evolutionary relationships between species. Through visualising these relationships, these trees further our understanding of the process of evolution. The number of possible trees grows rapidly with the number of species considered and exhaustive searches for optimal trees within the full tree space become infeasible with our current computer technology.

To make a search feasible the search space can be restricted, for example by fixing a circular ordering of the leaves of a phylogeny. There is then a number of trees that will be compatible with this circular ordering. A European collaboration between scientists from TGAC, the University of East Anglia and the University of Greifswald, further explored this restricted tree space.

One way of generally searching tree space is by starting with a tree and applying tree modification operations: tree bisection and reconnection (TBR) (1) , subtree prune and re-graft (SPR) (2) and nearest neighbour interchange (NNI) (3).

These are commonly implemented in various tree reconstruction algorithms. The set of trees that can be reached by applying one of each of these operations is called the ‘neighbourhood’ of the tree for that operation. The size of these neighbourhoods is related to the efficiency of local searches. To characterise and explore the tree operations further, in this study, the TBR, SPR and NNI neighbourhoods for a fixed circular ordering were investigated.

It was found that, when the SPR and TBR operations are applied, the size of a given circular neighbourhood will depend on the starting tree’s topology. The study also identified upper and lower bounds of the size of the tree neighbourhood when the SPR and TBR operations are applied as well as characterised the starting trees that lead to achieving these minimum and maximum neighbourhoods.

Dr Sarah Bastkowski, co-author and Biomathematician in the Regulatory & Environmental Genomics group at TGAC, commented: “These insights advance our theoretical knowledge of this kind of restricted tree space and tree modification operation and could help to design algorithms capable of performing efficient searches for optimal phylogenetic trees.“

This paper titled, “Neighbourhoods of trees in circular orderings” is published in the Bulletin of Mathematical Biology.

Image: An unrooted phylogenetic tree on six species (this structure is called a caterpillar tree)


(1) Tree bisection and reconnection (TBR) – an edge within the tree is deleted, which yields two subtrees. These are reconnected through the insertion of a new edge between edges in the two subtrees

(2) Subtree prune and regraft (SPR) – is a TBR operation, where the choice of the two edges for reconnection is restricted to the one that was originally deleted and any other one in the other subtree

(3) Nearest neighbour interchange (NNI) – is a SPR operation, with an even more restricted choice for the reconnection, namly the two edges have exactly one edge between them

*******

For more information, please contact:

Hayley London
Marketing & Communications Officer, The Genome Analysis Centre (TGAC)
T: +44 (0)1603 450107
E: [email protected]

_________________________________________