title: K-partite RNA secondary structures.
abstract: RNA secondary structure prediction is a fundamental problem in structural bioinformatics. The prediction problem is difficult because RNA secondary structures may contain pseudoknots formed by crossing base pairs. We introduce k-partite secondary structures as a simple classification of RNA secondary structures with pseudoknots. An RNA secondary structure is k-partite if it is the union of k pseudoknot-free sub-structures. Most known RNA secondary structures are either bipartite or tripartite. We show that there exists a constant number k such that any secondary structure can be modified into a k-partite secondary structure with approximately the same free energy. This offers a partial explanation of the prevalence of k-partite secondary structures with small k. We give a complete characterization of the computational complexities of recognizing k-partite secondary structures for all k > or = 2, and show that this recognition problem is essentially the same as the k-colorability problem on circle graphs. We present two simple heuristics, iterated peeling and first-fit packing, for finding k-partite RNA secondary structures. For maximizing the number of base pair stackings, our iterated peeling heuristic achieves a constant approximation ratio of at most k for 2 < or = k < or = 5, and at most [Formula: see text] for k > or = 6. Experiment on sequences from PseudoBase shows that our first-fit packing heuristic outperforms the leading method HotKnots in predicting RNA secondary structures with pseudoknots. Supplementary Material can be found at www.libertonline.com.
authors.affiliation: Department of Computer Science, Utah State University, Logan, Utah 84322-4205, USA. mjiang@cc.usu.edu
authors.forename: Minghui
authors.initials: M
authors.lastname: Jiang
authors.forename: Pedro J
authors.initials: PJ
authors.lastname: Tejada
authors.forename: Ramoni O
authors.initials: RO
authors.lastname: Lasisi
authors.forename: Shanhong
authors.initials: S
authors.lastname: Cheng
authors.forename: D Scott
authors.initials: DS
authors.lastname: Fechser
mesh_terms: D020029:Base Pairing; D001483:Base Sequence; D019295:Computational Biology / Q000379:methods; D009690:Nucleic Acid Conformation; D012313:RNA / Q000737:chemistry*
chemical_list: D012313:RNA