A hybrid framework based on genetic algorithm and simulated annealing for RNA structure prediction with pseudoknots

RNA structure prediction with pseudoknots is an NP-complete problem, in which an optimal RNA structure with minimum energy is to be computed. In past decades, several methods have been developed to predict RNA structure with pseudoknots. Among them, metaheuristic approaches have proven to be beneficial for predicting long RNA structure in a very short time. In this paper, we have used two metaheuristic algorithms; Genetic Algorithm (GA) and Simulated Annealing (SA) for predicting RNA secondary structure with pseudoknots. We have also applied a combination of these two algorithms as GA-SA where GA is used for a global search and SA is used for a local search, and conversely SA-GA, where SA is used for a global search and GA is used for a local search. Four different energy models have been applied to calculate the energy of RNA structure. Five datasets, constructed from the RNA STRAND and Pseudobase++ database, have been used in the algorithms. The performances of the algorithms have been compared with several existing metaheuristic algorithms. Here we have obtained that the combination of GA and SA (GA-SA) gives better results than GA, SA and SA-GA algorithms and all other four state-of-art algorithms on all datasets.