A Fast Algorithm for Joint Reconstruction of Ancestral Amino Acid Sequences
- 1 June 2000
- journal article
- Published by Oxford University Press (OUP) in Molecular Biology and Evolution
- Vol. 17 (6), 890-896
- https://doi.org/10.1093/oxfordjournals.molbev.a026369
Abstract
A dynamic programming algorithm is developed for maximum-likelihood reconstruction of the set of all ancestral amino acid sequences in a phylogenetic tree. To date, exhaustive algorithms that find the most likely set of ancestral states (joint reconstruction) have running times that scale exponentially 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 sequences and is therefore applicable to practically any number of taxa. A detailed description of the new algorithm and an example of its application to cytochrome b sequences are provided.Keywords
This publication has 10 references indexed in Scilit:
- Correct and incorrect vertebrate phylogenies obtained by the entire mitochondrial DNA sequences.Molecular Biology and Evolution, 1999
- Problems with Parsimony in Sequences of Biased Base CompositionJournal of Molecular Evolution, 1998
- Positive Darwinian selection after gene duplication in primate ribonuclease genesProceedings of the National Academy of Sciences of the United States of America, 1998
- Probabilistic reconstruction of ancestral protein sequencesJournal of Molecular Evolution, 1996
- Active ancestral moleculesNature, 1995
- The rapid generation of mutation data matrices from protein sequencesBioinformatics, 1992
- Maximum likelihood inference of protein phylogeny and the origin of chloroplastsJournal of Molecular Evolution, 1990
- Ancestral lysozymes reconstructed, neutrality tested, and thermostability linked to hydrocarbon packingNature, 1990
- Evolutionary trees from DNA sequences: A maximum likelihood approachJournal of Molecular Evolution, 1981
- Toward Defining the Course of Evolution: Minimum Change for a Specific Tree TopologySystematic Zoology, 1971