基于进化算法和量子计算的多序列比对方法研究

摘要

多序列比对(MultipleSequencealignment-MSA)是生物信息学中最重要、也是最有挑战性的任务之一。目前虽有不少比对方法提出，但在准确性和效率方面仍不够完善，因此，还需要进一步改进现有比对方法和探索新的比对方法。本文在研读了现有比对方法之后，提出了用自适应遗传算法(AdaptiveGeneticAlgorithm-AGA)和量子进化算法(QuantumEvolutionAlgorithm-QEA)来求解MSA问题。 论文中提出了两种比对方法：AGAMSA和QEAMSA。AGAMSA是遗传算法求解MSA问题的方法之一，不同点在于：算法中针对MSA问题，采用仅对空位编码的方式减少了存储空间；设计了5种新的遗传算子，和SAGA算法中22种操作算子相比，减少了操作的复杂性，也提高了收敛速度；引入自适应策略来平衡收敛速度和全局最优两者间的矛盾。本文提出的QEAMSA是一种新的比对方法，它是对基本QEA算法做了改造：采用新的表示方法Q-bit来表示MSA问题，设计了适合于该问题的量子个体更新方法；为避免QEA随机性较强的缺点，引入了一个优化算子，使得QEA更好地应用于求解MSA问题。最后用两种算法分别都测试了Balibase比对库中五个具有不同特点的测试用例子集Refl～Ref5，将测试结果和目前被公认的CLUSTALX和SAGA等比对方法已公布的测试结果作了比较，结果表明：AGAMSA和QEAMSA对Ref1和Ref5的测试结果次于CLUSTALX和SAGA等方法；对Ref2～Ref4的测试结果好于CLUSTALX和SAGA等方法。对于全部的测试子集，QEAMSA都优于AGAMSA。实验结果证明：AGAMSA和QEAMSA都是有效的多序列比对方法，更适合于比对含有孤儿的比对序列和包含N/C末端的比对序列。

目录

文摘

英文文摘

创新性声明及关于论文使用授权的说明

第一章 绪论

第二章 序列比对基础

第三章 序列比对算法介绍

第四章 自适应遗传算法求解多序列比对问题

第五章 量子进化算法求解多序列比对问题

结束语

附录

致谢

参考文献

在校期间科研成果