{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T02:26:00Z","timestamp":1774491960414,"version":"3.50.1"},"reference-count":51,"publisher":"Oxford University Press (OUP)","issue":"1","license":[{"start":{"date-parts":[[2024,12,19]],"date-time":"2024-12-19T00:00:00Z","timestamp":1734566400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024,12,26]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>Biologically relevant RNA secondary structures are routinely predicted by efficient dynamic programming algorithms that minimize their free energy. Starting from such algorithms, one can devise partition function algorithms, which enable stochastic perspectives on RNA structure ensembles. As the most prominent example, McCaskill\u2019s partition function algorithm is derived from pseudoknot-free energy minimization. While this algorithm became hugely successful for the analysis of pseudoknot-free RNA structure ensembles, as of yet there exists only one pseudoknotted partition function implementation, which covers only simple pseudoknots and comes with a borderline-prohibitive complexity of O(n5) in the RNA length n.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>Here, we develop a partition function algorithm corresponding to the hierarchical pseudoknot prediction of HFold, which performs exact optimization in a realistic pseudoknot energy model. In consequence, our algorithm CParty carries over HFold\u2019s advantages over classical pseudoknot prediction in characterizing the Boltzmann ensemble at equilibrium. Given an RNA sequence S and a pseudoknot-free structure G, CParty computes the partition function over all possibly pseudoknotted density-2 structures G\u222aG\u2032 of S that extend the fixed G by a disjoint pseudoknot-free structure G\u2032. Thus, CParty follows the common hypothesis of hierarchical pseudoknot formation, where pseudoknots form as tertiary contacts only after a first pseudoknot-free \u201ccore\u201d G and we call the computed partition function hierarchically constrained (by G). Like HFold, the dynamic programming algorithm CParty is very efficient, achieving the low complexity of the pseudoknot-free algorithm, i.e. cubic time and quadratic space. Finally, by computing pseudoknotted ensemble energies, we unveil kinetics features of a therapeutic target in SARS-CoV-2.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>CParty is available at https:\/\/github.com\/HosnaJabbari\/CParty.<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btae748","type":"journal-article","created":{"date-parts":[[2024,12,19]],"date-time":"2024-12-19T20:35:29Z","timestamp":1734640529000},"source":"Crossref","is-referenced-by-count":3,"title":["CParty: hierarchically constrained partition function of RNA pseudoknots"],"prefix":"10.1093","volume":"41","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 1H9,","place":["Canada"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luke","family":"Trinity","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Victoria, Victoria, British Columbia V8P 5C2,","place":["Canada"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ulrike","family":"Stege","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Victoria, Victoria, British Columbia V8P 5C2,","place":["Canada"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7615-3930","authenticated-orcid":false,"given":"Yann","family":"Ponty","sequence":"additional","affiliation":[{"name":"Institut Polytechnique de Paris, 91120 Palaiseau, Paris,","place":["France"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Will","sequence":"additional","affiliation":[{"name":"Institut Polytechnique de Paris, 91120 Palaiseau, Paris,","place":["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 1H9,","place":["Canada"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2024,12,19]]},"reference":[{"key":"2025010821512587200_btae748-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":"2025010821512587200_btae748-B2","doi-asserted-by":"publisher","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":"J Mol Biol"},{"key":"2025010821512587200_btae748-B3","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":"2025010821512587200_btae748-B4","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":"2025010821512587200_btae748-B5","first-page":"7007","article-title":"Ribosomal frameshifting and transcriptional slippage: from genetic steganography and cryptography to adventitious use","volume":"44","author":"Atkins","year":"2016","journal-title":"Nucleic Acids Res"},{"key":"2025010821512587200_btae748-B6","doi-asserted-by":"publisher","first-page":"W39","DOI":"10.1093\/nar\/gkv416","article-title":"The meme suite","volume":"43","author":"Bailey","year":"2015","journal-title":"Nucleic Acids Res"},{"key":"2025010821512587200_btae748-B7","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 Bioinformatics"},{"key":"2025010821512587200_btae748-B8","doi-asserted-by":"crossref","first-page":"12706","DOI":"10.1073\/pnas.0905046106","article-title":"Triplex structures in an RNA pseudoknot enhance mechanical stability and increase efficiency of \u22121 ribosomal frameshifting","volume":"106","author":"Chen","year":"2009","journal-title":"Proc Natl Acad Sci USA"},{"key":"2025010821512587200_btae748-B9","doi-asserted-by":"publisher","first-page":"803","DOI":"10.1089\/cmb.2008.0219","article-title":"An O(n5) 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":"2025010821512587200_btae748-B10","doi-asserted-by":"crossref","first-page":"17349","DOI":"10.1073\/pnas.0906625106","article-title":"Assembly mechanisms of RNA pseudoknots are determined by the stabilities of constituent secondary structures. PNAS","volume":"106","author":"Cho","year":"2009","journal-title":"Proc Natl Acad Sci U S A"},{"key":"2025010821512587200_btae748-B11","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":"2025010821512587200_btae748-B12","doi-asserted-by":"crossref","first-page":"7280","DOI":"10.1093\/nar\/gkg938","article-title":"A statistical sampling algorithm for RNA secondary structure prediction","volume":"31","author":"Ding","year":"2003","journal-title":"Nucleic Acids Res"},{"key":"2025010821512587200_btae748-B13","doi-asserted-by":"crossref","first-page":"661","DOI":"10.1002\/wrna.1126","article-title":"Mechanisms and implications of programmed translational frameshifting","volume":"3","author":"Dinman","year":"2012","journal-title":"Wiley Interdiscip Rev RNA"},{"key":"2025010821512587200_btae748-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":"2025010821512587200_btae748-B15","doi-asserted-by":"crossref","first-page":"1389","DOI":"10.1002\/bip.360330909","article-title":"Statistics of RNA secondary structures","volume":"33","author":"Fontana","year":"1993","journal-title":"Biopolymers"},{"key":"2025010821512587200_btae748-B16","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1093\/bioinformatics\/16.8.665","article-title":"A systematic approach to dynamic programming in bioinformatics","volume":"16","author":"Giegerich","year":"2000","journal-title":"Bioinformatics"},{"key":"2025010821512587200_btae748-B17","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1006\/bulm.1998.0085","article-title":"RNA structures with pseudo-knots: graph-theoretical, combinatorial, and statistical properties","volume":"61","author":"Haslinger","year":"1999","journal-title":"Bull Math Biol"},{"key":"2025010821512587200_btae748-B18","doi-asserted-by":"crossref","first-page":"584","DOI":"10.1016\/j.molcel.2020.12.041","article-title":"Comprehensive in vivo secondary structure of the SARS-CoV-2 genome reveals novel regulatory motifs and mechanisms","volume":"81","author":"Huston","year":"2021","journal-title":"Mol Cell"},{"key":"2025010821512587200_btae748-B19","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":"2025010821512587200_btae748-B20","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":"2025010821512587200_btae748-B21","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1089\/cmb.20070198","article-title":"Novel and efficient RNA secondary structure prediction using hierarchical folding","volume":"15","author":"Jabbari","year":"2008","journal-title":"J Comput Biol"},{"key":"2025010821512587200_btae748-B22","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":"2025010821512587200_btae748-B23","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1261\/rna.078825.121","article-title":"Crystal structure of the severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2) frameshifting pseudoknot","volume":"28","author":"Jones","year":"2022","journal-title":"RNA"},{"key":"2025010821512587200_btae748-B24","doi-asserted-by":"crossref","first-page":"10741","DOI":"10.1074\/jbc.AC120.013449","article-title":"Structural and functional conservation of the programmed \u22121 ribosomal frameshift signal of SARS coronavirus 2 (SARS-CoV-2)","volume":"295","author":"Kelly","year":"2020","journal-title":"J Biol Chem"},{"key":"2025010821512587200_btae748-B25","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":"2025010821512587200_btae748-B26","doi-asserted-by":"crossref","first-page":"1","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":"2025010821512587200_btae748-B27","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1145\/332306.332551","volume-title":"Proceedings of the Fourth Annual International Conference on Computational Molecular Biology","author":"Lyngs\u00f8","year":"2000"},{"key":"2025010821512587200_btae748-B28","doi-asserted-by":"crossref","first-page":"12436","DOI":"10.1093\/nar\/gkaa1053","article-title":"Genome-wide mapping of SARS-CoV-2 RNA structures identifies therapeutically-relevant elements","volume":"48","author":"Manfredonia","year":"2020","journal-title":"Nucleic Acids Res"},{"key":"2025010821512587200_btae748-B29","doi-asserted-by":"crossref","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. PNAS","volume":"101","author":"Mathews","year":"2004","journal-title":"Proc Natl Acad Sci U S A"},{"key":"2025010821512587200_btae748-B30","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: Original Res Biomol"},{"key":"2025010821512587200_btae748-B31","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":"2025010821512587200_btae748-B32","first-page":"250","volume-title":"Algorithms in Bioinformatics, Number 6833 in LNBI","author":"Ponty","year":"2011"},{"key":"2025010821512587200_btae748-B33","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":"2025010821512587200_btae748-B34","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":"2025010821512587200_btae748-B35","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1186\/1471-2105-11-129","article-title":"RNAstructure: software for RNA secondary structure prediction and analysis","volume":"11","author":"Reuter","year":"2010","journal-title":"Bioinformatics"},{"key":"2025010821512587200_btae748-B36","doi-asserted-by":"publisher","first-page":"e1008387","DOI":"10.1371\/journal.pcbi.1008387","article-title":"RNA structure prediction using positive and negative evolutionary information","volume":"16","author":"Rivas","year":"2020","journal-title":"PLoS Comput Biol"},{"key":"2025010821512587200_btae748-B37","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":"2025010821512587200_btae748-B38","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":"2025010821512587200_btae748-B39","doi-asserted-by":"crossref","first-page":"11404","DOI":"10.1021\/jacs.1c03003","article-title":"To knot or not to knot: multiple conformations of the SARS-CoV-2 frameshifting RNA element","volume":"143","author":"Schlick","year":"2021","journal-title":"J Am Chem Soc"},{"key":"2025010821512587200_btae748-B40","doi-asserted-by":"crossref","first-page":"1040","DOI":"10.1016\/j.bpj.2020.10.012","article-title":"Structure-altering mutations of the SARS-CoV-2 frameshifting RNA element","volume":"120","author":"Schlick","year":"2021","journal-title":"Biophys J"},{"key":"2025010821512587200_btae748-B41","first-page":"321","author":"Sheikh","year":"2012"},{"key":"2025010821512587200_btae748-B42","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1006\/jmbi.1999.3001","article-title":"How RNA folds","volume":"293","author":"Tinoco","year":"1999","journal-title":"J Mol Biol"},{"key":"2025010821512587200_btae748-B43","doi-asserted-by":"crossref","first-page":"e1010922","DOI":"10.1371\/journal.pcbi.1010922","article-title":"Shapify: paths to SARS-CoV-2 frameshifting pseudoknot","volume":"19","author":"Trinity","year":"2023","journal-title":"PLoS Comput Biol"},{"key":"2025010821512587200_btae748-B44","doi-asserted-by":"crossref","first-page":"e1011787","DOI":"10.1371\/journal.pcbi.1011787","article-title":"Tying the knot: unraveling the intricacies of the coronavirus frameshift pseudoknot","volume":"20","author":"Trinity","year":"2024","journal-title":"PLoS Comput Biol"},{"key":"2025010821512587200_btae748-B45","doi-asserted-by":"publisher","first-page":"D280","DOI":"10.1093\/nar\/gkp892","article-title":"NNDB: the nearest neighbor parameter database for predicting stability of nucleic acid secondary structure","volume":"38","author":"Turner","year":"2010","journal-title":"Nucleic Acids Res"},{"key":"2025010821512587200_btae748-B46","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":"2025010821512587200_btae748-B47","doi-asserted-by":"publisher","first-page":"534","DOI":"10.1261\/rna.049874.115","article-title":"RNA catalysis \u2013 is that it?","volume":"21","author":"Wilson","year":"2015","journal-title":"RNA"},{"key":"2025010821512587200_btae748-B48","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":"2025010821512587200_btae748-B49","doi-asserted-by":"crossref","first-page":"5113","DOI":"10.1038\/s41467-021-25357-1","article-title":"Comprehensive mapping of SARS-CoV-2 interactions in vivo reveals functional virus\u2013host interactions","volume":"12","author":"Yang","year":"2021","journal-title":"Nat Commun"},{"key":"2025010821512587200_btae748-B50","doi-asserted-by":"crossref","first-page":"747","DOI":"10.1038\/s41594-021-00653-y","article-title":"Cryo-EM and antisense targeting of the 28-kDa frameshift stimulation element from the SARS-CoV-2 RNA genome","volume":"28","author":"Zhang","year":"2021","journal-title":"Nat Struct Mol Biol"},{"key":"2025010821512587200_btae748-B51","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"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btae748\/61238982\/btae748.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btae748\/61238982\/btae748.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btae748\/61238982\/btae748.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,8]],"date-time":"2025-01-08T21:51:47Z","timestamp":1736373107000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/doi\/10.1093\/bioinformatics\/btae748\/7928840"}},"subtitle":[],"editor":[{"given":"Lenore","family":"Cowen","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2024,12,19]]},"references-count":51,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,12,26]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btae748","relation":{},"ISSN":["1367-4811"],"issn-type":[{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2025,1]]},"published":{"date-parts":[[2024,12,19]]},"article-number":"btae748"}}