Phylogenetic and Chemical Probing Information as Soft Constraints in RNA Secondary Structure Prediction.

Extrinsic, experimental information can be incorporated into thermodynamics-based RNA folding algorithms in the form of pseudo-energies. Evolutionary conservation of RNA secondary structure elements is detectable in alignments of phylogenetically related sequences and provides evidence for the presence of certain base pairs that can also be converted into pseudo-energy contributions. We show that the centroid base pairs computed from a consensus folding model such as RNAalifold result in a substantial improvement of the prediction accuracy for single sequences. Evidence for specific base pairs turns out to be more informative than a position-wise profile for the conservation of the pairing status. A comparison with chemical probing data, furthermore, strongly suggests that phylogenetic base pairing data are more informative than position-specific data on (un)pairedness as obtained from chemical probing experiments. In this context we demonstrate, in addition, that the conversion of signal from probing data into pseudo-energies is possible using thermodynamic structure predictions as a reference instead of known RNA structures.

RNA Secondary Structure Thermodynamics.

Several different ways to predict RNA secondary structures have been suggested in the literature. Statistical methods, such as those that utilize stochastic context-free grammars (SCFGs), or approaches based on machine learning aim to predict the best representative structure for the underlying ensemble of possible conformations. Their parameters have therefore been trained on larger subsets of well-curated, known secondary structures. Physics-based methods, on the other hand, usually refrain from using optimized parameters. They model secondary structures from loops as individual building blocks which have been assigned a physical property instead: the free energy of the respective loop. Such free energies are either derived from experiments or from mathematical modeling. This rigorous use of physical properties then allows for the application of statistical mechanics to describe the entire state space of RNA secondary structures in terms of equilibrium probabilities. On that basis, and by using efficient algorithms, many more descriptors of the conformational state space of RNA molecules can be derived to investigate and explain the many functions of RNA molecules. Moreover, compared to other methods, physics-based models allow for a much easier extension with other properties that can be measured experimentally. For instance, small molecules or proteins can bind to an RNA and their binding affinity can be assessed experimentally. Under certain conditions, existing RNA secondary structure prediction tools can be used to model this RNA-ligand binding and to eventually shed light on its impact on structure formation and function.

Modified Nucleotides and RNA Structure Prediction.

Nucleotide modifications are occurrent in all types of RNA and play an important role in RNA structure formation and stability. Modified bases not only possess the ability to shift the RNA structure ensemble towards desired functional confirmations. By changes in the base pairing partner preference, they may even enlarge or reduce the conformational space, i.e., the number and types of structures the RNA molecule can adopt. However, most methods to predict RNA secondary structure do not provide the means to include the effect of modifications on the result. With the help of a heavily modified transfer RNA (tRNA) molecule, this chapter demonstrates how to include the effect of different base modifications into secondary structure prediction using the ViennaRNA Package. The constructive approach demonstrated here allows for the calculation of minimum free energy structure and suboptimal structures at different levels of modified base support. In particular we, show how to incorporate the isomerization of uridine to pseudouridine ( Ψ ) and the reduction of uridine to dihydrouridine (D).

A Guide to Computational Cotranscriptional Folding Featuring the SRP RNA.

Although RNA molecules are synthesized via transcription, little is known about the general impact of cotranscriptional folding in vivo. We present different computational approaches for the simulation of changing structure ensembles during transcription, including interpretations with respect to experimental data from literature. Specifically, we analyze different mutations of the E. coli SRP RNA, which has been studied comparatively well in previous literature, yet the details of which specific metastable structures form as well as when they form are still under debate. Here, we combine thermodynamic and kinetic, deterministic, and stochastic models with automated and visual inspection of those systems to derive the most likely scenario of which substructures form at which point during transcription. The simulations do not only provide explanations for present experimental observations but also suggest previously unnoticed conformations that may be verified through future experimental studies.

Modified RNAs and predictions with the ViennaRNA Package.

