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.
Unyanee Poolsap Yuki Kato Tatsuya Akutsu
Bioinformatics Center, Institute for Chemical Research, Kyoto University, Gokasho, Uji, Kyoto 611-0011, Japan
国际会议
The 7th Asia-Pacific Bioinformatics Conference(第七届亚太生物信息学大会)
北京
英文
439-448
2009-01-01（万方平台首次上网日期，不代表论文的发表时间）