A Multiobjective RNA Secondary Structure Prediction Algorithm Based on NSGAII

RNA plays an important role in biological cells. However, RNA secondary structure prediction with pseudoknots has been shown to be NP-complete Problem. Existing algorithms cannot predict pseudoknots structure with minimum free energy efficiently and accurately. In this paper, we propose a multi-objective optimization algorithm to predict RNA secondary structure with pseudoknots. Because the consecutive base pairs stack structure provides negative free energy which contributes to the reduction of free energy, two conflict objectives maximum base pair matching and minimum base pair groups are used to evaluate the candidate solutions. NSGAII algorithm is adapted in our algorithm to find a group of non-dominated solutions. The solution with minimal free energy in the pareto front is the optimal solution. The performance of our algorithm is evaluated by the instances from PseudoBase database, and compared with RnaStructure, IPknot, RNAflod, HotKnots, et al. The comparison results show that our algorithm is more accurate to predict RNA secondary structure.