Biologically significant sequence alignment using Boltzmann probabilities

In this paper, we give a dynamic programming algorithm with quadratic time and space complexity to compute the partition function for both global and local sequence alignments of two peptides and thus providing an efficient computation of the Boltzmann probability that a particular pair of amino acids is aligned. As proof of concept, our probabilistic refinement of both the Needleman-Wunsch [16] global and Smith-Waterman [19] local alignment algorithm is then compared with pair-wise BLAST to determine an optimal local alignment of bovine trypsin and pig elastase, an example considered in Lipman et al. [14]. A web-server of our prototype tool is currently available.[5]