Metrics on RNA secondary structures.

Many different programs have been developed for the prediction of the secondary structure of an RNA sequence. Some of these programs generate an ensemble of structures, all of which have free energy close to that of the optimal structure, making it important to be able to quantify how similar these different structures are. To deal with this problem, we define a new class of metrics, the mountain metrics, on the set of RNA secondary structures of a fixed length. We compare properties of these metrics with other well known metrics on RNA secondary structures. We also study some global and local properties of these metrics.     

Improved prediction of RNA tertiary structure with insights into native state dynamics

The importance of RNA tertiary structure is evident from the growing number of published high resolution NMR and X-ray crystallographic structures of RNA molecules. These structures provide insights into function and create a knowledge base that is leveraged by programs such as Assemble, ModeRNA, RNABuilder, NAST, FARNA, Mc-Sym, RNA2D3D, and iFoldRNA for tertiary structure prediction and design. While these methods sample native-like RNA structures during simulations, all struggle to capture the native RNA conformation after scoring. We propose RSIM, an improved RNA fragment assembly method that preserves RNA global secondary structure while sampling conformations. This approach enhances the quality of predicted RNA tertiary structure, provides insights into the native state dynamics, and generates a powerful visualization of the RNA conformational space. RSIM is available for download from http://www.github.com/jpbida/rsim.     

An improved secondary structure computation method and its application to intervening sequences in the human alpha-like globin mRNA precursors

Current secondary structure prediction computations have a seriousdrawback. The calculated thermodynamically most stable structureoften differs from that observed in solution or in crystal form.In this paper we suggest a way to partially overcome some ofthese limitations by simulating the RNA folding process andcalculating the frequencies of occurrence of the various substructuresobtained. The frequently recurring substructures are then selectedto construct the secondary structure of the whole RNA. 142 tRNAmolecules and an E. coli 16S rRNA molecule have been examinedby this method. The percentages of successful prediction ofthe correct helices are significantly higher than those calculatedpreviously. The secondary structures of intervening sequences(IVSs) excised from human -like globin pre-mRNAs are also computed.Thus, in this method the secondary structures obtained are composedof the statistically more significant substructures. This hasalso been demonstrated by using randomly shuffled sequences.The secondary structures of each of the randomized sequencesare computed and their mean and standard deviations are usedin evaluating the significance of the substructures obtainedin the folding of the biological sequence. Some potentiallyappealing structural features aligning adjacent exons for ligationhave been found. Received on April 3, 1987; accepted on October 18, 1987     

Pfold: RNA secondary structure prediction using stochastic context-free grammars

RNA secondary structures are important in many biological processes and efficient structure prediction can give vital directions for experimental investigations. Many available programs for RNA secondary structure prediction only use a single sequence at a time. This may be sufficient in some applications, but often it is possible to obtain related RNA sequences with conserved secondary structure. These should be included in structural analyses to give improved results. This work presents a practical way of predicting RNA secondary structure that is especially useful when related sequences can be obtained. The method improves a previous algorithm based on an explicit evolutionary model and a probabilistic model of structures. Predictions can be done on a web server at http://www.daimi.au.dk/~compbio/pfold.     

An algorithm for the display of nucleic acid secondary structure.

A simple algorithm is presented for the graphic display of nucleic acid secondary structure. Examples of secondary structure displays are given for tRNA, 5S RNA and part of the 16S RNA. Due to its speed, this algorithm could easily be used in conjunction with secondary structure programs which calculate various alternate structures.     

Thermodynamics of three-way multibranch loops in RNA

RNA multibranch loops (junctions) are loops from which three or more helices exit. They are nearly ubiquitous in RNA secondary structures determined by comparative sequence analysis. In this study, systems in which two strands combine to form three-way junctions were used to measure the stabilities of RNA multibranch loops by UV optical melting and isothermal titration calorimetry (ITC). These data were used to calculate the free energy increment for initiation of a three-way junction on the basis of a nearest neighbor model for secondary structure stability. Imino proton NMR spectra were also measured for two systems and are consistent with the hypothesized helical structures. Incorporation of the experimental data into the mfold and RNA structure computer programs has contributed to an improvement in prediction of RNA secondary structure from sequence.     

