{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,21]],"date-time":"2026-05-21T04:10:26Z","timestamp":1779336626641,"version":"3.51.4"},"reference-count":24,"publisher":"Oxford University Press (OUP)","issue":"5","license":[{"start":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T00:00:00Z","timestamp":1776816000000},"content-version":"vor","delay-in-days":1,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"French national research agency ANR","award":["ANR-21-CE45-0034\u201301"],"award-info":[{"award-number":["ANR-21-CE45-0034\u201301"]}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000046","name":"National Research Council of Canada","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000046","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026,5,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Motivation<\/jats:title>\n                    <jats:p>The biological functions of RNAs are tightly connected to their specific RNA structures. As experimental techniques to determine high-accuracy structures are costly and time-consuming, computational prediction approaches became indispensable for biological RNA research; most notably, the prediction of minimum free energy secondary structures. Pseudoknots are prevalent, highly significant structural motifs, yet they are commonly ignored to achieve acceptable efficiency. Existing reliable pseudoknot prediction methods typically have prohibitive complexity. A route to fast scalable pseudoknot prediction was suggested with HFold following the hierarchical folding hypothesis. Recent successful sparsification of the CCJ pseudoknot prediction algorithm in Knotty promises a further boost by introducing this technique to hierarchical folding.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>We introduce Spark, a sparsified algorithm for predicting pseudoknotted RNA structures. Spark predicts exactly the same minimum-energy structures as its predecessor HFold in the accurate HotKnots 2.0 energy model for pseudoknots. While sparsification maintains exact energy minimization and theoretical complexity, it strongly improves the time and space consumption over HFold. We benchmarked the performance of Spark against HFold and, as a pseudoknot-free baseline, RNAfold. Compared with HFold, Spark substantially reduces both run time and memory usage, while achieving run times close to RNAfold. Across all tested sequence lengths, Spark used the least memory and consistently ran faster than HFold.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Conclusion<\/jats:title>\n                    <jats:p>Combining sparsification and hierarchical folding in Spark results in an remarkably fast and memory-efficient tool for the accurate prediction of pseudoknotted RNA structures. Consequently, Spark practically enables pseudoknot prediction in large scale and even for very long RNA sequences.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Availability<\/jats:title>\n                    <jats:p>Spark software is available on Github (https:\/\/github.com\/TheCOBRALab\/Spark), with a permanent archive of the software and results deposited on Zenodo (https:\/\/doi.org\/10.5281\/zenodo.19073315).<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btag194","type":"journal-article","created":{"date-parts":[[2026,4,18]],"date-time":"2026-04-18T11:12:23Z","timestamp":1776510743000},"source":"Crossref","is-referenced-by-count":0,"title":["Spark: sparse hierarchical energy minimization for scalable prediction of RNA pseudoknots"],"prefix":"10.1093","volume":"42","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7143-1367","authenticated-orcid":false,"given":"Mateo","family":"Gray","sequence":"first","affiliation":[{"name":"Department of Biomedical Engineering, University of Alberta, Edmonton, Alberta, T6G 2R3, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Will","sequence":"additional","affiliation":[{"name":"Laboratoire d\u2019informatique de l\u2019\u00c9cole polytechnique (LIX), Institut Polytechnique de Paris, 91120 Palaiseau, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7155-2297","authenticated-orcid":false,"given":"Hosna","family":"Jabbari","sequence":"additional","affiliation":[{"name":"Department of Biomedical Engineering, University of Alberta, Edmonton, Alberta, T6G 2R3, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2026,4,21]]},"reference":[{"key":"2026052023574462000_btag194-B1","doi-asserted-by":"publisher","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":"2026052023574462000_btag194-B2","doi-asserted-by":"publisher","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":"2026052023574462000_btag194-B3","doi-asserted-by":"publisher","first-page":"803","DOI":"10.1089\/cmb.2008.0219","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":"J Comput Biol"},{"key":"2026052023574462000_btag194-B4","doi-asserted-by":"publisher","first-page":"604","DOI":"10.1016\/j.cell.2009.02.003","article-title":"The dynamic landscapes of RNA architecture","volume":"136","author":"Cruz","year":"2009","journal-title":"Cell"},{"key":"2026052023574462000_btag194-B5","doi-asserted-by":"publisher","first-page":"1664","DOI":"10.1017\/s1355838298980116","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":"2026052023574462000_btag194-B6","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1186\/s13015-024-00256-4","article-title":"SparseRNAfolD: optimized sparse RNA pseudoknot-free folding with dangle consideration","volume":"19","author":"Gray","year":"2024","journal-title":"Algorithms Mol Biol"},{"key":"2026052023574462000_btag194-B7","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/978-3-540-74126-8_30","volume-title":"Algorithms in Bioinformatics","author":"Jabbari","year":"2007"},{"key":"2026052023574462000_btag194-B8","doi-asserted-by":"publisher","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":"2026052023574462000_btag194-B9","doi-asserted-by":"publisher","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":"2026052023574462000_btag194-B10","doi-asserted-by":"publisher","first-page":"3849","DOI":"10.1093\/bioinformatics\/bty420","article-title":"Knotty: efficient and accurate prediction of complex RNA pseudoknot structures","volume":"34","author":"Jabbari","year":"2018","journal-title":"Bioinformatics"},{"key":"2026052023574462000_btag194-B11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4230\/LIPIcs.WABI.2017.12","author":"Jabbari","year":"2017"},{"key":"2026052023574462000_btag194-B12","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.gene.2005.06.037","article-title":"Regulation of translation via mRNA structure in prokaryotes and eukaryotes","volume":"361","author":"Kozak","year":"2005","journal-title":"Gene"},{"key":"2026052023574462000_btag194-B13","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1186\/1748-7188-6-26","article-title":"ViennaRNA package 2.0","volume":"6","author":"Lorenz","year":"2011","journal-title":"Algorithms Mol Biol"},{"key":"2026052023574462000_btag194-B14","doi-asserted-by":"publisher","first-page":"7287","DOI":"10.1073\/pnas.0401799101","article-title":"Incorporating chemical modification constraints into a dynamic programming algorithm for prediction of RNA secondary structure","volume":"101","author":"Matthews","year":"2004","journal-title":"Proc Natl Acad Sci USA"},{"key":"2026052023574462000_btag194-B15","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1038\/nrg3681","article-title":"Insights into RNA structure and function from genome-wide studies","volume":"15","author":"Mortimer","year":"2014","journal-title":"Nat Rev Genet"},{"key":"2026052023574462000_btag194-B16","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":"2026052023574462000_btag194-B17","doi-asserted-by":"publisher","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":"2026052023574462000_btag194-B18","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1007\/978-3-642-12683-3_31","volume-title":"Research in Computational Molecular Biology","author":"Salari","year":"2010"},{"key":"2026052023574462000_btag194-B19","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/j.tibs.2009.10.004","article-title":"Role of RNA structure in regulating pre-mRNA splicing","volume":"35","author":"Warf","year":"2010","journal-title":"Trends Biochem Sci"},{"key":"2026052023574462000_btag194-B20","doi-asserted-by":"publisher","first-page":"856","DOI":"10.1089\/cmb.2007.R020","article-title":"A study of accessible motifs and RNA folding complexity","volume":"14","author":"Wexler","year":"2007","journal-title":"J Comput Biol"},{"key":"2026052023574462000_btag194-B21","doi-asserted-by":"publisher","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"},{"key":"2026052023574462000_btag194-B22","doi-asserted-by":"publisher","first-page":"534","DOI":"10.1261\/rna.049874.115","article-title":"RNA catalysis\u2014is that it?","volume":"21","author":"Wilson","year":"2015","journal-title":"RNA"},{"key":"2026052023574462000_btag194-B23","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\/ACM Trans Comput Biol Bioinform"},{"key":"2026052023574462000_btag194-B24","doi-asserted-by":"crossref","first-page":"e0298164","DOI":"10.1371\/journal.pone.0298164","article-title":"Unveiling hidden structural patterns in the sars-cov-2 genome: computational insights and comparative analysis","volume":"19","author":"Ziesel","year":"2024","journal-title":"PLoS One"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btag194\/68131894\/btag194.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/42\/5\/btag194\/68131894\/btag194.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/42\/5\/btag194\/68131894\/btag194.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,21]],"date-time":"2026-05-21T03:58:22Z","timestamp":1779335902000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/doi\/10.1093\/bioinformatics\/btag194\/8660451"}},"subtitle":[],"editor":[{"given":"Bj\u00f6rn","family":"Gr\u00fcning","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2026,4,21]]},"references-count":24,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2026,5,3]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btag194","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2026,5]]},"published":{"date-parts":[[2026,4,21]]},"article-number":"btag194"}}