A Multiobjective RNA Secondary Structure Prediction Algorithm Based on NSGAII

作者:Zhang, Kai*; Lv, Yulin
来源:IEEE SmartWorld, Ubiquitous Intelligence & Computing, Advanced & Trusted Computing, Scalable Computing & Communications, Cloud & Big Data Computing, Internet of People and Smart City Innovation (SmartWorld/SCALCOM/UIC/ATC/CBDCom/IOP/SCI), China,Guangdong,Guangzhou, 2018-11-07 to 2018-11-11.
DOI:10.1109/SmartWorld.2018.00251

摘要

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.

全文