Quantum Genetic Algorithm And Its Application In Multiple Sequence Alignment

Multiple Sequence Alignment (MSA) is fundamental task as it represents an essential platform to conduct other tasks in informatics such as the construction of phylogenetic trees, the structural and functional prediction of new protein sequences and the detection of the interaction between protein sequences. Unfortunately, finding an accurate multiple alignment has been shown NP-hard which is challenging for the algorithm with high speed and good quality. Several intelligent optimization methods have been applied in the field and worked well. Genetic algorithm is a stochastic iterative optimization algorithm for the complex combinatorial optimization problem. However, the classical GA has slow convergence rate for the MSA which exhibits a great temporal and apace complexity. In the process of optimization, the algorithm can not full use of the information of the best individual and easy to getting retrogression.This paper describes a novel approach QGAlign to deal with multiple sequence alignment which inspired by quantum characteristics. The algorithm firstly presents a new coding method referred to as Quantum Probabilistic Coding Method. A quantum rotation mutation operator and five genetic operators are designed based on it. The algorithm applies the quantum superposition state into the chromosome coding, which enhances the diversity of the population; it applies quantum rotated mutation to optimize the population in the guidance of the best chromosome, which accelerates the convergence rate of the algorithm. At the same time, in order to avoid the quantum rotated mutation might bring the local optimization, we designed five genetic operator based on the MSA problem to enhance the enlightenment and diversity. These genetic operators play an important role in experimental verification. Experimental results of the data from BAliBASE2.0 have shown the effectiveness of the QGAlign which using a small population size and a less iterations and its ability to achieve good quality solutions comparing with those addressed by other popular multiple alignment programs, such as CLUSTAL X, SAGA and so on.