Shapes of RNA pseudoknot structures

Abstract

In this paper we study abstract shapes of $k$-noncrossing, $\sigma$-canonical RNA pseudoknot structures. We consider ${\mathsf{lv}}_k^1$- and ${\mathsf{lv}}_k^5$-shapes, which represent a generalization of the abstract ${\pi }^{\prime }$- and $\pi$-shapes of RNA secondary structures introduced by \citet{Giegerich:04ashape}. Using a novel approach we compute the generating functions of ${\mathsf{lv}}_k^1$- and ${\mathsf{lv}}_k^5$-shapes as well as the generating functions of all ${\mathsf{lv}}_k^1$- and ${\mathsf{lv}}_k^5$-shapes induced by all $k$-noncrossing, $\sigma$-canonical RNA structures for fixed $n$. By means of singularity analysis of the generating functions, we derive explicit asymptotic expressions.

24 pages, 7 figures,

References in corpus (1)

• Asymptotic analysis of $k$-noncrossing matchings