Prediction of RNA secondary structure, including pseudoknotting, by computer simulation.

A computer program is presented which determines the secondary structure of linear RNA molecules by simulating a hypothetical process of folding. This process implies the concept of 'nucleation centres', regions in RNA which locally trigger the folding. During the simulation, the RNA is allowed to fold into pseudoknotted structures, unlike all other programs predicting RNA secondary structure. The simulation uses published, experimentally determined free energy values for nearest neighbour base pair stackings and loop regions, except for new extrapolated values for loops larger than seven nucleotides. The free energy value for a loop arising from pseudoknot formation is set to a single, estimated value of 4.2 kcal/mole. Especially in the case of long RNA sequences, our program appears superior to other secondary structure predicting programs described so far, as tests on tRNAs, the LSU intron of Tetrahymena thermophila and a number of plant viral RNAs show. In addition, pseudoknotted structures are often predicted successfully. The program is written in mainframe APL and is adapted to run on IBM compatible PCs, Atari ST and Macintosh personal computers. On an 8 MHz 8088 standard PC without coprocessor, using STSC APL, it folds a sequence of 700 nucleotides in one and a half hour.     

RNA Sampler: a new sampling based algorithm for common RNA secondary structure prediction and structural alignment

MOTIVATION: Non-coding RNA genes and RNA structural regulatory motifs play important roles in gene regulation and other cellular functions. They are often characterized by specific secondary structures that are critical to their functions and are often conserved in phylogenetically or functionally related sequences. Predicting common RNA secondary structures in multiple unaligned sequences remains a challenge in bioinformatics research. Methods and RESULTS: We present a new sampling based algorithm to predict common RNA secondary structures in multiple unaligned sequences. Our algorithm finds the common structure between two sequences by probabilistically sampling aligned stems based on stem conservation calculated from intrasequence base pairing probabilities and intersequence base alignment probabilities. It iteratively updates these probabilities based on sampled structures and subsequently recalculates stem conservation using the updated probabilities. The iterative process terminates upon convergence of the sampled structures. We extend the algorithm to multiple sequences by a consistency-based method, which iteratively incorporates and reinforces consistent structure information from pairwise comparisons into consensus structures. The algorithm has no limitation on predicting pseudoknots. In extensive testing on real sequence data, our algorithm outperformed other leading RNA structure prediction methods in both sensitivity and specificity with a reasonably fast speed. It also generated better structural alignments than other programs in sequences of a wide range of identities, which more accurately represent the RNA secondary structure conservations. AVAILABILITY: The algorithm is implemented in a C program, RNA Sampler, which is available at http://ural.wustl.edu/software.html     

RNA secondary structures: comparison and determination of frequently recurring substructures by consensus

A method for assessing the preserved stem - loops of RNA secondarystructures is presented. Frequently recurring helical stemsin a set of secondary structures resulting from the simulatedfolding process of a given RNA are assessed and consensus structuralmotifs can then be selected to construct a secondary structureof the RNA. Alternatively, it can be applied to a series of‘optimal’ and ‘suboptimal’ secondarystructures computed using the dynamic program developed by Williamsand Tinoco. To demonstrate the power and the usefulness of theprogram we give examples of this procedure. Received on October 28, 1987; accepted on April 2, 1989     

Enhancement of accuracy and efficiency for RNA secondary structure prediction by sequence segmentation and MapReduce

Background

Ribonucleic acid (RNA) molecules play important roles in many biological processes including gene expression and regulation. Their secondary structures are crucial for the RNA functionality, and the prediction of the secondary structures is widely studied. Our previous research shows that cutting long sequences into shorter chunks, predicting secondary structures of the chunks independently using thermodynamic methods, and reconstructing the entire secondary structure from the predicted chunk structures can yield better accuracy than predicting the secondary structure using the RNA sequence as a whole. The chunking, prediction, and reconstruction processes can use different methods and parameters, some of which produce more accurate predictions than others. In this paper, we study the prediction accuracy and efficiency of three different chunking methods using seven popular secondary structure prediction programs that apply to two datasets of RNA with known secondary structures, which include both pseudoknotted and non-pseudoknotted sequences, as well as a family of viral genome RNAs whose structures have not been predicted before. Our modularized MapReduce framework based on Hadoop allows us to study the problem in a parallel and robust environment.

