Premium
Searching for Most Parsimonious Trees with Simulated Evolutionary Optimization
Author(s) -
Moilanen Atte
Publication year - 1999
Publication title -
cladistics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 2.323
H-Index - 92
eISSN - 1096-0031
pISSN - 0748-3007
DOI - 10.1111/j.1096-0031.1999.tb00393.x
Subject(s) - computer science , tree (set theory) , binary number , tree rearrangement , binary tree , evolutionary algorithm , word (group theory) , artificial intelligence , algorithm , theoretical computer science , mathematics , phylogenetic tree , arithmetic , biology , combinatorics , biochemistry , geometry , gene
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 optimization 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.