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

Bordewich, M.; Gascuel, O.; Huber, K.T.; Moulton, V.

doi:10.1109/tcbb.2008.37

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

Bordewich, M.; Gascuel, O.; Huber, K.T.; Moulton, V.

Authors

Professor Magnus Bordewich m.j.r.bordewich@durham.ac.uk
Professor

O. Gascuel

K.T. Huber

V. Moulton

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 balanced minimum evolution (BME) principle, which computer studies have demonstrated to have high accuracy. FastME includes two variants: balanced subtree prune and regraft (BSPR) and 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.

Citation

Bordewich, M., Gascuel, O., Huber, K., & Moulton, V. (2009). Consistency of Topological Moves Based on the Balanced Minimum Evolution Principle of Phylogenetic Inference. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 6(1), 110-117. https://doi.org/10.1109/tcbb.2008.37

Journal Article Type	Article
Publication Date	Jan 1, 2009
Deposit Date	Dec 21, 2009
Publicly Available Date	Jan 6, 2010
Journal	IEEE/ACM Transactions on Computational Biology and Bioinformatics
Print ISSN	1545-5963
Electronic ISSN	1557-9964
Publisher	Association for Computing Machinery (ACM)
Peer Reviewed	Peer Reviewed
Volume	6
Issue	1
Pages	110-117
DOI	https://doi.org/10.1109/tcbb.2008.37
Public URL	https://durham-repository.worktribe.com/output/1546528

Files

Published Journal Article (492 Kb)
PDF

Copyright Statement
©2009 IEEE. This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.