Particle Swarm Optimization With Probability Statistic For Biological Multiple Sequence Alignment

With the in-depth study of genome, biological sequence data show explosive growth, which results of an urgent need to use efficient computer algorithms for processing these massive data. Biological sequence alignment is a significant, challenging and basic issue, and has very important significance for discovering the function, structure and evolution of nucleic acid and protein sequence alignment. However, for large-scale sequence alignment, existing algorithms have a problem of low accuracy. So, some further researches on the problem are made in this dissertation.Firstly, in this paper we deeply research a variety of sequence alignment status at home and at abroad, and systematically describe and analyze the advantages and disadvantages of various types of algorithms, and analyze the impact of gap penalty, replacing the matrix and the objective function on sequence alignment.Secondly, we proceed from the standard model of particle swarm, and research the advantages and disadvantages of a variety of improved particle swarm optimization algorithm, and conclude the limitations of particle swarm optimization algorithm. For its limitations, a new algorithm model is designed and a new algorithm is proposed based on the combination of probability statistics theory and particle swarm optimization ideas. The algorithm Generate new solutions with the help of a model which is established according to the distributional probability of high quality solutions. This design may enhance the study capability of particles and improve the accuracy of alignment. It is verified by simulation that the new algorithm can effectively avoid falling into local convergence and the accuracy of the optimal solution has been improved.Thirdly, we apply the new proposed algorithm to multiple sequence alignment problems, and propose multiple sequence alignment algorithm based on particle swarm optimization with probability statistic and automatic adaptive mutation. By means of a new coding method, the limit to the number of alignment sequence on algorithm is eliminated. By reference to variation operation, algorithm global convergence is guaranteed. The experiments results using 142 samples in BALIBASE may verify the feasibility and effectiveness of the algorithm.Finally, a sequence alignment software based on new proposed algorithm is designed and developed. With the advantages of simpleness and practicality, the software not only provides a platform about detecting the algorithm accuracy for computer researchers, but also supplies a application platform for biologists.