A unique secondary folding pattern for 5S RNA corresponds to the lowest energy homologous secondary structure in 17 different prokaryotes.

A general secondary structure is proposed for the 5S RNA of prokaryotic ribosomes, based on helical energy filtering calculations. We have considered all secondary structures that are common to 17 different prokaryotic 5S RNAs and for each 5S sequence calculated the (global) minimum energy secondary structure (300,000 common structures are possible for each sequence). The 17 different minimum energy secondary structures all correspond, with minor differences, to a single, secondary structure model. This is strong evidence that this general 5S folding pattern corresponds to the secondary structure of the functional 5S rRNA. The general 5S secondary structure is forked and in analogy with the cloverleaf of tRNA is named the "wishbone" model. It constant 8 double helical regions; one in the stem, four in the first, or constant arm, and three in the second arm. Four of these double helical regions are present in a model earlier proposed (1) and four additional regions not proposed by them are presented here. In the minimum energy general structure, the four helices in the constant arm are exactly 15 nucleotide pairs long. These helices are stacked in the sequences from gram-positive bacteria and probably stacked in gram-negative sequences as well. In sequences from gram-positive bacteria the length of the constant arm is maintained at 15 stacked pairs by an unusual minimum energy interaction involving a C26-G57 base pair intercalated between two adjacent helical regions.     

Detecting riboSNitches with RNA folding algorithms: a genome-wide benchmark

Ribonucleic acid (RNA) secondary structure prediction continues to be a significant challenge, in particular when attempting to model sequences with less rigidly defined structures, such as messenger and non-coding RNAs. Crucial to interpreting RNA structures as they pertain to individual phenotypes is the ability to detect RNAs with large structural disparities caused by a single nucleotide variant (SNV) or riboSNitches. A recently published human genome-wide parallel analysis of RNA structure (PARS) study identified a large number of riboSNitches as well as non-riboSNitches, providing an unprecedented set of RNA sequences against which to benchmark structure prediction algorithms. Here we evaluate 11 different RNA folding algorithms’ riboSNitch prediction performance on these data. We find that recent algorithms designed specifically to predict the effects of SNVs on RNA structure, in particular remuRNA, RNAsnp and SNPfold, perform best on the most rigorously validated subsets of the benchmark data. In addition, our benchmark indicates that general structure prediction algorithms (e.g. RNAfold and RNAstructure) have overall better performance if base pairing probabilities are considered rather than minimum free energy calculations. Although overall aggregate algorithmic performance on the full set of riboSNitches is relatively low, significant improvement is possible if the highest confidence predictions are evaluated independently.     

The computer simulation of RNA folding involving pseudoknot formation.

The algorithm and the program for the prediction of RNA secondary structure with pseudoknot formation have been proposed. The algorithm simulates stepwise folding by generating random structures using Monte Carlo method, followed by the selection of helices to final structure on the basis of both their probabilities of occurrence in a random structure and free energy parameters. The program versions have been tested on ribosomal RNA structures and on RNAs with pseudoknots evidenced by experimental data. It is shown that the simulation of folding during RNA synthesis improves the results. The introduction of pseudoknot formation permits to predict the pseudoknotted structures and to improve the prediction of long-range interactions. The computer program is rather fast and allows to predict the structures for long RNAs without using large memory volumes in usual personal computer.     

Conformational Entropy of the RNA Phosphate Backbone and Its Contribution to the Folding Free Energy

While major contributors to the free energy of RNA tertiary structures such as basepairing, base-stacking, and charge and counterion interactions have been studied extensively, little is known about the intrinsic free energy of the backbone. To assess the magnitude of the entropic strains along the phosphate backbone and their impact on the folding free energy, we have formulated a mathematical treatment for computing the volume of the main-chain torsion-angle conformation space between every pair of nucleobases along any sequence to compute the corresponding backbone entropy. To validate this method, we have compared the computed conformational entropies against a statistical free energy analysis of structures in the crystallographic database from several-thousand backbone conformations between nearest-neighbor nucleobases as well as against extensive computer simulations. Using this calculation, we analyzed the backbone entropy of several ribozymes and riboswitches and found that their entropic strains are highly localized along their sequences. The total entropic penalty due to steric congestions in the backbone for the native fold can be as high as 2.4 cal/K/mol per nucleotide for these medium and large RNAs, producing a contribution to the overall free energy of up to 0.72 kcal/mol per nucleotide. For these RNAs, we found that low-entropy high-strain residues are predominantly located at loops with tight turns and at tertiary interaction platforms with unusual structural motifs.     

Conformational Entropy of the RNA Phosphate Backbone and Its Contribution to the Folding Free Energy

