TY - GEN

T1 - Distribution of Graph-Distances in Boltzmann Ensembles of RNA Secondary Structures

AU - Backofen, Rolf

AU - Fricke, Markus

AU - Marz, Manja

AU - Qin, Jing

AU - Stadler, Peter F.

N1 - The WABI proceedings will be published in the Lecture Notes in Computer Science: Lecture Notes in Bioinformatics series by Springer-Verlag.

PY - 2013

Y1 - 2013

N2 - 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 effects 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(n
11). Although we were able to reduce this to O(n
6) for many practical applications a further reduction seems difficult. 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.

AB - 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 effects 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(n
11). Although we were able to reduce this to O(n
6) for many practical applications a further reduction seems difficult. 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.

U2 - 10.1007/978-3-642-40453-5_10

DO - 10.1007/978-3-642-40453-5_10

M3 - Article in proceedings

SN - 9783642404528

T3 - Lecture Notes in Computer Science

SP - 112

EP - 125

BT - Algorithms in Bioinformatics

A2 - Darling, Aaron

A2 - Stoye, Jens

PB - Springer

T2 - 13th International Workshop, WABI 2013

Y2 - 2 September 2013 through 4 September 2013

ER -