Quantum Genetic Algorithm and Its Application in Multiple Sequence Alignment
|School||Xi'an University of Electronic Science and Technology|
|Course||Computer Software and Theory|
|Keywords||Quantum Genetic Algorithm Multiple sequence alignment Probability coding COFFEE|
Biological information in the multiple sequence alignment problem , is forecast , the interaction between the probe sequence on the basis of phylogenetic tree , the function of genes and proteins . However , the multiple sequence alignment problem is an NP-hard problem , very challenging , sequence alignment algorithm speed and quality requirements . Some intelligent optimization method is applied in the field , and achieved good results . The genetic algorithm is a random iterative optimization algorithm for solving complex combinatorial optimization problems advantage . However, due to the multiple sequence alignment problem itself, the complexity of traditional genetic algorithm convergence rate is relatively slow , there is no guidance on the individual to be corrected with a certain blindness , prone to degradation phenomena . Inspired by the characteristics of the quantum , this paper presents a new quantum the genetic algorithm QGAlign solve biological sequence analysis of the multiple sequence alignment problem . The algorithm was first proposed a new quantum probability encoding method and design of the rotation angle based on the encoding method of quantum mutation operator and five genetic operators . The quantum superposition characteristic chromosome coding , and enhance the diversity of the population ; quantum revolving door through optimal solution to guide the evolutionary process of the groups , and to accelerate the speed of convergence of the algorithm . In order to avoid the quantum rotation gate variability may bring the problem of local optimum design of genetic operators based on the multiple sequence alignment problem , and to optimize the results of comparison , the evolutionary process more enlightening and diversity . Through experimental validation of a genetic operators optimize the performance of the algorithm . The data in BAliBASE2.0 library test compared with CLUSTAL X, SAGA other methods , the results showed that the framework of the algorithm has good ability of global optimization , and has a small population , the fewer the number of iterations , the feasible .