Bayesian adaptive sequence alignment algorithms

The selection of a scoring matrix and gap penalty parameters continues tobe an important problem in sequence alignment. We describe here analgorithm, the 'Bayes block aligner, which bypasses this requirement.Instead of requiring a fixed set of parameter settings, this algorithmreturns the Bayesian posterior probability for the number of gaps and forthe scoring matrices in any series of interest. Furthermore, instead ofreturning the single best alignment for the chosen parameter settings, thisalgorithm returns the posterior distribution of all alignments consideringthe full range of gapping and scoring matrices selected, weighing each inproportion to its probability based on the data. We compared the Bayesaligner with the popular Smith-Waterman algorithm with parameter settingsfrom the literature which had been optimized for the identification ofstructural neighbors, and found that the Bayes aligner correctly identifiedmore structural neighbors. In a detailed examination of the alignment of apair of kinase and a pair of GTPase sequences, we illustrate thealgorithm's potential to identify subsequences that are conserved todifferent degrees. In addition, this example shows that the Bayes alignerreturns an alignment-free assessment of the distance between a pair ofsequences.