Efficient tree searches with available algorithms.

Phylogenetic methods based on optimality criteria are highly desirable for their logic properties, but time-consuming when compared to other methods of tree construction. Traditionally, researchers have been limited to exploring tree space by using multiple replicates of Wagner addition followed by typical hill climbing algorithms such as SPR or/and TBR branch swapping but these methods have been shown to be insufi cient for "large" data sets (or even for small data sets with a complex tree space). Here, I review different algorithms and search strategies used for phylogenetic analysis with the aim of clarifying certain aspects of this important part of the phylogenetic inference exercise. The techniques discussed here apply to both major families of methods based on optimality criteria—parsimony and maximum likelihood—and allow the thorough analysis of complex data sets with hundreds to thousands of terminal taxa. A new technique, called pre-processed searches is proposed for reusing phylogenetic results obtained in previous analyses, to increase the applicability of the previously proposed jumpstarting phylogenetics method. This article is aimed to serve as an educational and algorithmic reference to biologists interested in phylogenetic analysis. Rationale analysis, numerical methods are preferred over other methods because of their effi ciency and repeatability. Within numerical methods, those based on optimality criteria are to be preferred because they allow for hypothesis testing and tree comparisons based on objective measures. However, methods based on optimality criteria are more time consuming than most other numerical methods (e.g. UPGMA, neighbor-joining). The reason for this is simple, in order to choose an optimal solution, multiple trees need to be compared. The two main optimality criteria are parsimony and maximum likelihood 1 . While their limits on effi cient searches differ due to the computation requirements by each method (e.g. Sanderson and Kim, 2000; Goloboff, 2003), the issues discussed in this article apply, at least in principle, to both methodologies. Finding the optimal tree(s) for a given optimality criterion—the so-called "tree search"—is a NP- complete problem (Garey et al. 1977; Garey and Johnson, 1977; Chor and Tuller, 2005); a problem that is unlikely to have a solution in polynomial time. Tree searches are diffi cult due to the exponential growth of possible trees when increasing the number of terminals (OTUs) (Felsenstein, 1978). If a method were to compare all the possible trees using an explicit enumeration technique, an optimality value (tree length for parsimony or −lnL score for maximum likelihood) would be assigned to each tree and those that optimize the selected criterion would be chosen. However, explicit enumeration is not a very effi cient method and there are many algorithmic speedups that will fi nd the optimal solution with- out the burden of evaluating all possible trees. An alternative solution to explicit enumeration is the use of shortcuts that guarantee fi nding all optimal trees. The most common shortcut is the branch and bound algorithm (Hendy and Penny, 1982). Although for teaching purposes explicit enumeration and branch and bound do the trick, for most biologically interesting datasets these algorithms cannot be usefully applied. Instead, most investigators use different types of heuristics to attempt achieving an optimal— if not "the" optimal—solution by avoiding the intractability of exact methods. Heuristic methods can- not guarantee fi nding the optimal solution, unlike exact methods, although convergence measures can be used (see below) as indicators of the quality of the result. Historically, the fi rst heuristic method of tree construction is the algorithm proposed by Wagner (1961) and implemented by Farris (1970). Such trees were originally calculated by hand and used as fi nal results 1 For the purpose of this discussion I will avoid other methods derived from the purely optimality criterion-based methods, such as Bayesian phylogenet- ics or parsimony jackknifi ng, because they are based on repeating "quick-and-dirty" analyses a large number of times.