Facilitating RNA structure prediction with microarrays

Determining RNA secondary structure is important for understanding structure-function relationships and identifying potential drug targets. This paper reports the use of microarrays with heptamer 2'-O-methyl oligoribonucleotides to probe the secondary structure of an RNA and thereby improve the prediction of that secondary structure. When experimental constraints from hybridization results are added to a free-energy minimization algorithm, the prediction of the secondary structure of Escherichia coli 5S rRNA improves from 27 to 92% of the known canonical base pairs. Optimization of buffer conditions for hybridization and application of 2'-O-methyl-2-thiouridine to enhance binding and improve discrimination between AU and GU pairs are also described. The results suggest that probing RNA with oligonucleotide microarrays can facilitate determination of secondary structure.     

Comparison of P-RnaPredict and mfold--algorithms for RNA secondary structure prediction

MOTIVATION: Ribonucleic acid is vital in numerous stages of protein synthesis; it also possesses important functional and structural roles within the cell. The function of an RNA molecule within a particular organic system is principally determined by its structure. The current physical methods available for structure determination are time-consuming and expensive. Hence, computational methods for structure prediction are sought after. The energies involved by the formation of secondary structure elements are significantly greater than those of tertiary elements. Therefore, RNA structure prediction focuses on secondary structure. RESULTS: We present P-RnaPredict, a parallel evolutionary algorithm for RNA secondary structure prediction. The speedup provided by parallelization is investigated with five sequences, and a dramatic improvement in speedup is demonstrated, especially with longer sequences. An evaluation of the performance of P-RnaPredict in terms of prediction accuracy is made through comparison with 10 individual known structures from 3 RNA classes (5S rRNA, Group I intron 16S rRNA and 16S rRNA) and the mfold dynamic programming algorithm. P-RnaPredict is able to predict structures with higher true positive base pair counts and lower false positives than mfold on certain sequences. AVAILABILITY: P-RnaPredict is available for non-commercial usage. Interested parties should contact Kay C. Wiese (wiese@cs.sfu.ca).     

The evolution of 5S RNA secondary structures

We have applied the Pipas-McMahon algorithm based on free energy calculations to the search for a 5S RNA base-pair structure common to all known sequences. We find that a 'Y' shaped model is consistently among the structures having the lowest free energy using 5S RNA sequences from either eukaryotic or prokaryotic sources. Compaison of this 'Y' structure with models which have recently been proposed show these models to be remarkably similar, and the minor differences are explicable based on the technique used to obtain the model. That prokaryotic and eukaryotic 5S RNA can adopt a similar secondary structure is strong support for its resistance to change during evolution.     

Lasar raman evidence for a new cloverleaf secondary structure for eucaryotic 5 S RNA

None of the many previously proposed secondary structures for eucaryotic 5 S RNA and 5.8 S RNA are consistent with all the known physical properties and suspected functions of these molecules. The present Raman results for yeast 5 S RNA require a highly ordered secondary structure. A new, highly stable “cloverleaf” secondary structure not only accounts for the Raman data, but also accommodates previously established physical and functional features. Homologous cloverleaf structures can be adapted to other eucaryotic 5 S RNA species, with stability numbers that increase monotonically from lower to higher animals. The generality of the new cloverleaf structure for eucaryotic 5 S RNA is supported by the recent success of similar cloverleafs in accounting for the properties and functions of procaryotic 5 S RNA and eucaryotic 5.8 S RNA.     

Secondary structure of total protein and 23S RNA in 50S ribosomal subunits and in the isolated state

Optical and sedimentational studies of isolated 23S RNA, total proteins and some RNP-complexes of the 50S subunits were carried out. It is shown that the secondary structure content of 23S RNA in the ribosome is lower than in the isolated state. Ribosomal proteins stabilize the 23S RNA structure and make it more compact. At the same time they cause some unwinding effect on the secondary structure of the 23S RNA and possibly fix some segments of the 23S RNA in the conformation necessary for its function. In turn, the 23S RNA increased somewhat the level of the total ordered secondary structure in the ribosomal proteins. There was no considerable change of the ratio between the alpha- and beta-structures in the proteins.     

