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

Autor:	Shablya, Yuriy, Kruchinin, Dmitry
Rok vydání:	2023
Předmět:	Computer Science - Data Structures and Algorithms Computer Science - Discrete Mathematics 68R05 G.2.1
Druh dokumentu:	Working Paper
Popis:	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 - 2 m$ and $O(m (n - m)^2)$ for $m > n - 2 m$. In contrast to the existing algorithms, the new algorithms do not require preprocessing steps and have better time complexity. Comment: 14 pages
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2301.11890 Zobrazit plný text záznamu View this record from Arxiv