{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T19:54:45Z","timestamp":1774641285999,"version":"3.50.1"},"reference-count":49,"publisher":"Oxford University Press (OUP)","issue":"13","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":1937,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/2.5"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011,7,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Pseudoknots found in secondary structures of a number of functional RNAs play various roles in biological processes. Recent methods for predicting RNA secondary structures cover certain classes of pseudoknotted structures, but only a few of them achieve satisfying predictions in terms of both speed and accuracy.<\/jats:p>\n               <jats:p>Results: We propose IPknot, a novel computational method for predicting RNA secondary structures with pseudoknots based on maximizing expected accuracy of a predicted structure. IPknot decomposes a pseudoknotted structure into a set of pseudoknot-free substructures and approximates a base-pairing probability distribution that considers pseudoknots, leading to the capability of modeling a wide class of pseudoknots and running quite fast. In addition, we propose a heuristic algorithm for refining base-paring probabilities to improve the prediction accuracy of IPknot. The problem of maximizing expected accuracy is solved by using integer programming with threshold cut. We also extend IPknot so that it can predict the consensus secondary structure with pseudoknots when a multiple sequence alignment is given. IPknot is validated through extensive experiments on various datasets, showing that IPknot achieves better prediction accuracy and faster running time as compared with several competitive prediction methods.<\/jats:p>\n               <jats:p>Availability: The program of IPknot is available at http:\/\/www.ncrna.org\/software\/ipknot\/. IPknot is also available as a web server at http:\/\/rna.naist.jp\/ipknot\/.<\/jats:p>\n               <jats:p>Contact: \u00a0satoken@k.u-tokyo.ac.jp; ykato@is.naist.jp<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btr215","type":"journal-article","created":{"date-parts":[[2011,6,17]],"date-time":"2011-06-17T23:32:32Z","timestamp":1308353552000},"page":"i85-i93","source":"Crossref","is-referenced-by-count":267,"title":["IPknot: fast and accurate prediction of RNA secondary structures with pseudoknots using integer programming"],"prefix":"10.1093","volume":"27","author":[{"given":"Kengo","family":"Sato","sequence":"first","affiliation":[{"name":"1 Graduate School of Frontier Sciences, University of Tokyo, 5-1-5 Kashiwanoha, Kashiwa, Chiba 277-8561, 2Graduate School of Information Science, Nara Institute of Science and Technology, 8916-5 Takayama, Ikoma, Nara 630-0192, 3Bioinformatics Center, Institute for Chemical Research, Kyoto University, Gokasho, Uji, Kyoto 611-0011, and 4Computational Biology Research Center (CBRC), National Institute of Advanced Industrial Science and Technology (AIST), 2-41-6, Aomi, Koto-ku, Tokyo 135-0064, Japan"}]},{"given":"Yuki","family":"Kato","sequence":"additional","affiliation":[{"name":"1 Graduate School of Frontier Sciences, University of Tokyo, 5-1-5 Kashiwanoha, Kashiwa, Chiba 277-8561, 2Graduate School of Information Science, Nara Institute of Science and Technology, 8916-5 Takayama, Ikoma, Nara 630-0192, 3Bioinformatics Center, Institute for Chemical Research, Kyoto University, Gokasho, Uji, Kyoto 611-0011, and 4Computational Biology Research Center (CBRC), National Institute of Advanced Industrial Science and Technology (AIST), 2-41-6, Aomi, Koto-ku, Tokyo 135-0064, Japan"}]},{"given":"Michiaki","family":"Hamada","sequence":"additional","affiliation":[{"name":"1 Graduate School of Frontier Sciences, University of Tokyo, 5-1-5 Kashiwanoha, Kashiwa, Chiba 277-8561, 2Graduate School of Information Science, Nara Institute of Science and Technology, 8916-5 Takayama, Ikoma, Nara 630-0192, 3Bioinformatics Center, Institute for Chemical Research, Kyoto University, Gokasho, Uji, Kyoto 611-0011, and 4Computational Biology Research Center (CBRC), National Institute of Advanced Industrial Science and Technology (AIST), 2-41-6, Aomi, Koto-ku, Tokyo 135-0064, Japan"}]},{"given":"Tatsuya","family":"Akutsu","sequence":"additional","affiliation":[{"name":"1 Graduate School of Frontier Sciences, University of Tokyo, 5-1-5 Kashiwanoha, Kashiwa, Chiba 277-8561, 2Graduate School of Information Science, Nara Institute of Science and Technology, 8916-5 Takayama, Ikoma, Nara 630-0192, 3Bioinformatics Center, Institute for Chemical Research, Kyoto University, Gokasho, Uji, Kyoto 611-0011, and 4Computational Biology Research Center (CBRC), National Institute of Advanced Industrial Science and Technology (AIST), 2-41-6, Aomi, Koto-ku, Tokyo 135-0064, Japan"}]},{"given":"Kiyoshi","family":"Asai","sequence":"additional","affiliation":[{"name":"1 Graduate School of Frontier Sciences, University of Tokyo, 5-1-5 Kashiwanoha, Kashiwa, Chiba 277-8561, 2Graduate School of Information Science, Nara Institute of Science and Technology, 8916-5 Takayama, Ikoma, Nara 630-0192, 3Bioinformatics Center, Institute for Chemical Research, Kyoto University, Gokasho, Uji, Kyoto 611-0011, and 4Computational Biology Research Center (CBRC), National Institute of Advanced Industrial Science and Technology (AIST), 2-41-6, Aomi, Koto-ku, Tokyo 135-0064, Japan"},{"name":"1 Graduate School of Frontier Sciences, University of Tokyo, 5-1-5 Kashiwanoha, Kashiwa, Chiba 277-8561, 2Graduate School of Information Science, Nara Institute of Science and Technology, 8916-5 Takayama, Ikoma, Nara 630-0192, 3Bioinformatics Center, Institute for Chemical Research, Kyoto University, Gokasho, Uji, Kyoto 611-0011, and 4Computational Biology Research Center (CBRC), National Institute of Advanced Industrial Science and Technology (AIST), 2-41-6, Aomi, Koto-ku, Tokyo 135-0064, Japan"}]}],"member":"286","published-online":{"date-parts":[[2011,6,14]]},"reference":[{"key":"2023012512155167800_B1","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/S0166-218X(00)00186-4","article-title":"Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots","volume":"104","author":"Akutsu","year":"2000","journal-title":"Discrete Appl. Math."},{"key":"2023012512155167800_B2","doi-asserted-by":"crossref","first-page":"115","DOI":"10.2174\/157489306777011996","article-title":"Recent advances in RNA secondary structure prediction with pseudoknots","volume":"1","author":"Akutsu","year":"2006","journal-title":"Current Bioinform."},{"key":"2023012512155167800_B3","doi-asserted-by":"crossref","first-page":"i19","DOI":"10.1093\/bioinformatics\/btm223","article-title":"Efficient parameter estimation for RNA secondary structure prediction","volume":"23","author":"Andronescu","year":"2007","journal-title":"Bioinformatics"},{"key":"2023012512155167800_B4","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1186\/1471-2105-9-340","article-title":"RNA STRAND: the RNA secondary structure and statistical analysis database","volume":"9","author":"Andronescu","year":"2008","journal-title":"BMC Bioinform."},{"key":"2023012512155167800_B5","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1261\/rna.1689910","article-title":"Improved free energy parameters for RNA pseudoknotted secondary structure prediction","volume":"16","author":"Andronescu","year":"2010","journal-title":"RNA"},{"key":"2023012512155167800_B6","doi-asserted-by":"crossref","first-page":"2304","DOI":"10.1261\/rna.1950510","article-title":"Computational approaches for RNA energy parameter estimation","volume":"16","author":"Andronescu","year":"2010","journal-title":"RNA"},{"key":"2023012512155167800_B7","doi-asserted-by":"crossref","first-page":"1870","DOI":"10.1261\/rna.2125310","article-title":"ProbKnot: fast prediction of RNA secondary structure including pseudoknots","volume":"16","author":"Bellaousov","year":"2010","journal-title":"RNA"},{"key":"2023012512155167800_B8","doi-asserted-by":"crossref","first-page":"474","DOI":"10.1186\/1471-2105-9-474","article-title":"RNAalifold: improved consensus structure prediction for RNA alignments","volume":"9","author":"Bernhart","year":"2008","journal-title":"BMC Bioinform."},{"key":"2023012512155167800_B9","doi-asserted-by":"crossref","first-page":"598","DOI":"10.1038\/nrmicro1704","article-title":"Viral RNA pseudoknots: versatile motifs in gene expression and replication","volume":"5","author":"Brierley","year":"2007","journal-title":"Nat. Rev. Microbiol."},{"key":"2023012512155167800_B10","doi-asserted-by":"crossref","first-page":"2634","DOI":"10.1093\/nar\/gkl346","article-title":"Predicting RNA pseudoknot folding thermodynamics","volume":"34","author":"Cao","year":"2006","journal-title":"Nucleic Acids Res."},{"key":"2023012512155167800_B11","doi-asserted-by":"crossref","first-page":"3209","DOI":"10.1073\/pnas.0712329105","article-title":"Centroid estimation in discrete high-dimensional spaces with applications in biology","volume":"105","author":"Carvalho","year":"2008","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023012512155167800_B12","doi-asserted-by":"crossref","first-page":"1994","DOI":"10.1093\/bioinformatics\/btn327","article-title":"FlexStem: improving predictions of RNA secondary structures with pseudoknots by reducing the search space","volume":"24","author":"Chen","year":"2008","journal-title":"Bioinformatics"},{"key":"2023012512155167800_B13","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/j.tcs.2004.03.042","article-title":"Classifying RNA pseudoknotted structures","volume":"320","author":"Condon","year":"2004","journal-title":"Theor. Comput. Sci."},{"key":"2023012512155167800_B14","doi-asserted-by":"crossref","first-page":"1664","DOI":"10.1002\/jcc.10296","article-title":"A partition function algorithm for nucleic acid secondary structure including pseudoknots","volume":"24","author":"Dirks","year":"2003","journal-title":"J. Comput. Chem."},{"key":"2023012512155167800_B15","doi-asserted-by":"crossref","first-page":"1295","DOI":"10.1002\/jcc.20057","article-title":"An algorithm for computing nucleic acid base-pairing probabilities including pseudoknots","volume":"25","author":"Dirks","year":"2004","journal-title":"J. Comput. Chem."},{"key":"2023012512155167800_B16","doi-asserted-by":"crossref","first-page":"330","DOI":"10.1101\/gr.2821705","article-title":"ProbCons: probabilistic consistency-based multiple sequence alignment","volume":"15","author":"Do","year":"2005","journal-title":"Genome Res."},{"key":"2023012512155167800_B17","doi-asserted-by":"crossref","first-page":"e90","DOI":"10.1093\/bioinformatics\/btl246","article-title":"CONTRAfold: RNA secondary structure prediction without physics-based models","volume":"22","author":"Do","year":"2006","journal-title":"Bioinformatics"},{"key":"2023012512155167800_B18","doi-asserted-by":"crossref","first-page":"i68","DOI":"10.1093\/bioinformatics\/btn177","article-title":"A max-margin model for efficient simultaneous alignment and folding of RNA sequences","volume":"24","author":"Do","year":"2008","journal-title":"Bioinformatics"},{"key":"2023012512155167800_B19","doi-asserted-by":"crossref","first-page":"919","DOI":"10.1038\/35103511","article-title":"Non-coding RNA genes and the modern RNA world","volume":"2","author":"Eddy","year":"2001","journal-title":"Nat. Rev. Genet."},{"key":"2023012512155167800_B20","doi-asserted-by":"crossref","first-page":"1547","DOI":"10.1007\/PL00000795","article-title":"Novel features in the tRNA-like world of plant viral RNAs","volume":"58","author":"Fechter","year":"2001","journal-title":"Cell. Mol. Life Sci."},{"key":"2023012512155167800_B21","doi-asserted-by":"crossref","first-page":"D141","DOI":"10.1093\/nar\/gkq1129","article-title":"Rfam: Wikipedia, clans and the \u201cdecimal\u201d release","volume":"39","author":"Gardner","year":"2011","journal-title":"Nucleic Acids Res."},{"key":"2023012512155167800_B22","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1093\/bioinformatics\/btn601","article-title":"Prediction of RNA secondary structure using generalized centroid estimators","volume":"25","author":"Hamada","year":"2009","journal-title":"Bioinformatics"},{"key":"2023012512155167800_B23","doi-asserted-by":"crossref","first-page":"3236","DOI":"10.1093\/bioinformatics\/btp580","article-title":"CentoroidAlign: fast and accurate aligner for structured RNAs by maximizing expected sum-of-pairs score","volume":"25","author":"Hamada","year":"2009","journal-title":"Bioinformatics"},{"key":"2023012512155167800_B24","doi-asserted-by":"crossref","first-page":"586","DOI":"10.1186\/1471-2105-11-586","article-title":"Prediction of RNA secondary structure by maximizing pseudo-expected accuracy","volume":"11","author":"Hamada","year":"2010","journal-title":"BMC Bioinform."},{"key":"2023012512155167800_B25","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1093\/nar\/gkq792","article-title":"Improving the accuracy of predicting secondary structure for aligned RNA sequences","volume":"39","author":"Hamada","year":"2011","journal-title":"Nucleic Acids Res."},{"key":"2023012512155167800_B26","doi-asserted-by":"crossref","first-page":"3429","DOI":"10.1093\/nar\/gkg599","article-title":"Vienna RNA secondary structure server","volume":"31","author":"Hofacker","year":"2003","journal-title":"Nucleic Acids Res."},{"key":"2023012512155167800_B27","doi-asserted-by":"crossref","first-page":"1059","DOI":"10.1016\/S0022-2836(02)00308-X","article-title":"Secondary structure prediction for aligned RNA sequences","volume":"319","author":"Hofacker","year":"2002","journal-title":"J. Mol. Biol"},{"key":"2023012512155167800_B28","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/BF00818163","article-title":"Fast folding and comparison of RNA secondary structures","volume":"125","author":"Hofacker","year":"1994","journal-title":"Monatsh. Chem."},{"key":"2023012512155167800_B29","doi-asserted-by":"crossref","first-page":"656","DOI":"10.1093\/nar\/gkl943","article-title":"High sensitivity RNA pseudoknot prediction","volume":"35","author":"Huang","year":"2007","journal-title":"Nucleic Acids Res."},{"key":"2023012512155167800_B30","doi-asserted-by":"crossref","first-page":"915","DOI":"10.1089\/cmb.2009.0119","article-title":"K-partite RNA secondary structures","volume":"17","author":"Jiang","year":"2010","journal-title":"J. Comput. Biol."},{"key":"2023012512155167800_B31","doi-asserted-by":"crossref","first-page":"i460","DOI":"10.1093\/bioinformatics\/btq372","article-title":"RactIP: fast and accurate prediction of RNA\u2013RNA interaction using integer programming","volume":"26","author":"Kato","year":"2010","journal-title":"Bioinformatics"},{"key":"2023012512155167800_B32","doi-asserted-by":"crossref","first-page":"3423","DOI":"10.1093\/nar\/gkg614","article-title":"Pfold: RNA secondary structure prediction using stochastic context-free grammars","volume":"31","author":"Knudsen","year":"2003","journal-title":"Nucleic Acids Res."},{"key":"2023012512155167800_B33","doi-asserted-by":"crossref","first-page":"8","DOI":"10.3410\/B2-8","article-title":"RNA pseudoknots: folding and finding","volume":"2","author":"Liu","year":"2010","journal-title":"F1000 Biol. Rep."},{"key":"2023012512155167800_B34","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1145\/332306.332551","article-title":"Pseudoknots in RNA secondary structures","author":"Lyngs\u00f8","year":"2000","journal-title":"Proc. 4th Ann. Intl. Conf. Comput. Mol. Biol. (RECOMB2000)"},{"key":"2023012512155167800_B35","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1089\/106652700750050862","article-title":"RNA pseudoknot prediction in energy-based models","volume":"7","author":"Lyngs\u00f8","year":"2000","journal-title":"J. Comput. Biol."},{"key":"2023012512155167800_B36","doi-asserted-by":"crossref","first-page":"911","DOI":"10.1006\/jmbi.1999.2700","article-title":"Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structure","volume":"288","author":"Mathews","year":"1999","journal-title":"J. Mol. Biol."},{"key":"2023012512155167800_B37","doi-asserted-by":"crossref","first-page":"1105","DOI":"10.1002\/bip.360290621","article-title":"The equilibrium partition function and base pair binding probabilities for RNA secondary structure","volume":"29","author":"McCaskill","year":"1990","journal-title":"Biopolymers"},{"issue":"Suppl 1","key":"2023012512155167800_B38","doi-asserted-by":"crossref","first-page":"S38","DOI":"10.1186\/1471-2105-10-S1-S38","article-title":"Prediction of RNA secondary structure with pseudoknots using integer programming","volume":"10","author":"Poolsap","year":"2009","journal-title":"BMC Bioinform."},{"key":"2023012512155167800_B39","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1186\/1471-2105-5-104","article-title":"Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics","volume":"5","author":"Reeder","year":"2004","journal-title":"BMC Bioinform."},{"key":"2023012512155167800_B40","doi-asserted-by":"crossref","first-page":"1494","DOI":"10.1261\/rna.7284905","article-title":"HotKnots: heuristic prediction of RNA secondary structures including pseudoknots","volume":"11","author":"Ren","year":"2005","journal-title":"RNA"},{"key":"2023012512155167800_B41","doi-asserted-by":"crossref","first-page":"2053","DOI":"10.1006\/jmbi.1998.2436","article-title":"A dynamic programming algorithm for RNA structure prediction including pseudoknots","volume":"285","author":"Rivas","year":"1999","journal-title":"J. Mol. Biol."},{"key":"2023012512155167800_B42","doi-asserted-by":"crossref","first-page":"1197","DOI":"10.1089\/cmb.2006.13.1197","article-title":"Pseudoknots in RNA secondary structures: representation, enumeration, and prevalence","volume":"13","author":"R\u00f8dland","year":"2006","journal-title":"J. Comput. Biol."},{"key":"2023012512155167800_B43","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1093\/bioinformatics\/btg373","article-title":"An iterated loop matching approach to the prediction of RNA secondary structures with pseudoknots","volume":"20","author":"Ruan","year":"2004","journal-title":"Bioinformatics"},{"key":"2023012512155167800_B44","doi-asserted-by":"crossref","first-page":"e213","DOI":"10.1371\/journal.pbio.0030213","article-title":"Pseudoknots: RNA structures with diverse functions","volume":"3","author":"Staple","year":"2005","journal-title":"PLoS Biol."},{"key":"2023012512155167800_B45","doi-asserted-by":"crossref","first-page":"4673","DOI":"10.1093\/nar\/22.22.4673","article-title":"CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice","volume":"22","author":"Thompson","year":"1994","journal-title":"Nucleic Acids Res."},{"key":"2023012512155167800_B46","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1093\/nar\/29.1.194","article-title":"PseudoBase: structural information on RNA pseudoknots","volume":"29","author":"van Batenburg","year":"2001","journal-title":"Nucleic Acids Res."},{"key":"2023012512155167800_B47","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1109\/TCBB.2004.22","article-title":"Prediction of consensus RNA secondary structures including pseudoknots","volume":"1","author":"Witwer","year":"2004","journal-title":"IEEE Trans. Comput. Biol. Bioinform."},{"key":"2023012512155167800_B48","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1093\/nar\/9.1.133","article-title":"Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information","volume":"9","author":"Zuker","year":"1981","journal-title":"Nucleic Acids Res."},{"key":"2023012512155167800_B49","doi-asserted-by":"crossref","first-page":"3406","DOI":"10.1093\/nar\/gkg595","article-title":"Mfold web server for nucleic acid folding and hybridization prediction","volume":"31","author":"Zuker","year":"2003","journal-title":"Nucleic Acids Res."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/27\/13\/i85\/48884195\/bioinformatics_27_13_i85.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/27\/13\/i85\/48884195\/bioinformatics_27_13_i85.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T14:35:31Z","timestamp":1674657331000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/27\/13\/i85\/178778"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,6,14]]},"references-count":49,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2011,7,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btr215","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2011,7,1]]},"published":{"date-parts":[[2011,6,14]]}}}