Skip to Main content Skip to Navigation
Journal articles

Consistency of Topological Moves Based on the Balanced Minimum Evolution Principle of Phylogenetic Inference

Magnus Bordewich 1 Olivier Gascuel 2, * Katharina Huber 3 Vincent Moulton 3
* Corresponding author
2 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Many phylogenetic algorithms search the space of possible trees using topological rearrangements and some optimality criterion. FastME is such an approach that uses the {em balanced minimum evolution (BME)} principle, which computer studies have demonstrated to have high accuracy. FastME includes two variants: {em balanced subtree prune and regraft (BSPR)} and {em balanced nearest neighbor interchange (BNNI)}. These algorithms take as input a distance matrix and a putative phylogenetic tree. The tree is modified using SPR or NNI operations, respectively, to reduce the BME length relative to the distance matrix, until a tree with (locally) shortest BME length is found. Following computer simulations, it has been conjectured that BSPR and BNNI are consistent, i.e. for an input distance that is a tree-metric, they converge to the corresponding tree. We prove that the BSPR algorithm is consistent. Moreover, even if the input contains small errors relative to a tree-metric, we show that the BSPR algorithm still returns the corresponding tree. Whether BNNI is consistent remains open.
Complete list of metadata

Cited literature [27 references]  Display  Hide  Download
Contributor : Olivier Gascuel <>
Submitted on : Wednesday, September 24, 2008 - 10:56:05 AM
Last modification on : Thursday, July 19, 2018 - 4:58:09 PM
Long-term archiving on: : Thursday, June 3, 2010 - 9:58:28 PM


Files produced by the author(s)




Magnus Bordewich, Olivier Gascuel, Katharina Huber, Vincent Moulton. Consistency of Topological Moves Based on the Balanced Minimum Evolution Principle of Phylogenetic Inference. IEEE/ACM Transactions on Computational Biology and Bioinformatics, Institute of Electrical and Electronics Engineers, 2009, 6 (1), pp.110-117. ⟨10.1109/TCBB.2008.37⟩. ⟨lirmm-00324146⟩



Record views


Files downloads