Incorporating global features of RNA motifs in predictions for an ensemble of secondary structures for encapsidated MS2 bacteriophage RNA

The secondary structure of encapsidated MS2 genomic RNA poses an interesting RNA folding challenge. Cryoelectron microscopy has demonstrated that encapsidated MS2 RNA is well-ordered. Models of MS2 assembly suggest that the RNA hairpin-protein interactions and the appropriate placement of hairpins in the MS2 RNA secondary structure can guide the formation of the correct icosahedral particle. The RNA hairpin motif that is recognized by the MS2 capsid protein dimers, however, is energetically unfavorable, and thus free energy predictions are biased against this motif. Computer programs called Crumple, Sliding Windows, and Assembly provide useful tools for prediction of viral RNA secondary structures when the traditional assumptions of RNA structure prediction by free energy minimization may not apply. These methods allow incorporation of global features of the RNA fold and motifs that are difficult to include directly in minimum free energy predictions. For example, with MS2 RNA the experimental data from SELEX experiments, crystallography, and theoretical calculations of the path for the series of hairpins can be incorporated in the RNA structure prediction, and thus the influence of free energy considerations can be modulated. This approach thoroughly explores conformational space and generates an ensemble of secondary structures. The predictions from this new approach can test hypotheses and models of viral assembly and guide construction of complete three-dimensional models of virus particles.     

ProbKnot: Fast prediction of RNA secondary structure including pseudoknots

It is a significant challenge to predict RNA secondary structures including pseudoknots. Here, a new algorithm capable of predicting pseudoknots of any topology, ProbKnot, is reported. ProbKnot assembles maximum expected accuracy structures from computed base-pairing probabilities in O(N²) time, where N is the length of the sequence. The performance of ProbKnot was measured by comparing predicted structures with known structures for a large database of RNA sequences with fewer than 700 nucleotides. The percentage of known pairs correctly predicted was 69.3%. Additionally, the percentage of predicted pairs in the known structure was 61.3%. This performance is the highest of four tested algorithms that are capable of pseudoknot prediction. The program is available for download at: http://rna.urmc.rochester.edu/RNAstructure.html.     

A new algorithm for RNA secondary structure design

The function of many RNAs depends crucially on their structure. Therefore, the design of RNA molecules with specific structural properties has many potential applications, e.g. in the context of investigating the function of biological RNAs, of creating new ribozymes, or of designing artificial RNA nanostructures. Here, we present a new algorithm for solving the following RNA secondary structure design problem: given a secondary structure, find an RNA sequence (if any) that is predicted to fold to that structure. Unlike the (pseudoknot-free) secondary structure prediction problem, this problem appears to be hard computationally. Our new algorithm, "RNA Secondary Structure Designer (RNA-SSD)", is based on stochastic local search, a prominent general approach for solving hard combinatorial problems. A thorough empirical evaluation on computationally predicted structures of biological sequences and artificially generated RNA structures as well as on empirically modelled structures from the biological literature shows that RNA-SSD substantially out-performs the best known algorithm for this problem, RNAinverse from the Vienna RNA Package. In particular, the new algorithm is able to solve structures, consistently, for which RNAinverse is unable to find solutions. The RNA-SSD software is publically available under the name of RNA Designer at the RNASoft website (www.rnasoft.ca).     

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.     

On a seven-dimensional representation of RNA secondary structures

In this paper, we proposed a seven-dimensional (7D) representation of ribonucleic acid (RNA) secondary structures. The use of the 7D representation is illustrated by constructing structure invariants. Comparisons with the similarity/dissimilarity results based on 7D representation for a set of RNA 3 secondary structures at the 3′-terminus of different viruses, are considered to illustrate the use of our structure invariants based on the entries in derived sequence matrices restricted to a selected width of a band along the main diagonal.     

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.     

Kinetic barriers and the role of topology in protein and RNA folding

This review compares the folding behavior of proteins and RNAs. Topics covered include the role of topology in the determination of folding rates, major folding events including collapse, properties of denatured states, pathway heterogeneity, and the influence of the mode of initiation on the folding pathway.     

A DEAD-box RNA helicase promotes thermodynamic equilibration of kinetically trapped RNA structures in vivo

RNAs must assemble into specific structures in order to carry out their biological functions, but in vitro RNA folding reactions produce multiple misfolded structures that fail to exchange with functional structures on biological time scales. We used carefully designed self-cleaving mRNAs that assemble through well-defined folding pathways to identify factors that differentiate intracellular and in vitro folding reactions. Our previous work showed that simple base-paired RNA helices form and dissociate with the same rate and equilibrium constants in vivo and in vitro. However, exchange between adjacent secondary structures occurs much faster in vivo, enabling RNAs to quickly adopt structures with the lowest free energy. We have now used this approach to probe the effects of an extensively characterized DEAD-box RNA helicase, Mss116p, on a series of well-defined RNA folding steps in yeast. Mss116p overexpression had no detectable effect on helix formation or dissociation kinetics or on the stability of interdomain tertiary interactions, consistent with previous evidence that intracellular factors do not affect these folding parameters. However, Mss116p overexpression did accelerate exchange between adjacent helices. The nonprocessive nature of RNA duplex unwinding by DEAD-box RNA helicases is consistent with a branch migration mechanism in which Mss116p lowers barriers to exchange between otherwise stable helices by the melting and annealing of one or two base pairs at interhelical junctions. These results suggest that the helicase activity of DEAD-box proteins like Mss116p distinguish intracellular RNA folding pathways from nonproductive RNA folding reactions in vitro and allow RNA structures to overcome kinetic barriers to thermodynamic equilibration in vivo.     