一种预测单链RNA分子二级结构的计算机算法

本文给出了一个利用已知能量数据构成具有最小自由能的单链RNA分子二级结构的计算机算法,并给出了此算法的可行性证明和应用实例。     

RNA-SSPT: RNA Secondary Structure Prediction Tools

The prediction of RNA structure is useful for understanding evolution for both in silico and in vitro studies. Physical methods like NMR studies to predict RNA secondary structure are expensive and difficult. Computational RNA secondary structure prediction is easier. Comparative sequence analysis provides the best solution. But secondary structure prediction of a single RNA sequence is challenging. RNA-SSPT is a tool that computationally predicts secondary structure of a single RNA sequence. Most of the RNA secondary structure prediction tools do not allow pseudoknots in the structure or are unable to locate them. Nussinov dynamic programming algorithm has been implemented in RNA-SSPT. The current studies shows only energetically most favorable secondary structure is required and the algorithm modification is also available that produces base pairs to lower the total free energy of the secondary structure. For visualization of RNA secondary structure, NAVIEW in C language is used and modified in C# for tool requirement. RNA-SSPT is built in C# using Dot Net 2.0 in Microsoft Visual Studio 2005 Professional edition. The accuracy of RNA-SSPT is tested in terms of Sensitivity and Positive Predicted Value. It is a tool which serves both secondary structure prediction and secondary structure visualization purposes.     

An efficient algorithm to compute the landscape of locally optimal RNA secondary structures with respect to the Nussinov-Jacobson energy model.

We make a novel contribution to the theory of biopolymer folding, by developing an efficient algorithm to compute the number of locally optimal secondary structures of an RNA molecule, with respect to the Nussinov-Jacobson energy model. Additionally, we apply our algorithm to analyze the folding landscape of selenocysteine insertion sequence (SECIS) elements from A. Bock (personal communication), hammerhead ribozymes from Rfam (Griffiths-Jones et al., 2003), and tRNAs from Sprinzl's database (Sprinzl et al., 1998). It had previously been reported that tRNA has lower minimum free energy than random RNA of the same compositional frequency (Clote et al., 2003; Rivas and Eddy, 2000), although the situation is less clear for mRNA (Seffens and Digby, 1999; Workman and Krogh, 1999; Cohen and Skienna, 2002),(1) which plays no structural role. Applications of our algorithm extend knowledge of the energy landscape differences between naturally occurring and random RNA. Given an RNA molecule a(1), ... , a(n) and an integer k > or = 0, a k-locally optimal secondary structure S is a secondary structure on a(1), ... , a(n) which has k fewer base pairs than the maximum possible number, yet for which no basepairs can be added without violation of the definition of secondary structure (e.g., introducing a pseudoknot). Despite the fact that the number numStr(k) of k-locally optimal structures for a given RNA molecule in general is exponential in n, we present an algorithm running in time O(n (4)) and space O(n (3)), which computes numStr(k) for each k. Structurally important RNA, such as SECIS elements, hammerhead ribozymes, and tRNA, all have a markedly smaller number of k-locally optimal structures than that of random RNA of the same dinucleotide frequency, for small and moderate values of k. This suggests a potential future role of our algorithm as a tool to detect noncoding RNA genes.     

Secondary structure of the 5'-terminal region of the 18S ribosomal RNA5.3S fragment from the rat liver

Two small RNA fragments, 5,3S and 4,7S, were observed in gel electrophoretic analysis of RNA of the 40S ribosomal subunit of rat liver. 5,3S RNA (134-136 nucleotides long) proved to be 5'-terminal fragment of 18S ribosomal RNA, whereas 4,7 RNA is the degradation product of 5,3S RNA with 27-28 5'-terminal nucleotides lost. The secondary structure of 5,3S RNA was probed with two structure-specific nucleases, S1 nuclease and the double-strand specific cobra venom endoribonuclease. The nuclease digestion data agree well with the computer generated secondary structure model for 5,3S RNA. This model predicts that the 5'-terminal part of rat liver ribosomal 18S RNA forms an independent structural domain. The affinity chromatography experiments with the immobilized 5,3S fragment show that 5,3S RNA does not bind rat liver ribosomal proteins.     