Results

On average, the maximum accuracy retention values are larger than one for our chunking methods and the seven prediction programs over 50 non-pseudoknotted sequences, meaning that the secondary structure predicted using chunking is more similar to the real structure than the secondary structure predicted by using the whole sequence. We observe similar results for the 23 pseudoknotted sequences, except for the NUPACK program using the centered chunking method. The performance analysis for 14 long RNA sequences from the Nodaviridae virus family outlines how the coarse-grained mapping of chunking and predictions in the MapReduce framework exhibits shorter turnaround times for short RNA sequences. However, as the lengths of the RNA sequences increase, the fine-grained mapping can surpass the coarse-grained mapping in performance.

Conclusions

By using our MapReduce framework together with statistical analysis on the accuracy retention results, we observe how the inversion-based chunking methods can outperform predictions using the whole sequence. Our chunk-based approach also enables us to predict secondary structures for very long RNA sequences, which is not feasible with traditional methods alone.

     

RNA helicases: modulators of RNA structure

RNA molecules play an essential role in many cellular processes, often as components of ribonucleoprotein complexes. Like proteins, RNA molecules adopt sequence-specific secondary and tertiary structures that are essential for function; alteration of these structures therefore provides a means of regulating RNA function. The discovery of DEAD box proteins, a large family of proteins that share several highly conserved motifs and have known or putative ATP-dependent RNA helicase activity, has provoked growing interest in the concept that regulation of RNA function may occur through local unwinding of complex RNA structures.     

Predicting RNA Structure Using Mutual Information

BACKGROUND: With the ever-increasing number of sequenced RNAs and the establishment of new RNA databases, such as the Comparative RNA Web Site and Rfam, there is a growing need for accurately and automatically predicting RNA structures from multiple alignments. Since RNA secondary structure is often conserved in evolution, the well known, but underused, mutual information measure for identifying covarying sites in an alignment can be useful for identifying structural elements. This article presents MIfold, a MATLAB toolbox that employs mutual information, or a related covariation measure, to display and predict conserved RNA secondary structure (including pseudoknots) from an alignment. RESULTS: We show that MIfold can be used to predict simple pseudoknots, and that the performance can be adjusted to make it either more sensitive or more selective. We also demonstrate that the overall performance of MIfold improves with the number of aligned sequences for certain types of RNA sequences. In addition, we show that, for these sequences, MIfold is more sensitive but less selective than the related RNAalifold structure prediction program and is comparable with the COVE structure prediction package. CONCLUSION: MIfold provides a useful supplementary tool to programs such as RNA Structure Logo, RNAalifold and COVE, and should be useful for automatically generating structural predictions for databases such as Rfam.     

A program for predicting significant RNA secondary structures

We describe a program for the analysis of RNA secondary structure.There are two new features in this program. (i) To get vectorspeeds on a vector pipeline machine (such as Cray X-MP/24) wehave vectorized the secondary structure dynamic algorithm. (ii)The statistical significance of a locally ‘optimal’secondary structure is assessed by a Monte Carlo method. Theresults can be depicted graphically including profiles of thestability of local secondary structures and the distributionof the potentially significant secondary structures in the RNAmolecules. Interesting regions where both the potentially significantsecondary structures and ‘open’ structures (single-strandedcoils) occur can be identified by the plots mentioned above.Furthermore, the speed of the vectorized code allows repeatedMonte Carlo simulations with different overlapping window sizes.Thus, the optimal size of the significant secondary structureoccurring in the interesting region can be assessed by repeatingthe Monte Carlo simulation. The power of the program is demonstratedin the analysis of local secondary structures of human T-celllymphotrophic virus type III (HIV). Received on August 17, 1987; accepted on January 5, 1988     

