Effects of secondary structures in RNA on interlocking probabilities

In 1967 Wang and Schwartz reported on the formation of interlocked rings between linear or circular DNA molecules by the enzyme topoisomerase. We propose viewing the secondary structured loop in RNA (or single stranded DNA) as analogous to a circular DNA molecule. Formation of a catenane between such an RNA loop with a DNA molecule may constitute a probe of the secondary and general three dimensioanl structure of the RNA molecule. The experimental results may be compared with the theoretical calculation. We suggest here a method for estimating linkage probabilities and calculate them for several cases for which secondary structures of the RNA have been proposed.     

RNA folding pathway functional intermediates: their prediction and analysis.

The massively parallel genetic algorithm (GA) for RNA structure prediction uses the concepts of mutation, recombination, and survival of the fittest to evolve a population of thousands of possible RNA structures toward a solution structure. As described below, the properties of the algorithm are ideally suited to use in the prediction of possible folding pathways and functional intermediates of RNA molecules given their sequences. Utilizing Stem Trace, an interactive visualization tool for RNA structure comparison, analysis of not only the solution ensembles developed by the algorithm, but also the stages of development of each of these solutions, can give strong insight into these folding pathways. The GA allows the incorporation of information from biological experiments, making it possible to test the influence of particular interactions between structural elements on the dynamics of the folding pathway. These methods are used to reveal the folding pathways of the potato spindle tuber viroid (PSTVd) and the host killing mechanism of Escherichia coli plasmid R1, both of which are successfully explored through the combination of the GA and Stem Trace. We also present novel intermediate folds of each molecule, which appear to be phylogenetically supported, as determined by use of the methods described below.     

Local gapped subforest alignment and its application in finding RNA structural motifs.

RNA molecules whose secondary structures contain similar substructures often have similar functions. Therefore, an important task in the study of RNA is to develop methods for discovering substructures in RNA secondary structures that occur frequently (also referred to as motifs). In this paper, we consider the problem of computing an optimal local alignment of two given labeled ordered forests F1 and F2. This problem asks for a substructure of F1 and a substructure of F2 that exhibit a high similarity. Since an RNA molecule's secondary structure can be represented as a labeled ordered forest, the problem we study has a direct application to finding potential motifs. We generalize the previously studied concept of a closed subforest to a gapped subforest and present the first algorithm for computing the optimal local gapped subforest alignment of F1 and F2. We also show that our technique can improve the time and space complexity of the previously most efficient algorithm for optimal local closed subforest alignment. Furthermore, we prove that a special case of our local gapped subforest alignment problem is equivalent to a problem known in the literature as the local sequence-structure alignment problem (lssa) and modify our main algorithm to obtain a much faster algorithm for lssa than the one previously proposed. An implementation of our algorithm is available at www.comp.nus.edu.sg/~bioinfo/LGSFAligner/. Its running time is significantly faster than the original lssa program.     

Conservation of secondary structure in 5 S ribosomal RNA: a uniform model for eukaryotic, eubacterial, archaebacterial and organelle sequences is energetically favourable

The most commonly accepted secondary structure models for 5S RNA differ for molecules of eubacterial origin, where the four-helix model of Fox and Woese is generally cited, and those of eukaryotic origin, where a fifth helix is assumed to exist. We have carefully aligned all available sequences from eukaryotes, eubacteria, chloroplasts, archaebacteria and plant mitochondria. We could thus derive a unified secondary structure model applicable to all 5S RNA sequences known to-date. It contains the five helices already present in the eukaryotic model, extended by additional segments that were not previously assumed to be universally present. One of the helices can be written in two equilibrium forms, which could reflect the existence of a flexible, dynamic structure. For the derivation of the model and the estimation of the free energies we followed a set of rules optimized to predict the tRNA cloverleaf. The stability of the unified model is higher than that of nearly all previously proposed sequence-specific and general models.     

