On the page number of RNA secondary structures with pseudoknots

Let S denote the set of (possibly noncanonical) base pairs {i, j} of an RNA tertiary structure; i.e. {i, j} is an element of S if there is a hydrogen bond between the ith and jth nucleotide. The page number of S, denoted pi(S), is the minimum number k such that 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(S) <= pi(S) <= omega(S) . log n, where the clique number of S, omega(S), denotes the maximum number of base pairs that pairwise cross each other.