@incollection{backofen13:_distr_graph_distan_boltz_ensem,
author = {Backofen, Rolf and Fricke, Markus and Marz, Manja and Qin, Jing
          and Stadler, Peter F.},
title = {Distribution of Graph-Distances in Boltzmann Ensembles of RNA Secondary Structures},
booktitle = {Algorithms in Bioinformatics},
year = {2013},
doi = {10.1007/978-3-642-40453-5_10},
url = {http://dx.doi.org/10.1007/978-3-642-40453-5_10},
volume = {8126},
user = {backofen},
series = {Lecture Notes in Computer Science},
publisher = {Springer Berlin Heidelberg},
pages = {112-125},
isbn = {978-3-642-40452-8},
editor = {Darling, Aaron and Stoye, Jens},
abstract = {Large RNA molecules often carry multiple functional
            domains whose spatial arrangement is an important
            determinant of their function. Pre-mRNA splicing,
            furthermore, relies on the spatial proximity of the
            splice junctions that can be separated by very long
            introns. Similar e
            ects appear in the processing of
            RNA virus genomes. Albeit a crude measure, the
            distribution of spatial distances in thermodynamic
            equilibrium therefore provides useful information on
            the overall shape of the molecule can provide 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
            arbitrary nucleotides can be computed in polynomial
            time by means of dynamic programming. A naive
            implementation would yield recursions with a very high
            time complexity of O(n11). Although we were able to
            reduce this to O(n6) for many practical applications a
            further reduction seems dicult. We conclude,
            therefore, that sampling approaches, which are much
            easier to implement, are also theoretically favorable
            for most real-life applications, in particular since
            these primarily concern long-range interactions in
            very large RNA molecules.}
}