Correlation of RNA Secondary Structure Statistics with Thermodynamic Stability and Applications to Folding

The accurate prediction of the secondary and tertiary structure of an RNA with different folding algorithms is dependent on several factors, including the energy functions. However, an RNA higher-order structure cannot be predicted accurately from its sequence based on a limited set of energy parameters. The inter- and intramolecular forces between this RNA and other small molecules and macromolecules, in addition to other factors in the cell such as pH, ionic strength, and temperature, influence the complex dynamics associated with transition of a single stranded RNA to its secondary and tertiary structure. Since all of the factors that affect the formation of an RNAs 3D structure cannot be determined experimentally, statistically derived potential energy has been used in the prediction of protein structure. In the current work, we evaluate the statistical free energy of various secondary structure motifs, including base-pair stacks, hairpin loops, and internal loops, using their statistical frequency obtained from the comparative analysis of more than 50,000 RNA sequences stored in the RNA Comparative Analysis Database (rCAD) at the Comparative RNA Web (CRW) Site. Statistical energy was computed from the structural statistics for several datasets. While the statistical energy for a base-pair stack correlates with experimentally derived free energy values, suggesting a Boltzmann-like distribution, variation is observed between different molecules and their location on the phylogenetic tree of life. Our statistical energy values calculated for several structural elements were utilized in the Mfold RNA-folding algorithm. The combined statistical energy values for base-pair stacks, hairpins and internal loop flanks result in a significant improvement in the accuracy of secondary structure prediction; the hairpin flanks contribute the most.     

The conformation of chicken, rat and human U1A RNAs in solution.

Chicken, rat and human U1A RNAs in solution, were examined for secondary structure, using several methods including hydrolysis by various nucleases, hybridization to DNA oligomers and analysis of fragment interactions. The experimental results showed that the three U1A RNAs have the same structure, stable over a wide range of pH and ionic conditions. They allowed the selection of one out of several possible models constructed from the data of primary structure. This model is characterized by 4 hairpins and two single-stranded regions, the two hairpins from the 3' part of the molecule bearing very stable stems. In addition, the experimental results showed that in contrast to the 5' half of the molecule, the 3' half has a compact conformation probably stabilized by tertiary interactions. The 5' end of U1A RNA is accessible and free of base-pairing so that it might base-pair with regions of other RNA molecules, for instance, with the extremities of introns as has been recently proposed in a model of splicing.     

Local sequence-structure motifs in RNA

Ribonuclic acid (RNA) enjoys increasing interest in molecular biology; despite this interest fundamental algorithms are lacking, e.g. for identifying local motifs. As proteins, RNA molecules have a distinctive structure. Therefore, in addition to sequence information, structure plays an important part in assessing the similarity of RNAs. Furthermore, common sequence-structure features in two or several RNA molecules are often only spatially local, where possibly large parts of the molecules are dissimilar. Consequently, we address the problem of comparing RNA molecules by computing an optimal local alignment with respect to sequence and structure information. While local alignment is superior to global alignment for identifying local similarities, no general local sequence-structure alignment algorithms are currently known. We suggest a new general definition of locality for sequence-structure alignments that is biologically motivated and efficiently tractable. To show the former, we discuss locality of RNA and prove that the defined locality means connectivity by atomic and non-atomic bonds. To show the latter, we present an efficient algorithm for the newly defined pairwise local sequence-structure alignment (lssa) problem for RNA. For molecules of lengthes n and m, the algorithm has worst-case time complexity of O(n2 x m2 x max(n,m)) and a space complexity of only O(n x m). An implementation of our algorithm is available at http://www.bio.inf.uni-jena.de. Its runtime is competitive with global sequence-structure alignment.     

A vector-based method for drawing RNA secondary structure.

