An Improved Genetic Algorithm for Multiple Sequence Alignment

作者：Fan, Hui; Wu, Ronghui^*; Liao, Bo; Lu, Xinguo

来源：Journal of Computational and Theoretical Nanoscience, 2012, 9(10): 1558-1564.

DOI：10.1166/jctn.2012.2244

• Multiple Sequence Alignment
• Genetic Algorithm
• Variance
• Intelligent Operator
• T-COFFEE

Multiple sequence alignment is one of the most important and common tasks in Bioinformatics, however, it is a NP complete problem. The problem of using genetic algorithm solve multiple sequence alignment is that the found solution maybe not the best one because of the randomness and the premature convergence of the algorithm and the lack of the diversity of the population. This article presents three ways to improve the genetic algorithm: the first one is that it puts forward some intelligent operators, which consider the characteristics of the biological sequences, for instance the insertion or the deletion often occur continuously in one position, and this way accelerates the evolution speed and improves the quality of the solution. The second one is that using the variance of fitness value adjusts the probability of intelligent mutation and random mutation to keep the diversity of the population. The variance of fitness value evaluates the diversity of the population, the diversity is not good when the variance below a threshold and it is necessary to increase the rate of random mutation and reduce the rate of intelligent mutation, and vice versa. The last one is that we use the cycles of evolution to void the large setting of the generation. We have tested the algorithm with four representative sequence sets. We also compare the achieved results with the results provided by T-COFFEE.

• 出版日期2012-10
• 单位湖南大学