title: On the page number of RNA secondary structures with pseudoknots.
abstract: 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 Scan 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.
authors.affiliation: Department of Biology, Boston College, Chestnut Hill, MA 02467, USA. clote@bc.edu
authors.forename: Peter
authors.initials: P
authors.lastname: Clote
authors.forename: Stefan
authors.initials: S
authors.lastname: Dobrev
authors.forename: Ivan
authors.initials: I
authors.lastname: Dotu
authors.forename: Evangelos
authors.initials: E
authors.lastname: Kranakis
authors.forename: Danny
authors.initials: D
authors.lastname: Krizanc
authors.forename: Jorge
authors.initials: J
authors.lastname: Urrutia
mesh_terms: D020029:Base Pairing; D006860:Hydrogen Bonding; D008956:Models, Chemical; D008957:Models, Genetic; D008958:Models, Molecular; D009690:Nucleic Acid Conformation; D012313:RNA / Q000737:chemistry*; D013816:Thermodynamics
chemical_list: D012313:RNA