A Method Of Biological Sequence Alignment Based Ant Colony Optimization Algorithm

This article mainly introduced the method of biologicalsequence alignment based on the Ant Colony Algorithm(ACA).We began with the introduction of some relatedtopics,including some correlation conceptions of sequencealignment,the principle and character in using dynamicprogramming algorithm to solve sequence alignment and so on.Then the article introduced the basic principle, identity,development and the application of ACA,and analyzed the designthought of ACA, using the Traveling Salesman Problem as anexample.In this foundation,the article has found the keyentrance to solve sequence alignment with ACA. In view of someflaws of ACA, such as falling into the regional optimal solutioneasily and the slow convergence rate, this article presentedsome corresponding improvement methods.The key point of this article is the introduction to themodel and design of biological sequence alignment algorithmbased on ACA.How to find a valid key entrance between ACA andsequence alignment is the key of solving question.We found that,in the dynamic programming algorithm , a most superior sequencealignment is a trail extends from upper left to right under ofthe matrix. It enlightened us that we can take every trailextends from upper left to right under of the matrix as aalignment of sequence. In this way,a relation is establishedbetween ACA and sequence alignment.After solving the question of key entrance,we can give somecorresponding change to ACA according to the actual situationof sequence alignment.When an ant choose its direction of advance,We regulate thatit can only select one among three directions,including levelto right, vertical to under and decline along the diagonal linedirection.Firstly we get the score of every trail according tothe inspiration information which influenced by threefactor,including alignment score, pheromone concentration andthe control of vacancy number.As follows shows:SCORE izjk = τ ijk(t)αMβdγThen the direction of advance of an ant can be confirmed byusing the method of roulette.When all of the ants arrive at the right under of matrix,thepheromone concentration of all trails should be updated entirely.The recent information element must be added, and the oldinformation element must volatilize. The increment of pheromoneis related with the score of sequence alignment of this trail.From this we can conclude that the model alignment algorithmadopt is similar to the Ant-Cycle model. In such model,theincrement of pheromone is related with the quality oftrail,which reflect the entire information of sequencealignment.After the most important two steps,the selection of trailand the updating of pheromone,have reconstructed,this articlehave also reconstructed the flow of the algorithm,saving optimalsolution of Each turn of search, the search finished flag andso on in order to make the algorithm more suitable to the questionof sequence alignment. After the experiment which selecteddifferent length and multi-groups DNA sequence has carried on,it indicated that this kind new alignment algorithm is feasibleand valid.The ACA has the phenomenon of "early-maturing",which issame with many optimized algorithms and is easy to fall into theregional optimal solution. In view of this flaw, this articlehas carried on the transformation to the algorithm. Variableelement q 0 can be used in the roulette method.The value of q 0is the partition function of the number of search times:?????<≤<≤<≤=11max0011000cnNCNCcnNCncNCnqc 0 may take a small value,but c1 may take a great value.When the algorithm has ran,it selected the direction of mostpheromone by a big probability until it searches n 0 times.Hereafter in order to prevent the search falling into local mostsuperior,the algorithm searched other solutions by a bigprobability in the neighborhood of regional optimal solutionuntil it searched n1 times. In order to make the algorithmconvergent to a entire optimal solution,the algorithm selectedthe direction of most pheromone by a big probability once againuntil it finished. While using Variable element q 0,Restrictingthe pheromone concentration of the trail can better solve thequestion of falling into the local optimal solution easily.This article adopts the strategy of individual variation tosolve another flaw of ACA——slow convergence rate. Individualvariation enables the strategy of ants'trail selection topossess variety. Simulations show that the speed of convergenceof the improved ACA algorithm can be enhanced greatly.At last, the contents of the paper are summarized and thefuture work is proposed.