Tree Searches Under Sankoff Parsimony

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.