Abstract:  In this paper we introduce a combinatorial framework which provides an interpretation of RNA pseudoknot structures as sampling paths of a Markov process. Our results give insight into the cross-serial interactions of RNA pseudoknot structures, i.e., their crossings. They 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 which generates RNA pseudoknot structures with uniform probability in linear time. This algorithm serves as a stepping stone to sequence specific as well as energy based transition probabilities. The approach employs a correspondence between pseudoknotstructures, parametrized in terms of themaximal number of mutually crossing arcs and certain tableau sequences. The latter can be viewed as lattice paths, whose generating functions are shown to be D-finite. 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.

  AMS Classification: 

  Keywords:   

  Download:   pdf