基于云平台的转录组数据Error correction算法的研究

发布时间：2017-05-20 09:13

  本文关键词：基于云平台的转录组数据Error correction算法的研究，，由笔耕文化传播整理发布。

【摘要】：基因测序技术可以帮助了解生物的遗传信息,从而识别生物体的致病基因和研究正确有效的治疗方法。由于现有技术的限制,DNA通常被打断成短片段,再用基因组装算法将其拼接。然而短片段序列中存在碱基错误,如何修正是组装算法的重要研究问题。现有的串行Error correction算法基于这样一种思想：来自于同一个基因组位置的reads共享某一段长度的子片段(K-mer),通过估算K-mer,找出最有可能出错的碱基并修改。比如K-mer清单算法,利用K-mer青单图来寻找错误碱基,虽然较为快速,但碱基纠错准确率不高。而K-mer枚举比对算法利用枚举出的K-mer找到具有相同特征的reads,再由这些reads找到错误碱基,虽然提高了准确率,但是计算复杂,内存消耗过大。因此两种算法无法胜任处理海量短片段序列的任务。本文提出并行Error correction算法,利用Hadoop的分布式文件系统(HDFS, Hadoop Distributed Filesystem)、Map/Reduce (Google Map/Reduce的开源实现)并行编程模型和新的碱基修改规则,提高Error correction的速度和准确率,减少Error correction内存的占用。本文主要工作包括：(1)针对Hadoop的Map/Reduce并行编程模型对原有算法的操作流程以及整体架构进行改进。设计适合用于并行Error correction算法的链表,利用该链表存储相关的K-mer信息和reads信息。利用Map/Reduce并行编程模型进行数据预处理：转变短片段序列的存储格式,过滤短片段序列中无用的信息,并行枚举出所有的K-mer,为后续的reads比对做准备。(2)利用Map/Reduce并行编程模型完成K-mer与reads的序列比对,得到所有包含相同K-mer特征的reads序列,用设计好的链表分组存储所有比对过后的序列。改进碱基修改规则,设计一种较为完善的计算平均碱基质量分数的规则,将之应用到并行算法中,并利用新规则修改错误碱基,以提高最终结果的准确率。(3)通过对并行算法和串行算法的运行时间、内存占用、以及纠错准确率的比较和分析,实验室结果表明并行Error correction算法是可行的,也是有效的。
【关键词】：Error correction reads 云计算 基因组装 并行化
【学位授予单位】：广西大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：Q811.4;TP393.09
【目录】：

• 摘要4-6
• ABSTRACT6-11
• 第一章 绪论11-16
• 1.1 研究背景11
• 1.2 研究意义11-12
• 1.3 研究现状12-14
• 1.3.1 Error correction算法的研究现状12-13
• 1.3.2 Hadoop的研究现状13-14
• 1.4 论文的研究内容和组织结构14-16
• 1.4.1 本文的研究内容14
• 1.4.2 论文组织结构14-16
• 第二章 相关知识介绍16-23
• 2.1 DNA序列测序相关知识16-17
• 2.1.1 测序技术简介16
• 2.1.2 第一代测序技术16
• 2.1.3 第二代测序技术16-17
• 2.2 Error correction相关知识17-18
• 2.2.1 Error correction算法的作用17
• 2.2.2 Error correction算法的相关概念17-18
• 2.3 Hadoop相关知识18-22
• 2.3.1 Hadoop项目简介18-20
• 2.3.2 HDFS与Map/Reduce的体系结构20-22
• 2.4 本章小结22-23
• 第三章 基于云平台的Error correction算法23-47
• 3.1 Error correction算法23-26
• 3.1.1 几种常见的串行Error correction算法23-25
• 3.1.2 并行化的Error correction算法25-26
• 3.1.3 并行化Error correction算法中Map/Reduce的工作流程与机制26
• 3.2 并行Error correction算法的数据结构26-28
• 3.3 并行Error correction算法的数据预处理28-33
• 3.3.1 修改文件格式28-29
• 3.3.2 过滤数据文件29-31
• 3.3.3 并行枚举出所有K-mer31-33
• 3.4 并行Error correction算法K-mer与Reads的序列比对33-41
• 3.4.1 读入K-mer与reads数据34-37
• 3.4.2 K-mer与reads的比对37-39
• 3.4.3 利用比对结果构建链表并演化链表39-41
• 3.5 完善碱基纠错规则并修改错误碱基41-43
• 3.6 后续碱基微调工作43-46
• 3.7 本章小结46-47
• 第四章 实验结果和分析47-54
• 4.1 Open stack云平台的部署策略47-49
• 4.1.1 Open stac软硬件环境介绍47
• 4.1.2 针对并行Error correction算法的云平台部署47-49
• 4.2 Hadoop集群的部署策略49-50
• 4.2.1 针对并行Error correction算法的Hadoop部署49-50
• 4.3 实验的数据来源50-51
• 4.4 实验结果分析51-53
• 4.5 本章小结53-54
• 第五章 总结与展望54-56
• 5.1 本文工作总结54
• 5.2 工作展望54-56
• 参考文献56-60
• 致谢60-61
• 攻读硕士学位期间发表和录用的论文61

【参考文献】

中国期刊全文数据库 前4条

1 李建江;崔健;王聃;严林;黄义双;;MapReduce并行编程模型研究综述[J];电子学报;2011年11期

2 白瑞俊;刘光明;张瑞虹;柴宝强;;虚拟化技术OpenStack在高性能计算集群上的应用与研究[J];计算机光盘软件与应用;2013年15期

3 李知杰;赵健飞;;OpenStack开源云计算平台[J];软件导刊;2012年12期

4 李英壮;汪楠;李先毅;;基于OpenStack开发云平台的设计与实现[J];武汉大学学报(理学版);2012年S1期

中国硕士学位论文全文数据库 前1条

1 曾培龙;基于reads引导的基因组序列拼接[D];哈尔滨工业大学;2012年

  本文关键词：基于云平台的转录组数据Error correction算法的研究，由笔耕文化传播整理发布。

本文编号：381192