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 2T times faster than a complete down-pass optimization. An approximate but accurate method is from 3T to 8T times faster than a down-pass. Other algorithms that provide additional increases of speed for simple symmetrical transformation costs are described.