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

In this paper, we study the combinatorial set of RNA secondary structures. The main contribution of this paper is the developed ranking and unranking algorithms for the combinatorial set of pseudoknot-free RNA secondary structures of length [Formula: see text] with [Formula: see text] base-pairs. The developed algorithms are based on a bijection between the set of RNA structures and the variants of the corresponding AND/OR tree structure. Assuming a unit-cost RAM model, the developed algorithms have polynomial time complexity [Formula: see text] for [Formula: see text] and [Formula: see text] for [Formula: see text]. In contrast to the existing algorithms, the new algorithms do not require preprocessing steps and have better overall time complexity.