Graph-distance distribution of the Boltzmann ensemble of RNA secondary structures

Algorithms for Molecular Biology

Jing Qin¹  Markus Fricke²  Manja Marz²  Peter F Stadler⁴  Rolf Backofen³ 

[1] Department of Mathematics and Computer Science, Campusvej 55, DK-5230, Odense M, Denmark

[2] Bioinformatics/High Throughput Analysis Faculty of Mathematics und Computer Science Friedrich-Schiller-University, Leutragraben 1, D-07743 Jena, Germany

[3] Center for Biological Signaling Studies (BIOSS), Albert-Ludwigs-Universität, Freiburg, Germany

[4] Santa Fe Institute, 1399 Hyde Park Rd., NM87501 Santa Fe, USA

关键词: smFRET;    Pre-mRNA splicing;    Partition function;    Boltzmann distribution;    Graph-distance;   

Others  :  1082116
DOI  :  10.1186/1748-7188-9-19

 received in 2013-11-30, accepted in 2014-06-30,  发布年份 2014

【 摘 要 】

Background

Large RNA molecules are often composed of multiple functional domains whose spatial arrangement strongly influences their function. Pre-mRNA splicing, for instance, relies on the spatial proximity of the splice junctions that can be separated by very long introns. Similar effects appear in the processing of RNA virus genomes. Albeit a crude measure, the distribution of spatial distances in thermodynamic equilibrium harbors useful information on the shape of the molecule that in turn can give insights into the interplay of its functional domains.

Result

Spatial distance can be approximated by the graph-distance in RNA secondary structure. We show here that the equilibrium distribution of graph-distances between a fixed pair of nucleotides can be computed in polynomial time by means of dynamic programming. While a naïve implementation would yield recursions with a very high time complexity of O(n⁶D⁵) for sequence length n and D distinct distance values, it is possible to reduce this to O(n⁴) for practical applications in which predominantly small distances are of of interest. Further reductions, however, seem to be difficult. Therefore, we introduced sampling approaches that are much easier to implement. They are also theoretically favorable for several real-life applications, in particular since these primarily concern long-range interactions in very large RNA molecules.

Conclusions

The graph-distance distribution can be computed using a dynamic programming approach. Although a crude approximation of reality, our initial results indicate that the graph-distance can be related to the smFRET data. The additional file and the software of our paper are available from http://www.rna.uni-jena.de/RNAgraphdist.html webcite.

【 授权许可】

   
2014 Qin et al.; licensee BioMed Central Ltd.

【 图 表 】

Figure 1.

Figure 2.

Figure 3.

Figure 4.

Figure 5.

Figure 6.

【 参考文献 】

