{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T02:25:58Z","timestamp":1774491958951,"version":"3.50.1"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"S1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2009,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>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.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>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.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusion<\/jats:title>\n            <jats:p>Our integer programming-based approach for RNA structure prediction is flexible and extensible.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1471-2105-10-s1-s38","type":"journal-article","created":{"date-parts":[[2009,1,30]],"date-time":"2009-01-30T20:05:03Z","timestamp":1233345903000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":20,"title":["Prediction of RNA secondary structure with pseudoknots using integer programming"],"prefix":"10.1186","volume":"10","author":[{"given":"Unyanee","family":"Poolsap","sequence":"first","affiliation":[]},{"given":"Yuki","family":"Kato","sequence":"additional","affiliation":[]},{"given":"Tatsuya","family":"Akutsu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,1,30]]},"reference":[{"issue":"4","key":"3221_CR1","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1186\/gb-2004-5-4-105","volume":"5","author":"SA Shabalina","year":"2004","unstructured":"Shabalina SA, Spiridonov NA: The mammalian transcriptome and the function of non-coding DNA sequences. Genome Biology. 2004, 5 (4): 105-10.1186\/gb-2004-5-4-105.","journal-title":"Genome Biology"},{"key":"3221_CR2","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1093\/nar\/28.1.201","volume":"28","author":"FHDvan Batenburg","year":"2000","unstructured":"Batenburg FHDvan, Gultyaev AP, Pleij CWA, Ng J, Oliehoek J: PseudoBase: a database with RNA pseudoknots. Nucleic Acids Research. 2000, 28: 201-204. 10.1093\/nar\/28.1.201.","journal-title":"Nucleic Acids Research"},{"key":"3221_CR3","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1093\/nar\/9.1.133","volume":"9","author":"M Zuker","year":"1981","unstructured":"Zuker M, Stiegler P: Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information. Nucleic Acids Research. 1981, 9: 133-148. 10.1093\/nar\/9.1.133.","journal-title":"Nucleic Acids Research"},{"key":"3221_CR4","doi-asserted-by":"publisher","first-page":"3406","DOI":"10.1093\/nar\/gkg595","volume":"31","author":"M Zuker","year":"2003","unstructured":"Zuker M: Mfold web server for nucleic acid folding and hybridization prediction. Nucleic Acids Research. 2003, 31: 3406-3415. 10.1093\/nar\/gkg595.","journal-title":"Nucleic Acids Research"},{"key":"3221_CR5","doi-asserted-by":"publisher","first-page":"2053","DOI":"10.1006\/jmbi.1998.2436","volume":"285","author":"E Rivas","year":"1999","unstructured":"Rivas E, Eddy SR: A dynamic programming algorithm for RNA structure prediction including pseudoknots. Journal of Molecular Biology. 1999, 285: 2053-2068. 10.1006\/jmbi.1998.2436.","journal-title":"Journal of Molecular Biology"},{"key":"3221_CR6","volume-title":"BMC Bioinformatics","author":"J Reeder","year":"2004","unstructured":"Reeder J, Giegerich R: Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics. BMC Bioinformatics. 2004, 5:"},{"key":"3221_CR7","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1093\/bioinformatics\/btg373","volume":"20","author":"J Ruan","year":"2004","unstructured":"Ruan J, Stormo GD, Zhang W: An iterated loop matching approach to the prediction of RNA secondary structures with pseudoknots. Bioinformatics. 2004, 20: 58-66. 10.1093\/bioinformatics\/btg373.","journal-title":"Bioinformatics"},{"key":"3221_CR8","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/S0166-218X(00)00186-4","volume":"104","author":"T Akutsu","year":"2000","unstructured":"Akutsu T: Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots. Discrete Applied Mathematics. 2000, 104: 45-62. 10.1016\/S0166-218X(00)00186-4.","journal-title":"Discrete Applied Mathematics"},{"key":"3221_CR9","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1089\/106652700750050862","volume":"7","author":"RB Lyngs\u00f8","year":"2000","unstructured":"Lyngs\u00f8 RB, Pedersen CNS: RNA pseudoknot prediction in energy-based models. Journal of Computational Biology. 2000, 7: 409-427. 10.1089\/106652700750050862.","journal-title":"Journal of Computational Biology"},{"key":"3221_CR10","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/S0304-3975(98)00090-5","volume":"210","author":"Y Uemura","year":"1999","unstructured":"Uemura Y, Hasegawa A, Kobayashi S, Yokomori T: Tree adjoining grammars for RNA structure prediction. Theoretical Computer Science. 1999, 210: 277-303. 10.1016\/S0304-3975(98)00090-5.","journal-title":"Theoretical Computer Science"},{"key":"3221_CR11","doi-asserted-by":"publisher","first-page":"2611","DOI":"10.1093\/bioinformatics\/bti385","volume":"21","author":"H Matsui","year":"2005","unstructured":"Matsui H, Sato K, Sakakibara Y: Pair stochastic tree adjoining grammars for aligning and predicting pseudoknot RNA structures. Bioinformatics. 2005, 21: 2611-2617. 10.1093\/bioinformatics\/bti385.","journal-title":"Bioinformatics"},{"key":"3221_CR12","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1093\/bioinformatics\/16.4.334","volume":"16","author":"E Rivas","year":"2000","unstructured":"Rivas E, Eddy SR: The language of RNA: a formal grammar that includes pseudoknots. Bioinformatics. 2000, 16: 334-340. 10.1093\/bioinformatics\/16.4.334.","journal-title":"Bioinformatics"},{"issue":"Suppl 1","key":"3221_CR13","doi-asserted-by":"publisher","first-page":"i66","DOI":"10.1093\/bioinformatics\/btg1007","volume":"19","author":"L Cai","year":"2003","unstructured":"Cai L, Malmberg RL, Wu Y: Stochastic modeling of RNA pseudoknotted structures: a grammatical approach. Bioinformatics. 2003, 19 (Suppl 1): i66-i73. 10.1093\/bioinformatics\/btg1007.","journal-title":"Bioinformatics"},{"key":"3221_CR14","first-page":"12","volume":"47","author":"Y Kato","year":"2006","unstructured":"Kato Y, Seki H, Kasami T: RNA pseudoknotted structure prediction using stochastic multiple context-free grammar. IPSJ Transactions on Bioinformatics. 2006, 47: 12-21.","journal-title":"IPSJ Transactions on Bioinformatics"},{"key":"3221_CR15","doi-asserted-by":"publisher","first-page":"810","DOI":"10.1137\/0145048","volume":"45","author":"D Sankoff","year":"1985","unstructured":"Sankoff D: Simultaneous solution of the RNA folding, alignment and protosequence problems. SIAM Journal on Applied Mathematics. 1985, 45: 810-825. 10.1137\/0145048.","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"3221_CR16","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1006\/jmbi.2001.5351","volume":"317","author":"DH Mathews","year":"2002","unstructured":"Mathews DH, Turner DH: Dynalign: an algorithm for finding the secondary structure common to two RNA sequences. Journal of Molecular Biology. 2002, 317: 191-203. 10.1006\/jmbi.2001.5351.","journal-title":"Journal of Molecular Biology"},{"key":"3221_CR17","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1038\/nature06684","volume":"452","author":"M Parisien","year":"2008","unstructured":"Parisien M, Major F: The MC-Fold and MC-Sym pipeline infers RNA structure from sequence data. Nature. 2008, 452: 51-55. 10.1038\/nature06684.","journal-title":"Nature"},{"key":"3221_CR18","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1142\/S0219720003000186","volume":"1","author":"J Xu","year":"2003","unstructured":"Xu J, Li M, Kim D, Xu Y: RAPTOR: optimal protein threading by linear programming. J Bioinform Comput Biol. 2003, 1: 95-117. 10.1142\/S0219720003000186.","journal-title":"J Bioinform Comput Biol"},{"key":"3221_CR19","unstructured":"ILOG CPLEX. [http:\/\/www.ilog.com\/products\/cplex\/]"},{"issue":"Database issue","key":"3221_CR20","doi-asserted-by":"publisher","first-page":"D121","DOI":"10.1093\/nar\/gki081","volume":"33","author":"S Griffiths-Jones","year":"2005","unstructured":"Griffiths-Jones S, Moxon S, Marshall M, Khanna A, Eddy SR, Bateman A: Rfam: annotating non-coding RNAs in complete genomes. Nucleic Acids Res. 2005, 33 (Database issue): D121-D124. 10.1093\/nar\/gki081.","journal-title":"Nucleic Acids Res"},{"key":"3221_CR21","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1126\/science.2468181","volume":"244","author":"M Zuker","year":"1989","unstructured":"Zuker M: On finding all suboptimal foldings of an RNA molecule. Science. 1989, 244: 48-52. 10.1126\/science.2468181.","journal-title":"Science"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-10-S1-S38.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T02:47:03Z","timestamp":1630464423000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-10-S1-S38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1]]},"references-count":21,"journal-issue":{"issue":"S1","published-print":{"date-parts":[[2009,1]]}},"alternative-id":["3221"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-10-s1-s38","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1]]},"assertion":[{"value":"30 January 2009","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"S38"}}