MOTIVATION: In living organisms, many RNA molecules are modified post-transcriptionally. This turns the widely known four-letter RNA alphabet ACGU into a much larger one with currently more than 300 known distinct modified bases. The roles for the majority of modified bases remain uncertain, but many are already well-known for their ability to influence the preferred structures that an RNA may adopt. In fact, tRNAs sometimes require certain modifications to fold into their cloverleaf shaped structure. However, predicting the structure of RNAs with base modifications is still difficult due to the lack of efficient algorithms that can deal with the extended sequence alphabet, as well as missing parameter sets that account for the changes in stability induced by the modified bases. RESULTS: We present an approach to include sparse energy parameter data for modified bases into the ViennaRNA Package. Our method does not require any changes to the underlying efficient algorithms but instead uses a set of plug-in constraints that adapt the predictions in terms of loop evaluation at runtime. These adaptations are efficient in the sense that they are only performed for loops where additional parameters are actually available for. In addition, our approach also facilitates the inclusion of more modified bases as soon as further parameters become available. AVAILABILITY AND IMPLEMENTATION: Source code and documentation are available at https://www.tbi.univie.ac.at/RNA.

Local RNA folding revisited.

Most of the functional RNA elements located within large transcripts are local. Local folding therefore serves a practically useful approximation to global structure prediction. Due to the sensitivity of RNA secondary structure prediction to the exact definition of sequence ends, accuracy can be increased by averaging local structure predictions over multiple, overlapping sequence windows. These averages can be computed efficiently by dynamic programming. Here we revisit the local folding problem, present a concise mathematical formalization that generalizes previous approaches and show that correct Boltzmann samples can be obtained by local stochastic backtracing in McCaskill's algorithms but not from local folding recursions. Corresponding new features are implemented in the ViennaRNA package to improve the support of local folding. Applications include the computation of maximum expected accuracy structures from RNAplfold data and a mutual information measure to quantify the sensitivity of individual sequence positions.

Mono-valent salt corrections for RNA secondary structures in the ViennaRNA package.

BACKGROUND: RNA features a highly negatively charged phosphate backbone that attracts a cloud of counter-ions that reduce the electrostatic repulsion in a concentration dependent manner. Ion concentrations thus have a large influence on folding and stability of RNA structures. Despite their well-documented effects, salt effects are not handled consistently by currently available secondary structure prediction algorithms. Combining Debye-Hückel potentials for line charges and Manning's counter-ion condensation theory, Einert et al. (Biophys J 100: 2745-2753, 2011) modeled the energetic contributions of monovalent cations on loops and helices. RESULTS: The model of Einert et al. is adapted to match the structure of the dynamic programming recursion of RNA secondary structure prediction algorithms. An empirical term describing the salt dependence of the duplex initiation energy is added to improve co-folding predictions for two or more RNA strands. The slightly modified model is implemented in the ViennaRNA package in such way that only the energy parameters but not the algorithmic structure is affected. A comparison with data from the literature show that predicted free energies and melting temperatures are in reasonable agreement with experiments. CONCLUSION: The new feature in the ViennaRNA package makes it possible to study effects of salt concentrations on RNA folding in a systematic manner. Strictly speaking, the model pertains only to mono-valent cations, and thus covers the most important parameter, i.e., the NaCl concentration. It remains a question for future research to what extent unspecific effects of bi- and tri-valent cations can be approximated in a similar manner. AVAILABILITY: Corrections for the concentration of monovalent cations are available in the ViennaRNA package starting from version 2.6.0.

DrTransformer: heuristic cotranscriptional RNA folding using the nearest neighbor energy model.

MOTIVATION: Folding during transcription can have an important influence on the structure and function of RNA molecules, as regions closer to the 5' end can fold into metastable structures before potentially stronger interactions with the 3' end become available. Thermodynamic RNA folding models are not suitable to predict structures that result from cotranscriptional folding, as they can only calculate properties of the equilibrium distribution. Other software packages that simulate the kinetic process of RNA folding during transcription exist, but they are mostly applicable for short sequences. RESULTS: We present a new algorithm that tracks changes to the RNA secondary structure ensemble during transcription. At every transcription step, new representative local minima are identified, a neighborhood relation is defined and transition rates are estimated for kinetic simulations. After every simulation, a part of the ensemble is removed and the remainder is used to search for new representative structures. The presented algorithm is deterministic (up to numeric instabilities of simulations), fast (in comparison with existing methods), and it is capable of folding RNAs much longer than 200 nucleotides. AVAILABILITY AND IMPLEMENTATION: This software is open-source and available at https://github.com/ViennaRNA/drtransformer. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Caveats to Deep Learning Approaches to RNA Secondary Structure Prediction.

