Research On RNA Secondary Structure Prediction Algorithm Based On Simulated Annealing

RNA plays a pivotal role in biological cells and the bases of RNA molecules bind to each other under the action of hydrogen bonds to form different secondary structures.Although the dynamic programming algorithm can efficiently solve the secondary structure without pseudoknot,the pseudoknot of the RNA molecule has an important influence on the cell function,which destroys the nested base pair rules.It makes the traditional dynamic programming algorithm could not successfully solve the problem.As the length of the RNA sequence increases,the base pairing combination of the sequence increases exponentially,and the problem of RNA secondary structure prediction with pseudoknot has been proved to be an NP-complete problem.At present,many researchers at home and abroad have proposed many different RNA secondary structure prediction algorithms,but these algorithms have some shortcomings.Among them,the algorithm of sequence comparison analysis has high prediction accuracy,but the algorithm relies on a large number of known homologous sequence information;the algorithm of the dynamic programming has a slow convergence speed and the prediction accuracy is not good when predicting long-chain RNA sequences.Therefore,no matter which algorithm is used for prediction,there are still some problems.It is very important to construct an effective algorithm to improve the accuracy of predicting the secondary structure of RNA molecules with pseudoknot.In this paper,after transforming this prediction problem into an equivalent combinatorial optimization problem,an RNA secondary structure prediction algorithm with pseudoknot based on simulated annealing is proposed.Firstly,based on the constraints of the minimum stem length and the minimum loop length,a highly efficient base pairing method is designed and a detailed conflict solution is provided for the conflicting bases.Then,the number of stem and the total number of base pairs of the RNA sequence are used as factors for evaluating the secondary structure of RNA,and an effective fitness evaluation function is proposed.In this paper,15 test sequences are randomly selected from the PseudoBase database,and compared with other leading prediction algorithms such as IPknot,TT2 NE,and HotKnots.The experimental results verify the effectiveness of the proposed algorithm.According to the two factors of the above evaluation function,the problem of RNA secondary structure prediction with pseudoknot can be converted into a multi-objective minimization problem.Therefore,based on the above algorithm,this paper proposes a long-chain RNA secondary structure prediction algorithm based on multi-objective simulated annealing.Firstly,the dominating relationship between the different solutions of the proposed algorithm is defined in detail.Then,to ensure the uniform distribution of the Pareto front,a strategy to increase the diversity of RNA secondary structure is designed.Finally,the most stable RNA secondary structure in the Pareto front is calculated by the neighbor thermodynamic parameters.Compared with other algorithms,the results show that the proposed algorithm has the ability to predict the secondary structure of long-chain RNA.