基于遗传算法和模拟退火算法的DNA多序列比对算法研究

摘要

提出了一种基于遗传算法和模拟退火算法的DNA多序列比对算法.针对多序列比对的具体特点,指出交叉操作是导致比对计算复杂度提高的原因之一,因而在本研究所提出的多序列比对算法中,取消了遗传算法中通常采用的交叉操作算子,设计了适合多序列比对特点的插入删除算子和合并分离算子,同时在多序列比对的总对数评分规则的基础上提出了完全比对块的概念,采用了完全比对块加权的个体适应度值评价函数以引导遗传算法寻优局部比对.本研究还引入了基于模拟退火算法的遗传操作算子调用机制,以便在避免完全比对块过多的被遗传操作所破坏的同时防止遗传算法陷入局部极小,达到兼顾算法寻优质量和效率的目的.最后通过一个DNA多序列比对的算例验证了算法的可行性.