Fast Fitch-parsimony algorithms for large data sets

The speed of analytical algorithms becomes increasingly important as system atists accumulate larger data sets. In this paper I discuss several time-sa ving modifications to published Fitch-parsimony tree search algorithms, inc luding shortcuts that allow rapid evaluation of tree lengths and fast reopt imization of trees after clipping or joining of subtrees, as well as search strategies that allows one to successively increase the exhaustiveness of branch swapping. I also describe how Fitch-parsimony algorithms can be rest ructured to take full advantage of the computing power of modern microproce ssors by horizontal or vertical packing of characters, allowing simultaneou s processing of many characters, and by avoidance of conditional branches t hat disturb instruction flow. These new multicharacter algorithms are parti cularly useful for large data sets of characters with a small number of sta tes, such as nucleotide characters. As an example, the multicharacter algor ithms are estimated to be 3.6-10 times faster than single-character equival ents on a PowerPC 604. The speed gain is even larger on processors using MM X, Altivec or similar technologies allowing single instructions to be perfo rmed on multiple data simultaneously. (C) 1998 The Willi Hennig Society.