Swarm Intelligence Optimization Algorithm For Multiple Sequence Alignment Application

Sequences Alignment is one of the most fundamental methods in bioinformatics, and it has essential meaning for the research of Nucleic acids sequences and protein sequences. It is possible to find the similar part among sequences through sequences alignment. And the number of the similar part and the level of similarity provide evidence to calculate the parent of these sequences according to the Theory of Biological Evolution. In other word, the relation of these sequences how to evolve could be known. At the same time, we may forecast the function and structure of unknown sequences. Sequences Alignment also provides help in Life sciences and medicine. If aligning the healthy sequence to unhealthy sequence, it is good to find the gene which is unhealthy and the position of it. So, it is good for disease's cure.The main content of this paper is Multiple Sequences Alignment. The main aim is to improve the precision of multiple sequence alignment. Firstly, introduce the research status and relevant algorithms especially the algorithms based on swarm intelligence, for example genetic algorithm, PSO Particle Swarm Optimization, Simulated Annealing Algorithm and so on. Then, solving multiple sequence alignment using artificially bee colony algorithm artificially bee colony algorithm. At the end, propose two new algorithm through improving the PSO and ABC, and the simulation results prove the better performance.We introduce emphatically the model of the basic Particle Swarm Optimization (PSO), and some methods of changing inertia weight, for example linear inertia weight, adaptive inertia weight and so on. When inertia weight is big, the global searching ability of particle increases. When inertia weight is small, the local searching ability of particle increases. After the deep analysis of this theory, propose a new method of changing inertia weight-subsection weight. In other word, divide algorithm into two parts, the strategy in one part is different from the second part. Every particle has Self learning ability, Social survival ability and communicative competence among a little space presenting Individual optimal location, global optimal location and group optimal respectively. Through combine group optimal and subsection weight, propose a new SWGPSO algorithm.The model of Artificial Bee Colony algorithm comes from the behavior of bee foraging. In this model, employed bees, onlookers and scouts work respectively, and communicate. Try to solving multiple sequences alignment using Artificial Bee Colony algorithm. The results of simulating confirm its property. Generally speaking, single algorithm is not the best, so we introduce Metropolis acceptance criteria into ABC's searching process. The results of simulation experiment demonstrate that ABC_SA algorithm is able to settle multiple sequence alignment effectively by increasing the food source's diversity and is able to converge at global optimal alignment.