A rapid heuristic algorithm for finding minimum evolution trees

The minimum sum of branch lengths (S), or the minimum evolution (ME) princi ple, has been shown to be a good optimization criterion in phylogenetic inf erence, Unfortunately, the number of topologies to be analyzed is computati onally prohibitive when a large number of taxa are involved. Therefore, sim plified, heuristic methods, such as the neighbor-joining (NJ) method, are u sually employed instead, The NJ method analyzes only a small number of tree s (compared with the size of the entire search space); so, the tree obtaine d may not be the ME tree (for which the S value is minimum over the entire search space), Different compromises between very restrictive and exhaustiv e search spaces have been proposed recently, In particular, the "stepwise a lgorithm" (SA) utilizes what is known in computer science as the "beam sear ch," whereas the NJ method employs a "greedy search." SA is virtually guara nteed to find the ME trees while being much faster than exhaustive search a lgorithms. In this study we propose an even faster method for finding the M E tree, The new algorithm adjusts its search exhaustiveness (from greedy to complete) according to the statistical reliability of the tree node being reconstructed. It is also virtually guaranteed to find the ME tree. The per formances and computational efficiencies of ME, SA, NJ, and our new method were compared in extensive simulation studies. The new algorithm was found to perform practically as well as the SA (and, therefore, ME) methods and s lightly better than the NJ method, For searching for the globally optimal M E tree, the new algorithm is significantly faster than existing ones, thus making it relatively practical for obtaining all trees with an S value equa l to or smaller than that of the NJ tree, even when a large number of taxa is involved. (C) 2000 Academic Press.