Approximation algorithms for predicting RNA secondary structures with arbitrary pseudoknots.
We study three closely related problems motivated by the prediction of RNA secondary structures with arbitrary pseudoknots: the problem 2-Interval Pattern proposed by Vialette, the problem Maximum Base Pair Stackings proposed by Leong et al., and the problem Maximum Stacking Base Pairs proposed by Lyngsø. For the 2-Interval Pattern, we present polynomialtime approximation algorithms for the problem over the preceding-and-crossing model and on input with the unitary restriction. For Maximum Base Pair Stackings and Maximum Stacking Base Pairs, we present polynomial-time approximation algorithms for the two problems on explicit input of candidate base pairs. We also propose a new problem called Length-Weighted Balanced 2-Interval Pattern, which is natural in the context of RNA secondary structure prediction.
Jiang
Minghui
M
Department of Computer Science, Utah State University, 4205 Old Main Hill, Logan, UT 84322-4205, USA. mjiang@cc.usu.edu
D000465:Algorithms; D001483:Base Sequence; D019295:Computational Biology / Q000379:methods*; D008957:Models, Genetic; D008969:Molecular Sequence Data; D009690:Nucleic Acid Conformation; D012313:RNA / Q000737:chemistry*
D012313:RNA