MOTIVATION: To produce a polygonal display of RNA secondary structure with minimal overlap and distortion of structural elements, with minimal search for positioning them, and with minimal user intervention. RESULTS: A new algorithm for automatically drawing RNA secondary structure has been developed. The algorithm represents the direction and space for a structural element using vector and vector space. Two heuristics are used. The first heuristic is concerned with ordering structural elements to be positioned and the second with positioning them in space. The algorithm and a graphical user interface have been implemented in a working program called VizQFolder on IBM PC compatibles. Experimental results demonstrate that VizQFolder is capable of automatically generating nearly overlap-free polygonal displays for long RNA molecules. The only distortion performed to avoid overlap is the rotation of helices, leading to efficient generation of a polygonal display without sacrificing its readability. VizQFolder is not coupled to a specific prediction program of RNA secondary structure, and thus can be used for visualizing secondary structure models obtained by any means. AVAILABILITY: The executable code of VizQFolder is available at http://automation.inha.ac.kr/khan. It can also be obtained from the authors upon request.     

Evolving stochastic context-free grammars for RNA secondary structure prediction

ABSTRACT: BACKGROUND: Stochastic Context-Free Grammars (SCFGs) were applied successfully to RNA secondary structure prediction in the early 90s, and used in combination with comparative methods in the late 90s. The set of SCFGs potentially useful for RNA secondary structure prediction is very large, but a few intuitively designed grammars have remained dominant. In this paper we investigate two automatic search techniques for effective grammars - exhaustive search for very compact grammars and an evolutionary algorithm to find larger grammars. We also examine whether grammar ambiguity is as problematic to structure prediction as has been previously suggested. RESULTS: These search techniques were applied to predict RNA secondary structure on a maximal data set and revealed new and interesting grammars, though none are dramatically better than classic grammars. In general, results showed that many grammars with quite different structure could have very similar predictive ability. Many ambiguous grammars were found which were at least as effective as the best current unambiguous grammars. CONCLUSIONS: Overall the method of evolving SCFGs for RNA secondary structure prediction proved effective in finding many grammars that had strong predictive accuracy, as good or slightly better than those designed manually. Furthermore, several of the best grammars found were ambiguous, demonstrating that such grammars should not be disregarded.     

PseudoViewer: automatic visualization of RNA pseudoknots

MOTIVATION: Several algorithms have been developed for drawing RNA secondary structures, however none of these can be used to draw RNA pseudoknot structures. In the sense of graph theory, a drawing of RNA secondary structures is a tree, whereas a drawing of RNA pseudoknots is a graph with inner cycles within a pseudoknot as well as possible outer cycles formed between a pseudoknot and other structural elements. Thus, RNA pseudoknots are more difficult to visualize than RNA secondary structures. Since no automatic method for drawing RNA pseudoknots exists, visualizing RNA pseudoknots relies on significant amount of manual work and does not yield satisfactory results. The task of visualizing RNA pseudoknots by hand becomes more challenging as the size and complexity of the RNA pseudoknots increase. RESULTS: We have developed a new representation and an algorithm for drawing H-type pseudoknots with RNA secondary structures. Compared to existing representations of H-type pseudoknots, the new representation ensures uniform and clear drawings with no edge crossing for any H-type pseudoknots. To the best of our knowledge, this is the first algorithm for automatically drawing RNA pseudoknots with RNA secondary structures. The algorithm has been implemented in a Java program, which can be executed on any computing system. Experimental results demonstrate that the algorithm generates an aesthetically pleasing drawing of all H-type pseudoknots. The results have also shown that the drawing has high readability, enabling the user to quickly and easily recognize the whole RNA structure as well as the pseudoknots themselves.     

A method for discovering common patterns from two RNA secondary structures and its application to structural repeat detection

