title: Prediction of RNA secondary structure with pseudoknots using integer programming.
abstract: 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.
authors.affiliation: Bioinformatics Center, Institute for Chemical Research, Kyoto University, Gokasho, Uji, Kyoto 611-0011, Japan. unyanee@kuicr.kyoto-u.ac.jp
authors.forename: Unyanee
authors.initials: U
authors.lastname: Poolsap
authors.forename: Yuki
authors.initials: Y
authors.lastname: Kato
authors.forename: Tatsuya
authors.initials: T
authors.lastname: Akutsu
mesh_terms: 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
chemical_list: D012313:RNA