Improved approximation algorithm of RNA structure prediction with pseudoknots

Based on MFE principle and the relative stability of the n-stems in RNA molecules, Minimum free energy method is adopted widely to predict RNA secondary structure, an improved approximation algorithm is presented to predict RNA pseudoknotted structure, the algorithm can solve arbitrary nested or parallel pseudoknots the algorithm takes O(n³) time and O(n²) space. This algorithm not only reduces the time complexity to O(n³), but also widens the maximum length of the sequence. The preliminary experimental test on the RNA sub-sequences in PseudoBase confirm that the algorithm outperforms other known algorithms in predicting accuracy, sensitivity and specificity.