While major contributors to the free energy of RNA tertiary structures such as basepairing, base-stacking, and charge and counterion interactions have been studied extensively, little is known about the intrinsic free energy of the backbone. To assess the magnitude of the entropic strains along the phosphate backbone and their impact on the folding free energy, we have formulated a mathematical treatment for computing the volume of the main-chain torsion-angle conformation space between every pair of nucleobases along any sequence to compute the corresponding backbone entropy. To validate this method, we have compared the computed conformational entropies against a statistical free energy analysis of structures in the crystallographic database from several-thousand backbone conformations between nearest-neighbor nucleobases as well as against extensive computer simulations. Using this calculation, we analyzed the backbone entropy of several ribozymes and riboswitches and found that their entropic strains are highly localized along their sequences. The total entropic penalty due to steric congestions in the backbone for the native fold can be as high as 2.4 cal/K/mol per nucleotide for these medium and large RNAs, producing a contribution to the overall free energy of up to 0.72 kcal/mol per nucleotide. For these RNAs, we found that low-entropy high-strain residues are predominantly located at loops with tight turns and at tertiary interaction platforms with unusual structural motifs.     

Topological Organization of Picornaviral Genomes: Statistical Prediction of RNA Structural Signals

We have analyzed 11 picornaviral RNA genomic sequences by optimal and suboptimal minimum free energy folding algorithms. The systematic summation of all pairing partners for each base in the suboptimal structures (P-num value) shows a distinct pattern of alternating low and high values when plotted against the sequence length and indicate regions within each genome where secondary structure(s) are likely to play a significant role in virus biology. The individual folds augmented by data from phylogenetic folds, collectively suggest some revisions of existing models for 5′-untranslated regions of cardioviruses and enteroviruses that might better explain the functions of these regions.     

Practicality and time complexity of a sparsified RNA folding algorithm

Commonly used RNA folding programs compute the minimum free energy structure of a sequence under the pseudoknot exclusion constraint. They are based on Zuker's algorithm which runs in time O(n(3)). Recently, it has been claimed that RNA folding can be achieved in average time O(n(2)) using a sparsification technique. A proof of quadratic time complexity was based on the assumption that computational RNA folding obeys the "polymer-zeta property". Several variants of sparse RNA folding algorithms were later developed. Here, we present our own version, which is readily applicable to existing RNA folding programs, as it is extremely simple and does not require any new data structure. We applied it to the widely used Vienna RNAfold program, to create sibRNAfold, the first public sparsified version of a standard RNA folding program. To gain a better understanding of the time complexity of sparsified RNA folding in general, we carried out a thorough run time analysis with synthetic random sequences, both in the context of energy minimization and base pairing maximization. Contrary to previous claims, the asymptotic time complexity of a sparsified RNA folding algorithm using standard energy parameters remains O(n(3)) under a wide variety of conditions. Consistent with our run-time analysis, we found that RNA folding does not obey the "polymer-zeta property" as claimed previously. Yet, a basic version of a sparsified RNA folding algorithm provides 15- to 50-fold speed gain. Surprisingly, the same sparsification technique has a different effect when applied to base pairing optimization. There, its asymptotic running time complexity appears to be either quadratic or cubic depending on the base composition. The code used in this work is available at: .     

Recognition of messenger RNA during translational initiation in Escherichia coli

The structural aspects of recognition by E. coli ribosomes of translational initiation regions on homologous messenger RNAs have been reviewed. Also discussed is the location of initiation region on mRNA, its confines, typical nucleotide sequences responsible for initiation signal, and the influence of RNA macrostructure on protein synthesis initiation. Most of the published DNA nucleotide sequences surrounding the start of various E. coli genes and those of its phages have been collected.     

Boltzmann ensemble features of RNA secondary structures: a comparative analysis of biological RNA sequences and random shuffles

Ensemble-based approaches to RNA secondary structure prediction have become increasingly appreciated in recent years. Here, we utilize sampling and clustering of the Boltzmann ensemble of RNA secondary structures to investigate whether biological sequences exhibit ensemble features that are distinct from their random shuffles. Representative messenger RNAs (mRNAs), structural RNAs, and precursor microRNAs (miRNAs) are analyzed for nine ensemble features. These include structure clustering features, the energy gap between the minimum free energy (MFE) and the ensemble, the numbers of high-frequency base pairs in the ensemble and in clusters, the average base-pair distance between the MFE structure and the ensemble, and between-cluster and within-cluster sums of squares. For each of the features, we observe a lack of significant distinction between mRNAs and their random shuffles. For five features, significant differences are found between structural RNAs and random counterparts. For seven features including the five for structural RNAs, much greater differences are observed between precursor miRNAs and random shuffles. These findings reveal differences in the Boltzmann structure ensemble among different types of functional RNAs. In addition, for two ensemble features, we observe distinctive, non-overlapping distributions for precursor miRNAs and random shuffles. A distributional separation can be particularly useful for the prediction of miRNA genes.     

No evidence that mRNAs have lower folding free energies than random sequences with the same dinucleotide distribution

This work investigates whether mRNA has a lower estimated folding free energy than random sequences. The free energy estimates are calculated by the mfold program for prediction of RNA secondary structures. For a set of 46 mRNAs it is shown that the predicted free energy is not significantly different from random sequences with the same dinucleotide distribution. For random sequences with the same mononucleotide distribution it has previously been shown that the native mRNA sequences have a lower predicted free energy, which indicates a more stable structure than random sequences. However, dinucleotide content is important when assessing the significance of predicted free energy as the physical stability of RNA secondary structure is known to depend on dinucleotide base stacking energies. Even known RNA secondary structures, like tRNAs, can be shown to have predicted free energies indistinguishable from randomized sequences. This suggests that the predicted free energy is not always a good determinant for RNA folding.     

