求解MSA问题的新型单亲遗传算法

多序列联配(MSA)在生物信息学研究中占有重要地位,MSA问题是一个典型的NP问题,遗传算法是求解NP完全问题的一种理想方法。文章针对MSA问题,提出了一种新型单亲遗传算法(PGA),不使用交叉算子,只使用变异和选择算子。并根据群体的多样性自适应调节变异概率,有效消除了算法中的欺骗性条件,使用灾变算子来确保算法的搜索能力。整个算法模拟了自然界进化的周期性,较好地解决了群体的多样性和收敛深度的矛盾。算法的分析和测试表明,该算法是有效的。

A New Partheno-genetic Algorithm for MSA Problem

Multiple Sequence Alignment (MSA)has great importance in the field of Bioinformatics,MSA is a typical NP-Complete problem,and genetic algorithms (GAs )is the perfect method for solving NP-Complete.In this paper,a new partheno-genetic algorithm(PGA)has been presented to solve MSA,which only employs mutation operator and selec-tion operator to produce the offspring,instead of crossover operator.At the same time ,a method,which can change the possibility of the mutation operators,has been presented.In this way,algorithms can eliminate effectively the deceptive conditions.In addition,a specific cataclysm operator is designed to ensure its capability of searching.The algorithm simu-lates the recurrence of nature evolution process,and solve the contradiction between the diversity of population and the converge speed.As it has been proved by analysis and test,a better result is obtained by the new PGA.