Multiple sequence alignment has proved to be a remarkably successful means of representing and organizing much of the present deluge of inferred protein sequence data. It is crucial to research on the structure and function of proteins, promoting the detection and description of sequence motifs and aiding efforts at protein modeling, structure prediction and engineering. In addition, by organizing information on mutational variation, multiple sequence alignment can elucidate molecular evolution and serve as the input for phylogenetic reconstruction. The importance of local multiple sequence alignment has long been appreciated and has been the subject of extensive study. The goal of automated methods is to produce optimized alignments, using only the information intrinsic to the sequences themselves. Unfortunately, rigorous algorithms for finding optimal solutions are so computationally expensive as to limit their application to a very small number of sequences. On the other hand, many heuristic approaches gain speed at the sacrifice of sensitivity to subtle patterns. We have developed a new statistically based algorithm that aligns sequences by means of predictive inference. Using residue frequencies, this Gibbs sampling algorithm iteratively selects alignments in accordance with their conditional probabilities. The newly formed alignments in turn update an evolving residue frequency model. When equilibrium is reached the most probable alignment can be identified. If a detectable pattern is present, we have found convergence is rapid. Effectively, the algorithm finds optimal local alignments from multiple sequences in linear time (seconds on current workstations). Its use is illustrated on test sets of helix turn helix proteins, lipocalins, and prenyltranferases. Continuing work on this project focuses on the relaxation of assumptions concerning motif size and number, and the independence of input sequences. The inclusion of residue interactions will also be explored.
