Peter Clote, Feng Lou, and Alain Denise
Pairwise alignment, suboptimal alignment, BAliBASE
In comparative protein modeling, the quality of a template model depends heavily on the quality of the initial alignment between a given protein with unknown structure to various template proteins, whose tertiary structure is available in the Protein Data Bank (PDB). Although pairwise sequence alignment has been solved for more than three decades, there remains a large discrepancy between the accuracy of the best sequence alignment between two amino acid sequences, as produced by the Needleman-Wunsch [15] or Smith-Waterman [19] algorithms, and that of the best structural alignment between two protein X-ray structures, as produced by the software DALI, CE, Topofit, etc. To improve the quality of initial alignments in template modeling, one can integrate valuable information from an ensemble of generated suboptimal alignments, that is alignments whose score is below the best possible score. In this paper, we present a novel algorithm to produce suboptimal pairwise alignments. Specifically, given any initial alignment A0 of two nucleic acid or amino acid sequences, our algorithm SubOpt simultaneously computes the optimal alignment Ak having trace distance k from A0, thus producing a small, representative yet divergent ensemble of suboptimal structures in time and space O(n3). A web server for SubOpt is under construction at http://bioinformatics.bc.edu/clotelab/.
Important Links:
Go Back
