Bayesian adaptive sequence alignment algorithms

The selection of a scoring matrix and gap penalty parameters. continues to be an important problem in sequence alignment. We describe here an algorithm, the 'Bayes block aligner; which bypasses this requirement. Instead of requiring a fixed set of parameter settings, this algorithm returns the Bayesian posterior probability for the number of gaps and for the scoring matrices in any sei ies of interest. Furthermore, instead of returning the single best alignment for. the chosen parameter settings, this algorithm returns the posterior distribution of all alignments considering the full range of gapping and scoring matrices selected, weighing each in proportion to its probability based on the data. We compared the Bayes aligner with the popular Smith-Waterman algorithm with parameter settings fi-om the literature which had been optimized for the identification of structural neighbors, and found that the Bayes aligner correctly identified more structural neighbours. In a detailed examination of the alignment of a pail of Kinase and a pair of GTPase sequences, Mie illustrate the algorithm's potential to identify subsequences that ai-e conserved to different degrees. In addition, this example shows that the Bayes aligner returns an alignment-free assessment of the distance between a pail of sequences. Availability: Software is available at http://www.wadsworth.org/res&res/bioinfo/ Contact: junzhu, lawrence@wadsworth.org, jliu@stat.stanford.edu.