Research On Secondary Structure Prediction Of Nucleic Acids Based On Genetic Algorithm

DNA and RNA molecules play an important role in the whole process of biological evolution.In recent years,with the development of biological technology,the selfassembly technology of nucleic acid molecules which has been optimized in biomolecule computing,biosensor,targeted drug therapy also has an important application.In these fields,both the optimal design and structure prediction of nucleic acid molecules are important research topics.The nucleic acid molecules can be attracted by the hydrogen bonds of the bases,folded to form different secondary structures.Any single stranded nucleic acid molecule has a large number of base pairs,and finding the most stable structure of nucleic acid molecules is a complex combinatorial optimization problem.In addition,the problem of predicting the secondary structure of nucleic acid molecules containing pseudoknot has been proved to be a NP complete problem.Therefore,it is important and significant in theory and application to predict the secondary structure of the nucleic acid molecules with pseudoknot.A lot of scholars have proposed a variety of algorithms to predict the secondary structure of nucleic acid molecules.Among these algorithms,accurate algorithm performs well when the nucleic acid molecule is small,but with the increase of the number of nucleic acid bases,the accurate algorithm is incapable of action and cannot predict the structures in limited time,and the traditional dynamic programming algorithm is unable to predict pseudoknots;on the other hand,some approximation algorithms can deal with longer sequences,but the convergence rate is too slow.By observing RNA molecules with pseudoknots in the PseudoBase database,although these secondary structures contain cross boundary in a dome map and are impossible to be solved by the traditional dynamic programming algorithm,these figures are actually planar graph in fact.In this paper,an method to predict secondary structures with pseudokonts based on genetic algorithm is proposed,which allows to connect the hydrogen bonds below the RNA molecular skeleton to form planar pseudo knots,and reduce the free energy as much as possible.In this algorithm,the length of stems and free energy are used as the criteria for evaluating individuals.According to the characteristics of nucleic acid molecules,the improved crossover and mutation genetic operators are proposed.In addition,the nucleic acid molecules in PseudoBase database were tested and compared with ProbKnot,Mfold,HotKnots and other famous algorithms of secondary structure prediction,which proves the validity and reliability of this algorithm.In order to improve the computational efficiency of solving long nucleic acid molecules further,this paper selects the CUDA parallel computing model introduced by NVIDIA.Population initialization,fitness calculating,selection,crossover,mutation are running in GPU.The experimental results show that compared with the traditional CPU,the parallel computing model based on GPU can significantly improve the efficiency of the algorithm.