Research Of Multiple Sequence Alignment Algorithm Based On Quantum Genetic Algorithm And Improved Immune Genetic Algorithm

Along with the implementation of the Human Genome Project, huge amounts of new molecule biological data come out. To get worthy knowledge from the database is a very momentous task. Bioinformatics is developed very quickly to satisfy this requirement. As an interdiscipline, Bioinformatics applies mathematics and computer science to the obtaining, processing, storage, sorting, query and analysis of the information of biological macromolecule to illustrate and understand the significance that the large database contains.In bioinformatics, sequence alignment that compares the similarity of sequence data is a basic method for dealing with information. It's very important for discovering the information of function, structure and evolution in biological sequence. Sequence alignment is to find the maximum number of suited base or residue among several sequences with given mathematics model. The result of alignment reflects the extent of the algorithm discovers the similarity relationships among sequences and their biological characters. Therefore, designing a reasonable and efficient sequence alignment algorithm has become a significant topic of bioinformatics.Immune genetic algorithm is a new algorithm which has brought in immunity mechanism of organism. It takes advantage of the information of the best solution. Immune genetic algorithm picks up the snippet of the best solution and then inoculates other individuals with the snippet in order to make the algorithm converge. There is a degree of blindness when picking up vaccine in traditional IGA. To avoid this dilemma, here we make a change in selecting vaccine, which is picking up the second-class and third-class as well as the first-class snippet and then inoculate at random according to the fitness of the three snippets. By doing this we can make full use of the information of the best solution and avoid getting into the dilemma of local convergence so quickly.For Immune genetic algorithm, traditional crossover and mutation play an important role all the same and therefore the enactment of the probability for crossover and mutation is especially important. Traditional IGA adopts fixed probability. As a result, the relative smaller probability makes the rate of convergence extremely slow at the initial stage; on the other hand the relative bigger probability makes the superior value vibrate fiercely that convergence is hard to achieve at the latter stage. For that reason, this paper designs a fire-new method for setting the probability for crossover and mutation on the basis of information entropy and sigmoid function. The improved algorithm adjusts timely the probability according to the information entropy of the population, so the algorithm not only achieves rapid convergence at the initial stage, but also goes steadily at the latter stage. The experiment result shows that the improvement to IGA is effective.Quantum Genetic Algorithm is a kind of brand-new optimization method which applies quantum algorithm to general genetic algorithm. Compared with the traditional genetic algorithm, the QGA has the following three advantages: firstly, it can represent large solution space with few individuals, even one individual can find out the best solution; secondly, it has strong global searching capability; thirdly, it can converge very fast and get the best global solution within short time. In this paper, we apply QGA to the sequence alignment to bring forward a new multiple sequence alignment algorithm. QGA primarily uses quantum gates to update the population, accordingly, crossover operation and mutation operation become secondary.In genetic algorithm, crossover is a kind of method for searching the best solution. The commonly used crossover operations are one point crossover, multiple points crossover, equal crossover, arithmetic crossover. All of them are between two individuals. When the two individuals are the same, all of them are not effective. Here we quote a brand-new crossover operation which is made by using quantum coherence. It's called full interference crossover, FIC. The FIC arranges all of chromosome according to the diagonal. By using as much information as possible, FIC improves the partialness of common crossover operations. When the earliness appears, it can produce new individuals and bring motivity to the evolution. The mutation operation is carried out by using quantum not-gate. First, we choose some individuals with given probability, and then choose some bits of the individuals, at last we use quantum not-gate to these bits.By contrasting with traditional genetic algorithm,the main operation of quantum genetic algorithm is quantum gate. Therefore the conformation of quantum gate is not only the problem which quantum genetic algorithm will solve, but also vital to the capability of the algorithm. At present the most popular quantum gate is the rotation gate. It is very important to set the parameterθ_i in the rotation quantum gate. It would be better to keepθ_i adjust the rotation direction and the step length according to the information of the population. Here we adopt a strategy that would not rely on idiographic situations to set the rotation angle, which makes the algorithm universal to a certain extent. At the same time, the rotation angle changes along with generations, that is, Delta = 0.05π*exp( -t / t_max). It can be seen from this expression that at the initial stage of evolution, the step length is close to 0.05π, this makes the population converges fast. And then, with the increase of the generations and the global fitness, the step length reduces correspondingly, and this leads the stable convergence. This strategy provides the algorithm the ability to avoid the slow convergence at the initial stage and the strongly surge at the latter stage.Though quantum genetic algorithm is more excellent than traditional genetic algorithm, it can not avoid the dilemma of local convergence completely. So we improve QGA by bringing in the disaster strategy. The algorithm may get into local convergence if there is no change in a few generations. We can imitate the situation of disasters in the nature, keep the best solution and initialize all the other individuals. By doing this, we would avoid the local convergence to a certain extent and make the algorithm converge rapidly. Experimental results demonstrate the validity of this strategy. At the same time, we adopt the Two-Phase QGA. TPQGA makes the population initialize with individuals much closer to the best solution so as to find more excellent solution. We test the samples with the improved IGA as well as QGA. The result reveals that the improved IGA is effective when it is applied to the sequences with higher consistency, and QGA is effective for every type of sequence.