Efficient pattern matching for RNA secondary structures

We propose efficient methods to address key pattern matching problems in RNA secondary structures using the notion of structural strings. A structural string (s-string) is composed of constant symbols and parameter symbols from the alphabets Σ and Π, respectively. An individual symbol in the Π alphabet may be considered a complement of another unique symbol in Π. The notion of matching constants, parameters, and complements is referred to as the structural matching (s-match) problem, which is helpful in matching RNA and previously, was solved by the structural suffix tree (sST). Other approaches to RNA matching that do not openly consider the s-match include the use of affix data structures. In this paper, we provide new data structures and algorithms to address the s-match problem. Specifically, we introduce the structural suffix array and structural longest common prefix array and then identify how to s-match with these data structures. Our new s-matching solution is then used as the framework to answer various combinatorial queries encountered in matching RNA secondary structures.