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
* Auteur correspondant
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.
Type de document :
Article dans une revue
IEEE/ACM Transactions on Computational Biology and Bioinformatics, Institute of Electrical and Electronics Engineers, 2009, 6 (1), pp.110-117. 〈www.lirmm.fr/mab〉. 〈10.1109/TCBB.2008.37〉
Liste complète des métadonnées

Littérature citée [27 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00324146
Contributeur : Olivier Gascuel <>
Soumis le : mercredi 24 septembre 2008 - 10:56:05
Dernière modification le : jeudi 11 janvier 2018 - 06:26:12
Document(s) archivé(s) le : jeudi 3 juin 2010 - 21:58:28

Fichier

BordewichGascuelHuberMoulton_I...
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

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. 〈www.lirmm.fr/mab〉. 〈10.1109/TCBB.2008.37〉. 〈lirmm-00324146〉

Partager

Métriques

Consultations de la notice

172

Téléchargements de fichiers

101