The functional form of single stranded RNA molecules (like proteins) frequently requires a specific tertiary structure. The scaffold for this structure is provided by secondary structural elements which are hydrogen bonds within the molecule. This leads to several recognizable "domains" of secondary structure like hairpin loops, bulges and internal loops. There has been a significant amount of bioinformatics research directed at the RNA structure prediction problem. This article or section does not adequately cite its references or sources. ... A representation of the 3D structure of myoglobin, showing coloured alpha helices. ... Snapshot from a simulation of liquid water. ... Hairpin structure of RNA A hairpin loop in RNA is a sequence of nucleotides where a long segment of RNA can base-pair with each other, but a segment within that sequence can not base pair, causing a hairpin loop. ... Map of the human X chromosome (from the NCBI website). ...

Single sequence structure prediction

A common problem for researchers working with RNA is to determine the three-dimensional structure of the molecule given just the nucleic acid sequence. However, in the case of RNA much of the final structure is determined by the secondary structure or intra-molecular base-pairing interactions of the molecule. This is shown by the high conservation of base-pairings across diverse species. A representation of the 3D structure of the Myoglobin protein. ... Base pairs, of a DNA molecule. ...

One of the first attempts to predict RNA secondary structure was made by Ruth Nussinov and co-workers who used dynamic programming method for maximising the number of base-pairs (Nussinov 1978). However, there are several issues with this approach, most importantly the solution is not unique. Nussinov et al published an adaptation of their approach to use a simple nearest-neighbour energy model in 1980 (Nussinov 1980). Michael Zuker and Patrick Stiegler in 1981 proposed using a slightly refined dynamic programming approach that models nearest neighbour energy interactions that directly incorporates stacking into the prediction (Zuker 1981). The energies that are minimized by the recursion are derived from empirical calorimetric experiments, the most up-to-date parameters were published in 1999 (Mathews 1999). There has been recent progress in estimating "energy" parameters directly from known structures (Do 2006). Another approach researchers are using is to sample structures from the Boltzmann ensemble (McCaskill 1990, Ding 2003). In computer science, dynamic programming is a method of solving problems exhibiting the properties of overlapping subproblems and optimal substructure (described below) that takes much less time than naive methods. ... Ludwig Boltzmann Ludwig Boltzmann (February 20, 1844 – September 5, Austrian physicist famous for the invention of statistical mechanics. ...

One of the issues when predicting RNA secondary structure is that the standard recursions (eg. Nussinov/Zuker-Stiegler) exclude pseudoknot. Elena Rivas and Sean Eddy published a dynamic programming algorithm that could handle pseudoknots (Rivas 1999). However, the time and memory requirements of the method are prohibitive. This has prompted several researchers to implement versions of the algorithm that restrict the classes of pseudoknots, resulting in gains in performance. A pseudoknot is a RNA secondary structure that is minimally composed of two helical segments connected by single-stranded regions or loops. ...

S. cerevisiae tRNA-PHE structure space: the energies and structures were calculated using RNAsubopt and the structure distances computed using RNAdistance.

Comparative structure prediction

Align and fold

Evolution frequently preserves functional RNA structure better the RNA sequences. Hence, a common biological problem is to infer a common structure for two or more different RNA sequences. One of the first rigorous mathematical treatments of this problem was by David Sankoff (Sankoff 1985). However, this approach is notoriously computationally expensive. Some notable attempts at implementing restricted versions of Sankoff's algorithm are Foldalign (Havgaard 2005, Torarinsson 2007), Dynalign (Mathews 2002) and PMmulti/PMcomp (Hofacker 2004). This article is about evolution in biology. ...

Align then fold

A practical but heuristic approach is to use multiple sequence alignment tools to produce an alignment of several RNA sequences and then attempt to detect covarying (base paired) sites in the alignment. A common method is to use the mutual Information content (Chiu 1991, Gutell 1992), however, recent work has shown that this measure does not detect RNA structure covariation very well (Lindgreen 2006). Some alternative approaches using a sum of energetic and covariance terms (Hofacker 2002) or evolutionary SCFGs (Knudsen 2003) have been implemented. In computer science, besides the common use as rule of thumb (see heuristic), the term heuristic has two well-defined technical meanings. ... First 90 positions of a protein multiple sequence alignment of instances of the acidic ribosomal protein P0 (L10E) from several organisms. ... In probability theory and, in particular, information theory, the mutual information, or transinformation, of two random variables is a quantity that measures the mutual dependence of the two variables. ... A stochastic context-free grammar (SCFG; also probabilistic context-free grammar, PCFG) is a context-free grammar in which each production is augmented with a probability. ...

Fold then align

A less widely used approach is to fold the sequences using single sequence structure prediction methods and align the resulting structures using tree-based metrics (Shapiro 1990). The fundamental weakness with this approach is that single sequence predictions are often inaccurate, thus all further analyses are affected.

Tertiary structure prediction

Ab initio modelling

• Major F, Turcotte M, Gautheret D, Lapalme G, Fillion E, Cedergren R. The combination of symbolic and numerical computation for three-dimensional modeling of RNA. Science. 1991 Sep 13;253(5025):1255-60.

• Major F, Gautheret D, Cedergren R. Reproducing the three-dimensional structure of a tRNA molecule from structural constraints. Proc Natl Acad Sci U S A. 1993 Oct 15;90(20):9408-12.

Comparative modelling

References

• Chiu, D.K. and Kolodziejczak, T. (1991) Inferring consensus structure from nucleic acid sequences. Comput. Appl. Biosci, . 7, 347–352
• Ding Y, Lawrence CE. (2003) A statistical sampling algorithm for RNA secondary structure prediction. Nucleic Acids Res. 31(24):7280-301.
• Do CB, Woods DA, Batzoglou S. (2006) CONTRAfold: RNA secondary structure prediction without physics-based models. Bioinformatics. 22(14):e90-8.
• Gutell, R.R., et al. (1992) Identifying constraints on the higher-order structure of RNA: continued development and application of comparative sequence analysis methods. Nucleic Acids Res, . 20, 5785–5795
• Havgaard JH, Lyngso RB, Stormo GD, Gorodkin J. (2005) Pairwise local structural alignment of RNA sequences with sequence similarity less than 40%. Bioinformatics. 21(9):1815-24.
• Hofacker IL, Bernhart SH, Stadler PF. (2004) Alignment of RNA base pairing probability matrices. Bioinformatics. 20(14):2222-7.
• Hofacker IL, Fekete M, Stadler PF. (2002) Secondary structure prediction for aligned RNA sequences. J Mol Biol. 319(5):1059-66.
• Knudsen B, Hein J. (2003) Pfold: RNA secondary structure prediction using stochastic context-free grammars. Nucleic Acids Res. 31(13):3423-8.
• Lindgreen S, Gardner PP, Krogh A. (2006) Measuring covariation in RNA alignments: physical realism improves information measures. Bioinformatics. 22(24):2988-95.
• Mathews DH, Sabina J, Zuker M, Turner DH (1999) Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structure. J Mol Biol. 288(5):911-40.
• Mathews DH, Turner DH. (2002) Dynalign: an algorithm for finding the secondary structure common to two RNA sequences. J Mol Biol. 317(2):191-203.
• McCaskill JS. (1990) The equilibrium partition function and base pair binding probabilities for RNA secondary structure. Biopolymers. 29(6-7):1105-19.
• Nussinov R, Piecznik G, Grigg JR and Kleitman DJ (1978) Algorithms for loop matchings. SIAM Journal on Applied Mathematics.
• Nussinov R and Jacobson AB (1980) Fast algorithm for predicting the secondary structure of single-stranded RNA. Proc Natl Acad Sci U S A. 77(11):6309-13.
• Rivas E, Eddy SR. (1999) A dynamic programming algorithm for RNA structure prediction including pseudoknots. J Mol Biol. 285(5):2053-68.
• Sankoff D (1985) Simultaneous solution of the RNA folding, alignment and protosequence problems. SIAM Journal on Applied Mathematics. 45:810-825.
• Torarinsson E, Havgaard JH, Gorodkin J. (2007) Multiple structural alignment and clustering of RNA sequences. Bioinformatics.
• Zuker M, Stiegler P. (1981) Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information. Nucleic Acids Res. Jan 10;9(1):133-48.
• Shapiro BA and Zhang K (1990) Comparing Multiple RNA Secondary Structures Using Tree Comparisons Computer Applications in the Biosciences, vol. 6, no. 4, pp. 309-318.

See also

• RNA
• Non-coding RNA

This article or section does not adequately cite its references or sources. ... A non-coding RNA (ncRNA) is any RNA molecule that is not translated into a protein. ...

External links

Analyses and links to RNA analysis tools are available from Wikiomics.