Prediction of RNA secondary structure with pseudoknots using integer programming.
BACKGROUND
RNA secondary structure prediction is one major task in bioinformatics, and various computational methods have been proposed so far. Pseudoknot is one of the typical substructures appearing in several RNAs, and plays an important role in some biological processes. Prediction of RNA secondary structure with pseudoknots is still challenging since the problem is NP-hard when arbitrary pseudoknots are taken into consideration.


RESULTS
We introduce a new method of predicting RNA secondary structure with pseudoknots based on integer programming. In our formulation, we aim at minimizing the value of the objective function that reflects free energy of a folding structure of an input RNA sequence. We focus on a practical class of pseudoknots by setting constraints appropriately. Experimental results for a set of real RNA sequences show that our proposed method outperforms several existing methods in sensitivity. Furthermore, for a set of sequences of small length, our approach achieved good performance in both sensitivity and specificity.


CONCLUSIONS
Our integer programming-based approach for RNA structure prediction is flexible and extensible.
Poolsap
Unyanee
U
Bioinformatics Center, Institute for Chemical Research, Kyoto University, Gokasho, Uji, Kyoto 611-0011, Japan. unyanee@kuicr.kyoto-u.ac.jp
Kato
Yuki
Y
Akutsu
Tatsuya
T
D001483:Base Sequence; D019295:Computational Biology / Q000379:methods*; D008969:Molecular Sequence Data; D009690:Nucleic Acid Conformation; D012313:RNA / Q000737:chemistry* / Q000235:genetics; D017423:Sequence Analysis, RNA
D012313:RNA