Dynamic programming algorithms and grammatical modeling for protein beta-sheet prediction.
Protein structure prediction is one major task in computational biology, and various methods have been proposed for secondary structure prediction. In particular, it is a challenge to predict beta-sheet structures since they range over several discontinuous regions in an amino acid sequence. In this article, we propose dynamic programming algorithms for several kinds of antiparallel beta-sheets, where the proposed approach can be extended for more general classes of beta-sheets. Experimental results for real data show that our prediction algorithms have good performance in accuracy. We also show a relation between the proposed algorithms and an existing grammar-based method, and present another grammatical modeling. Furthermore, we prove that prediction of planar beta-sheet structures is NP-hard.
Kato
Yuki
Y
Bioinformatics Center, Institute for Chemical Research, Kyoto University, Uji, Kyoto, Japan. ykato@kuicr.kyoto-u.ac.jp
Akutsu
Tatsuya
T
Seki
Hiroyuki
H
D000465:Algorithms; D008962:Models, Theoretical; D011381:Programming Languages; D017433:Protein Structure, Secondary / Q000235:genetics*; D020539:Sequence Analysis, Protein / Q000379:methods*