Machine learning (ML) and in particular deep learning techniques have gained popularity for predicting structures from biopolymer sequences. An interesting case is the prediction of RNA secondary structures, where well established biophysics based methods exist. The accuracy of these classical methods is limited due to lack of experimental parameters and certain simplifying assumptions and has seen little improvement over the last decade. This makes RNA folding an attractive target for machine learning and consequently several deep learning models have been proposed in recent years. However, for ML approaches to be competitive for de-novo structure prediction, the models must not just demonstrate good phenomenological fits, but be able to learn a (complex) biophysical model. In this contribution we discuss limitations of current approaches, in particular due to biases in the training data. Furthermore, we propose to study capabilities and limitations of ML models by first applying them on synthetic data (obtained from a simplified biophysical model) that can be generated in arbitrary amounts and where all biases can be controlled. We assume that a deep learning model that performs well on these synthetic, would also perform well on real data, and vice versa. We apply this idea by testing several ML models of varying complexity. Finally, we show that the best models are capable of capturing many, but not all, properties of RNA secondary structures. Most severely, the number of predicted base pairs scales quadratically with sequence length, even though a secondary structure can only accommodate a linear number of pairs.

RNAxplorer: harnessing the power of guiding potentials to sample RNA landscapes.

MOTIVATION: Predicting the folding dynamics of RNAs is a computationally difficult problem, first and foremost due to the combinatorial explosion of alternative structures in the folding space. Abstractions are therefore needed to simplify downstream analyses, and thus make them computationally tractable. This can be achieved by various structure sampling algorithms. However, current sampling methods are still time consuming and frequently fail to represent key elements of the folding space. METHOD: We introduce RNAxplorer, a novel adaptive sampling method to efficiently explore the structure space of RNAs. RNAxplorer uses dynamic programming to perform an efficient Boltzmann sampling in the presence of guiding potentials, which are accumulated into pseudo-energy terms and reflect similarity to already well-sampled structures. This way, we effectively steer sampling toward underrepresented or unexplored regions of the structure space. RESULTS: We developed and applied different measures to benchmark our sampling methods against its competitors. Most of the measures show that RNAxplorer produces more diverse structure samples, yields rare conformations that may be inaccessible to other sampling methods and is better at finding the most relevant kinetic traps in the landscape. Thus, it produces a more representative coarse graining of the landscape, which is well suited to subsequently compute better approximations of RNA folding kinetics. AVAILABILITYAND IMPLEMENTATION: https://github.com/ViennaRNA/RNAxplorer/. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

RNA Secondary Structures with Limited Base Pair Span: Exact Backtracking and an Application.

The accuracy of RNA secondary structure prediction decreases with the span of a base pair, i.e., the number of nucleotides that it encloses. The dynamic programming algorithms for RNA folding can be easily specialized in order to consider only base pairs with a limited span L, reducing the memory requirements to O(nL), and further to O(n) by interleaving backtracking. However, the latter is an approximation that precludes the retrieval of the globally optimal structure. So far, the ViennaRNA package therefore does not provide a tool for computing optimal, span-restricted minimum energy structure. Here, we report on an efficient backtracking algorithm that reconstructs the globally optimal structure from the locally optimal fragments that are produced by the interleaved backtracking implemented in RNALfold. An implementation is integrated into the ViennaRNA package. The forward and the backtracking recursions of RNALfold are both easily constrained to structural components with a sufficiently negative z-scores. This provides a convenient method in order to identify hyper-stable structural elements. A screen of the C. elegans genome shows that such features are more abundant in real genomic sequences when compared to a di-nucleotide shuffled background model.

RNA modifications in structure prediction - Status quo and future challenges.

