K-partite RNA secondary structures.
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.
Jiang
Minghui
M
Department of Computer Science, Utah State University, Logan, Utah 84322-4205, USA. mjiang@cc.usu.edu
Tejada
Pedro J
PJ
Lasisi
Ramoni O
RO
Cheng
Shanhong
S
Fechser
D Scott
DS
D020029:Base Pairing; D001483:Base Sequence; D019295:Computational Biology / Q000379:methods; D009690:Nucleic Acid Conformation; D012313:RNA / Q000737:chemistry*
D012313:RNA