title: Gapped alignment of protein sequence motifs through Monte Carlo optimization of a hidden Markov model.
abstract: BACKGROUND
  Certain protein families are highly conserved across distantly related organisms and belong to large and functionally diverse superfamilies. The patterns of conservation present in these protein sequences presumably are due to selective constraints maintaining important but unknown structural mechanisms with some constraints specific to each family and others shared by a larger subset or by the entire superfamily. To exploit these patterns as a source of functional information, we recently devised a statistically based approach called contrast hierarchical alignment and interaction network (CHAIN) analysis, which infers the strengths of various categories of selective constraints from co-conserved patterns in a multiple alignment. The power of this approach strongly depends on the quality of the multiple alignments, which thus motivated development of theoretical concepts and strategies to improve alignment of conserved motifs within large sets of distantly related sequences.
  
  
  RESULTS
  Here we describe a hidden Markov model (HMM), an algebraic system, and Markov chain Monte Carlo (MCMC) sampling strategies for alignment of multiple sequence motifs. The MCMC sampling strategies are useful both for alignment optimization and for adjusting position specific background amino acid frequencies for alignment uncertainties. Associated statistical formulations provide an objective measure of alignment quality as well as automatic gap penalty optimization. Improved alignments obtained in this way are compared with PSI-BLAST based alignments within the context of CHAIN analysis of three protein families: Gialpha subunits, prolyl oligopeptidases, and transitional endoplasmic reticulum (p97) AAA+ ATPases.
  
  
  CONCLUSIONS
  While not entirely replacing PSI-BLAST based alignments, which likewise may be optimized for CHAIN analysis using this approach, these motif-based methods often more accurately align very distantly related sequences and thus can provide a better measure of selective constraints. In some instances, these new approaches also provide a better understanding of family-specific constraints, as we illustrate for p97 ATPases. Programs implementing these procedures and supplementary information are available from the authors.
authors.affiliation: Cold Spring Harbor Laboratory, 1 Bungtown Road, P,O, Box 100, Cold Spring Harbor, NY 11724, USA. neuwald@cshl.org
authors.forename: Andrew F
authors.initials: AF
authors.lastname: Neuwald
authors.forename: Jun S
authors.initials: JS
authors.lastname: Liu
mesh_terms: D020816:Amino Acid Motifs; D000595:Amino Acid Sequence; D000818:Animals; D019843:Archaeal Proteins / Q000737:chemistry; D001426:Bacterial Proteins / Q000737:chemistry; D017124:Conserved Sequence; D020558:GTP Phosphohydrolases / Q000737:chemistry; D015801:Helminth Proteins / Q000737:chemistry; D006867:Hydrolases / Q000737:chemistry; D008390:Markov Chains; D008969:Molecular Sequence Data; D009010:Monte Carlo Method; D000085822:Prolyl Oligopeptidases; D017510:Protein Folding; D017434:Protein Structure, Tertiary; D016415:Sequence Alignment / Q000379:methods / Q000706:statistics & numerical data*; D020539:Sequence Analysis, Protein / Q000379:methods / Q000706:statistics & numerical data*; D012697:Serine Endopeptidases / Q000737:chemistry; D012984:Software / Q000706:statistics & numerical data
chemical_list: D019843:Archaeal Proteins; D001426:Bacterial Proteins; D015801:Helminth Proteins; D006867:Hydrolases; D012697:Serine Endopeptidases; D000085822:Prolyl Oligopeptidases; D020558:GTP Phosphohydrolases