title: Graph-distance distribution of the Boltzmann ensemble of RNA secondary structures.
abstract: 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.
  
  
  RESULTS
  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 (6) D (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 http://www.rna.uni-jena.de/RNAgraphdist.html.
authors.affiliation: Department of Mathematics and Computer Science, Campusvej 55, DK-5230, Odense M, Denmark.
authors.forename: Jing
authors.initials: J
authors.lastname: Qin
authors.affiliation: Bioinformatics/High Throughput Analysis Faculty of Mathematics und Computer Science Friedrich-Schiller-University, Leutragraben 1, D-07743 Jena, Germany.
authors.forename: Markus
authors.initials: M
authors.lastname: Fricke
authors.affiliation: Bioinformatics/High Throughput Analysis Faculty of Mathematics und Computer Science Friedrich-Schiller-University, Leutragraben 1, D-07743 Jena, Germany.
authors.forename: Manja
authors.initials: M
authors.lastname: Marz
authors.affiliation: Max Planck Institute for Mathematics in the Sciences, Inselstraße 22, D-04103 Leipzig, Germany ; Bioinformatics Group, Department of Computer Science, and Interdisciplinary Center for Bioinformatics, University of Leipzig, Härtelstrasse 16-18, D-04107 Leipzig, Germany ; Fraunhofer Institut for Cell Therapy and Immunology, Perlickstraße 1, D-04103 Leipzig, Germany ; Institute for Theoretical Chemistry, University of Vienna, Währingerstrasse 17, A-1090 Vienna, Austria ; Santa Fe Institute, 1399 Hyde Park Rd., NM87501 Santa Fe, USA.
authors.forename: Peter F
authors.initials: PF
authors.lastname: Stadler
authors.affiliation: Department of Computer Science, Chair for Bioinformatics, University of Freiburg, Georges-Koehler-Allee 106, D-79110 Freiburg, Germany ; Center for Biological Signaling Studies (BIOSS), Albert-Ludwigs-Universität, Freiburg, Germany.
authors.forename: Rolf
authors.initials: R
authors.lastname: Backofen
keywords: Boltzmann distribution; Graph-distance; Partition function; Pre-mRNA splicing; smFRET