Research On RNA Secondary Structure Prediction Algorithm Based On Evolutionary Strategy

RNA molecules are single-stranded nucleic acid molecules that are polymerized by four bases.Not only are they important genetic material,they are also used to solve complex combinatorial optimization problems.Due to base complementarity,single-stranded RNA molecules can fold into different structures,and these secondary and tertiary structures determine the function of the RNA molecule.Therefore,accurate prediction of RNA structure is an important research topic in academic fields such as life sciences and computer sciences.At present,domestic and foreign scientists have proposed a variety of methods such as comparative sequence method,minimum free energy algorithm and heuristic algorithm to predict RNA secondary structure.However,neither the comparative sequence method nor the minimum free energy algorithm can predict the RNA secondary structure with pseudoknots,and the problem is also proved to be an NP-complete problem.Therefore,it is of great significance to design algorithms to solve the problem of predicting RNA secondary structure with pseudoknots.In this thesis,the problem of using pseudoknots to predict the secondary structure of RNA has been deeply studied and analyzed.The main research work includes the following two aspects.First,for the exponential base pairing solution space,the traditional complementary pairing efficiency is low,and the evolutionary algorithm is difficult to converge.An evolutionary strategy-based RNA secondary structure prediction algorithm is proposed,which transforms the problem into continuous 01 knapsack base pairs.Greatly improve the search efficiency of the knowledge space.RNA-seq examples from the Pseudo Base database were tested and compared with advanced algorithms such as RNAfold,RNAStructrue,Cylo Fold,TT2 NE,and IPKnot.The experimental results confirm the validity and reliability of the evolutionary strategy algorithm proposed in this thesis.Second,in view of the problem that the traditional single-objective optimization algorithm based on free energy is prone to fall into local optimum,an RNA secondary structure prediction algorithm based on a multi-objective evolution strategy is proposed,which simultaneously optimizes the total number of base pairs and the total number of stem regions.Aiming at these two conflicting goals,a set of non-dominant Pareto optimal solutions are obtained,which greatly improves the diversity of the algorithm in the solution space search.Finally,the free energies of the candidate solutions in the Pareto front are calculated using the nearest-neighbor thermodynamic parameters.The solution with the smallest free energy is the most stable RNA secondary structure.The final experimental results show that the multi-objective evolutionary strategy algorithm has better prediction performance than the evolutionary strategy algorithm in predicting long-chain RNA sequences.