| 【中文题名】 | 基于量子遗传算法和改进的免疫遗传算法的多序列比对算法研究 |
| 【英文题名】 | Research of Multiple Sequence Alignment Algorithm Based on Quantum Genetic Algorithm and Improved Immune Genetic Algorithm |
| 【学科专业】 | 计算机应用技术 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-8-7 |
| 【中关键词】 | 多序列比对,免疫遗传算法,量子遗传算法,sigmoid函数,信息熵,疫苗算子 |
| 【英关键词】 | |
| 【分类导航】 | 工业技术>自动化技术、计算机技术>自动化基础理论>人工智能理论>> |
| 【论文摘要】 |
多序列比对是生物信息学中最重要、也是最具有挑战性的任务之一。本文提出了一种基于量子遗传算法的多序列比对算法。另外,针对传统的免疫遗传算法在求解多序列比对问题时准确性和效率不足的状况,对免疫遗传算法进行了改进。
文中首先介绍了多序列比对的基础知识。然后针对传统的免疫遗传算法疫苗选择随机性强、容易陷入局部收敛的情况改进了疫苗算子,即利用轮盘赌方法随机的选择三个优良片段作为疫苗进行个体接种。另外,结合sigmoid函数和信息熵的概念,提出了一种全新的自适应策略,使得交叉率和变异率能够根据群体中所蕴含的信息的变化而相应的变化。实验结果表明改进的算法要好于传统的免疫遗传算法。
接下来,文章把量子遗传算法应用于多序列比对问题中,提出了基于量子遗传算法的多序列比对算法,并进行了适当的改进,包括设计了新的与问题无关的旋转角调整策略;为了加速收敛,采用了两阶段量子遗传算法;为了防止陷入局部收敛,加入了灾变策略。实验结果表明了算法的有效性。 |
| 【论文题纲】 |
|
提要 |
4-7 |
|
第一章 绪论 |
7-11 |
|
1.1 序列比对的历史 |
7-8 |
|
1.2 序列比对的研究现状 |
8-10 |
|
1.3 论文的结构和主要工作 |
10-11 |
|
第二章 序列比对基础与序列比对算法 |
11-23 |
|
2.1 序列比对基本概念 |
11-12 |
|
2.2 空位罚分的概念和策略 |
12-13 |
|
2.3 相似性替换矩阵 |
13-16 |
|
2.3.1 核酸替换矩阵 |
14-15 |
|
2.3.2 蛋白质替换矩阵 |
15-16 |
|
2.4 目标函数 |
16-19 |
|
2.4.1 SP目标函数 |
16-18 |
|
2.4.2 COFFEE目标函数 |
18-19 |
|
2.5 多序列比对结果的评判标准 |
19-20 |
|
2.5.1 BAliBASE 测试集 |
19 |
|
2.5.2 评价比对结果 |
19-20 |
|
2.6 多序列比对算法介绍 |
20-23 |
|
2.6.1 SAGA 算法 |
21-22 |
|
2.6.2 Clustal 算法 |
22-23 |
|
第三章 改进的免疫遗传算法求解多序列比对问题 |
23-37 |
|
3.1 免疫遗传算法介绍 |
23-25 |
|
3.2 针对多序列比对问题对免疫遗传算法的若干改进 |
25-32 |
|
3.2.1 变异算子的设计 |
25-27 |
|
3.2.2 交叉算子的设计 |
27-29 |
|
3.2.3 疫苗算子的改进 |
29 |
|
3.2.4 自适应函数的设计 |
29-32 |
|
3.3 算法的描述 |
32-34 |
|
3.3.1 编码及目标函数 |
32-33 |
|
3.3.2 算法过程 |
33-34 |
|
3.4 实验结果及分析 |
34-37 |
|
3.4.1 实验环境及测试用例 |
34 |
|
3.4.2 和实验相关的设置 |
34 |
|
3.4.3 实验结果及分析 |
34-37 |
|
第四章 量子遗传算法求解多序列比对问题 |
37-54 |
|
4.1 量子计算的背景 |
37-38 |
|
4.2 量子计算的基础知识 |
38-40 |
|
4.3 量子遗传算法 |
40-43 |
|
4.3.1 问题的表示 |
40-41 |
|
4.3.2 基本的量子遗传算法 |
41-43 |
|
4.4 多序列比对问题中量子遗传算法的设计 |
43-46 |
|
4.4.1 量子全干扰交叉 |
44 |
|
4.4.2 量子变异 |
44-45 |
|
4.4.3 通用的旋转角调整策略 |
45-46 |
|
4.4.4 群体灾变策略 |
46 |
|
4.4.5 两阶段量子遗传算法 |
46 |
|
4.5 基于量子遗传算法的多序列比对算法 |
46-50 |
|
4.5.1 算法中的一些问题 |
46-47 |
|
4.5.2 算法的描述 |
47-50 |
|
4.6 实验结果与分析 |
50-54 |
|
4.6.1 测试用例 |
50 |
|
4.6.2 基本参数的设置 |
50-51 |
|
4.6.3 与序列比对有关的设置 |
51 |
|
4.6.4 实验结果及分析 |
51-54 |
|
第五章 总结与展望 |
54-56 |
|
5.1 总结 |
54 |
|
5.2 下一步的工作 |
54-56 |
|
参考文献 |
56-59 |
|
摘要 |
59-62 |
|
Abstract |
62-65 |
|
致谢 |
65-66 |
|
导师及作者简介 |
66 |
|
| 【DOI】 | LunWen.ID:2.2008.388793 |
