Random $k$-noncrossing RNA Structures

Abstract

In this paper we derive polynomial time algorithms that generate random $k$-noncrossing matchings and $k$-noncrossing RNA structures with uniform probability. Our approach employs the bijection between $k$-noncrossing matchings and oscillating tableaux and the $P$-recursiveness of the cardinalities of $k$-noncrossing matchings. The main idea is to consider the tableaux sequences as paths of stochastic processes over shapes and to derive their transition probabilities.

19 pages, 8 figures

Cited by in corpus (9)

• The scarcity of crossing dependencies: a direct outcome of a specific constraint?
• A stronger null hypothesis for crossing dependencies
• Non-crossing dependencies: least effort, not grammar
• A generating tree approach to k-nonnesting partitions and permutations
• Set partitions with no m-nesting
• Edge crossings in random linear arrangements
• Random $k$-noncrossing partitions
• Reappraising the distribution of the number of edge crossings of graphs on a sphere
• Random 3-noncrossing partitions