{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,30]],"date-time":"2026-01-30T10:47:40Z","timestamp":1769770060918,"version":"3.49.0"},"reference-count":34,"publisher":"Oxford University Press (OUP)","issue":"22","license":[{"start":{"date-parts":[[2018,6,1]],"date-time":"2018-06-01T00:00:00Z","timestamp":1527811200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018,11,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>The computational prediction of RNA secondary structure by free energy minimization has become an important tool in RNA research. However in practice, energy minimization is mostly limited to pseudoknot-free structures or rather simple pseudoknots, not covering many biologically important structures such as kissing hairpins. Algorithms capable of predicting sufficiently complex pseudoknots (for sequences of length n) used to have extreme complexities, e.g. Pknots has O(n6) time and O(n4) space complexity. The algorithm CCJ dramatically improves the asymptotic run time for predicting complex pseudoknots (handling almost all relevant pseudoknots, while being slightly less general than Pknots), but this came at the cost of large constant factors in space and time, which strongly limited its practical application (\u223c200 bases already require 256\u00a0GB space).<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>We present a CCJ-type algorithm, Knotty, that handles the same comprehensive pseudoknot class of structures as CCJ with improved space complexity of \u0398(n3+Z)\u2014due to the applied technique of sparsification, the number of \u2018candidates\u2019, Z, appears to grow significantly slower than n4 on our benchmark set (which include pseudoknotted RNAs up to 400\u00a0nt). In terms of run time over this benchmark, Knotty clearly outperforms Pknots and the original CCJ implementation, CCJ 1.0; Knotty\u2019s space consumption fundamentally improves over CCJ 1.0, being on a par with the space-economic Pknots. By comparing to CCJ 2.0, our unsparsified Knotty variant, we demonstrate the isolated effect of sparsification. Moreover, Knotty employs the state-of-the-art energy model of \u2018HotKnots DP09\u2019, which results in superior prediction accuracy over Pknots.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>Our software is available at https:\/\/github.com\/HosnaJabbari\/Knotty.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Supplementary information<\/jats:title>\n                  <jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/bty420","type":"journal-article","created":{"date-parts":[[2018,5,24]],"date-time":"2018-05-24T19:11:34Z","timestamp":1527189094000},"page":"3849-3856","source":"Crossref","is-referenced-by-count":49,"title":["Knotty: efficient and accurate prediction of complex RNA pseudoknot structures"],"prefix":"10.1093","volume":"34","author":[{"given":"Hosna","family":"Jabbari","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Vermont, Burlington, VT, USA"}]},{"given":"Ian","family":"Wark","sequence":"additional","affiliation":[{"name":"Ingenuity Lab, Department of Chemical and Materials Engineering, University of Alberta, Edmonton, Canada"}]},{"given":"Carlo","family":"Montemagno","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, Southern Illinois University, Carbondale, IL, USA"}]},{"given":"Sebastian","family":"Will","sequence":"additional","affiliation":[{"name":"Theoretical Biochemistry Group (TBI), Institute for Theoretical Chemistry, University of Vienna, Vienna, Austria"}]}],"member":"286","published-online":{"date-parts":[[2018,6,1]]},"reference":[{"key":"2023012712380006600_bty420-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":"2023012712380006600_bty420-B2","doi-asserted-by":"crossref","first-page":"987","DOI":"10.1016\/j.jmb.2004.10.082","article-title":"Secondary structure prediction of interacting RNA molecules","volume":"345","author":"Andronescu","year":"2005","journal-title":"JMB"},{"key":"2023012712380006600_bty420-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":"2023012712380006600_bty420-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 Bioinformatics"},{"key":"2023012712380006600_bty420-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":"2023012712380006600_bty420-B6","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/j.jda.2010.09.001","article-title":"Sparse RNA folding: time and space efficient algorithms","volume":"9","author":"Backofen","year":"2011","journal-title":"J. Discrete Algorithms"},{"key":"2023012712380006600_bty420-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":"2023012712380006600_bty420-B8","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1006\/jmbi.1997.1021","article-title":"The structure of an RNA \u2018kissing\u2019 hairpin complex of the HIV TAR hairpin loop and its complement","volume":"269","author":"Chang","year":"1997","journal-title":"J. Mol. Biol"},{"key":"2023012712380006600_bty420-B9","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/j.vetmic.2013.04.026","article-title":"Japanese encephalitis virus non-coding RNA inhibits activation of interferon by blocking nuclear translocation of interferon regulatory factor 3","volume":"166","author":"Chang","year":"2013","journal-title":"Vet. Microbiol"},{"key":"2023012712380006600_bty420-B10","first-page":"803","article-title":"An O(n(5)) algorithm for MFE prediction of kissing hairpins and 4-chains in nucleic acids","volume":"16","author":"Chen","year":"2009","journal-title":"JCB"},{"key":"2023012712380006600_bty420-B11","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":"2023012712380006600_bty420-B12","doi-asserted-by":"crossref","first-page":"22.","DOI":"10.1186\/1471-2105-13-22","article-title":"Analysis of energy-based algorithms for RNA secondary structure prediction","volume":"13","author":"Hajiaghayi","year":"2012","journal-title":"BMC Bioinformatics"},{"key":"2023012712380006600_bty420-B13","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":"2023012712380006600_bty420-B14","author":"Jabbari","year":"2015"},{"key":"2023012712380006600_bty420-B15","doi-asserted-by":"crossref","first-page":"147.","DOI":"10.1186\/1471-2105-15-147","article-title":"A fast and robust iterative algorithm for prediction of RNA pseudoknotted secondary structures","volume":"15","author":"Jabbari","year":"2014","journal-title":"BMC Bioinformatics"},{"key":"2023012712380006600_bty420-B16","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1089\/cmb.2007.0198","article-title":"Novel and efficient RNA secondary structure prediction using hierarchical folding","volume":"15","author":"Jabbari","year":"2008","journal-title":"J. Comput. Biol"},{"key":"2023012712380006600_bty420-B17","doi-asserted-by":"crossref","first-page":"3742","DOI":"10.1093\/nar\/gky046","article-title":"Structural analyses of NEAT1 lncRNAs suggest long-range RNA interactions that may contribute to paraspeckle architecture","volume":"46","author":"Lin","year":"2018","journal-title":"Nucleic Acids Res"},{"key":"2023012712380006600_bty420-B18","author":"Lyngso","year":"2000"},{"key":"2023012712380006600_bty420-B19","doi-asserted-by":"crossref","first-page":"686","DOI":"10.1128\/jvi.71.1.686-696.1997","article-title":"Kissing of the two predominant hairpin loops in the coxsackie B virus 3\u2019 untranslated region is the essential structural feature of the origin of replication required for negative-strand RNA synthesis","volume":"71","author":"Melchers","year":"1997","journal-title":"J. Virol"},{"key":"2023012712380006600_bty420-B20","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1038\/nrg2521","article-title":"Long non-coding RNAs: insights into functions","volume":"10","author":"Mercer","year":"2009","journal-title":"Nat. Rev. Genet"},{"key":"2023012712380006600_bty420-B21","doi-asserted-by":"crossref","first-page":"39.","DOI":"10.1186\/1748-7188-5-39","article-title":"Sparsification of RNA structure prediction including pseudoknots","volume":"5","author":"M\u00f6hl","year":"2010","journal-title":"Algorithms Mol. Biol"},{"key":"2023012712380006600_bty420-B22","doi-asserted-by":"crossref","first-page":"3731","DOI":"10.1016\/j.jmb.2013.02.030","article-title":"Rise of the RNA machines: exploring the structure of long non-coding RNAs","volume":"425","author":"Novikova","year":"2013","journal-title":"J. Mol. Biol"},{"key":"2023012712380006600_bty420-B23","doi-asserted-by":"crossref","first-page":"6309","DOI":"10.1073\/pnas.77.11.6309","article-title":"Fast algorithm for predicting the secondary structure of single-stranded RNA","volume":"77","author":"Nussinov","year":"1980","journal-title":"Proceed. Natl. Acad. Sci. USA"},{"key":"2023012712380006600_bty420-B24","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1089\/cmb.2006.0108","article-title":"Parsing nucleic acid pseudoknotted secondary structure: algorithm and applications","volume":"14","author":"Rastegari","year":"2007","journal-title":"J. Comput. Biol"},{"key":"2023012712380006600_bty420-B25","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 Bioinformatics"},{"key":"2023012712380006600_bty420-B26","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":"JMB"},{"key":"2023012712380006600_bty420-B27","first-page":"473","volume-title":"Proceedings of RECOMB 2010, Volume 6044 of Lecture Notes in Computer Science","author":"Salari","year":"2010"},{"key":"2023012712380006600_bty420-B28","doi-asserted-by":"crossref","first-page":"i85","DOI":"10.1093\/bioinformatics\/btr215","article-title":"IPknot: fast and accurate prediction of RNA secondary structures with pseudoknots using integer programming","volume":"27","author":"Sato","year":"2011","journal-title":"Bioinformatics"},{"key":"2023012712380006600_bty420-B29","first-page":"321","volume-title":"Combinatorial Pattern Matching, Volume 7354 of Lecture Notes in Computer Science","author":"Sheikh","year":"2012"},{"key":"2023012712380006600_bty420-B30","doi-asserted-by":"crossref","first-page":"3058","DOI":"10.1093\/bioinformatics\/bts575","article-title":"Predicting pseudoknotted structures across two RNA sequences","volume":"28","author":"Sperschneider","year":"2012","journal-title":"Bioinformatics"},{"key":"2023012712380006600_bty420-B31","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/S0304-3975(98)00090-5","article-title":"Tree adjoining grammars for RNA structure prediction","volume":"210","author":"Uemura","year":"1999","journal-title":"Theor. Comput. Sci"},{"key":"2023012712380006600_bty420-B32","doi-asserted-by":"crossref","first-page":"1521","DOI":"10.1128\/JVI.76.3.1521-1526.2002","article-title":"Kissing interaction between 3? Noncoding and coding sequences is essential for porcine arterivirus RNA replication","volume":"76","author":"Verheije","year":"2002","journal-title":"J. Virol"},{"key":"2023012712380006600_bty420-B33","first-page":"856","article-title":"A study of accessible motifs and RNA folding complexity","volume":"14","author":"Wexler","year":"2007","journal-title":"JCB"},{"key":"2023012712380006600_bty420-B34","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1186\/s13015-016-0071-y","article-title":"Sparse RNA folding revisited: space-efficient minimum free energy structure prediction","volume":"11","author":"Will","year":"2016","journal-title":"Algorithms Mol. Biol"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/34\/22\/3849\/48921381\/bioinformatics_34_22_3849.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/34\/22\/3849\/48921381\/bioinformatics_34_22_3849.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T13:28:47Z","timestamp":1674826127000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/34\/22\/3849\/5026652"}},"subtitle":[],"editor":[{"given":"Alfonso","family":"Valencia","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2018,6,1]]},"references-count":34,"journal-issue":{"issue":"22","published-print":{"date-parts":[[2018,11,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bty420","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2018,11,15]]},"published":{"date-parts":[[2018,6,1]]}}}