一种基于遗传算法的DNA多序列比对方法

摘要

为了克服遗传算法应用于多序列比对时所遇到的比对序列数受限制以及比对寻优速度慢的缺点,提出了一种基于遗传算法的DNA多序列比对方法(GAMA);针对DNA多序列比对的特点,指出了传统遗传算法中的交叉操作将为序列比对带来沉重的计算负担;避开遗传算法通常所采用的遗传操作算子,设计了独特的遗传算子(插入删除算子和合并分离算子)、基于BLAST相似度评分方法和完全比对块加权的个体适应度值评价函数,采用了便于插入和删除操作以及相似度评分的基于字符和空位矩阵的染色体编码方案.本算法具有操作算子数量少,算子调用机制简明的特点.最后,给出了将GAMA应用于DNA多序列比对的算例,实验结果验证了本算法的可行性.