学位论文 > 优秀研究生学位论文题录展示

基于欧拉路径的并行DNA序列拼接

作　者: 陈大春
导　师: 任世军
学　校: 哈尔滨工业大学
专　业: 计算机科学与技术
关键词: 欧拉路径 de Bruijn图并行DNA拼接哈希映射
分类号: Q78
类　型: 硕士论文
年　份: 2010年
下　载: 196次
引　用: 0次
阅　读: 论文下载

内容摘要

DNA序列拼接是基因组测序的核心问题之一。从1977年Sanger测序技术发明开始,到2005年第二代测序技术问世这段时间,DNA测序主要采用Sanger测序技术。Sanger测序技术测得的DNA片段长度能达到1000bp,并且准确率能够达到99.999%。Sanger测序技术得到的DNA片段通常用交叠-排列-生成一致序列算法进行拼接。与第一代测序技术相比,第二代测序技术测得的DNA片段具有长度较短、错误率较高以及通量大等特点。针对这些序列的特点,第二代测序技术当前有三种拼接策略:贪心算法,交叠-排列-生成一致序列算法,以及基于de Bruijn图的欧拉路径算法。这三者中前两者需要计算所有DNA片段的共有序列,具有较高的时间复杂度。基于de Bruijn图的欧拉路径算法通过将read拆分为k-mer将DNA拼接问题转换为求欧拉路径问题。欧拉路径问题有线性时间算法。本文采用欧拉路径算法作为作DNA序列拼接算法。第二代测序技术的通量很高。第二代测序技术在一次运行能产生几G字节的read数据,基于de Bruijn图欧拉拼接算法将面临空间的瓶颈。本文描述一个基于de Bruijn图的并行拼接算法,该算法通过将由read拆分产生的k-mer分布存储在多个进程的哈希表中,并对k-mer编码降低内存消耗。DNA拼接并行执行,并通过发送和接收数据包在各个拼接进程之间共享数据。实验结果表明,该并行拼接算法具有近似线性的时间复杂度与空间复杂度,因而具有良好的可扩展性,能够解决较大规模基因组的序列拼接问题。

全文目录

摘要  4-5
Abstract  5-8
第1章绪论  8-16
  1.1 课题研究背景目的和意义  8-9
  1.2 基因组测序技术简介  9-14
    1.2.1 第一代测序技术  9-10
    1.2.2 第二代测序技术  10-12
    1.2.3 第二代测序技术的特点  12-13
    1.2.4 第二代测序技术应用  13-14
  1.3 DNA拼接研究现状  14
  1.4 论文的主要内容及章节安排  14-16
第2章拼接算法研究  16-26
  2.1 DNA序列拼接的主要困难  16-18
  2.2 当前拼接策略分析  18-23
    2.2.1 贪婪算法  19-20
    2.2.2 交叠-排列-生成一致序列算法  20
    2.2.3 欧拉路径算法  20-22
    2.2.4 多数据集混合拼接  22
    2.2.5 当前拼接策略比较  22-23
  2.3 基于欧拉路径的并行拼接算法  23-24
    2.3.1 ABySS拼接算法  23-24
    2.3.2 P-Assembler拼接算法  24
  2.4 并行拼接算法改进  24-25
  2.5 小结  25-26
第3章 DNA并行拼接的实现  26-39
  3.1 并行拼接平台  26
  3.2 de Bruijn图存储技术  26-28
    3.2.1 分布存储de Bruijn图  26-27
    3.2.2 编码压缩de Bruijn图  27-28
  3.3 并行地构建de Bruijn图  28-33
    3.3.1 并行构建de Bruijn图顶点  28-29
    3.3.2 DNA序列错误的并行修正  29-32
    3.3.3 并行生成de Bruijn图  32-33
  3.4 并行生成单通路  33-35
  3.5 并行拼接单通路  35-37
  3.6 小结  37-39
第4章拼接系统性能评价  39-44
  4.1 评测运行环境  39
  4.2 评测数据集的生成  39-40
  4.3 实验结果分析  40-43
    4.3.1 拼接算法正确性验证  41
    4.3.2 运行时间及空间与数据规模关系  41-43
  4.4 小结  43-44
结论  44-45
参考文献  45-50
致谢  50

基于欧拉路径的并行DNA序列拼接

内容摘要

全文目录

相似论文