A Gibbs sampler for the detection of subtle motifs in multiple sequences

We describe a statistically based algorithm that aligns protein 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, generally convergence is rapid. Effectively, the algorithm finds optimal local multiple alignments in linear time (seconds on current workstations). Its use is illustrated on test sets of lipocalins and prenyltranferases.<>