Boltzmann Alignment Demo, P. Clote

Web engine for a dynamic programming algorithm to compute the forward and backward partition function, which thus allows the computation of Boltzmann probability that two characters (amino acids or nucleotides) are aligned. This probability gives a measure of how often the designated two characters are aligned over all pairwise alignments, where an alignment A is weighted by exp(score(A)), where score is the PAM250, Blosum62, etc. score of the alignment. Using the Boltzmann probabilities we thus have a natural and efficiently computable notion of biological significance to the alignment of two characters. This approach can be confirmed using FSSP, 3d_ali and other biologically significant structural alignments.

Our current implementation supports both Needleman-Wunsch global alignment and Smith-Waterman local alignment, both using linear and affine gap penalties. However, the web server currently only supports the Smith-Waterman local alignment with linear gap penalty. (A couple of checkboxes and simple modifications of the cgi parser will yield full functionality. The final web server will have a color indicator representing the strength of the probability.)

Our current implementation allows any similarity matrix, though we use the default of PAM250 amino acid similarity matrix. Again, the final web server will incorporate several choices of similarity matrices.

For large sequences, such as two well-known yeast proteins Cdc25 and Ste6, due to floating point overflow caused by the addition of numbers exponential in alignment scores, we plan to use a centered window of default size (say) 50 to compute the Boltzmann probabilities on the alignment appearing withing the centered window. Currently this is not implemented, and probabilities are computed on the entire (local) alignment.

WARNING: Current implementation will crash when there is NO local alignment between 2 sequences; for instance on AAA and IIII, since PAM250 similarity of A with I is negative. This is an easy thing to fix, by testing if the alignment is empty, and will be rectified in the final web server.

Our implementation requires 4 command line arguments: peptide1, peptide2, similarityMatrix, gapPenalty. Here, peptide1 and peptide2 are FASTA format files for 2 amino acid sequences; alternatively, short sequences can be pasted into the form. The file similarityMatrix is in the format, as in PAM250 matrix, and you may give an arbitrary gap penalty (e.g. -10 for strong gap penalty, 0 for no gap penalty). With these parameters, click here to see the output for alignment on these 2 files. To see the cgi code, click here. With this output, one can then use gnuplot for graphical alignment output.

Insert 2 amino acid sequences amino acid sequences AND a gap penalty (e.g. -10 for strong gap penalty, and 0 for no gap penalty).

Select the type of operating system you use:

Select the method of entering the amino acid sequences:
Either paste in sequences or upload files in FASTA format. WARNING: The current implementation allows you either to upload 2 files or to paste 2 sequences, but NOT to upload one file and paste one sequence. Check the intended sequence entry mode.

First peptide

Second peptide

Gap penalty:

Print uploaded files?