Incremental Window-based Protein Sequence Alignment Algorithms

Huzefa Rangwala and George Karypis
5th European Conference on Computational Biology (ECCB), 2006
Download Paper
Motivation: Protein sequence alignment plays a critical role
in computational biology as it is an integral part in many analysis
tasks designed to solve problems in comparative genomics, structure
and function prediction, and homology modeling.

Methods: We have developed novel sequence alignment algorithms
that compute the alignment between a pair of sequences
based on short fixed- or variable-length high-scoring subsequences.
Our algorithms build the alignments by repeatedly selecting the
highest scoring pairs of subsequences and using them to construct
small portions of the final alignment. We utilize PSI-BLAST generated
sequence profiles and employ a profile-to-profile scoring
scheme derived from PICASSO.

Results: We evaluated the performance of the computed alignments
on two recently published benchmark datasets and compared
them against the alignments computed by existing state-of-the-art
dynamic programming-based profile-to-profile local and global sequence
alignment algorithms. Our results show that the new algorithms
achieve alignments that are comparable or better to those
achieved by existing algorithms. Moreover, our results also showed
that these algorithms can be used to provide better information as to
which of the aligned positions are more reliablea critical piece of
information for comparative modeling applications.

Supplemental data is available [hlink:[][here]].
Research topics: Bioinformatics