Skip to main content

Research Repository

Advanced Search

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

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

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


Authors

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
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

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.





You might also like



Downloadable Citations