Analysing RNA-kinetics based on folding space abstraction

Classified Dynamic Programming in RNA Structure Analysis

Analysis of the folding space of RNA generally suffers from its exponential size. With classified Dynamic Programming algorithms, it is possible to alleviate this burden and to analyse the folding space of RNA in great depth. Key to classified DP is that the search space is partitioned into classes based on an on-the-fly computed feature. A class-wise evaluation is then used to compute class-wide properties, such as the lowest free energy structure for each class, or aggregate properties, such as the class' probability. In this paper we describe the well-known shape and hishape abstraction of RNA structures, their power to help better understand RNA function and related methods that are based on these abstractions.

Simulation of Folding Kinetics for Aligned RNAs

Studying the folding kinetics of an RNA can provide insight into its function and is thus a valuable method for RNA analyses. Computational approaches to the simulation of folding kinetics suffer from the exponentially large folding space that needs to be evaluated. Here, we present a new approach that combines structure abstraction with evolutionary conservation to restrict the analysis to common parts of folding spaces of related RNAs. The resulting algorithm can recapitulate the folding kinetics known for single RNAs and is able to analyse even long RNAs in reasonable time. Our program RNAliHiKinetics is the first algorithm for the simulation of consensus folding kinetics and addresses a long-standing problem in a new and unique way.

pourRNA-a time- and memory-efficient approach for the guided exploration of RNA energy landscapes

MOTIVATION

The folding dynamics of ribonucleic acids (RNAs) are typically studied via coarse-grained models of the underlying energy landscape to face the exponential growths of the RNA secondary structure space. Still, studies of exact folding kinetics based on gradient basin abstractions are currently limited to short sequence lengths due to vast memory requirements. In order to compute exact transition rates between gradient basins, state-of-the-art approaches apply global flooding schemes that require to memorize the whole structure space at once. pourRNA tackles this problem via local flooding techniques where memorization is limited to the structure ensembles of individual gradient basins.

RESULTS

Compared to the only available tool for exact gradient basin-based macro-state transition rates (namely barriers), pourRNA computes the same exact transition rates up to 10 times faster and requires two orders of magnitude less memory for sequences that are still computationally accessible for exhaustive enumeration. Parallelized computation as well as additional heuristics further speed up computations while still producing high-quality transition model approximations. The introduced heuristics enable a guided trade-off between model quality and required computational resources. We introduce and evaluate a macroscopic direct path heuristics to efficiently compute refolding energy barrier estimations for the co-transcriptionally trapped RNA sv11 of length 115 nt. Finally, we also show how pourRNA can be used to identify folding funnels and their respective energetically lowest minima.

AVAILABILITY AND IMPLEMENTATION

pourRNA is freely available at https://github.com/ViennaRNA/pourRNA.

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.

Computational approaches for alternative and transient secondary structures of ribonucleic acids

Transient and alternative structures of ribonucleic acids (RNAs) play essential roles in various regulatory processes, such as translation regulation in living cells. Because experimental analyses for RNA structures are difficult and time-consuming, computational approaches based on RNA secondary structures are promising. In this article, we review computational methods for detecting and analyzing transient/alternative secondary structures of RNAs, including static approaches based on probabilistic distributions of RNA secondary structures and dynamic approaches such as kinetic folding and folding pathway predictions.

A Model for Viral Assembly around an Explicit RNA Sequence Generates an Implicit Fitness Landscape

Previously, a stochastic model of single-stranded RNA virus assembly was created to model the cooperative effects between capsid proteins and genomic RNA that would occur in a packaging signal-mediated assembly process. In such an assembly scenario, multiple secondary structural elements from within the RNA, termed "packaging signals" (PS), contact coat proteins and facilitate efficient capsid assembly. In this work, the assembly model is extended to incorporate explicit nucleotide sequence information as well as simple aspects of RNA folding that would be occurring during the RNA/capsid coassembly process. Applying this paradigm to a dodecahedral viral capsid, a computer-derived nucleotide sequence is evolved de novo that is optimal for packaging the RNA into capsids, while also containing capacity for coding for a viral protein. Analysis of the effects of mutations on the ability of the RNA sequence to successfully package into a viral capsid reveals a complex fitness landscape where the majority of mutations are neutral with respect to packaging efficiency with a small number of mutations resulting in a near-complete loss of RNA packaging. Moreover, the model shows how attempts to ablate PSs in the viral RNA sequence may result in redundant PSs already present in the genome fulfilling their packaging role. This explains why recent experiments that attempt to ablate putative PSs may not see an effect on packaging. This modeling framework presents an example of how an implicit mapping can be made from genotype to a fitness parameter important for viral biology, i.e., viral capsid yield, with potential applications to theoretical models of viral evolution.

