Bordewich, M. and Gascuel, O. and Huber, K. T. and 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). pp. 110-117.
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.
|Full text:||(VoR) Version of Record|
Download PDF (481Kb)
|Publisher Web site:||http://dx.doi.org/10.1109/TCBB.2008.37|
|Publisher 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.|
|Date accepted:||No date available|
|Date deposited:||06 January 2010|
|Date of first online publication:||January 2009|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|