量子遗传算法及其在多序列比对问题中的应用

论文摘要

生物信息中的多序列比对问题,是建立系统发育树,基因和蛋白质的功能预测,探测序列之间的相互作用等的基础。但是,多序列比对问题是一个NP-hard问题,非常具有挑战性,对序列比对算法的速度和质量有较高要求。一些智能优化方法应用于该领域中,取得了不错的结果。遗传算法是一种随机迭代优化算法,对于解决复杂的组合优化问题有优势。但是由于多序列比对问题本身的复杂性,传统的遗传算法收敛速度比较慢,没有指导的对个体进行修正,带有一定的盲目性,容易产生退化现象。在量子特性的启发下,本文提出了一种新的量子遗传算法QGAlign解决生物序列分析中的多序列比对问题。算法首次提出了一种新的量子概率编码方法,并设计了基于该编码方法的量子旋转角变异算子和五种遗传算子。利用量子叠加态特性对染色体进行编码,增强了种群的多样性;利用量子旋转门通过最优解来引导群体的进化过程,加快了算法的收敛速度。为了避免量子旋转门变异可能带来局部最优的问题,设计了基于多序列比对问题的遗传算子,来优化比对结果,使进化过程更具启发性和多样性。通过实验验证了遗传算子对算法的优化性能。对BAliBASE2.0库中的数据进行测试,与CLUSTAL X、SAGA等方法进行了比较,结果表明该算法框架具有很好的全局寻优能力,并且具有种群小、迭代次数少特点,是可行的。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景和动机
• 1.2 研究前沿现状
• 1.3 论文的主要工作及安排
• 第二章 量子进化算法
• 2.1 量子计算的基本概念
• 2.1.1 量子位与状态叠加
• 2.1.2 状态的相干
• 2.1.3 状态的纠缠
• 2.1.4 量子并行性
• 2.1.5 基本量子门
• 2.2 进化算法概述
• 2.2.1 基本要素
• 2.2.2 处理流程
• 2.2.3 遗传算法的缺陷
• 2.3 量子进化算法流程
• 2.3.1 量子进化算法的结构
• 2.3.2 量子遗传算法的框架
• 2.3.3 算子和参数选择的讨论
• 第三章 序列比对基本算法
• 3.1 序列比对生物模型
• 3.1.1 打分矩阵和罚分
• 3.1.2 目标函数
• 3.1.3 比对评判标准
• 3.2 双序列比对
• 3.3 多序列比对
• 3.3.1 问题描述
• 3.3.2 多序列比对算法介绍
• 3.3.3 Clustal比对算法
• 3.4 遗传多序列比对算法
• 3.4.1 遗传算法SAGA
• 3.4.2 免疫遗传算法
• 第四章 量子遗传多序列比对算法
• 4.1 量子概率问题表示
• 4.1.1 量子染色体编码
• 4.1.2 目标函数
• 4.2 算法流程
• 4.2.1 算法流程
• 4.2.2 详细描述
• 4.3 量子遗传算法的进化与优化机制
• 4.3.1 量子变异
• 4.3.2 遗传算子设计
• 4.4 实验结果及分析
• 4.5 结论与讨论
• 第五章 总结和展望
• 致谢
• 参考文献
• 研究成果