• [1]Yoffe AM, Prinsen P, Gelbart WM, Ben-Shaul A: The ends of a large RNA molecule are necessarily close. Nucl Acids Res 2011, 39:292-299.
• [2]Fang LT: The end-to-end distance of RNA as a randomly self-paired polymer. J Theor Biol 2011, 280:101-107.
• [3]Clote P, Ponty Y, Steyaert JM: Expected distance between terminal nucleotides of RNA secondary structures. J Math Biol 2012, 65:581-599.
• [4]Han HS, Reidys CM: The 5’-3’ distance of RNA secondary structures. J Comput Biol 2012, 19:867-878.
• [5]Forties RA, Bundschuh R: Modeling the interplay of single-stranded binding proteins and nucleic acid secondary structure. Bioinformatics 2010, 26:61-67.
• [6]Gerland U, Bundschuh R, Hwa T: Force-induced denaturation of RNA. Biophys J 2001, 81:1324-1332.
• [7]Müller M, Krzakala F, Mézard M: The secondary structure of RNA under tension. Eur Phys J E 2002, 9:67-77.
• [8]Gerland U, Bundschuh R, Hwa T: Translocation of structured polynucleotides through nanopores. Phys Biol 2004, 1:19-26.
• [9]Einert TR, Näger P, Orland H, Netz R: Impact of loop statistics on the thermodynamics of RNA Folding. Phys Rev Lett 2008, 101:048103.
• [10]Roy R, Hohng S, Ha T: A practical guide to single-molecule FRET. Nat Methods 2008, 5:507-516.
• [11]Das R, Baker D: Automated de novo prediction of native-like RNA tertiary structures. Proc Natl Acad Sci USA 2007, 104:14664-14669.
• [12]Kobitski A, Nierth A, Helm M, Jaschke A, Nienhaus UG: Mg2+-dependent folding of a Diels-Alderase ribozyme probed by single-molecule FRET analysis. Nucleic Acids Res 2007, 35(6):2047-2059.
• [13]Schuster P, Fontana W, Stadler PF, Hofacker IL: From sequences to shapes and back: a case study in RNA secondary structures. Proc R Soc London B 1994, 255(1344):279-84.
• [14]Mathews DH, Disney MD, Childs JL, Schroeder SJ, Zuker M, Turner DH: Incorporating chemical modification constraints into a dynamic programming algorithm for prediction of RNA secondary structure. Proc Natl Acad Sci USA 2004, 101:7287-7292.
• [15]McCaskill JS: The equilibrium partition function and base pair binding probabilities for RNA secondary structure. Biopolymers 1990, 29(6–7):1105-1119.
• [16]Lorenz R, Bernhart SH, Höner zu Siederdissen C, Tafer H, Flamm C, Stadler PF, Hofacker IL: ViennaRNA Package 2.0. Alg Mol Biol 2011, 6:26. BioMed Central Full Text
• [17]Lyngsø RB, Zuker M, Pedersen C: Fast evaluation of internal loops in RNA secondary structure prediction. Bioinformatics 1999, 15:440-445.
• [18]Ding Y, Lawrence C: A statistical sampling algorithm for RNA secondary structure prediction. Nucl Acids Res 2003, 31(24):7280-7301.
• [19]Fredman M, Tarjan R: Fibonacci heaps and their uses in improved network optimization algorithms. J ACM 1987, 34(3):596-615.
• [20]Darty K, Denise A, Ponty Y: VARNA: Interactive drawing and editing of the RNA secondary structure. Bioinformatics 2009, 25(15):1974-1975.
• [21]Leipply D, Lambert D, Draper DE: Ion-RNA interactions thermodynamic analysis of the effects of mono- and divalent ions on RNA conformational equilibria. Methods Enzymol 2009, 469:433-463.
• [22]Mathews D, Sabina J, Zuker M, Turner DH: Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structure. J Mol Biol 1999, 288:911-940.
• [23]Baraniak AP, Lasda EL, Wagner EJ, Garcia-Blanco MA: A stem structure in fibroblast growth factor receptor 2 transcripts mediates cell-type-specific splicing by approximating intronic control elements. Mol Cell Biol 2003, 23:9327-9337.
• [24]McManus CJ, Graveley BR: RNA structure and the mechanisms of alternative splicing. Curr Opin Genet Dev 2011, 21:373-379.
• [25]Amman F, Bernhart S, Doose D, Hofacker I, Qin J, Stadler P, Will S: The Trouble with Long-Range Base Pairs in RNA Folding. In Lecture Notes in Computer Science: Advances in Bioinformatics and Computational Biology, Volume 8213. Berlin, Heidelberg, New York: Springer-Verlag; 2013:1-11.
• [26]Celotto A, Graveley B: Exon-specific RNAi: a tool for dissecting the functional relevance of alternative splicing. RNA 2002, 8(6):718-724.
• [27]Dufour D, Mateos-Gomez PA, Enjuanes L, Gallego J, Sola I: Structure and functional relevance of a transcription-regulating sequence involved in coronavirus discontinuous RNA synthesis. J Virol 2011, 85(10):4963-4973.
• [28]Giegerich R, Meyer C: Algebraic dynamic programming. In Algebraic Methodology And Software Technology. Berlin, Heidelberg, New York: Springer-Verlag; 2002:349-364.
• [29]Reidys CM, Huang FWD, Andersen JE, Penner RC, Stadler PF, Nebel ME: Topology and prediction of RNA pseudoknots. Bioinformatics 2011, 27(8):1076-1085.
• [30]Lorenz R, Bernhart S, Qin J, Honer zu, Siederdissen C, Tanzer A, Amman F, Hofacker I: 2D meets 4G: G-Quadruplexes in RNA Secondary Structure Prediction. IEEE/ACM Trans Comput Biol Bioinformaticsdoi:10.1109/TCBB.2013.7
• [31]Li AX, Marz M, Qin J, Reidys CM: RNA-RNA interaction prediction based on multiple sequence alignments. Bioinformatics 2011, 27(4):456-463.
• [32]Senter E, Sheikh S, Dotu I, Ponty Y, Clote P: Using the fast fourier transform to accelerate the computational search for RNA conformational switches. PLoS ONE 2012, 7(12):e50506.