Search

BackgroundRNA features a highly negatively charged phosphate backbone that attracts a of cloud 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 by currently available secondary stucture prediction algorithms. Combining Debye-Hückel potentials for line charges and Manning’s counter-ion condensation theory, Einertet al. [Biophys. J.100: 2745-2753 (2011)] modeled the energetic effects contributions monovalent cations on loops and helices.ResultsThe model of Einertet al. is adapted to match the structure of the dynamic programming recursion of RNA secondary structure prediction algorithms. An empirical term describing the dependence 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 theViennaRNApackage 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.ConclusionThe new feature in theViennaRNApackage 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.AvailabilityCorrections for the concentration of monovalent cations are available in theViennaRNApackage starting from version 2.6.0.

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.

The simplest class of structures formed by \(N\ge 2\) interacting RNAs consists of all crossing-free base pairs formed over linear arrangements of the constituent RNA sequences. For each permutation of the N strands the structure prediction problem is algorithmically very similar – but not identical – to folding of a single, contiguous RNA. The differences arise from two sources: First, “nicks”, i.e., the transitions from one to the next piece of RNA, need to be treated with special care. Second, the connectedness of the structures needs to guaranteed. For the forward recursions, i.e., the computation of folding energies or partition functions, these modifications are rather straightforward and retain the cubic time complexity of the well-known folding algorithms. This is not the case for a straightforward implementation of the corresponding outside recursion, which becomes quartic. Cubic running times, however, can be restored by introducing linear-size auxiliary arrays. Asymptotically, the extra effort over the corresponding algorithms for a single RNA sequence of the same length is negligible in both time and space. An implementation within the framework of the ViennaRNA package conforms to the theoretical performance bounds and provides access to several algorithmic variants, include the handling of user-defined hard and soft constraints.

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.

We add CUDA GPU C program code to RNAfold to enable both it to be run on nVidia gaming graphics hardware and so that many thousands of RNA secondary structures can be computed in parallel. RNAfold predicts the folding pattern for RNA molecules by using O(n3) dynamic programming matrices to minimise the free energy of treating them as a sequence of bases. We benchmark RNAfold on RNA STRAND and artificial sequences of upto 30 000 bases on two GPUs and a GPGPU Tesla. The speed up is variable but up to 14 times.

Grow and graft genetic programming (GGGP) evolves more than 50000 parameters in a state-of-the-art C program to make functional source code changes which give more accurate predictions of how RNA molecules fold up. Genetic improvement updates 29% of the dynamic programming free energy model parameters. In most cases (50.3%) GI gives better results on 4655 known secondary structures from RNA_STRAND (29.0% are worse and 20.7% are unchanged). Indeed it also does better than parameters recommended by Andronescu, M., et al.: Bioinformatics 23(13) (2007) i19–i28.

RNAfold predicts the secondary structure of RNA molecules from their base sequence. We apply a mixture of manual and automated genetic improvements to its C source. GI gives a 1.6% improvement to parallel SSE4.1 code. The automatic programming evolutionary system has access to Intel library code and previous revisions. On 4 666 curated structures from RNA_STRAND, GGGP gives a combined speed up of 31.9%, with no loss of accuracy (GI code run 1.4 1011 times).

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.

G-quadruplexes are abundant locally stable structural elements in nucleic acids. The combinatorial theory of RNA structures and the dynamic programming algorithms for RNA secondary structure prediction are extended here to incorporate G-quadruplexes using a simple but plausible energy model. With preliminary energy parameters, we find that the overwhelming majority of putative quadruplex-forming sequences in the human genome are likely to fold into canonical secondary structures instead. Stable G-quadruplexes are strongly enriched, however, in the 5ÊUTR of protein coding mRNAs.

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. Electronic supplementary material The online version of this article (doi:10.1186/s13015-016-0070-z) contains supplementary material, which is available to authorized users.

The overwhelming majority of small nucleolar RNAs (snoRNAs) fall into two clearly defined classes characterized by distinctive secondary structures and sequence motifs. A small group of diverse ncRNAs, however, shares the hallmarks of one or both classes of snoRNAs but differs substantially from the norm in some respects. Here, we compile the available information on these exceptional cases, conduct a thorough homology search throughout the available metazoan genomes, provide improved and expanded alignments, and investigate the evolutionary histories of these ncRNA families as well as their mutual relationships.

