@article{Qin_Fricke_Marz-Graph_distr_the-2014,
author = {Qin, Jing and Fricke, Markus and Marz, Manja and Stadler, 
          Peter F. and Backofen, Rolf},
title = {Graph-distance distribution of the {Boltzmann} ensemble of 
         {RNA} secondary structures},
journal = {Algorithms Mol Biol},
year = {2014},
doi = {10.1186/1748-7188-9-19},
volume = {9},
user = {backofen},
pmid = {25285153},
pages = {19},
number = {},
issn = {1748-7188},
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. 
            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 naive 
            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.}
}