A stepwise algorithm for finding minimum evolution trees |
| |
Authors: | Kumar S |
| |
Institution: | Department of Biology, Pennsylvania State University, USA. imeg@psuvm.psu.edu |
| |
Abstract: | 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.
|
| |
Keywords: | |
本文献已被 Oxford 等数据库收录! |
|