Publica
Hier finden Sie wissenschaftliche Publikationen aus den FraunhoferInstituten. Distribution of graphdistances in Boltzmann ensembles of RNA secondary structures
 Darling, A.: Algorithms in bioinformatics. 13th international workshop, WABI 2013 : Sophia Antipolis, France, September 24, 2013; Proceedings Berlin: Springer, 2013 (Lecture Notes in Computer Science 8126) ISBN: 3642404529 ISBN: 9783642404528 (Print) ISBN: 9783642404535 (Online) pp.112125 
 International Workshop on Algorithms in Bioinformatics (WABI) <13, 2013, Sophia Antipolis> 

 English 
 Conference Paper 
 Fraunhofer IZI () 
Abstract
Large RNA molecules often carry multiple functional domains whose spatial arrangement is an important determinant of their function. PremRNA 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 graphdistance in RNA secondary structure. We show here that the equilibrium distribution of graphdistances 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 difficult. We conclude, therefore, that sampling approaches, which are much easier to implement, are also theoretically favorable for most reallife applications, in particular since these primarily concern longrange interactions in very large RNA molecules.