skip to content

Consistency of phylogenetic tree search algorithms based on the balanced minimum evolution principle

Friday 7th September 2007 - 10:00 to 10:20
INI Seminar Room 1

In phylogenetics, it is common practise to infer evolutionary or phylogenetic trees by searching tree-space, that is, searching through the collection of all possible phylogenetic trees on a given set of species or taxa using topological rearrangements and some optimality criterion. Recently, such an approach called the balanced nearest neighbor interchange (BNNI) algorithm was introduced, which is based on the balanced minimum evolution (BME) principle. This algorithm takes as input a distance matrix and a putative phylogenetic tree on a given set of species. It modifies this tree using nearest neighbor interchange (NNI) operations in such a way that the total BME length of the resulting tree decreases relative to the distance matrix. This process is repeated until a tree with (locally) shortest BME length is found. Guided by numerous computer simulations it has been conjectured that the BNNI algorithm is consistent, that is, when it is applied to an input distance that is a tree-metric, then it will always converge to the (unique) tree corresponding to that metric. To date this conjecture remains open. Here, however, we prove that a related algorithm | which we call the BSPR algorithm for short | that results from replacing NNI operations by the more general subtree prune and regraft (SPR) operations in the BNNI algorithm is, in fact, consistent. Moreover, we show that even if the input distance matrix contains (small) errors relative to the tree-metric, then the BSPR algorithm will still return the corresponding tree.

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons