A fast algorithm for joint reconstruction of ancestral amino acid sequences

A dynamic programming algorithm is developed for maximum-likelihood reconst ruction of the set of all ancestral amino acid sequences in a phylogenetic tree. To date, exhaustive algorithms that find the most likely set of ances tral states (joint reconstruction) have running times that scale exponentia lly with the number of sequences and are thus limited to Very few taxa. The time requirement of our new algorithm scales linearly with the number of s equences and is therefore applicable to practically any number of taxa. A d etailed description of the new algorithm and an example of its application to cytochrome b sequences are provided.