title: 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.
abstract: 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
authors.affiliation: The Institute of Statistical Mathematics, 4-6-7 Minami-Azabu, Minato-ku, Tokyo 106-8569, Japan. tal@ism.ac.jp
authors.forename: Tal
authors.initials: T
authors.lastname: Pupko
authors.forename: Itsik
authors.initials: I
authors.lastname: Pe'er
authors.forename: Masami
authors.initials: M
authors.lastname: Hasegawa
authors.forename: Dan
authors.initials: D
authors.lastname: Graur
authors.forename: Nir
authors.initials: N
authors.lastname: Friedman
mesh_terms: 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
chemical_list: D017299:Rod Opsins; D003576:Electron Transport Complex IV; D009113:Muramidase