We propose an ab initio method, named DiscoverR, for finding common patterns from two RNA secondary structures. The method works by representing RNA secondary structures as ordered labeled trees and performs tree pattern discovery using an efficient dynamic programming algorithm. DiscoverR is able to identify and extract the largest common substructures from two RNA molecules having different sizes without prior knowledge of the locations and topologies of these substructures. We also extend DiscoverR to find repeated regions in an RNA secondary structure, and apply this extended method to detect structural repeats in the 3'-untranslated region of a protein kinase gene. We describe the biological significance of a repeated hairpin found by our method, demonstrating the usefulness of the method. DiscoverR is implemented in Java; a jar file including the source code of the program is available for download at http://bioinformatics.njit.edu/DiscoverR.     

The nuclear 5S RNAs from chicken, rat and man. U5 RNAs are encoded by multiple genes

Preparations of chicken, rat and human nuclear 5S RNA contain two sets of molecules. The set with the lowest electrophoretic mobility (5Sa) contains RNAs identical or closely related to ribosomal 5S RNA from the corresponding animal species. In HeLa cells and rat brain, we only detected an RNA identical to the ribosomal 5S RNA. In hen brain and liver, we found other species differing by a limited number of substitutions. The results suggest that mutated 5S genes may be expressed differently according to the cell type. The set with the highest mobility corresponds to U5 RNA. In both rat brain and HeLa cells, U5 RNA was found to be composed of 4 and 5 different molecules respectively (U5A, U5B1-4) differing by a small number of substitutions or insertions. In hen brain, no U5B was detected but U5A' differing from U5A by the absence of the 3'-terminal adenosine. All the U5 RNAs contain the same set of modified nucleotides. They also have the same secondary structure which consists of two hairpins joined together by a 17 nucleotide long single-stranded region. The 3' half of the molecule has a compact conformation. Together, the results suggest that U5 RNAs are transcribed from a multigene family and that mutated genes may be expressed as far as secondary structure is conserved. The conformation of U5 RNA is likely to be related to its function and it is of interest to mention that several similarities of structure are found between U5 and U1A RNA.     

Analysis of internal loops within the RNA secondary structure in almost quadratic time

MOTIVATION: Evaluating all possible internal loops is one of the key steps in predicting the optimal secondary structure of an RNA molecule. The best algorithm available runs in time O(L(3)), L is the length of the RNA. RESULTS: We propose a new algorithm for evaluating internal loops, its run-time is O(M(*)log(2)L), M < L(2) is a number of possible nucleotide pairings. We created a software tool Afold which predicts the optimal secondary structure of RNA molecules of lengths up to 28 000 nt, using a computer with 2 Gb RAM. We also propose algorithms constructing sets of conditionally optimal multi-branch loop free (MLF) structures, e.g. the set that for every possible pairing (x, y) contains an optimal MLF structure in which nucleotides x and y form a pair. All the algorithms have run-time O(M(*)log(2)L).     

RNA pseudoknot prediction in energy-based models.

RNA molecules are sequences of nucleotides that serve as more than mere intermediaries between DNA and proteins, e.g., as catalytic molecules. Computational prediction of RNA secondary structure is among the few structure prediction problems that can be solved satisfactorily in polynomial time. Most work has been done to predict structures that do not contain pseudoknots. Allowing pseudoknots introduces modeling and computational problems. In this paper we consider the problem of predicting RNA secondary structures with pseudoknots based on free energy minimization. We first give a brief comparison of energy-based methods for predicting RNA secondary structures with pseudoknots. We then prove that the general problem of predicting RNA secondary structures containing pseudoknots is NP complete for a large class of reasonable models of pseudoknots.     

The hydrodynamic shape, conformation, and molecular model of Escherichia coli ribosomal 5 S RNA.

