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

Jing Qin, Markus Fricke, Manja Marz, Peter Stadler, Rolf Backofen

Research output: Contribution to journalJournal articleResearchpeer-review


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 6D 5) for sequence length n and D distinct distance values, it is possible to reduce this to O(n 4) 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

Original languageEnglish
Article number19
JournalAlgorithms for Molecular Biology
Issue number1
Number of pages20
Publication statusPublished - 11. Sept 2014


  • Boltzmann distribution
  • Graph-distance
  • Partition function
  • Pre-mRNA splicing
  • smFRET


Dive into the research topics of 'Graph-distance distribution of the Boltzmann ensemble of RNA secondary structures'. Together they form a unique fingerprint.

Cite this