The Study Of Heuristics Method For Multiple Sequence Alignments

Sequence alignment of bioinformatics is an important fundamental subject in bioinformatics research, one of its most basic task is to multiple sequence alignments. Still there is not an optimal algorithm of multiple sequence alignments. This paper proposes a method, which use genetic algorithm and particle swarm optimization algorithm of evolutionary algorithm, to solve the problems of multiple sequence alignments.Firstly, the effect on sequence alignment caused by the gap penalty, substitution matrix and objective function are analyzed, and the SP objective function and COFFEE objective function are implemented. Then The dynamic programming algorithm that is one of accurate algorithms of pairwise alignment is studied and implemented. And the Clustal W that is one of the multiple sequence alignments algorithm based on the heuristic method is analyzed in detail. Later through the study on current situation of the multiple sequence alignments algorithm and the analysis to the principle and characteristic of the genetic algorithm and particle swarm optimization algorithm and so on, present the multiple sequence alignments algorithm based on genetic algorithm MSAGA (a Genetic Algorithm dedicated for Multiple Sequence Alignment) and the multiple sequence alignments algorithm based on particle swarm optimization algorithm MSAPSO(a Particle Swarm Optimization dedicated for Multiple Sequence Alignment). Also the two algorithms based on SP objective function and COFFEE objective function are implemented, and both complexities of two algorithms are only related to evolution generational number and the size of population. Finally, The two algorithms are used to test benchmark multiple sequence alignments database BAliBASE. The results show that the proposed MSAGA and MSAPSO algorithm are feasible to solve the problem of sequence alignment.