A stepwise algorithm for finding minimum evolution trees

A stepwise algorithm for reconstructing minimum evolution (ME) trees fromevolutionary distance data is proposed. In each step, a taxon thatpotentially has a neighbor (another taxon connected to it with a singleinterior node) is first chosen and then its true neighbor searchediteratively. For m taxa, at most (m-1)!/2 trees are examined and the treewith the minimum sum of branch lengths (S) is chosen as the final tree.This algorithm provides simple strategies for restricting the tree spacesearched and allows us to implement efficient ways of dynamically computingthe ordinary least squares estimates of S for the topologies examined.Using computer simulation, we found that the efficiency of the ME method inrecovering the correct tree is similar to that of the neighbor-joiningmethod (Saitou and Nei 1987). A more exhaustive search is unlikely toimprove the efficiency of the ME method in finding the correct tree becausethe correct tree is almost always included in the tree space searched withthis stepwise algorithm. The new algorithm finds trees for which S valuesmay not be significantly different from that of the ME tree if the correcttree contains very small interior branches or if the pairwise distanceestimates have large sampling errors. These topologies form a set ofplausible alternatives to the ME tree and can be compared with each otherusing statistical tests based on the minimum evolution principle. The newalgorithm makes it possible to use the ME method for large data sets.