RGRNA: prediction of RNA secondary structure based on replacement and growth of stems

Owing to their structural diversity, RNAs perform many diverse biological functions in the cell. RNA secondary structure is thus important for predicting RNA function. Here, we propose a new combinatorial optimization algorithm, named RGRNA, to improve the accuracy of predicting RNA secondary structure. Following the establishment of a stempool, the stems are sorted by length, and chosen from largest to smallest. If the stem selected is the true stem, the secondary structure of this stem when combined with another stem selected at random will have low free energy, and the free energy will tend to gradually diminish. The free energy is considered as a parameter and the structure is converted into binary numbers to determine stem compatibility, for step-by-step prediction of the secondary structure for all combinations of stems. The RNA secondary structure can be predicted by the RGRNA method. Our experimental results show that the proposed algorithm outperforms RNAfold in terms of sensitivity, specificity, and Matthews correlation coefficient value.     

Nucleotide sequences of the 5.8S rRNAs of a mollusc and a porifer, and considerations regarding the secondary structure of 5.8S rRNA and its interaction with 28S rRNA

We report the primary structures of the 5.8 S ribosomal RNAs isolated from the sponge Hymeniacidon sanguinea and the snail Arion rufus. We had previously proposed (Ursi et al., Nucl. Acids Res. 10, 3517-3530 (1982)) a secondary structure model on the basis of a comparison of twelve 5.8 S RNA sequences then known, and a matching model for the interaction of 5.8 S RNA with 26 S RNA in yeast. Here we show that the secondary structure model can be extended to the 25 sequences presently available, and that the interaction model can be extended to the binding of 5.8 S RNA to the 5'-terminal domain of 28 S (26 S) RNA in three species.     

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

Secondary structure of a 345-base RNA fragment covering the S8/S15 protein binding domain of Escherichia coli 16S ribosomal RNA

A technique for isolating defined fragments of a large RNA has been developed and applied to a ribosomal RNA. A section of the Escherichia coli rrnB cistron corresponding to the S8/S15 protein binding domain of 16S ribosomal RNA was cloned into a single-stranded DNA phage; after hybridization of the phage DNA with 16S RNA and digestion with T1 ribonuclease, the protected RNA was separated from the DNA under denaturing conditions to yield a 345-base RNA fragment with unique ends (bases 525-869 in the 16S sequence). The secondary structure of this fragment was determined by mapping the cleavage sites of enzymes specific for single-stranded or double-helical RNA. The fragment structure is almost identical with that proposed for the corresponding region of intact 16S RNA on the basis of phylogenetic comparisons [Woese, C. R., Gutell, R., Gupta, R., & Noller, H. (1983) Microbiol. Rev. 47, 621-669]. We conclude that this section of RNA constitutes an independently folding domain that may be studied in isolation from the rest of the 16S RNA. The structure mapping experiments have indicated several interesting features in the RNA structure. (i) The largest bulge loop in the molecule (20 bases) contains specific tertiary structure. (ii) A region of long-range secondary structure, pairing bases about 200 residues apart in the sequence, can hydrogen bond in two different mutually exclusive schemes. Both appear to exist simultaneously in the RNA fragment under our conditions. (iii) The long-range secondary structure and one adjacent helix melt between 37 and 60 degrees C in the absence of Mg2+, while the rest of the structure is quite stable.     

The language of RNA: a formal grammar that includes pseudoknots

MOTIVATION: In a previous paper, we presented a polynomial time dynamic programming algorithm for predicting optimal RNA secondary structure including pseudoknots. However, a formal grammatical representation for RNA secondary structure with pseudoknots was still lacking. RESULTS: Here we show a one-to-one correspondence between that algorithm and a formal transformational grammar. This grammar class encompasses the context-free grammars and goes beyond to generate pseudoknotted structures. The pseudoknot grammar avoids the use of general context-sensitive rules by introducing a small number of auxiliary symbols used to reorder the strings generated by an otherwise context-free grammar. This formal representation of the residue correlations in RNA structure is important because it means we can build full probabilistic models of RNA secondary structure, including pseudoknots, and use them to optimally parse sequences in polynomial time.     

