On the page number of RNA secondary structures with pseudoknots

Let ${mathcal {S}}$ denote the set of (possibly noncanonical) base pairs {i, j} of an RNA tertiary structure; i.e. ${{i, j} in mathcal {S}}$ if there is a hydrogen bond between the ith and jth nucleotide. The page number of ${mathcal {S}}$ , denoted ${pi(mathcal {S})}$ , is the minimum number k such that ${mathcal {S}}$ can be decomposed into a disjoint union of k secondary structures. Here, we show that computing the page number is NP-complete; we describe an exact computation of page number, using constraint programming, and determine the page number of a collection of RNA tertiary structures, for which the topological genus is known. We describe an approximation algorithm from which it follows that ${omega(mathcal {S}) leq pi(mathcal {S}) leq omega(mathcal {S}) cdot log n}$ , where the clique number of ${mathcal {S}, omega(mathcal {S})}$ , denotes the maximum number of base pairs that pairwise cross each other.