Research Of Multiple Sequence Alignment Based On Genetic Algorithm

Sequence alignment is the most common fundamental subject in modern bioinformatics, while Multiple Sequence Alignment (MSA) is one of the most important and challenge work in sequence alignment. Research on Multiple Sequence Alignment is significant for recognition of protein domain structure, prediction of secondary structure, gene identification, and molecular phylogenetic analysis and so on. As a combinatorial optimization problem of NP-completeness, how to solve multiple sequence alignment is still a problem in bioinformatics so far. In this paper, we studied the application of Genetic Algorithm (GA) in multiple sequence alignment and proposed a multigroup parallel genetic algorithm and a kind of crowding niche genetic algorithm based on Penalty Function, which provide a new way to solve problems in multiple sequence alignment.The main work of this paper is as follows:(1) In view of the problem that genetic algorithm is easy to fall into local optimization and converge slowly at the later stage of multiple sequence alignment; we propose a multigroup parallel genetic algorithm. We utilize the methods of multigroup parallel and migration strategy, and design a new kind of mutation operator by making use of the features that gap would rarely occurred alone in MSA, which enhances its ability to achieve good quality solutions. Then we choose some sequences from the BALIBASE database1.0as our test data and analyze the relative merits of various typical algorithms. The experiment results show the effectiveness of our method.(2)In order to go a step further to improve the ability of global search and population diversity of the algorithm, we introduce a crowding niche genetic algorithm with penalty function on the basis of chapter three. The application of crowding niche genetic algorithms based on penalty function in MSA has to solve three probelms:similarity computation between the two multiple sequence individuals, selection of penalty function and selection of given distance L on the algorithms. Then we use the same dataset in chapter three to validate the algorithm by comparing and analyzing the test results with chapter three’s, which shows that the crowding niche genetic algorithms based on penalty function has a better global search ability and population diversity.