An RNA folding algorithm including pseudoknots based on dynamic weighted matching

On the basis of maximum weighted matching (MWM) algorithm, we introduced a dynamic weight related with stem length and used a recursive algorithm to predict RNA secondary structures by searching the stem structure with maximum weight summation step-by-step. This algorithm not only avoids the complicated free energy calculation, but also it could attain higher prediction accuracy. Moreover, our algorithm can predict most types of potential pseudoknots in the RNA structure.     

Finding common RNA pseudoknot structures in polynomial time

This paper presents the first polynomial time algorithm for finding common RNA substructures that include pseudoknots and similar structures. While a more general problem is known to be NP-hard, this algorithm exploits special features of RNA structures to match RNA bonds correctly in polynomial time. Although the theoretical upper bound on the algorithm?s time and space usage is high, the data-driven nature of its computation enables it to avoid computing unnecessary cases, dramatically reducing the actual running time. The algorithm works well in practice, and has been tested on sample RNA structures that include pseudoknots and pseudoknot-like tertiary structures.