The structure of ribosomal 5 S RNA has been examined using several physical biochemical techniques. Hydrodynamic measurements yield a s020,omega and [eta] of 5.5 x 10(-13) x and 6.9 ml/g, respectively. Other parameters calculated from these values indicate the shape of 5 S RNA is consistent with that of a prolate ellipsoid 160 A in length and 32 A wide. Sedimentation equilibrium results show that 5 S RNA exists as a monomer in the reconstitution buffer with an apparent molecular weight of 44,000. Ultraviolet absorption difference spectra show that approximately 75% of the bases in 5 S RNA are involved in base pairing, and of these base pairs 70% are G-C and 30% are A-U. These results on the overall shape and secondary structure of 5 S RNA have been incorporated with the results of other investigators as to the possible location of single-stranded and double-stranded helical regions, and a molecular model for 5 S RNA is proposed. The molecular model consists of three double helices in the shape of a prolate ellipsoid, with two of the double helical regions at one end of the molecule. The structure is consistent with the available data on the structure and function of 5 S RNA and bears similarity to the molecular model proposed by Osterberg et al. ((1976) Eur. J. Biochem. 68, 481-487) based on small angle x-ray scattering results and the secondary structure proposed by Madison ((1968) Annu. Rev. Biochem. 37, 131-148).     

Thermodynamic heuristics with case-based reasoning: combined insights for RNA pseudoknot secondary structure

The secondary structure of RNA pseudoknots has been extensively inferred and scrutinized by computational approaches. Experimental methods for determining RNA structure are time consuming and tedious; therefore, predictive computational approaches are required. Predicting the most accurate and energy-stable pseudoknot RNA secondary structure has been proven to be an NP-hard problem. In this paper, a new RNA folding approach, termed MSeeker, is presented; it includes KnotSeeker (a heuristic method) and Mfold (a thermodynamic algorithm). The global optimization of this thermodynamic heuristic approach was further enhanced by using a case-based reasoning technique as a local optimization method. MSeeker is a proposed algorithm for predicting RNA pseudoknot structure from individual sequences, especially long ones. This research demonstrates that MSeeker improves the sensitivity and specificity of existing RNA pseudoknot structure predictions. The performance and structural results from this proposed method were evaluated against seven other state-of-the-art pseudoknot prediction methods. The MSeeker method had better sensitivity than the DotKnot, FlexStem, HotKnots, pknotsRG, ILM, NUPACK and pknotsRE methods, with 79% of the predicted pseudoknot base-pairs being correct.     

Modular evolution and increase of functional complexity in replicating RNA molecules

At early stages of biochemical evolution, the complexity of replicating molecules was limited by unavoidably high mutation rates. In an RNA world, prior to the appearance of cellular life, an increase in molecular length, and thus in functional complexity, could have been mediated by modular evolution. We describe here a scenario in which short, replicating RNA sequences are selected to perform a simple function. Molecular function is represented through the secondary structure corresponding to each sequence, and a given target secondary structure yields the optimal function in the environment where the population evolves. The combination of independently evolved populations may have facilitated the emergence of larger molecules able to perform more complex functions (including RNA replication) that could arise as a combination of simpler ones. We quantitatively show that modular evolution has relevant advantages with respect to the direct evolution of large functional molecules, among them the allowance of higher mutation rates, the shortening of evolutionary times, and the very possibility of finding complex structures that could not be otherwise directly selected.     

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.     

Identification and classification of ncRNA molecules using graph properties

The study of non-coding RNA genes has received increased attention in recent years fuelled by accumulating evidence that larger portions of genomes than previously acknowledged are transcribed into RNA molecules of mostly unknown function, as well as the discovery of novel non-coding RNA types and functional RNA elements. Here, we demonstrate that specific properties of graphs that represent the predicted RNA secondary structure reflect functional information. We introduce a computational algorithm and an associated web-based tool (GraPPLE) for classifying non-coding RNA molecules as functional and, furthermore, into Rfam families based on their graph properties. Unlike sequence-similarity-based methods and covariance models, GraPPLE is demonstrated to be more robust with regard to increasing sequence divergence, and when combined with existing methods, leads to a significant improvement of prediction accuracy. Furthermore, graph properties identified as most informative are shown to provide an understanding as to what particular structural features render RNA molecules functional. Thus, GraPPLE may offer a valuable computational filtering tool to identify potentially interesting RNA molecules among large candidate datasets.