Chemical modifications of RNA nucleotides change their identity and characteristics and thus alter genetic and structural information encoded in the genomic DNA. tRNA and rRNA are probably the most heavily modified genes, and often depend on derivatization or isomerization of their nucleobases in order to correctly fold into their functional structures. Recent RNomics studies, however, report transcriptome wide RNA modification and suggest a more general regulation of structuredness of RNAs by this so called epitranscriptome. Modification seems to require specific substrate structures, which in turn are stabilized or destabilized and thus promote or inhibit refolding events of regulatory RNA structures. In this review, we revisit RNA modifications and the related structures from a computational point of view. We discuss known substrate structures, their properties such as sub-motifs as well as consequences of modifications on base pairing patterns and possible refolding events. Given that efficient RNA structure prediction methods for canonical base pairs have been established several decades ago, we review to what extend these methods allow the inclusion of modified nucleotides to model and study epitranscriptomic effects on RNA structures.

Predicting RNA secondary structures from sequence and probing data.

RNA secondary structures have proven essential for understanding the regulatory functions performed by RNA such as microRNAs, bacterial small RNAs, or riboswitches. This success is in part due to the availability of efficient computational methods for predicting RNA secondary structures. Recent advances focus on dealing with the inherent uncertainty of prediction by considering the ensemble of possible structures rather than the single most stable one. Moreover, the advent of high-throughput structural probing has spurred the development of computational methods that incorporate such experimental data as auxiliary information.

RNA folding with hard and soft constraints.

BACKGROUND: A large class of RNA secondary structure prediction programs uses an elaborate energy model grounded in extensive thermodynamic measurements and exact dynamic programming algorithms. External experimental evidence can be in principle be incorporated by means of hard constraints that restrict the search space or by means of soft constraints that distort the energy model. In particular recent advances in coupling chemical and enzymatic probing with sequencing techniques but also comparative approaches provide an increasing amount of experimental data to be combined with secondary structure prediction. RESULTS: Responding to the increasing needs for a versatile and user-friendly inclusion of external evidence into diverse flavors of RNA secondary structure prediction tools we implemented a generic layer of constraint handling into the ViennaRNA Package. It makes explicit use of the conceptual separation of the "folding grammar" defining the search space and the actual energy evaluation, which allows constraints to be interleaved in a natural way between recursion steps and evaluation of the standard energy function. CONCLUSIONS: The extension of the ViennaRNA Package provides a generic way to include diverse types of constraints into RNA folding algorithms. The computational overhead incurred is negligible in practice. A wide variety of application scenarios can be accommodated by the new framework, including the incorporation of structure probing data, non-standard base pairs and chemical modifications, as well as structure-dependent ligand binding.

SHAPE directed RNA folding.

SUMMARY: Chemical mapping experiments allow for nucleotide resolution assessment of RNA structure. We demonstrate that different strategies of integrating probing data with thermodynamics-based RNA secondary structure prediction algorithms can be implemented by means of soft constraints. This amounts to incorporating suitable pseudo-energies into the standard energy model for RNA secondary structures. As a showcase application for this new feature of the ViennaRNA Package we compare three distinct, previously published strategies to utilize SHAPE reactivities for structure prediction. The new tool is benchmarked on a set of RNAs with known reference structure. AVAILABILITY AND IMPLEMENTATION: The capability for SHAPE directed RNA folding is part of the upcoming release of the ViennaRNA Package 2.2, for which a preliminary release is already freely available at http://www.tbi.univie.ac.at/RNA. CONTACT: michael.wolfinger@univie.ac.at SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Model-Free RNA Sequence and Structure Alignment Informed by SHAPE Probing Reveals a Conserved Alternate Secondary Structure for 16S rRNA.

Discovery and characterization of functional RNA structures remains challenging due to deficiencies in de novo secondary structure modeling. Here we describe a dynamic programming approach for model-free sequence comparison that incorporates high-throughput chemical probing data. Based on SHAPE probing data alone, ribosomal RNAs (rRNAs) from three diverse organisms--the eubacteria E. coli and C. difficile and the archeon H. volcanii--could be aligned with accuracies comparable to alignments based on actual sequence identity. When both base sequence identity and chemical probing reactivities were considered together, accuracies improved further. Derived sequence alignments and chemical probing data from protein-free RNAs were then used as pseudo-free energy constraints to model consensus secondary structures for the 16S and 23S rRNAs. There are critical differences between these experimentally-informed models and currently accepted models, including in the functionally important neck and decoding regions of the 16S rRNA. We infer that the 16S rRNA has evolved to undergo large-scale changes in base pairing as part of ribosome function. As high-quality RNA probing data become widely available, structurally-informed sequence alignment will become broadly useful for de novo motif and function discovery.

