METHODS FOR FASTER PARSIMONY ANALYSIS

Abstract — Several algorithms to speed up branch swapping searches for most parsimonious trees are described. The method for indirect tree length calculation when moving a clipped clade, based on final states for the divided tree, is expanded to take into account polymorphic characters, and to include the possibility of rejecting several locations as suboptimal by checking just one node. Three different algorithms for faster estimation of final state assignments for the divided tree based on calculations for the whole tree are presented. The first of these is approximate; it uses information from the final state sets for the whole tree. The second is exact, but it is slower than the first, and requires more memory; it is based on the union of the state sets of the descendants for each node. The third is also exact; it requires more memory and programming effort than the other two but it is faster, it is based on final and preliminary state sets for the whole tree ("incremental two-pass optimization"). Efficient ways to derive state assignments for collapsing trees, based on final states for the divided tree, are described. The recently proposed method of "incremental optimization" is discussed. It is likely that searches using that method will be no faster than searches using indirect calculation as originally described, and will be quite slower than the modified indirect calculation described here. Searches using that method will probably be significantly slowed down when zero-length branches are to be collapsed, since shortcuts for faster collapsing are not directly applicable.