%0 Book Section %1 statphys23_0324 %A Wolfsheimer, S. %A Burghardt, B. %A Hartmann, A.K. %B Abstract Book of the XXIII IUPAP International Conference on Statistical Physics %C Genova, Italy %D 2007 %E Pietronero, Luciano %E Loreto, Vittorio %E Zapperi, Stefano %K calculations density events matrix montecarlo rare rna secondary states statphys23 structure topic-10 transfer %T Complexity of RNA secondary structure and density of states calculations %U http://st23.statphys23.org/webservices/abstract/preview_pop.php?ID_PAPER=324 %X Models for RNA secondary structures (the topology of folded RNA) without pseudo knots have interesting properties: On one side they are complex systems with an ultrametric-like state-space structure, leading to high entropic barriers 1. Due to this fact, Monte Carlo methods to obtain ground-state properties (energy, degeneracy etc.) and density of states become stuck very quickly. On the other side, in contrast to many complex systems, the ground states and the density of states can be computed in polynomial time exactly. Hence, RNA secondary structure provides an ideal benchmark system for new Monte Carlo methods. Here we considered two different Monte Carlo approaches: Entropic sampling 2 as a prototype of ``flat histogram'' methods and ParQ, a transition matrix approach, which was suggested very recently 3. For entropic sampling we find a broad distribution of tunneling times, i.e.\ the tunneling time varies from sample to sample over several orders of magnitude, similar as in 4. The tunneling time can be described by a fat tailed generalized extreme value distribution (see fig.). As pointed out above, static properties of RNA secondary structure are computationally easy to obtain, hence we address the question: What makes a particular realization ``difficult'' for Monte Carlo algorithms? We investigated different quantities, which might characterize the ``complexity'' of realizations: The fraction of the number of ground states and the number of first excited states $g(E_1)/g(E_0)$, average overlap of ground states as well as deviation from ultrametricity. Most significant correlations could be found between $g(E_1)/g(E_0)$ and the tunneling time (see inset). Furthermore the relation between difficult realizations and relative error of both algorithms, entropic sampling and ParQ, comes out clearly. 1 P.G. Higgs, Phys.Rev.Lett. 76 404 (1996) 2 J. Lee, Phys. Rev. Lett. 71 , 2353 (1993) 3 F. Heilmann, K. H. Hoffmann, Europhys. Lett., 70 (2), 155 (2005) 4 P. Dayal et.al., Phys.Rev.Lett. 92 097201 (2004)

@incollection{statphys23_0324, abstract = {Models for RNA secondary structures (the topology of folded RNA) without pseudo knots have interesting properties: On one side they are complex systems with an ultrametric-like state-space structure, leading to high entropic barriers [1]. Due to this fact, Monte Carlo methods to obtain ground-state properties (energy, degeneracy etc.) and density of states become stuck very quickly. On the other side, in contrast to many complex systems, the ground states and the density of states can be computed in polynomial time exactly. Hence, RNA secondary structure provides an ideal benchmark system for new Monte Carlo methods. Here we considered two different Monte Carlo approaches: Entropic sampling [2] as a prototype of ``flat histogram'' methods and ParQ, a transition matrix approach, which was suggested very recently [3]. For entropic sampling we find a broad distribution of tunneling times, i.e.\ the tunneling time varies from sample to sample over several orders of magnitude, similar as in [4]. The tunneling time can be described by a fat tailed generalized extreme value distribution (see fig.). As pointed out above, static properties of RNA secondary structure are computationally easy to obtain, hence we address the question: What makes a particular realization ``difficult'' for Monte Carlo algorithms? We investigated different quantities, which might characterize the ``complexity'' of realizations: The fraction of the number of ground states and the number of first excited states $g(E_1)/g(E_0)$, average overlap of ground states as well as deviation from ultrametricity. Most significant correlations could be found between $g(E_1)/g(E_0)$ and the tunneling time (see inset). Furthermore the relation between difficult realizations and relative error of both algorithms, entropic sampling and ParQ, comes out clearly. [1] P.G. Higgs, Phys.Rev.Lett. 76 404 (1996) [2] J. Lee, Phys. Rev. Lett. 71 , 2353 (1993) [3] F. Heilmann, K. H. Hoffmann, Europhys. Lett., 70 (2), 155 (2005) [4] P. Dayal et.al., Phys.Rev.Lett. 92 097201 (2004)}, added-at = {2007-06-20T10:16:09.000+0200}, address = {Genova, Italy}, author = {Wolfsheimer, S. and Burghardt, B. and Hartmann, A.K.}, biburl = {https://www.bibsonomy.org/bibtex/2de84aa4baffe8ee4954dd96b91559bb4/statphys23}, booktitle = {Abstract Book of the XXIII IUPAP International Conference on Statistical Physics}, editor = {Pietronero, Luciano and Loreto, Vittorio and Zapperi, Stefano}, interhash = {a07dd4d7ab2a862e5118d9dfa464604c}, intrahash = {de84aa4baffe8ee4954dd96b91559bb4}, keywords = {calculations density events matrix montecarlo rare rna secondary states statphys23 structure topic-10 transfer}, month = {9-13 July}, timestamp = {2007-06-20T10:16:17.000+0200}, title = {Complexity of RNA secondary structure and density of states calculations}, url = {http://st23.statphys23.org/webservices/abstract/preview_pop.php?ID_PAPER=324}, year = 2007 }