Design of Artificial Riboswitches as Biosensors

RNA aptamers readily recognize small organic molecules, polypeptides, as well as other nucleic acids in a highly specific manner. Many such aptamers have evolved as parts of regulatory systems in nature. Experimental selection techniques such as SELEX have been very successful in finding artificial aptamers for a wide variety of natural and synthetic ligands. Changes in structure and/or stability of aptamers upon ligand binding can propagate through larger RNA constructs and cause specific structural changes at distal positions. In turn, these may affect transcription, translation, splicing, or binding events. The RNA secondary structure model realistically describes both thermodynamic and kinetic aspects of RNA structure formation and refolding at a single, consistent level of modelling. Thus, this framework allows studying the function of natural riboswitches in silico. Moreover, it enables rationally designing artificial switches, combining essentially arbitrary sensors with a broad choice of read-out systems. Eventually, this approach sets the stage for constructing versatile biosensors.

An implementation of the Gillespie algorithm for RNA kinetics with logarithmic time update

In this paper I outline a fast method called KFOLD for implementing the Gillepie algorithm to stochastically sample the folding kinetics of an RNA molecule at single base-pair resolution. In the same fashion as the KINFOLD algorithm, which also uses the Gillespie algorithm to predict folding kinetics, KFOLD stochastically chooses a new RNA secondary structure state that is accessible from the current state by a single base-pair addition/deletion following the Gillespie procedure. However, unlike KINFOLD, the KFOLD algorithm utilizes the fact that many of the base-pair addition/deletion reactions and their corresponding rates do not change between each step in the algorithm. This allows KFOLD to achieve a substantial speed-up in the time required to compute a prediction of the folding pathway and, for a fixed number of base-pair moves, performs logarithmically with sequence size. This increase in speed opens up the possibility of studying the kinetics of much longer RNA sequences at single base-pair resolution while also allowing for the RNA folding statistics of smaller RNA sequences to be computed much more quickly.

Fast, approximate kinetics of RNA folding

In this article, we introduce the software suite Hermes, which provides fast, novel algorithms for RNA secondary structure kinetics. Using the fast Fourier transform to efficiently compute the Boltzmann probability that a secondary structure S of a given RNA sequence has base pair distance x (resp. y) from reference structure A (resp. B), Hermes computes the exact kinetics of folding from A to B in this coarse-grained model. In particular, Hermes computes the mean first passage time from the transition probability matrix by using matrix inversion, and also computes the equilibrium time from the rate matrix by using spectral decomposition. Due to the model granularity and the speed of Hermes, it is capable of determining secondary structure refolding kinetics for large RNA sequences, beyond the range of other methods. Comparative benchmarking of Hermes with other methods indicates that Hermes provides refolding kinetics of accuracy suitable for use in the computational design of RNA, an important area of synthetic biology. Source code and documentation for Hermes are available.

Thermodynamic and kinetic folding of riboswitches

Riboswitches are structured RNA regulatory elements located in the 5'-UTRs of mRNAs. Ligand-binding induces a structural rearrangement in these RNA elements, effecting events in downstream located coding sequences. Since they do not require proteins for their functions, they are ideally suited for computational analysis using the toolbox of RNA structure prediction methods. By their very definition riboswitch function depends on structural change. Methods that consider only the thermodynamic equilibrium of an RNA are therefore of limited use. Instead, one needs to employ computationally more expensive methods that consider the energy landscape and the folding dynamics on that landscape. Moreover, for the important class of kinetic riboswitches, the mechanism of riboswitch function can only be understood in the context of co-transcriptional folding. We present a computational approach to simulate the dynamic behavior of riboswitches during co-transcriptional folding in the presence and absence of a ligand. Our investigations show that the abstraction level of RNA secondary structure in combination with a dynamic folding landscape approach is expressive enough to understand how riboswitches perform their function. We apply our approach to a experimentally validated theophylline-binding riboswitch.

Profiling small RNA reveals multimodal substructural signals in a Boltzmann ensemble

As the biomedical impact of small RNAs grows, so does the need to understand competing structural alternatives for regions of functional interest. Suboptimal structure analysis provides significantly more RNA base pairing information than a single minimum free energy prediction. Yet computational enhancements like Boltzmann sampling have not been fully adopted by experimentalists since identifying meaningful patterns in this data can be challenging. Profiling is a novel approach to mining RNA suboptimal structure data which makes the power of ensemble-based analysis accessible in a stable and reliable way. Balancing abstraction and specificity, profiling identifies significant combinations of base pairs which dominate low-energy RNA secondary structures. By design, critical similarities and differences are highlighted, yielding crucial information for molecular biologists. The code is freely available via http://gtfold.sourceforge.net/profiling.html.