Random K-noncrossing RNA structures.

Abstract

In this paper, we introduce a combinatorial framework that provides an interpretation of RNA pseudoknot structures as sampling paths of a Markov process. Our results facilitate a variety of applications ranging from the energy-based sampling of pseudoknot structures as well as the ab initio folding via hidden Markov models. Our main result is an algorithm that generates RNA pseudoknot structures with uniform probability. This algorithm serves as a steppingstone to sequence-specific as well as energy-based transition probabilities. The approach employs a correspondence between pseudoknot structures, parametrized in terms of the maximal number of mutually crossing arcs and certain tableau sequences. The latter can be viewed as lattice paths. The main idea of this paper is to view each such lattice path as a sampling path of a stochastic process and to make use of D-finiteness for the efficient computation of the corresponding transition probabilities.