Algorithms for ranking and unranking the combinatorial set of RNA secondary structures

In this paper, we study the combinatorial set of RNA secondary structures of length $n$ with $m$ base-pairs. For a compact representation, we encode an RNA secondary structure by the corresponding Motzkin word. For this combinatorial set, we construct an AND/OR tree structure, find a bijection between the combinatorial set and the set of variants of the AND/OR tree, and develop algorithms for ranking and unranking the variants of the AND/OR tree. The developed ranking and unranking algorithms have polynomial time complexity $O(m^2(n-m))$ for $m<n-2m$ and $O(m(n-m{)}^2)$ for $m>n-2m$. In contrast to the existing algorithms, the new algorithms do not require preprocessing steps and have better time complexity.