CParty: Conditional partition function for density-2RNA pseudoknots

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 most prominent example McCaskills 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(n5) 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 HFolds 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 {cup} 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. AvailibilityCParty is available at https://github.com/HosnaJabbari/CParty.