Premium
In search for more accurate alignments in the twilight zone
Author(s) -
Jaroszewski Lukasz,
Li Weizhong,
Godzik Adam
Publication year - 2002
Publication title -
protein science
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 3.353
H-Index - 175
eISSN - 1469-896X
pISSN - 0961-8368
DOI - 10.1110/ps.4820102
Subject(s) - alignment free sequence analysis , sequence alignment , multiple sequence alignment , computer science , sequence (biology) , bottleneck , structural alignment , protein structure prediction , algorithm , computational biology , protein structure , data mining , bioinformatics , pattern recognition (psychology) , artificial intelligence , biology , peptide sequence , genetics , gene , biochemistry , embedded system
A major bottleneck in comparative modeling is the alignment quality; this is especially true for proteins whose distant relationships could be reliably recognized only by recent advances in fold recognition. The best algorithms excel in recognizing distant homologs but often produce incorrect alignments for over 50% of protein pairs in large fold‐prediction benchmarks. The alignments obtained by sequence–sequence or sequence–structure matching algorithms differ significantly from the structural alignments. To study this problem, we developed a simplified method to explicitly enumerate all possible alignments for a pair of proteins. This allowed us to estimate the number of significantly different alignments for a given scoring method that score better than the structural alignment. Using several examples of distantly related proteins, we show that for standard sequence–sequence alignment methods, the number of significantly different alignments is usually large, often about 10 10 alternatives. This distance decreases when the alignment method is improved, but the number is still too large for the brute force enumeration approach. More effective strategies were needed, so we evaluated and compared two well‐known approaches for searching the space of suboptimal alignments. We combined their best features and produced a hybrid method, which yielded alignments that surpassed the original alignments for about 50% of protein pairs with minimal computational effort.