Multiple Sequence Alignment Using Genetic Algorithm

Multiple sequences alignment (MSA) is an elementary problem in bioinformatics. It is an important method of revealing biologic pattern of multiple sequences. Sequence alignment is a NP Complete problem and a great challenge to any quick and accurate algorithms. In this paper, we choose Genetic Algorithm(GA), one of the data mining methods, to solve multiple sequences alignment problem. The biological sequences are expressed by initial population of genetic algorithm. The quality of the alignment is expressed by individual' s fitness. Special genetic operators are used. In the process of evolution, alignments are continuously selected and mutated. The whole population' s fitness are upgraded. The best individual is selected to be the result of alignment. Furthermore, we analyze different effects that different operators have in the evolution process and suggest two strategies: choose operator by its contribution and use efficient operators. Finally, a multiple sequences alignment system is developed in VS. NET environment. We use sequences form BAliBASE (Benchmark Alignment dataBASE) to test our algorithm and comprare our algorithm with two other classic algorithms. The result show that our algorithm is feasible and effective.