Graph-distance distribution of the Boltzmann ensemble of RNA secondary structures
Tóm tắt
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. 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(n6D5) for sequence length n and D distinct distance values, it is possible to reduce this to O(n4) 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. 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
.
Tài liệu tham khảo
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. 10.1093/nar/gkq642.
Fang LT: The end-to-end distance of RNA as a randomly self-paired polymer. J Theor Biol. 2011, 280: 101-107. 10.1016/j.jtbi.2011.04.010.
Clote P, Ponty Y, Steyaert JM: Expected distance between terminal nucleotides of RNA secondary structures. J Math Biol. 2012, 65: 581-599. 10.1007/s00285-011-0467-8.
Han HS, Reidys CM: The 5’-3’ distance of RNA secondary structures. J Comput Biol. 2012, 19: 867-878. 10.1089/cmb.2011.0301.
Forties RA, Bundschuh R: Modeling the interplay of single-stranded binding proteins and nucleic acid secondary structure. Bioinformatics. 2010, 26: 61-67. 10.1093/bioinformatics/btp627.
Gerland U, Bundschuh R, Hwa T: Force-induced denaturation of RNA. Biophys J. 2001, 81: 1324-1332. 10.1016/S0006-3495(01)75789-X.
Müller M, Krzakala F, Mézard M: The secondary structure of RNA under tension. Eur Phys J E. 2002, 9: 67-77.
Gerland U, Bundschuh R, Hwa T: Translocation of structured polynucleotides through nanopores. Phys Biol. 2004, 1: 19-26. 10.1088/1478-3967/1/1/002.
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-
Roy R, Hohng S, Ha T: A practical guide to single-molecule FRET. Nat Methods. 2008, 5: 507-516. 10.1038/nmeth.1208.
Das R, Baker D: Automated de novo prediction of native-like RNA tertiary structures. Proc Natl Acad Sci USA. 2007, 104: 14664-14669. 10.1073/pnas.0703836104.
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. 10.1093/nar/gkm072.
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. 10.1098/rspb.1994.0040.
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. 10.1073/pnas.0401799101.
McCaskill JS: The equilibrium partition function and base pair binding probabilities for RNA secondary structure. Biopolymers. 1990, 29 (6–7): 1105-1119.
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-10.1186/1748-7188-6-26.
Lyngsø RB, Zuker M, Pedersen C: Fast evaluation of internal loops in RNA secondary structure prediction. Bioinformatics. 1999, 15: 440-445. 10.1093/bioinformatics/15.6.440.
Ding Y, Lawrence C: A statistical sampling algorithm for RNA secondary structure prediction. Nucl Acids Res. 2003, 31 (24): 7280-7301. 10.1093/nar/gkg938.
Fredman M, Tarjan R: Fibonacci heaps and their uses in improved network optimization algorithms. J ACM. 1987, 34 (3): 596-615. 10.1145/28869.28874.
Darty K, Denise A, Ponty Y: VARNA: Interactive drawing and editing of the RNA secondary structure. Bioinformatics. 2009, 25 (15): 1974-1975. 10.1093/bioinformatics/btp250.
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.
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. 10.1006/jmbi.1999.2700.
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. 10.1128/MCB.23.24.9327-9337.2003.
McManus CJ, Graveley BR: RNA structure and the mechanisms of alternative splicing. Curr Opin Genet Dev. 2011, 21: 373-379. 10.1016/j.gde.2011.04.001.
Amman F, Bernhart S, Doose D, Hofacker I, Qin J, Stadler P, Will S: The Trouble with Long-Range Base Pairs in RNA Folding. Lecture Notes in Computer Science: Advances in Bioinformatics and Computational Biology, Volume 8213. 2013, Berlin, Heidelberg, New York: Springer-Verlag, 1-11.
Celotto A, Graveley B: Exon-specific RNAi: a tool for dissecting the functional relevance of alternative splicing. RNA. 2002, 8 (6): 718-724. 10.1017/S1355838202021064.
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. 10.1128/JVI.02317-10.
Giegerich R, Meyer C: Algebraic dynamic programming. Algebraic Methodology And Software Technology. 2002, Berlin, Heidelberg, New York: Springer-Verlag, 349-364.
Reidys CM, Huang FWD, Andersen JE, Penner RC, Stadler PF, Nebel ME: Topology and prediction of RNA pseudoknots. Bioinformatics. 2011, 27 (8): 1076-1085. 10.1093/bioinformatics/btr090.
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 Bioinformatics. doi:10.1109/TCBB.2013.7,
Li AX, Marz M, Qin J, Reidys CM: RNA-RNA interaction prediction based on multiple sequence alignments. Bioinformatics. 2011, 27 (4): 456-463. 10.1093/bioinformatics/btq659.
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-10.1371/journal.pone.0050506.