A Flexible Stem-Based Local Search Algorithm for Predicting RNA Secondary Structures Including Pseudoknots

We demonstrate a new algorithm named FlexStem to predict RNA secondary structures with pseudoknots. Our approach is based on the free energy minimization criterion, and utilizes a sophisticated energy model that is more accurate and supports more types of pseudoknots. By using a "maximal stem" and "stem merging" strategy, the search space for RNA structure prediction is significantly reduced. We have also developed a greedy search algorithm with perturbation on stems. The FlexStem algorithm is applied to a large number of sequences taken from Sprinzl, Pseudobase and other reliable resource. We find that FlexStem outperforms the well-known optimal and heuristic algorithms such as Mfold, PKNOTS, HotKnots and ILM in overall sensitivity and has comparable results to those algorithms in overall specificity. Performance evaluation demonstrate that FlexStem requires significantly less time than the optimal algorithm PKNOTS. In addition, our algorithm has better prediction results on pseudoknot-free sequences compared to competing algorithms.