Name
Title | ||
|---|---|---|
Consistency of topological moves based on the balanced minimum evolution principle of phylogenetic inference. |
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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1109/TCBB.2008.37 | IEEE/ACM Trans. Comput. Biology Bioinform. |
Keywords | Field | DocType |
biology computing,optimisation,topology,trees (mathematics),FastME,balanced minimum evolution principle,balanced nearest neighbor interchange,balanced subtree prune and regraft,optimality criterion,phylogenetic algorithms,phylogenetic inference,phylogenetic tree,topological rearrangements,trees,BNNI algorithm,BSPR algorithm,Nearest Neighbor Interchange (NNI),Robinson Foulds distance,balanced minimum evolution principle (BME),consistency,phylogenetic tree,quartet-distance,safety radius,subtree prune and regraft (SPR),topological move,tree-length | Phylogenetic inference,Phylogenetic tree,Optimality criterion,Computer errors,Artificial intelligence,k-nearest neighbors algorithm,Topology,Combinatorics,Tree (data structure),Greedy algorithm,Distance matrix,Bioinformatics,Mathematics,Machine learning | Journal |
Volume | Issue | ISSN |
6 | 1 | 1557-9964 |
Citations | PageRank | References |
5 | 0.56 | 9 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Magnus Bordewich | 1 | 183 | 18.62 |
| Olivier Gascuel | 2 | 433 | 76.01 |
| Katharina T. Huber | 3 | 139 | 24.31 |
| Vincent Moulton | 4 | 39 | 7.46 |