Modular, k-noncrossing diagrams

MaRDI QIDQ976735zbMATH OpenFDO

Authors Christian M. Reidys, Rita R. Wang, Albus Y. Y. Zhao

Publication date 16 June 2010

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1003.2710, https://eudml.org/doc/226713, http://www.emis.de/journals/EJC/Volume_17/Abstracts/v17i1r76.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: In this paper we compute the generating function of modular, $k$-noncrossing diagrams. A $k$-noncrossing diagram is called modular if it does not contains any isolated arcs and any arc has length at least four. Modular diagrams represent the deformation retracts of RNA pseudoknot structures cite{Stadler:99,Reidys:07pseu,Reidys:07lego} and their properties reflect basic features of these bio-molecules. The particular case of modular noncrossing diagrams has been extensively studied cite{Waterman:78b, Waterman:79,Waterman:93, Schuster:98}. Let ${sfQ}_k(n)$ denote the number of modular $k$-noncrossing diagrams over $n$ vertices. We derive exact enumeration results as well as the asymptotic formula ${sfQ}_k(n)sim{c}_k{n}^{-(k-1{)}^2-frack-12}gamm{a}_k^{-n}$ for $k=3,\mathrm{...},9$ and derive a new proof of the formula ${sfQ}_2(n)sim1.4848,n^{-3/2},1.8489^{-n}$ cite{Schuster:98}.

Review text

Summary: We compute the generating function of modular, \(k\)-noncrossing diagrams. A \(k\)-noncrossing diagram is called modular if it does not contain any isolated arcs and any arc has length at least four. Modular diagrams represent the deformation retracts of RNA tertiary structures and their properties reflect basic features of these bio-molecules. The particular case of modular noncrossing diagrams has been extensively studied. Let \(\mathbb{Q}_k(n)\) denote the number of modular \(k\)-noncrossing diagrams over \(n\) vertices. We derive exact enumeration results as well as the asymptotic formula \[ \mathbb{Q}_k(n)\sim c_kn^{-(-1)^2-{k-1\over 2}}\gamma^{-n}_k \] for \(k=3,\dots,9\) and derive a new proof of the formula \(\mathbb{Q}_2(n)\sim 1.8489^n\) [\textit{I. L. Hofacker}, \textit{P. Schuster} and \textit{P. F. Stadler}, Discrete Appl. Math. 88, No. 1--3, 207--237 (1998; Zbl 0918.05004)].

Recommendations

• On the uniform generation of modular diagrams
• Efficient counting and asymptotics of \(k\)-noncrossing tangled diagrams
• Asymptotic enumeration of RNA structures with pseudoknots
• On the decomposition of \(k\)-noncrossing RNA structures
• Combinatorics of RNA structures with pseudoknots

Cited in

(11)

• Efficient counting and asymptotics of \(k\)-noncrossing tangled diagrams
• On the decomposition of \(k\)-noncrossing RNA structures
• The block spectrum of RNA pseudoknot structures
• On RNA-RNA interaction structures of fixed topological genus
• Statistics of topological RNA structures
• k-noncrossing and k-nonnesting graphs and fillings of Ferrers diagrams
• Topological classification and enumeration of RNA structures by genus
• On the uniform generation of modular diagrams
• The KOH terms and classes of unimodal \(N\)-modular diagrams
• Combinatorial analysis of interacting RNA molecules
• Combinatorics of RNA-RNA interaction

This page was built for publication: Modular, \(k\)-noncrossing diagrams

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q976735)