Approximation Algorithm for Pseudoknotted RNA Structure Prediction

Pseudoknotted RNA secondary structure prediction is an important problem in computational biology. Existing polynomial time algorithms have no performance guarantee or can handle only limited types of pseudoknots. Now for stacking base pairs prediction, the best approximation ratio of existing approximation algorithm is 3. In this paper allowing arbitrary pseudoknots, an approximation algorithm is given to maximize the number of stacking base pairs, and the approximation ratio of the approximation algorithm is improved from 3 to 1.5.