The Enhanced Quantum Genetic Algorithm And Its Application To RNA Secondary Structure Prediction

RNA secondary structure prediction is an important research field of molecular biology,which is of great significance to promote the development of life sciences.RNA molecular structure consists of three structures: primary structure,secondary structure,tertiary structure.The secondary structure is a structure between the primary structure and the tertiary structure,which stores much advanced structure information.Therefore,the study of RNA secondary structure has become an important research problems in the field of bioinformatics.However,because RNA molecules are easily degraded and crystals are difficult to obtain,it is difficult to obtain RNA's secondary structure by experimental methods.Thereby,the development of RNA secondary structure prediction methods based on computer algorithms is a widely used and effective way.At present,the methods used for RNA secondary structure prediction include comparative sequence analysis,dynamic programming algorithm,heuristic algorithm and so on.Comparative sequence analysis method needs to know a large number of homologous RNA sequences in advance,and it is overly dependent on the RNA sequence database,which is less effective for the newly discovered RNAs.The complexity of the dynamic programming algorithm is too high,and the processing capacity of long RNA sequences is limited.Although the heuristic algorithm can predict the RNA secondary structure quickly,the classical heuristic algorithm often has the problem of low search efficiency and easy to fall into the local optimal solution.In order to solve the above problem,we propose a method based on quantum genetic algorithm to predict the RNA secondary structure by using the parallel characteristics of quantum computation.By using quantum bits to encode populations,the algorithm has a strong search capability even with the small population.In this thesis,we first compare several methods of RNA secondary structure prediction,analyze its advantages,disadvantages and applicable conditions.Combining the characteristics of RNA secondary structure prediction problem,we propose a quantum genetic algorithm to predict the secondary structure of RNA.Second,the algorithm is designed by analyzing the collected data,including the design of each functional module and the preparation of quantum genetic algorithm.Third,in order to make the quantum genetic algorithm better for RNA secondary structure prediction problem,faster convergence to optimal solution and better global search,this thesis further adds crossover operator and mutation operator on the basis of standard quantum genetic algorithm,which enhance the global search ability of the algorithm.The adaptive rotation angle strategy is also added,making the population update more moderate and controllable.Finally,the experimental results of Genetic Algorithm(GA),Quantum Genetic Algorithm(QGA)and Enhanced Quantum Genetic Algorithm(EQGA)are compared.The results show that the Enhanced Quantum Genetic Algorithm is effective in RNA secondary structure prediction problem,and has stronger global search ability and faster convergence rate than traditional Genetic Algorithm.