Design criteria for synthetic riboswitches acting on transcription.

Riboswitches are RNA-based regulators of gene expression composed of a ligand-sensing aptamer domain followed by an overlapping expression platform. The regulation occurs at either the level of transcription (by formation of terminator or antiterminator structures) or translation (by presentation or sequestering of the ribosomal binding site). Due to a modular composition, these elements can be manipulated by combining different aptamers and expression platforms and therefore represent useful tools to regulate gene expression in synthetic biology. Using computationally designed theophylline-dependent riboswitches we show that 2 parameters, terminator hairpin stability and folding traps, have a major impact on the functionality of the designed constructs. These have to be considered very carefully during design phase. Furthermore, a combination of several copies of individual riboswitches leads to a much improved activation ratio between induced and uninduced gene activity and to a linear dose-dependent increase in reporter gene expression. Such serial arrangements of synthetic riboswitches closely resemble their natural counterparts and may form the basis for simple quantitative read out systems for the detection of specific target molecules in the cell.

The ViennaRNA web services.

The ViennaRNA package is a widely used collection of programs for thermodynamic RNA secondary structure prediction. Over the years, many additional tools have been developed building on the core programs of the package to also address issues related to noncoding RNA detection, RNA folding kinetics, or efficient sequence design considering RNA-RNA hybridizations. The ViennaRNA web services provide easy and user-friendly web access to these tools. This chapter describes how to use this online platform to perform tasks such as prediction of minimum free energy structures, prediction of RNA-RNA hybrids, or noncoding RNA detection. The ViennaRNA web services can be used free of charge and can be accessed via http://rna.tbi.univie.ac.at.

TSSAR: TSS annotation regime for dRNA-seq data.

BACKGROUND: Differential RNA sequencing (dRNA-seq) is a high-throughput screening technique designed to examine the architecture of bacterial operons in general and the precise position of transcription start sites (TSS) in particular. Hitherto, dRNA-seq data were analyzed by visualizing the sequencing reads mapped to the reference genome and manually annotating reliable positions. This is very labor intensive and, due to the subjectivity, biased. RESULTS: Here, we present TSSAR, a tool for automated de novo TSS annotation from dRNA-seq data that respects the statistics of dRNA-seq libraries. TSSAR uses the premise that the number of sequencing reads starting at a certain genomic position within a transcriptional active region follows a Poisson distribution with a parameter that depends on the local strength of expression. The differences of two dRNA-seq library counts thus follow a Skellam distribution. This provides a statistical basis to identify significantly enriched primary transcripts.We assessed the performance by analyzing a publicly available dRNA-seq data set using TSSAR and two simple approaches that utilize user-defined score cutoffs. We evaluated the power of reproducing the manual TSS annotation. Furthermore, the same data set was used to reproduce 74 experimentally validated TSS in H. pylori from reliable techniques such as RACE or primer extension. Both analyses showed that TSSAR outperforms the static cutoff-dependent approaches. CONCLUSIONS: Having an automated and efficient tool for analyzing dRNA-seq data facilitates the use of the dRNA-seq technique and promotes its application to more sophisticated analysis. For instance, monitoring the plasticity and dynamics of the transcriptomal architecture triggered by different stimuli and growth conditions becomes possible.The main asset of a novel tool for dRNA-seq analysis that reaches out to a broad user community is usability. As such, we provide TSSAR both as intuitive RESTful Web service ( http://rna.tbi.univie.ac.at/TSSAR) together with a set of post-processing and analysis tools, as well as a stand-alone version for use in high-throughput dRNA-seq data analysis pipelines.

Predicting RNA structure: advances and limitations.

RNA secondary structures can be predicted using efficient algorithms. A widely used software package implementing a large number of computational methods is the ViennaRNA Package. This chapter describes how to use programs from the ViennaRNA Package to perform common tasks such as prediction of minimum free-energy structures, suboptimal structures, or base pairing probabilities, and generating secondary structure plots with reliability annotation. Moreover, we present recent methods to assess the folding kinetics of an RNA via 2D projections of the energy landscape, identification of local minima and energy barriers, or simulation of RNA folding as a Markov process.