CParty: Hierarchically Constrained Partition Function of RNA Pseudoknots
Preprint
Abstract
Biologically relevant RNA secondary structures are routinely predicted by efficient dynamic programming algorithmsthat minimize their free energy. Starting from such algorithms, one can devise partition function algorithms, which enable stochastic perspectives on RNA structure ensembles. As most prominent example McCaskill's partition function algorithm is derived from pseudoknot-free energy minimization. While this algorithm became hugely successful for the stochastic analysis of pseudoknot-free RNA structure, 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(n^5) in the RNA length n. In this article, 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 stochastic analysis. In only cubic time, it computes the hierarchically constrained partition function over pseudoknotted density-2 structures G U G', composed of pseudoknot-free parts G and G', where G is given. Thus, it follows the common hypothesis of hierarchical pseudoknot formation, where pseudoknots form as tertiary contacts only after a first pseudoknot-free 'core' G. Like HFold, CParty is very efficient, achieving the low complexity of the pseudoknot-free algorithm. Finally, by computing pseudoknotted ensemble energies, we unveil kinetics features of a therapeutic target in SARS-CoV-2. Availibility: CParty is available at https://github.com/HosnaJabbari/CParty.Keywords
This publication has 32 references indexed in Scilit:
- A Combinatorial Framework for Designing (Pseudoknotted) RNA Algorithms2011
- NUPACK: Analysis and design of nucleic acid systemsJournal of Computational Chemistry, 2010
- HFold: RNA Pseudoknotted Secondary Structure Prediction Using Hierarchical FoldingLecture Notes in Computer Science, 2007
- Prediction of RNA secondary structure by free energy minimizationCurrent Opinion in Structural Biology, 2006
- A partition function algorithm for nucleic acid secondary structure including pseudoknotsJournal of Computational Chemistry, 2003
- Dynamic programming algorithms for RNA secondary structure prediction with pseudoknotsDiscrete Applied Mathematics, 2000
- How RNA foldsJournal of Molecular Biology, 1999
- Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structureJournal of Molecular Biology, 1999
- A dynamic programming algorithm for RNA structure prediction including pseudoknots 1 1Edited by I. TinocoJournal of Molecular Biology, 1999
- The equilibrium partition function and base pair binding probabilities for RNA secondary structureBiopolymers, 1990