The Research Of Sequence Alignment Method Based On Genetic Algorithm

With the biomolecular data growing rapidly and the Human Genome Projectcarrying out, bioinformatics developed gradually. In bioinformatics, the problem ofsequence alignment is the most basic and most important issue in bioinformatics,sequence alignment can be used for analyzing sequence, so as to predict the structureand function of biological sequences. Sequence alignment can also be seen as acombinatorial optimization problem, and the genetic algorithm which is a globaloptimization algorithm for solving large-scale problems can be used to solvesequence alignment problem. In this paper, the problem of the genetic algorithmbeing applied in the pairwise sequence alignment and multiple sequence alignment isstudied.After sequence alignment problem researching, we put forward a kind ofimproved genetic algorithm to solve the sequence alignment problem. As putting thegenetic algorithm in sequence alignment problem maybe easily fall into localoptimal solution, instability and other issues, this paper carried out threeimprovements: first, the use of the method of the combination of the smart geneticoperator and the general genetic operator in genetic operator, the design ofintelligent genetic operator is in order to make the algorithm converge to the area ofthe optimal solution rapidly and to converge to the optimal solution while thegeneral genetic operator can generate new genes and maintain the diversity of thepopulation; second, introduced the index for evaluating the population diversity, thatis used the variance to assess the diversity of the population which is used forchoosing different intelligent variation rate and general variation rate, this canguarantee the diversity of the population and avoid the algorithm falling into localoptimum; Third, stop criterion is introduced the concept of the evolutionary cycle,whether the cycle count is added is determined by comparing the difference of theoptimal solution in current period and the previous period and the threshold, theoptimal result will output when the cycle count reaches the specified value, it avoidsthe population fall into a local optimum prematurely and improves the stability ofthe algorithm. It will obtain very good results when solving the problem on sequenceused the improved genetic algorithm with the above three strategies.The improved genetic algorithm used in pairwise sequence alignment and multiple sequence alignment is in order to verify the validity of this method, wecompared the results in the number of character matching columns and the fitnessvalue with the classical algorithm T-COFFEE, we can get that this method iseffective from the experimental results and the experimental analysis.