Partitioning and Classification of RNA Secondary Structures into Pseudonotted and Pseudoknot-free Regions Using a Graph-Theoretical Approach

Dual graphs have been applied to model RNA secondary structures with pseudoknots, or intertwined base pairs. In this paper we present a linear-time algorithm to partition dual graphs into maximal topological components called blocks and determine whether each block contains a pseudoknot or not. We show that a block contains a pseudoknot if and only if the block has a vertex of degree 3 or more; this characterization allows us to efficiently isolate smaller RNA fragments and classify them as pseudoknotted or pseudoknot-free regions, while keeping these sub-structures intact. Applications to RNA design can be envisioned since modular building blocks with intact pseudoknots can be combined to form new constructs.