Evidence that microRNA precursors, unlike other non-coding RNAs, have lower folding free energies than random sequences

MOTIVATION: Most non-coding RNAs are characterized by a specific secondary and tertiary structure that determines their function. Here, we investigate the folding energy of the secondary structure of non-coding RNA sequences, such as microRNA precursors, transfer RNAs and ribosomal RNAs in several eukaryotic taxa. Statistical biases are assessed by a randomization test, in which the predicted minimum free energy of folding is compared with values obtained for structures inferred from randomly shuffling the original sequences. RESULTS: In contrast with transfer RNAs and ribosomal RNAs, the majority of the microRNA sequences clearly exhibit a folding free energy that is considerably lower than that for shuffled sequences, indicating a high tendency in the sequence towards a stable secondary structure. A possible usage of this statistical test in the framework of the detection of genuine miRNA sequences is discussed.     

Statistics of RNA secondary structures

A statistical reference for RNA secondary structures with minimum free energies is computed by folding large ensembles of random RNA sequences. Four nucleotide alphabets are used: two binary alphabets, AU and GC, the biophysical AUGC and the synthetic GCXK alphabet. RNA secondary structures are made of structural elements, such as stacks, loops, joints, and free ends. Statistical properties of these elements are computed for small RNA molecules of chain lengths up to 100. The results of RNA structure statistics depend strongly on the particular alphabet chosen. The statistical reference is compared with the data derived from natural RNA molecules with similar base frequencies. Secondary structures are represented as trees. Tree editing provides a quantitative measure for the distance d_t, between two structures. We compute a structure density surface as the conditional probability of two structures having distance t given that their sequences have distance h. This surface indicates that the vast majority of possible minimum free energy secondary structures occur within a fairly small neighborhood of any typical (random) sequence. Correlation lengths for secondary structures in their tree representations are computed from probability densities. They are appropriate measures for the complexity of the sequence-structure relation. The correlation length also provides a quantitative estimate for the mean sensitivity of structures to point mutations. © 1993 John Wiley & Sons, Inc.     

Moments of the Boltzmann distribution for RNA secondary structures

We here present a dynamic programming algorithm which is capable of calculating arbitrary moments of the Boltzmann distribution for RNA secondary structures. We have implemented the algorithm in a program called RNA-VARIANCE and investigate the difference between the Boltzmann distribution of biological and random RNA sequences. We find that the minimum free energy structure of biological sequences has a higher probability in the Boltzmann distribution than random sequences. Moreover, we show that the free energies of biological sequences have a smaller variance than random sequences and that the minimum free energy of biological sequences is closer to the expected free energy of the rest of the structures than that of random sequences. These results suggest that biologically functional RNA sequences not only require a thermodynamically stable minimum free energy structure, but also an ensemble of structures whose free energies are close to the minimum free energy.     

The relation between mRNA folding and protein structure

About 200 mRNA sequences of Escherichia coli and human with matching protein secondary structure data were studied. The mRNA folding for each native sequence and for corresponding randomized sequences was calculated through free energy minimization. We have found that the folding energy of mRNA segments in different protein secondary structures is significantly different. The average Z score is more negative for regular secondary structure (alpha-helix and beta-strand) than that for coil. This suggests that the codon choice in native mRNA sequence coding for protein regular structure contributes more to the mRNA folding stability.     

Combinatorial analysis of interacting RNA molecules

Recently several minimum free energy (MFE) folding algorithms for predicting the joint structure of two interacting RNA molecules have been proposed. Their folding targets are interaction structures, that can be represented as diagrams with two backbones drawn horizontally on top of each other such that (1) intramolecular and intermolecular bonds are noncrossing and (2) there is no “zigzag” configuration. This paper studies joint structures with arc-length at least four in which both, interior and exterior stack-lengths are at least two (no isolated arcs). The key idea in this paper is to consider a new type of shape, based on which joint structures can be derived via symbolic enumeration. Our results imply simple asymptotic formulas for the number of joint structures with surprisingly small exponential growth rates. They are of interest in the context of designing prediction algorithms for RNA-RNA interactions.     

Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information.

This paper presents a new computer method for folding an RNA molecule that finds a conformation of minimum free energy using published values of stacking and destabilizing energies. It is based on a dynamic programming algorithm from applied mathematics, and is much more efficient, faster, and can fold larger molecules than procedures which have appeared up to now in the biological literature. Its power is demonstrated in the folding of a 459 nucleotide immunoglobulin gamma 1 heavy chain messenger RNA fragment. We go beyond the basic method to show how to incorporate additional information into the algorithm. This includes data on chemical reactivity and enzyme susceptibility. We illustrate this with the folding of two large fragments from the 16S ribosomal RNA of Escherichia coli.