Searching for Most Parsimonious Trees with Simulated
Evolutionary Optimization
Cladistics, 15 (1):
39--50 (1999)DOI: doi:10.1006/clad.1998.0081
Abstract
This study describes novel algorithms for searching
for most parsimonious trees. These algorithms are
implemented as a parsimony computer program, PARSIGAL,
which performs well even with difficult data sets. For
high level search, PARSIGAL uses an evolutionary
optimisation algorithm, which feeds good tree
candidates to a branch-swapping local search procedure.
This study also describes an extremely fast method of
recomputing state sets for binary characters (additive
or nonadditive characters with two states), based on
packing 32 characters into a single memory word and
recomputing the tree simultaneously for all 32
characters using fast bitwise logical operations. The
operational principles of PARSIGAL are quite different
from those previously published for other parsimony
computer programs. Hence it is conceivable that
PARSIGAL may be able to locate islands of trees that
are different from those that are easily located with
existing parsimony computer programs.