From analysis of protein structural alignments toward a novel approach to align protein sequences

Citations Over Time

Abstract

Alignment of protein sequences is a key step in most computational methods for prediction of protein function and homology-based modeling of three-dimensional (3D)-structure. We investigated correspondence between "gold standard" alignments of 3D protein structures and the sequence alignments produced by the Smith-Waterman algorithm, currently the most sensitive method for pair-wise alignment of sequences. The results of this analysis enabled development of a novel method to align a pair of protein sequences. The comparison of the Smith-Waterman and structure alignments focused on their inner structure and especially on the continuous ungapped alignment segments, "islands" between gaps. Approximately one third of the islands in the gold standard alignments have negative or low positive score, and their recognition is below the sensitivity limit of the Smith-Waterman algorithm. From the alignment accuracy perspective, the time spent by the algorithm while working in these unalignable regions is unnecessary. We considered features of the standard similarity scoring function responsible for this phenomenon and suggested an alternative hierarchical algorithm, which explicitly addresses high scoring regions. This algorithm is considerably faster than the Smith-Waterman algorithm, whereas resulting alignments are in average of the same quality with respect to the gold standard. This finding shows that the decrease of alignment accuracy is not necessarily a price for the computational efficiency.

Related Papers

• → Alignment of protein sequences by their profiles(2004)191 cited
• → Pairwise alignment of nucleotide sequences using maximal exact matches(2019)9 cited
• → ALIGN_MTX—An optimal pairwise textual sequence alignment program, adapted for using in sequence-structure alignment(2009)10 cited
• Biological Sequence Alignment for Bioinformatics Applications Using MATLAB(2011)
• → Efficient Algorithms for Triple-wise Alignment and Its Applications(2010)