@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},
     year=2013,
     isbn={978-3-642-40452-8},
     booktitle={Algorithms in Bioinformatics},
     volume=8126,
     series={Lecture Notes in Computer Science},
     editor={Darling, Aaron and Stoye, Jens},
     doi={10.1007/978-3-642-40453-5_10},
     url={http://dx.doi.org/10.1007/978-3-642-40453-5_10},
     publisher={Springer Berlin Heidelberg},
     pages={112-125},
     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 eects 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.} ,
  user =	 {backofen}
}