| 摘要 | 第3-5页 |
| abstract | 第5-7页 |
| 1 引言 | 第14-22页 |
| 1.1 研究背景和意义 | 第14-17页 |
| 1.2 国内外研究现状 | 第17-19页 |
| 1.2.1 拼接算法研究现状 | 第17页 |
| 1.2.2 比对算法研究现状 | 第17-19页 |
| 1.3 论文内容及组织结构 | 第19-22页 |
| 2 基因拼接与比对算法介绍 | 第22-39页 |
| 2.1 测序知识概述 | 第22-24页 |
| 2.1.1 第一代测序技术 | 第22页 |
| 2.1.2 第二代测序技术 | 第22-23页 |
| 2.1.3 第三代测序技术 | 第23-24页 |
| 2.2 拼接问题描述及难点 | 第24-25页 |
| 2.2.1 拼接问题描述 | 第24页 |
| 2.2.2 拼接问题分类 | 第24页 |
| 2.2.3 拼接问题涉及的概念术语 | 第24页 |
| 2.2.4 拼接问题的挑战 | 第24-25页 |
| 2.3 已有的拼接算法及软件工具 | 第25-29页 |
| 2.3.1 贪心算法 | 第26页 |
| 2.3.2 OLC(overlap–layout–consensus)方法 | 第26-27页 |
| 2.3.3 DBG(DeBruijnGraph)算法 | 第27页 |
| 2.3.4 评估拼接算法的标准 | 第27-28页 |
| 2.3.5 相关软件 | 第28-29页 |
| 2.4 多序列比对问题描述 | 第29-30页 |
| 2.4.1 序列比对问题描述 | 第29页 |
| 2.4.2 序列比对的意义 | 第29-30页 |
| 2.5 已有的比对算法及软件工具 | 第30-39页 |
| 2.5.1 经典算法 | 第30-32页 |
| 2.5.2 启发式智能算法 | 第32-33页 |
| 2.5.3 并行算法 | 第33-35页 |
| 2.5.4 评估指标 | 第35-37页 |
| 2.5.5 相关软件 | 第37-39页 |
| 3 改进拼接算法的并行性研究 | 第39-64页 |
| 3.1 Hadoop平台概述 | 第39-48页 |
| 3.1.1 MapReduce介绍 | 第39-43页 |
| 3.1.2 Spark介绍 | 第43-48页 |
| 3.2 记忆K-mers来源Read的拼接算法(SA-BR) | 第48-49页 |
| 3.2.1 DBG算法的不足 | 第48-49页 |
| 3.2.2 改进策略的提出 | 第49页 |
| 3.3 MapReduce下的并行SA-BR拼接算法(SA-BR-MR) | 第49-54页 |
| 3.3.1 算法流程 | 第49-50页 |
| 3.3.2 拼接过程 | 第50-53页 |
| 3.3.3 算法的并行性分析及设计 | 第53-54页 |
| 3.4 Spark中的并行SA-BR拼接算法(SA-BR-Spark) | 第54-61页 |
| 3.4.1 引入 | 第54-55页 |
| 3.4.2 算法的并行性分析及设计 | 第55页 |
| 3.4.3 详细拼接步骤 | 第55-60页 |
| 3.4.4 难点及克服 | 第60-61页 |
| 3.5 拼接算法的加速策略 | 第61-63页 |
| 3.5.1 十六进制表示 | 第61-62页 |
| 3.5.2 效率的评估 | 第62-63页 |
| 3.6 本章小结 | 第63-64页 |
| 4 改进多序列星比对算法的并行性研究 | 第64-85页 |
| 4.1 基于新策略的改进星比对算法(MSA-K-Mers) | 第64页 |
| 4.1.1 原星比对算法的不足 | 第64页 |
| 4.1.2 改进策略的提出 | 第64页 |
| 4.2 MapReduce下改进星比对算法(MSA-K-Mers-MR)的并行性研究 | 第64-74页 |
| 4.2.1 算法设计 | 第64-67页 |
| 4.2.2 例子演示 | 第67-74页 |
| 4.3 Spark下改进星比对算法(MSA-K-Mers-Spark)的并行性研究 | 第74-79页 |
| 4.3.1 算法设计 | 第74-76页 |
| 4.3.2 改进算法的实施过程 | 第76-79页 |
| 4.4 双序列比对的思想策略 | 第79-81页 |
| 4.5 两种环境下算法并行化过程中的难点及克服 | 第81-83页 |
| 4.5.1 MapReduce中改进星比对算法的并行化的难点及克服 | 第81-82页 |
| 4.5.2 Spark环境下算法并行化过程中的难点及克服 | 第82-83页 |
| 4.6 进一步并行化的Improved-MSA-K-Mers-Spark的设计 | 第83页 |
| 4.7 本章小结 | 第83-85页 |
| 5 实验结果与分析 | 第85-97页 |
| 5.1 实验环境 | 第85页 |
| 5.2 实验设计与结果分析 | 第85-96页 |
| 5.2.1 拼接算法的准确性 | 第85-90页 |
| 5.2.2 K的取值范围总结 | 第90页 |
| 5.2.3 不同平台下并行化编程对时间的影响比较 | 第90-92页 |
| 5.2.4 比对算法的精确性 | 第92-94页 |
| 5.2.5 比对算法的效率提升 | 第94-95页 |
| 5.2.6 Spark不同配置服务器下结果的比较 | 第95页 |
| 5.2.7 算法效率的进一步提升 | 第95-96页 |
| 5.3 本章小结 | 第96-97页 |
| 6 总结与展望 | 第97-100页 |
| 6.1 总结 | 第97-98页 |
| 6.2 展望 | 第98-100页 |
| 致谢 | 第100-101页 |
| 参考文献 | 第101-109页 |
| 作者简介 | 第109-110页 |