Stem-bulge RNAs (sbRNAs) are a group of small, functionally yet uncharacterized noncoding RNAs first described in C. elegans, with a few homologous sequences postulated in C. briggsae. In this study, we report on a comprehensive survey of this ncRNA family in the phylum Nematoda. Employing homology search strategies based on both sequence and secondary structure models and a computational promoter screen we identified a total of 240 new sbRNA homologs. For the majority of these loci we identified both promoter regions and transcription termination signals characteristic for pol-III transcripts. Sequence and structure comparison with known RNA families revealed that sbRNAs are homologs of vertebrate Y RNAs. Most of the sbRNAs show the characteristic Ro protein binding motif, and contain a region highly similar to a functionally required motif for DNA replication previously thought to be unique to vertebrate Y RNAs. The single Y RNA that was previously described in C. elegans, however, does not show this motif, and in general bears the hallmarks of a highly derived family member.

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.

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.

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., Author Summary Despite the clear functional importance of structure in RNA molecules, it remains very difficult to correctly identify and annotate similar RNA structures because their sequences are often poorly conserved even for RNAs that form very similar higher-order structures. A solution is to use a metric that identifies structural motifs but this, too, is difficult because RNA structure modeling based on sequence alone is generally not very accurate. In this work, we use SHAPE chemical probing to obtain model-free information about RNA structure and then exploit this information to align RNAs by sequence. We show for ribosomal RNAs that sequence alignments based on SHAPE experimental information alone are as accurate as those that actually use sequence information. In addition, we identify regions in the 16S ribosomal RNA that form conserved secondary structures that are different from currently accepted models. These differences, rather than being errors, reveal sites of conformational flexibility that may underlie mechanistic functions in ribosome assembly and translation regulation. We anticipate that structure-informed sequence alignment and structure modeling will become broadly useful tools in RNA function analysis.

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. 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. 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.

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.

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.

Background Secondary structure forms an important intermediate level of description of nucleic acids that encapsulates the dominating part of the folding energy, is often well conserved in evolution, and is routinely used as a basis to explain experimental findings. Based on carefully measured thermodynamic parameters, exact dynamic programming algorithms can be used to compute ground states, base pairing probabilities, as well as thermodynamic properties. Results The ViennaRNA Package has been a widely used compilation of RNA secondary structure related computer programs for nearly two decades. Major changes in the structure of the standard energy model, the Turner 2004 parameters, the pervasive use of multi-core CPUs, and an increasing number of algorithmic variants prompted a major technical overhaul of both the underlying RNAlib and the interactive user programs. New features include an expanded repertoire of tools to assess RNA-RNA interactions and restricted ensembles of structures, additional output information such as centroid structures and maximum expected accuracy structures derived from base pairing probabilities, or z-scores for locally stable secondary structures, and support for input in fasta format. Updates were implemented without compromising the computational efficiency of the core algorithms and ensuring compatibility with earlier versions. Conclusions The ViennaRNA Package 2.0, supporting concurrent computations via OpenMP, can be downloaded from http://www.tbi.univie.ac.at/RNA.

Objectives: The analysis of individual cell fates within a population of stem and progenitor cells is still a major experimental challenge in stem cell biology. However, new monitoring techniques, such as high-resolution time-lapse video microscopy, facilitate tracking and quantitative analysis of single cells and their progeny. Information on cellular development, divisional history and differentiation are naturally comprised into a pedigree-like structure, denoted as cellular genealogy. To extract reliable information concerning effecting variables and control mechanisms underlying cell fate decisions, it is necessary to analyse a large number of cellular genealogies. Materials and Methods: Here, we propose a set of statistical measures that are specifically tailored for the analysis of cellular genealogies. These measures address the degree and symmetry of cellular expansion, as well as occurrence and correlation of characteristic events such as cell death. Furthermore, we discuss two different methods for reconstruction of lineage fate decisions and show their impact on the interpretation of asymmetric developments. In order to illustrate these techniques, and to circumvent the present shortage of available experimental data, we obtain cellular genealogies from a single-cell-based mathematical model of haematopoietic stem cell organization. Results and Conclusions: Based on statistical analysis of cellular genealogies, we conclude that effects of external variables, such as growth conditions, are imprinted in their topology. Moreover, we demonstrate that it is essential to analyse timing of cell fate-specific changes and of occurrence of cell death events in the divisional context in order to understand the mechanisms of lineage commitment.

Many experimental findings on heterogeneity, flexibility, and plasticity of tissue stem cells are currently challenging stem cell concepts that assume a cell intrinsically predefined, unidirectional differentiation program. In contrast to these classical concepts, nonhierarchical self-organizing systems provide an elegant and comprehensive alternative to explain the experimental data. Here we present the application of such a self-organizing concept to quantitatively describe the hematopoietic stem cell system. Focusing on the analysis of individual-stem-cell fates and clonal dynamics, we particularly discuss implications of the theoretical results on the interpretation of experimental findings. We demonstrate that it is possible to understand hematopoietic stem cell organization without assumptions on unidirectional developmental hierarchies, preprogrammed asymmetric division events or other assumptions implying the existence of a predetermined stem cell entity. The proposed perspective, therefore, changes the general paradigm of thinking about stem cells.