Prediction of common secondary structures of RNAs: a genetic algorithm approach

In this study we apply a genetic algorithm to a set of RNA sequences to find common RNA secondary structures. Our method is a three-step procedure. At the first stage of the procedure for each sequence, a genetic algorithm is used to optimize the structures in a population to a certain degree of stability. In this step, the free energy of a structure is the fitness criterion for the algorithm. Next, for each structure, we define a measure of structural conservation with respect to those in other sequences. We use this measure in a genetic algorithm to improve the structural similarity among sequences for the structures in the population of a sequence. Finally, we select those structures satisfying certain conditions of structural stability and similarity as predicted common structures for a set of RNA sequences. We have obtained satisfactory results from a set of tRNA, 5S rRNA, rev response elements (RRE) of HIV-1 and RRE of HIV-2/SIV, respectively.     

Xenopus laevis 18S ribosomal RNA: experimental determination of secondary structural elements, and locations of methyl groups in the secondary structure model.

18S ribosomal RNA from X. laevis was subjected to partial digestion with ribonucleases A or T1 under a variety of conditions, and base-paired fragments were isolated. Sequence analysis of the fragments enabled five base-paired secondary structural elements of the 18S RNA to be established. Four of these elements (covering bases 221-256, 713-757, 1494-1555 and 1669-1779) confirm our previous secondary structure predictions, whereas the fifth (comprising bases 1103-1125) represents a phylogenetically conserved "switch" structure, which can also form in prokaryotic 16S RNA. The results are incorporated into a refined model of the 18S RNA secondary structure, which also includes the locations of the many methyl groups in X. laevis 18S RNA. In general the methyl groups occur in non-helical regions, at hairpin loop ends, or at helix boundaries and imperfections. One large cluster of 2'-O-methyl groups occurs in a region of complicated secondary structure in the 5'-one third of the molecule.     

Sequences of the 5S rRNAs of the thermo-acidophilic archaebacterium Sulfolobus solfataricus (Caldariella acidophila) and the thermophilic eubacteria Bacillus acidocaldarius and Thermus aquaticus.

We have determined the nucleotide sequences of the 5 S rRNAs of three thermophilic bacteria: the archaebacterium Sulfolobus solfataricus, also named Caldariella acidophila, and the eubacteria Bacillus acidocaldarius and Thermus aquaticus. A 5 S RNA sequence for the latter species had already been published, but it looked suspect on the basis of its alignment with other 5 S RNA sequences and its base-pairing pattern. The corrected sequence aligns much better and fits in the universal five helix secondary structure model, as do the sequences for the two other examined species. The sequence found for Sulfolobus solfataricus is identical to that determined by others for Sulfolobus acidocaldarius. The secondary structure of its 5 S RNA shows a number of exceptional features which distinguish it not only from eubacterial and eukaryotic 5 S RNAs, but also from the limited number of archaebacterial 5 S RNA structures hitherto published. The free energy change of secondary structure formation is large in the three examined 5 S RNAs.     

How RNA folds.

We describe the RNA folding problem and contrast it with the much more difficult protein folding problem. RNA has four similar monomer units, whereas proteins have 20 very different residues. The folding of RNA is hierarchical in that secondary structure is much more stable than tertiary folding. In RNA the two levels of folding (secondary and tertiary) can be experimentally separated by the presence or absence of Mg2+. Secondary structure can be predicted successfully from experimental thermodynamic data on secondary structure elements: helices, loops, and bulges. Tertiary interactions can then be added without much distortion of the secondary structure. These observations suggest a folding algorithm to predict the structure of an RNA from its sequence. However, to solve the RNA folding problem one needs thermodynamic data on tertiary structure interactions, and identification and characterization of metal-ion binding sites. These data, together with force versus extension measurements on single RNA molecules, should provide the information necessary to test and refine the proposed algorithm.