Algorithm independent properties of RNA secondary structure predictions

Algorithms predicting RNA secondary structures based on different folding criteria – minimum free energies (mfe), kinetic folding (kin), maximum matching (mm) – and different parameter sets are studied systematically. Two base pairing alphabets were used: the binary GC and the natural four-letter AUGC alphabet. Computed structures and free energies depend strongly on both the algorithm and the parameter set. Statistical properties, such as mean number of base pairs, mean numbers of stacks, mean loop sizes, etc., are much less sensitive to the choice of parameter set and even of algorithm. Some features of RNA secondary structures, such as structure correlation functions, shape space covering and neutral networks, seem to depend only on the base pairing logic (GC or AUGC alphabet). Received: 16 May 1996 / Accepted: 10 July 1996     

Predicted RNA secondary structures for the conserved regions in dengue virus

Dengue fever, dengue hemorrhagic fever and dengue shock syndrome are the prevalent mosquito borne viral infections worldwide. The dengue virus belongs to the genus flavivirus with conserved RNA domains peptidase_S7 and dexHc among its members. The secondary structures for RNA domains peptidase_S7 and DexHc are hence predicted and discussed with other known viral RNA structures to glean structural insights through comparison.     

In silico predicted robustness of viroid RNA secondary structures. II. Interaction between mutation pairs

Viroids are plant subviral pathogens whose genomes are constituted by a single-stranded and covalently closed small RNA molecule that does not encode for any protein. Most of the 29 described viroid species fold into a rodlike or quasi-rodlike structure, whereas a few of them fold as highly branched structures. In a previous study, we used RNA thermodynamic secondary structure prediction algorithms to compare the mutational robustness of all viroid species. Here we used the same approach to explore the sign and strength of epistasis among pairs of random mutations. We found that antagonistic interactions were more abundant than synergistic ones. However, despite their lower frequency, synergistic interactions tended to be more intense. Mutational robustness and the intensity of epistasis were correlated such that viroid species with large average mutational effects showed stronger antagonistic epistasis, whereas viroids with mild average mutational effects showed weaker antagonistic interactions. The strength of antagonistic epistasis decreased with genome complexity as a consequence of the gained robustness of duplicated genomes. In good agreement with our previous finding of an evolutionary trend toward increased robustness, we now found a trend toward reduced antagonistic epistasis.     

In silico predicted robustness of viroids RNA secondary structures. I. The effect of single mutations

Viroids are plant subviral pathogens whose genomes are constituted by a single-stranded and covalently closed small RNA molecule that does not encode for any protein. Despite this genomic simplicity, they are able of inducing devastating symptoms in susceptible plants. Most of the 29 described viroid species fold into a rodlike or quasi-rodlike structure, whereas a few of them fold as branched structures. The shape of these RNA structures is perhaps one of the most characteristic properties of viroids and sometimes is considered their only phenotype. Here we use RNA thermodynamic secondary structure prediction algorithms to compare the mutational robustness of all viroid species. After characterizing the statistical properties of the distribution of mutational effects on structure stability and the wideness of neutral neighborhood for each viroid species, we show an evolutionary trend toward increased structural robustness during viroid radiation, giving support to the adaptive value of robustness. Differences in robustness among the 2 viroid families can be explained by the larger fragility of branched structures compared with the rodlike ones. We also show that genomic redundancy can contribute to the robustness of these simple RNA genomes.     

Statistics of RNA melting kinetics

We present and study the behavior of a simple kinetic model for the melting of RNA secondary structures, given that those structures are known. The model is then used as a map that. assigns structure dependent overall rate constants of melting (or refolding) to a sequence. This induces a landscape of reaction rates, or activation energies, over the space of sequences with fixed length. We study the distribution and the correlation structure of these activation energies. Correspondence to: P. Schuster     

Selecting near-native protein structures from ab initio models using ensemble clustering

Background: Ab initio protein structure prediction is to predict the tertiary structure of a protein from its amino acid sequence alone. As an important topic in bioinformatics, considerable efforts have been made on designing the ab initio methods. Unfortunately, lacking of a perfect energy function, it is a difficult task to select a good near-native structure from the predicted decoy structures in the last step. Methods: Here we propose an ensemble clustering method based on k-medoids to deal with this problem. The k-medoids method is run many times to generate clustering ensembles, and then a voting method is used to combine the clustering results. A confidence score is defined to select the final near-native model, considering both the cluster size and the cluster similarity. Results: We have applied the method to 54 single-domain targets in CASP-11. For about 70.4% of these targets, the proposed method can select better near-native structures compared to the SPICKER method used by the I-TASSER server. Conclusions: The experiments show that, the proposed method is effective in selecting the near-native structure from decoy sets for different targets in terms of the similarity between the selected structure and the native structure.