A branch-and-bound algorithm for the inference of ancestral amino-acid sequences when the replacement rate varies among sites: Application to the evolution of five gene families.
BACKGROUND
We developed an algorithm to reconstruct ancestral sequences, taking into account the rate variation among sites of the protein sequences. Our algorithm maximizes the joint probability of the ancestral sequences, assuming that the rate is gamma distributed among sites. Our algorithm probably finds the global maximum. The use of 'joint' reconstruction is motivated by studies that use the sequences at all the internal nodes in a phylogenetic tree, such as, for instance, the inference of patterns of amino-acid replacement, or tracing the biochemical changes that occurred during the evolution of a given protein family.


RESULTS
We give an algorithm that guarantees finding the global maximum. The efficient search method makes our method applicable to datasets with large number sequences. We analyze ancestral sequences of five gene families, exploring the effect of the amount of among-site-rate-variation, and the degree of sequence divergence on the resulting ancestral states.


BACKGROUND
http://evolu3.ism.ac.jp/~tal/


BACKGROUND
tal@ism.ac.jp
Pupko
Tal
T
The Institute of Statistical Mathematics, 4-6-7 Minami-Azabu, Minato-ku, Tokyo 106-8569, Japan. tal@ism.ac.jp
Pe'er
Itsik
I
Hasegawa
Masami
M
Graur
Dan
D
Friedman
Nir
N
D000465:Algorithms; D000595:Amino Acid Sequence; D030541:Databases, Genetic; D003576:Electron Transport Complex IV / Q000235:genetics; D019143:Evolution, Molecular; D014644:Genetic Variation / Q000235:genetics; D016013:Likelihood Functions; D008957:Models, Genetic; D015233:Models, Statistical; D008969:Molecular Sequence Data; D009113:Muramidase / Q000235:genetics; D016296:Mutagenesis / Q000235:genetics; D010802:Phylogeny; D015203:Reproducibility of Results; D017299:Rod Opsins / Q000235:genetics; D012680:Sensitivity and Specificity; D016415:Sequence Alignment / Q000379:methods* / Q000592:standards; D020539:Sequence Analysis, Protein / Q000379:methods* / Q000706:statistics & numerical data*; D017386:Sequence Homology, Amino Acid
D017299:Rod Opsins; D003576:Electron Transport Complex IV; D009113:Muramidase