{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T01:11:56Z","timestamp":1773277916312,"version":"3.50.1"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"published-print":{"date-parts":[[2010,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>Although many RNA molecules contain pseudoknots, computational prediction of pseudoknotted RNA structure is still in its infancy due to high running time and space consumption implied by the dynamic programming formulations of the problem.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>In this paper, we introduce sparsification to significantly speedup the dynamic programming approaches for pseudoknotted RNA structure prediction, which also lower the space requirements. Although sparsification has been applied to a number of RNA-related structure prediction problems in the past few years, we provide the first application of sparsification to pseudoknotted RNA structure prediction specifically and to handling gapped fragments more generally - which has a much more complex recursive structure than other problems to which sparsification has been applied. We analyse how to sparsify four pseudoknot structure prediction algorithms, among those the most general method available (the Rivas-Eddy algorithm) and the fastest one (Reeder-Giegerich algorithm). In all algorithms the number of \"candidate\" substructures to be considered is reduced.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusions<\/jats:title>\n            <jats:p>Our experimental results on the sparsified Reeder-Giegerich algorithm suggest a linear speedup over the unsparsified implementation.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1748-7188-5-39","type":"journal-article","created":{"date-parts":[[2011,1,25]],"date-time":"2011-01-25T07:14:33Z","timestamp":1295939673000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["Sparsification of RNA structure prediction including pseudoknots"],"prefix":"10.1186","volume":"5","author":[{"given":"Mathias","family":"M\u00f6hl","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Raheleh","family":"Salari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Will","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Backofen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S Cenk","family":"Sahinalp","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,12,31]]},"reference":[{"issue":"4","key":"229_CR1","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1016\/j.cell.2009.02.007","volume":"136","author":"PA Sharp","year":"2009","unstructured":"Sharp PA: The centrality of RNA. Cell. 2009, 136 (4): 577-80. 10.1016\/j.cell.2009.02.007","journal-title":"Cell"},{"issue":"5871","key":"229_CR2","doi-asserted-by":"publisher","first-page":"1787","DOI":"10.1126\/science.1155472","volume":"319","author":"PP Amaral","year":"2008","unstructured":"Amaral PP, Dinger ME, Mercer TR, Mattick JS: The eukaryotic genome as an RNA machine. Science. 2008, 319 (5871): 1787-9. 10.1126\/science.1155472","journal-title":"Science"},{"issue":"6","key":"229_CR3","doi-asserted-by":"publisher","first-page":"852","DOI":"10.1101\/gr.5650707","volume":"17","author":"S Washietl","year":"2007","unstructured":"Washietl S, Pedersen JS, Korbel JO, Stocsits C, Gruber AR, Hackermuller J, Hertel J, Lindemeyer M, Reiche K, Tanzer A, Ucla C, Wyss C, Antonarakis SE, Denoeud F, Lagarde J, Drenkow J, Kapranov P, Gingeras TR, Guigo R, Snyder M, Gerstein MB, Reymond A, Hofacker IL, Stadler PF: Structured RNAs in the ENCODE selected regions of the human genome. Genome Res. 2007, 17 (6): 852-64. 10.1101\/gr.5650707","journal-title":"Genome Res"},{"issue":"Spec No 1","key":"229_CR4","doi-asserted-by":"publisher","first-page":"R17","DOI":"10.1093\/hmg\/ddl046","volume":"15","author":"JS Mattick","year":"2006","unstructured":"Mattick JS, Makunin IV: Non-coding RNA. Hum Mol Genet. 2006, 15 (Spec No 1): R17-29. 10.1093\/hmg\/ddl046","journal-title":"Hum Mol Genet"},{"issue":"6","key":"229_CR5","doi-asserted-by":"publisher","first-page":"e213.","DOI":"10.1371\/journal.pbio.0030213","volume":"3","author":"DW Staple","year":"2005","unstructured":"Staple DW, Butcher SE: Pseudoknots: RNA structures with diverse functions. PLoS Biol. 2005, 3 (6): e213.- 10.1371\/journal.pbio.0030213","journal-title":"PLoS Biol"},{"issue":"26","key":"229_CR6","doi-asserted-by":"publisher","first-page":"15310","DOI":"10.1073\/pnas.2536430100","volume":"100","author":"A Xayaphoummine","year":"2003","unstructured":"Xayaphoummine A, Bucher T, Thalmann F, Isambert H: Prediction and statistics of pseudoknots in RNA structures using exactly clustered stochastic simulations. Proc Natl Acad Sci USA. 2003, 100 (26): 15310-5. 10.1073\/pnas.2536430100","journal-title":"Proc Natl Acad Sci USA"},{"key":"229_CR7","volume-title":"Proceedings of the Fourth Annual International Conferences on Computational Molecular Biology","author":"RB Lyngso","year":"2000","unstructured":"Lyngso RB, Pedersen CNS: Pseudoknots in RNA Secondary Structures. Proceedings of the Fourth Annual International Conferences on Computational Molecular Biology. 2000, ACM Press,"},{"issue":"5","key":"229_CR8","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. J Mol Biol. 1999, 285 (5): 2053-68. 10.1006\/jmbi.1998.2436","journal-title":"J Mol Biol"},{"key":"229_CR9","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. Theor Comput Sci. 1999, 210: 277-303. 10.1016\/S0304-3975(98)00090-5","journal-title":"Theor Comput Sci"},{"key":"229_CR10","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 pseu-doknots. Discrete Appl Math. 2000, 104: 45-62. 10.1016\/S0166-218X(00)00186-4","journal-title":"Discrete Appl Math"},{"key":"229_CR11","first-page":"239","volume-title":"Proceedings of the second conference on Asia-Pacific bioinformatics","author":"JS Deogun","year":"2004","unstructured":"Deogun JS, Donis R, Komina O, Ma F: RNA secondary structure prediction with simple pseudoknots. Proceedings of the second conference on Asia-Pacific bioinformatics. 2004, 239-246. Darlinghurst, Australia, Australia: Aus-tralian Computer Society, Inc.,"},{"issue":"13","key":"229_CR12","doi-asserted-by":"publisher","first-page":"1664","DOI":"10.1002\/jcc.10296","volume":"24","author":"RM Dirks","year":"2003","unstructured":"Dirks RM, Pierce NA: A partition function algorithm for nucleic acid secondary structure including pseudoknots. J Comput Chem. 2003, 24 (13): 1664-77. 10.1002\/jcc.10296","journal-title":"J Comput Chem"},{"key":"229_CR13","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1186\/1471-2105-5-104","volume":"5","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: 104- 10.1186\/1471-2105-5-104","journal-title":"BMC Bioinformatics"},{"key":"229_CR14","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/j.tcs.2004.03.042","volume":"320","author":"A Condon","year":"2004","unstructured":"Condon A, Davy B, Rastegari B, Zhao S, Tarrant F: Classifying RNA pseudoknotted structures. Theor Comput Sci. 2004, 320: 35-50. 10.1016\/j.tcs.2004.03.042","journal-title":"Theor Comput Sci"},{"issue":"3","key":"229_CR15","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1089\/cmb.2009.0168","volume":"17","author":"M M\u00f6hl","year":"2010","unstructured":"M\u00f6hl M, Will S, Backofen R: Lifting prediction to alignment of RNA pseudoknots. J Comput Biol. 2010, 17 (3): 429-42.","journal-title":"J Comput Biol"},{"key":"229_CR16","first-page":"473","volume-title":"Proceedings of the Tenth Annual International Conferences on Computational Molecular Biology, Volume 3909 of Lect Notes Comput Sci","author":"Y Wexler","year":"2006","unstructured":"Wexler Y, Zilberstein CBZ, Ziv-Ukelson M: A Study of Accessible Motifs and RNA Folding Complexity. Proceedings of the Tenth Annual International Conferences on Computational Molecular Biology, Volume 3909 of Lect Notes Comput Sci. Edited by: Apostolico A, Guerra C, Istrail S, Pevzner PA, Waterman MS. 2006, 473-487. Springer,"},{"key":"229_CR17","first-page":"249","volume-title":"Proceedings of the 20th Symposium on Combinatorial Pattern Matching, Volume 5577 of Lect Notes Comput Sci","author":"R Backofen","year":"2009","unstructured":"Backofen R, Tsur D, Zakov S, Ziv-Ukelson M: Sparse RNA Folding: Time and Space Eficient Algorithms. Proceedings of the 20th Symposium on Combinatorial Pattern Matching, Volume 5577 of Lect Notes Comput Sci. Edited by: Kucherov G, Ukkonen E. 2009, 249-262. Springer,"},{"key":"229_CR18","first-page":"174","volume-title":"Proceedings of the 8th Workshop on Algorithms in Bioinformatics, Volume 5251 of Lect Notes Comput Sci","author":"M Ziv-Ukelson","year":"2008","unstructured":"Ziv-Ukelson M, Gat-Viks I, Wexler Y, Shamir R: A Faster Algorithm for RNA Co-folding. Proceedings of the 8th Workshop on Algorithms in Bioinformatics, Volume 5251 of Lect Notes Comput Sci. Edited by: Crandall KA, Lagergren J. 2008, 174-185. Springer,"},{"key":"229_CR19","first-page":"473","volume-title":"Proceedings iof the Fourteenth Annual International Conferences on Computational Molecular Biology, Volume 6044 of Lect Notes Comput Sci","author":"R Salari","year":"2010","unstructured":"Salari R, M\u00f6hl M, Will S, Sahinalp S, Backofen R: Time and Space Efficient RNA-RNA Interaction Prediction via Sparse Folding. Proceedings iof the Fourteenth Annual International Conferences on Computational Molecular Biology, Volume 6044 of Lect Notes Comput Sci. Edited by: Berger B. 2010, 473-490. Springer Berlin\/Heidelberg,"},{"key":"229_CR20","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1093\/nar\/28.1.201","volume":"28","author":"FH van Batenburg","year":"2000","unstructured":"van Batenburg FH, Gultyaev AP, Pleij CW, Ng J, Oliehoek J: PseudoBase: a database with RNA pseudoknots. Nucleic Acids Res. 2000, 28: 201-4. 10.1093\/nar\/28.1.201","journal-title":"Nucleic Acids Res"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1748-7188-5-39.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,2]],"date-time":"2021-09-02T22:14:11Z","timestamp":1630620851000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/1748-7188-5-39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,12]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,12]]}},"alternative-id":["229"],"URL":"https:\/\/doi.org\/10.1186\/1748-7188-5-39","relation":{},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,12]]},"assertion":[{"value":"27 October 2010","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 December 2010","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 December 2010","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"39"}}