Pattern analysis of RNA secondary structure similarity and consensus of minimal-energy folding

We describe an automated procedure to search for consensus structures or substructures in a set of homologous or related RNA molecules. The procedure is based on the calculation of optimal and sub-optimal secondary structures using thermodynamic rules for base-pairing by energy-minimization. A linear representation of the secondary structures of the related RNAs is used so that they can be compared and classified using standard alignment and clusterings programs. We illustrate the method by means of two sets of homologous small RNAs, U2 and U3, and a set of alpha-globin mRNAs and show that biologically interesting consensus structures are obtained.     

Viral IRES Prediction System - a Web Server for Prediction of the IRES Secondary Structure In Silico

The internal ribosomal entry site (IRES) functions as cap-independent translation initiation sites in eukaryotic cells. IRES elements have been applied as useful tools for bi-cistronic expression vectors. Current RNA structure prediction programs are unable to predict precisely the potential IRES element. We have designed a viral IRES prediction system (VIPS) to perform the IRES secondary structure prediction. In order to obtain better results for the IRES prediction, the VIPS can evaluate and predict for all four different groups of IRESs with a higher accuracy. RNA secondary structure prediction, comparison, and pseudoknot prediction programs were implemented to form the three-stage procedure for the VIPS. The backbone of VIPS includes: the RNAL fold program, aimed to predict local RNA secondary structures by minimum free energy method; the RNA Align program, intended to compare predicted structures; and pknotsRG program, used to calculate the pseudoknot structure. VIPS was evaluated by using UTR database, IRES database and Virus database, and the accuracy rate of VIPS was assessed as 98.53%, 90.80%, 82.36% and 80.41% for IRES groups 1, 2, 3, and 4, respectively. This advance useful search approach for IRES structures will facilitate IRES related studies. The VIPS on-line website service is available at http://140.135.61.250/vips/.     

IBM microcomputer programs that analyze DNA sequences for tRNA genes

A set of four computer programs that search DNA sequence datafiles for transfer RNA genes have been written in IBM (Microsoft)BASIC for the IBM personal computer. These programs locate andplot predicted secondary structures of tRNA genes in the cloverleafconformation. The set of programs are applicable to eukaryotictRNA genes, including those containing intervening sequences,and to prokaryotic and mitochondrial tRNA genes. In addition,two of the programs search up to 150 residues downstream oftRNA gene sequences for possible eukaryotic RNA polymerase IIItermination sites comprised of at least four consecutive T residues.Molecular biologists studying a variety of gene sequences andflanking regions can use these programs to search for the additionalpresence of tRNA genes. Furthermore, investigators studyingtRNA gene structure-to-function relationships would not needto do extensive restriction mapping to locate tRNA gene sequenceswithin their cloned DNA fragments. Received on October 29, 1985; accepted on January 28, 1986     

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.     

RAG-3D: a search tool for RNA 3D substructures

To address many challenges in RNA structure/function prediction, the characterization of RNA''s modular architectural units is required. Using the RNA-As-Graphs (RAG) database, we have previously explored the existence of secondary structure (2D) submotifs within larger RNA structures. Here we present RAG-3D—a dataset of RNA tertiary (3D) structures and substructures plus a web-based search tool—designed to exploit graph representations of RNAs for the goal of searching for similar 3D structural fragments. The objects in RAG-3D consist of 3D structures translated into 3D graphs, cataloged based on the connectivity between their secondary structure elements. Each graph is additionally described in terms of its subgraph building blocks. The RAG-3D search tool then compares a query RNA 3D structure to those in the database to obtain structurally similar structures and substructures. This comparison reveals conserved 3D RNA features and thus may suggest functional connections. Though RNA search programs based on similarity in sequence, 2D, and/or 3D structural elements are available, our graph-based search tool may be advantageous for illuminating similarities that are not obvious; using motifs rather than sequence space also reduces search times considerably. Ultimately, such substructuring could be useful for RNA 3D structure prediction, structure/function inference and inverse folding.