The detection and alignment of locally conserved regions in multiple sequences can provide insight into protein structure, function and evolution. A Gibbs sampling algorithm has been shown useful for multiple sequence alignment when the relationship between the sequences in subtle. However, when the sequences understudy contain many common collinear motifs the sampler can experience difficulty in convergence. In this project we seek to develop a version of the algorithm which overcomes this deficiency. The algorithm is a backwards forwards algorithm that takes advantage of a recursive property similar to the one commonly used by dynamic programming algorithms developed for the alignment of pairs of sequences. In this project we seek to develop a statistical method for determining gap penalties and for assessing the statistical significance to alterative gaping models. These statistically based gap penalties are based on the premise that under the null all alignments are equally likely. Consequently more flexible alignment, e.g. those that permit more gaps, must be down weighted to account for the access number alignment that emerge from the alignment conditions are relaxed. We also are exploring the application of these methods for the detection of subtlety related sequences in a database.
