Accession Number : ADA444856


Title :   Incremental Window-based Protein Sequence Alignment Algorithms


Corporate Author : MINNESOTA UNIV MINNEAPOLIS DEPT OF COMPUTER SCIENCE


Personal Author(s) : Rangwala, Huzefa ; Karypis, George


Full Text : http://www.dtic.mil/get-tr-doc/pdf?AD=ADA444856


Report Date : 23 MAR 2006


Pagination or Media Count : 10


Abstract : 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 reliable a critical piece of information for comparative modeling applications.


Descriptors :   *ALGORITHMS , *OPTIMIZATION , *PROTEINS , *SEQUENCES , ALIGNMENT , DYNAMIC PROGRAMMING , AMINO ACIDS


Subject Categories : BIOCHEMISRTY
      GENETIC ENGINEERING AND MOLECULAR BIOLOGY
      NUMERICAL MATHEMATICS
      MEDICINE AND MEDICAL RESEARCH


Distribution Statement : APPROVED FOR PUBLIC RELEASE