Searching RNA Substructures with Arbitrary Pseudoknots

RNA functions depend on its three-dimensional structure formed largely from hydrogen bonds between pairs of nucleotides. RNAs with analogous functions exhibit highly similar structures without showing significant sequence similarity necessarily. Understanding the relationships between the structure and the functions has been considered one of the challenges in biology. In this study, we face the problem of identifying a given structural pattern into an RNA secondary structure with arbitrary pseudoknots. We abstract the shape in terms of secondary structure, formalized by the arc diagram, and we introduce a set of operators necessary and sufficient to describe any arc diagram in terms of relations among loops. For each molecule, we uniquely associate the relation matrix, and we face the aforementioned problem in terms of searching a submatrix. The algorithms work in polynomial time.