Consistency of phylogenetic tree search algorithms based on the balanced minimum evolution principle
Seminar Room 1, Newton Institute
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.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.