{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,13]],"date-time":"2026-07-13T10:21:10Z","timestamp":1783938070147,"version":"3.55.0"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2004,8,4]],"date-time":"2004-08-04T00:00:00Z","timestamp":1091577600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/2.0"},{"start":{"date-parts":[[2004,8,4]],"date-time":"2004-08-04T00:00:00Z","timestamp":1091577600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/2.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"abstract":"<jats:title>Abstract<\/jats:title><jats:sec>\n                        <jats:title>Background<\/jats:title>\n                        <jats:p>The general problem of RNA secondary structure prediction under the widely used thermodynamic model is known to be NP-complete when the structures considered include arbitrary pseudoknots. For restricted classes of pseudoknots, several polynomial time algorithms have been designed, where the <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>6<\/jats:sup>)time and <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>4<\/jats:sup>) space algorithm by Rivas and Eddy is currently the best available program.<\/jats:p>\n                     <\/jats:sec><jats:sec>\n                        <jats:title>Results<\/jats:title>\n                        <jats:p>We introduce the class of canonical simple recursive pseudoknots and present an algorithm that requires <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>4<\/jats:sup>) time and <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>2<\/jats:sup>) space to predict the energetically optimal structure of an RNA sequence, possible containing such pseudoknots. Evaluation against a large collection of known pseudoknotted structures shows the adequacy of the canonization approach and our algorithm.<\/jats:p>\n                     <\/jats:sec><jats:sec>\n                        <jats:title>Conclusions<\/jats:title>\n                        <jats:p>RNA pseudoknots of medium size can now be predicted reliably as well as efficiently by the new algorithm.<\/jats:p>\n                     <\/jats:sec>","DOI":"10.1186\/1471-2105-5-104","type":"journal-article","created":{"date-parts":[[2004,8,13]],"date-time":"2004-08-13T06:22:48Z","timestamp":1092378168000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":228,"title":["Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics"],"prefix":"10.1186","volume":"5","author":[{"given":"Jens","family":"Reeder","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert","family":"Giegerich","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2004,8,4]]},"reference":[{"key":"220_CR1","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/0378-1119(88)90492-1","volume":"73","author":"T Cech","year":"1988","unstructured":"Cech T: Conserved sequences and structures of group I introns: building an active site for RNA catalysis\u2013A review.\n                           Gene 1988, 73: 259\u2013271. 10.1016\/0378-1119(88)90492-1","journal-title":"Gene"},{"issue":"3","key":"220_CR2","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1093\/nar\/29.3.753","volume":"29","author":"I Barette","year":"2001","unstructured":"Barette I, Poisson G, Gendron P, Major F: Pseudoknots in prion protein mRNAs confirmed by comparative sequence analysis and pattern searching.\n                           Nucleic Acids Research 2001, 29(3):753\u2013758. 10.1093\/nar\/29.3.753","journal-title":"Nucleic Acids Research"},{"key":"220_CR3","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1038\/418122a","volume":"418","author":"C Dennis","year":"2002","unstructured":"Dennis C: The brave new world of RNA.\n                           Nature 2002, 418: 122\u2013124. 10.1038\/418122a","journal-title":"Nature"},{"key":"220_CR4","doi-asserted-by":"publisher","first-page":"591","DOI":"10.1007\/BF02459506","volume":"46","author":"M Zuker","year":"1984","unstructured":"Zuker M, Sankoff S: RNA secondary structures and their prediction.\n                           Bull Math Biol 1984, 46: 591\u2013621.","journal-title":"Bull Math Biol"},{"key":"220_CR5","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/BF00818163","volume":"125","author":"I Hofacker","year":"1994","unstructured":"Hofacker I, Fontana W, Stadler P, Bonhoeffer L, Tacker M, Schuster P: Fast folding and comparison of RNA secondary structures.\n                           Monatshefte Chemie 1994, 125: 167\u2013188.","journal-title":"Monatshefte Chemie"},{"key":"220_CR6","doi-asserted-by":"publisher","first-page":"911","DOI":"10.1006\/jmbi.1999.2700","volume":"288","author":"D Mathews","year":"1999","unstructured":"Mathews D, Sabina J, Zuker M, Turner D: Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structure.\n                           Journal of Molecular Biology 1999, 288: 911\u2013940. 10.1006\/jmbi.1999.2700","journal-title":"Journal of Molecular Biology"},{"key":"220_CR7","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.\n                           Discrete Applied Mathematics 2000, 104: 45\u201362. 10.1016\/S0166-218X(00)00186-4","journal-title":"Discrete Applied Mathematics"},{"key":"220_CR8","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1089\/106652700750050862","volume":"7","author":"RB Lyngs\u00f8","year":"2001","unstructured":"Lyngs\u00f8 RB, Pedersen CN: RNA pseudoknot prediction in energy based models.\n                           Journal of Computational Biology 2001, 7: 409\u2013428. 10.1089\/106652700750050862","journal-title":"Journal of Computational Biology"},{"issue":"8","key":"220_CR9","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1093\/bioinformatics\/14.8.691","volume":"14","author":"JE Tabaska","year":"1998","unstructured":"Tabaska JE, Cary RB, Gabow HN, Stormo GD: An RNA folding method capable of identifying pseudoknots and base triples.\n                           Bioinformatics 1998, 14(8):691\u2013699. 10.1093\/bioinformatics\/14.8.691","journal-title":"Bioinformatics"},{"key":"220_CR10","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.\n                           Bioinformatics 2004, 20: 58\u201366. 10.1093\/bioinformatics\/btg373","journal-title":"Bioinformatics"},{"key":"220_CR11","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.\n                           Journal of Molecular Biology 1999, 285: 2053\u20132068. 10.1006\/jmbi.1998.2436","journal-title":"Journal of Molecular Biology"},{"key":"220_CR12","first-page":"201","volume-title":"In Proceedings of the fourth annual international conference on computational molecular biology","author":"RB Lyngs\u00f8","year":"2000","unstructured":"Lyngs\u00f8 RB, Pedersen CN: Pseudoknots in RNA secondary structures.\n                           In Proceedings of the fourth annual international conference on computational molecular biology ACM Press 2000, 201\u2013209."},{"key":"220_CR13","first-page":"239","volume-title":"In Proc Second Asia-Pacific Bioinformatics Conference 2004","author":"J Deogun","year":"2004","unstructured":"Deogun J, Donis E, Komina O, Ma F: RNA secondary structure prediction with simple pseudoknots.\n                           In Proc Second Asia-Pacific Bioinformatics Conference 2004 2004, 239\u2013246."},{"key":"220_CR14","unstructured":"PseudoBase homepage[http:\/\/wwwbio.LeidenUniv.nl\/~Batenburg\/PKB.html]"},{"key":"220_CR15","first-page":"349","volume-title":"In Algebraic Methodology And Software Technology, 9th International Conference, AMAST 2002","author":"R Giegerich","year":"2002","unstructured":"Giegerich R, Meyer C: Algebraic Dynamic Programming.\n                           In Algebraic Methodology And Software Technology, 9th International Conference, AMAST 2002\n                           (Edited by: Kirchner H, Ringeissen C). Saint-Gilles-les-Bains, Reunion Island, France: Springer LNCS 2422 2002, 349\u2013364."},{"key":"220_CR16","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1007\/3-540-45123-4_6","volume-title":"In Proc Combinatorial Pattern Matching","author":"R Giegerich","year":"2000","unstructured":"Giegerich R: Explaining and controlling ambiguity in dynamic programming.\n                           In Proc Combinatorial Pattern Matching Springer Verlag 2000, 46\u201359."},{"key":"220_CR17","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1002\/(SICI)1097-0282(199902)49:2<145::AID-BIP4>3.0.CO;2-G","volume":"49","author":"S Wuchty","year":"1998","unstructured":"Wuchty S, Fontana W, Hofacker I, Schuster P: Complete suboptimal folding of RNA and the stability of secondary structures.\n                           Biopolymers 1998, 49: 145\u2013165. Publisher Full Text 10.1002\/(SICI)1097-0282(199902)49:2%3C145::AID-BIP4%3E3.3.CO;2-7","journal-title":"Biopolymers"},{"key":"220_CR18","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1006\/jmbi.1999.3001","volume":"293","author":"I Tinoco Jr","year":"1999","unstructured":"Tinoco I Jr, Bustamante C: How RNA folds.\n                           Journal of Molecular Biology 1999, 293: 271\u2013281. 10.1006\/jmbi.1999.3001","journal-title":"Journal of Molecular Biology"},{"issue":"4","key":"220_CR19","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.\n                           Bioinformatics 2000, 16(4):334\u2013340. 10.1093\/bioinformatics\/16.4.334","journal-title":"Bioinformatics"},{"key":"220_CR20","doi-asserted-by":"publisher","first-page":"66","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.\n                           Bioinformatics 2003, 19: 66\u201373. 10.1093\/bioinformatics\/btg1007","journal-title":"Bioinformatics"},{"issue":"3","key":"220_CR21","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/j.scico.2003.12.005","volume":"51","author":"R Giegerich","year":"2004","unstructured":"Giegerich R, Meyer C, Steffen P: A discipline of dynamic programming over sequence data.\n                           Science of Computer Programming 2004, 51(3):215\u2013263. 10.1016\/j.scico.2003.12.005","journal-title":"Science of Computer Programming"},{"issue":"22","key":"220_CR22","doi-asserted-by":"publisher","first-page":"4724","DOI":"10.1093\/nar\/29.22.4724","volume":"29","author":"T Macke","year":"2001","unstructured":"Macke T, Ecker D, Gutell R, Gautheret D, Case D, Sampath R: RNAMotif, an RNA secondary structure definition and search algorithm.\n                           Nucleid Acids Research 2001, 29(22):4724\u20134735. 10.1093\/nar\/29.22.4724","journal-title":"Nucleid Acids Research"},{"key":"220_CR23","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1093\/bioinformatics\/16.8.665","volume":"16","author":"R Giegerich","year":"2000","unstructured":"Giegerich R: A systematic approach to dynamic programming in bioinformatics.\n                           Bioinformatics 2000, 16: 665\u2013677. 10.1093\/bioinformatics\/16.8.665","journal-title":"Bioinformatics"},{"key":"220_CR24","volume-title":"PhD thesis, Universit\u00e4t Bielefeld, Technische Fakult\u00e4t","author":"D Evers","year":"2003","unstructured":"Evers D: RNA folding via algebraic dynamic programming.\n                           PhD thesis, Universit\u00e4t Bielefeld, Technische Fakult\u00e4t 2003."},{"key":"220_CR25","unstructured":"Algebraic Dynamic Programming home page[http:\/\/bibiserv.techfak.uni-bielefeld.de\/adp]"},{"key":"220_CR26","doi-asserted-by":"publisher","first-page":"1664","DOI":"10.1002\/jcc.10296","volume":"24","author":"R Dirks","year":"2003","unstructured":"Dirks R, Pierce NA: A partition function algorithm for nucleic acid secondary structure including pseudoknots.\n                           Journal of Computational Chemistry 2003, 24: 1664\u20131677. 10.1002\/jcc.10296","journal-title":"Journal of Computational Chemistry"},{"key":"220_CR27","doi-asserted-by":"publisher","first-page":"609","DOI":"10.1017\/S135583829998189X","volume":"5","author":"AP Gultyaev","year":"1999","unstructured":"Gultyaev AP, van Batenburg F, Pleij C: An approximation of loop free energy values of RNA H-pseudoknots.\n                           RNA 1999, 5: 609\u2013617. 10.1017\/S135583829998189X","journal-title":"RNA"},{"issue":"4","key":"220_CR28","first-page":"333","volume":"13","author":"D Searls","year":"1997","unstructured":"Searls D: Linguistic approaches to biological sequences.\n                           CABIOS 1997, 13(4):333\u2013344.","journal-title":"CABIOS"},{"key":"220_CR29","first-page":"143","volume-title":"In Proceedings 4th ISMB","author":"F Lefebvre","year":"1996","unstructured":"Lefebvre F: A grammar-based unification of several alignment and folding algorithms.\n                           In Proceedings 4th ISMB AAAI Press, Menlo Park, CA, USA 1996, 143\u2013154."},{"key":"220_CR30","first-page":"118","volume-title":"In German Conference on Bioinformatics","author":"D Evers","year":"2001","unstructured":"Evers D, Giegerich R: Reducing the conformation space in RNA structure prediction.\n                           In German Conference on Bioinformatics 2001, 118\u2013124."},{"key":"220_CR31","unstructured":"BibiServ: Bielefeld Bioinformatics Server.[http:\/\/bibiserv.techfak.uni-bielefeld.de\/]"},{"key":"220_CR32","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1038\/26912","volume":"395","author":"A Ferr\u00e9-D'Amar\u00e9","year":"1998","unstructured":"Ferr\u00e9-D'Amar\u00e9 A, Zhou K, Doudna J: Crystal structure of a hepatitis delta virus ribozyme.\n                           Nature 1998, 395: 567\u2013674. 10.1038\/26912","journal-title":"Nature"},{"issue":"2","key":"220_CR33","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1093\/bioinformatics\/19.2.299","volume":"19","author":"PD Rijk","year":"2003","unstructured":"Rijk PD, Wuyts J, Wachter RD: RnaViz2: an improved representation of RNA secondary structure.\n                           Bioinformatics 2003, 19(2):299\u2013300. 10.1093\/bioinformatics\/19.2.299","journal-title":"Bioinformatics"},{"issue":"15","key":"220_CR34","doi-asserted-by":"publisher","first-page":"6988","DOI":"10.1073\/pnas.89.15.6988","volume":"89","author":"C Tuerk","year":"1992","unstructured":"Tuerk C, MacDougal S, Gold L: RNA pseudoknots that inhibit Human Immunodeficiency Virus Type 1 Reverse Transcriptase.\n                           PNAS 1992, 89(15):6988\u20136992.","journal-title":"PNAS"},{"issue":"8","key":"220_CR35","doi-asserted-by":"crossref","first-page":"5990","DOI":"10.1128\/jvi.71.8.5990-5996.1997","volume":"71","author":"B Deiman","year":"1997","unstructured":"Deiman B, Kortlever R, Pleij C: The role of the pseudoknot at the 3' end of turnip yellow mosaic virus RNA in minus-strand synthesis by the viral RNA-dependent RNA polymerase.\n                           J Virol 1997, 71(8):5990\u20135996.","journal-title":"J Virol"},{"issue":"21","key":"220_CR36","doi-asserted-by":"publisher","first-page":"7673","DOI":"10.1093\/nar\/13.21.7673","volume":"13","author":"A van Belkum","year":"1985","unstructured":"van Belkum A, Abrahams JP, Pleij CW, Bosch L: Five pseudoknots are present at the 204 nucleotides long 3' noncoding region of tobacco mosaic virus RNA.\n                           Nucleic Acid Research 1985, 13(21):7673\u20137686.","journal-title":"Nucleic Acid Research"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-5-104.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/1471-2105-5-104\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-5-104.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T12:15:42Z","timestamp":1728303342000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-5-104"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,8,4]]},"references-count":36,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2004,12]]}},"alternative-id":["220"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-5-104","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,8,4]]},"assertion":[{"value":"27 February 2004","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 August 2004","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 August 2004","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"104"}}