CParty: hierarchically constrained partition function of RNA pseudoknots
Open Access
- 19 December 2024
- journal article
- research article
- Published by Oxford University Press (OUP) in Bioinformatics
- Vol. 41 (1)
Abstract
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’s 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 in the RNA length n. 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’s advantages over classical pseudoknot prediction to 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 of S that extend the fixed G by a disjoint pseudoknot-free structure . Thus, CParty follows the common hypothesis of hierarchical pseudoknot formation, where pseudoknots form as tertiary contacts only after a first pseudoknot-free ‘core’ 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, ie cubic time and quadratic space. Finally, by computing pseudoknotted ensemble energies, we unveil kinetics features of a therapeutic target in SARS-CoV-2. CParty is available at https://github.com/HosnaJabbari/CParty. Supplementary data are available at Bioinformatics online.
Keywords
This publication has 50 references indexed in Scilit:
- Secondary Structure Prediction of Interacting RNA MoleculesJournal of Molecular Biology, 2005
- Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamicsBMC Bioinformatics, 2004
- Incorporating chemical modification constraints into a dynamic programming algorithm for prediction of RNA secondary structureProceedings of the National Academy of Sciences, 2004
- A statistical sampling algorithm for RNA secondary structure predictionNucleic Acids Research, 2003
- A partition function algorithm for nucleic acid secondary structure including pseudoknotsJournal of Computational Chemistry, 2003
- A systematic approach to dynamic programming in bioinformaticsBioinformatics, 2000
- How RNA foldsJournal of Molecular Biology, 1999
- A dynamic programming algorithm for RNA structure prediction including pseudoknots 1 1Edited by I. TinocoJournal of Molecular Biology, 1999
- Statistics of RNA secondary structuresBiopolymers, 1993
- Optimal computer folding of large RNA sequences using thermodynamics and auxiliary informationNucleic Acids Research, 1981