Molecular Biology and Evolution, Vol 13, 584-593, Copyright © 1996 by Society for Molecular Biology and Evolution
S Kumar
A stepwise algorithm for reconstructing minimum evolution (ME) trees from
evolutionary distance data is proposed. In each step, a taxon that
potentially has a neighbor (another taxon connected to it with a single
interior node) is first chosen and then its true neighbor searched
iteratively. For m taxa, at most (m-1)!/2 trees are examined and the tree
with the minimum sum of branch lengths (S) is chosen as the final tree.
This algorithm provides simple strategies for restricting the tree space
searched and allows us to implement efficient ways of dynamically computing
the ordinary least squares estimates of S for the topologies examined.
Using computer simulation, we found that the efficiency of the ME method in
recovering the correct tree is similar to that of the neighbor-joining
method (Saitou and Nei 1987). A more exhaustive search is unlikely to
improve the efficiency of the ME method in finding the correct tree because
the correct tree is almost always included in the tree space searched with
this stepwise algorithm. The new algorithm finds trees for which S values
may not be significantly different from that of the ME tree if the correct
tree contains very small interior branches or if the pairwise distance
estimates have large sampling errors. These topologies form a set of
plausible alternatives to the ME tree and can be compared with each other
using statistical tests based on the minimum evolution principle. The new
algorithm makes it possible to use the ME method for large data sets.
ORIGINAL ARTICLE
A stepwise algorithm for finding minimum evolution trees
Department of Biology, Pennsylvania State University, USA. imeg@psuvm.psu.edu
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  O. Gascuel and M. Steel Neighbor-Joining Revealed Mol. Biol. Evol., November 1, 2006; 23(11): 1997 - 2000. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 P. Larranaga, B. Calvo, R. Santana, C. Bielza, J. Galdiano, I. Inza, J. A. Lozano, R. Armananzas, G. Santafe, A. Perez, et al. Machine learning in bioinformatics Brief Bioinform, March 1, 2006; 7(1): 86 - 112. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 K. Tamura, M. Nei, and S. Kumar Prospects for inferring very large phylogenies by using the neighbor-joining method PNAS, July 27, 2004; 101(30): 11030 - 11035. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
R. Desper and O. Gascuel Theoretical Foundation of the Balanced Minimum Evolution Method of Phylogenetic Inference and Its Relationship to Weighted Least-Squares Tree Fitting Mol. Biol. Evol., March 1, 2004; 21(3): 587 - 598. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
T. Gubitz, A. Caldwell, and A. Hudson Rapid Molecular Evolution of CYCLOIDEA-like Genes in Antirrhinum and Its Relatives Mol. Biol. Evol., September 1, 2003; 20(9): 1537 - 1544. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
V. Ranwez and O. Gascuel Improvement of Distance-Based Phylogenetic Methods by a Local Maximum Likelihood Approach Using Triplets Mol. Biol. Evol., November 1, 2002; 19(11): 1952 - 1963. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
S. Ota and W.-H. Li NJML+: An Extension of the NJML Method to Handle Protein Sequence Data and Computer Software Implementation Mol. Biol. Evol., November 1, 2001; 18(11): 1983 - 1992. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
M. S. Rosenberg and S. Kumar Incomplete taxon sampling is not a problem for phylogenetic inference PNAS, August 23, 2001; (2001) 191248498. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
K. Takahashi and M. Nei Efficiencies of Fast Algorithms of Phylogenetic Inference Under the Criteria of Maximum Parsimony, Minimum Evolution, and Maximum Likelihood When a Large Number of Sequences Are Used Mol. Biol. Evol., August 1, 2000; 17(8): 1251 - 1258. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
O. Gascuel On the Optimization Principle in Phylogenetic Analysis and the Minimum-Evolution Criterion Mol. Biol. Evol., March 1, 2000; 17(3): 401 - 405. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
M. Nei, S. Kumar, and K. Takahashi The optimization principle in phylogenetic analysis tends to give incorrect topologies when the number of nucleotides or amino acids used is small PNAS, October 13, 1998; 95(21): 12390 - 12397. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
M. S. Rosenberg and S. Kumar Incomplete taxon sampling is not a problem for phylogenetic inference PNAS, September 11, 2001; 98(19): 10751 - 10756. [Abstract] [Full Text] [PDF]
|
|