Efficient Conversion of RNA Pseudoknots to Knot-Free Structures Using a Graphical Model

RNA secondary structures are vital in determining the 3-D structures of noncoding RNA molecules, which in turn affect their functions. Computational RNA secondary structure alignment and analysis are biologically significant, because they help identify numerous functionally important motifs. Unfortunately, many analysis methods suffer from computational intractability in the presence of pseudoknots. The conversion of knotted to knot-free secondary structures is an essential preprocessing step, and is regarded as pseudoknot removal. Although exact methods have been proposed for this task, their computational complexities are undetermined, and so their efficiencies in processing complex pseudoknots are currently unknown. We transformed the pseudoknot removal problem into a circle graph maximum weight independent set (MWIS) problem, in which each MWIS represents a unique optimal deknotted structure. An existing circle graph MWIS algorithm was extended to report either single or all solutions. Its time complexity depends on the number of MWISs, and is guaranteed to report one solution in polynomial time. Experimental results suggest that our extended algorithm is much more efficient than the state-of-the-art tool. We also devised a novel concept called the structural scoring function, and investigated its effectiveness in more accurate solution candidate selection for a certain criteria.