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

Additional Metadata
Persistent URL dx.doi.org/10.1007/s00285-011-0493-6
Journal Journal of Mathematical Biology
Clote, P. (Peter), Dobrev, S. (Stefan), Dotu, I. (Ivan), Kranakis, E, Krizanc, D. (Danny), & Urrutia, J. (Jorge). (2012). On the page number of RNA secondary structures with pseudoknots. Journal of Mathematical Biology, 65(6-7), 1337–1357. doi:10.1007/s00285-011-0493-6