Premium
Tree Searches Under Sankoff Parsimony
Author(s) -
Goloboff Pablo A.
Publication year - 1998
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.1998.tb00336.x
Subject(s) - biology , tree (set theory) , mathematics , combinatorics
Algorithms to speed up tree searches under Sankoff parsimony are described. For T terminal taxa, an exact algorithm allows calculating length during searches T to 2 T times faster than a complete down‐pass optimization. An approximate but accurate method is from 3 T to 8 T times faster than a down‐pass. Other algorithms that provide additional increases of speed for simple symmetrical transformation costs are described.