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

DNA序列拼接中deBruijn图结构的研究

作　者: 王东阳
导　师: 任世军
学　校: 哈尔滨工业大学
专　业: 计算机科学与技术
关键词: DNA序列拼接 Euler路径 de Bruijn图信息系统
分类号: Q523
类　型: 硕士论文
年　份: 2011年
下　载: 57次
引　用: 0次
阅　读: 论文下载

内容摘要

生物信息学是研究对生物数据进行获取、存储、分析等多个方面的一门综合性学科,是生命科学研究的重要组成部分。基因组测序是生物信息学中最基本的研究方向之一,然而大多数生物的基因组都不可能在实验中一次性测得,需要利用序列拼接技术对实验中获得的零散的DNA片段进行拼接操作。当前的序列拼接算法主要有两类:基于Hamilton路径的拼接算法和基于Euler路径的拼接算法。基于Hamilton路径的算法会导致NP-完全问题,具有过高的时间复杂度;基于Euler路径的拼接算法把DNA序列拼接问题转化为在de Bruijn图中寻找Euler路径的问题,存在线性时间算法,但需要的存储空间较Hamilton路径算法多。随着测序技术的发展,测序过程中获得的DNA片段越来越短,基于Euler路径的拼接算法在处理这种短片段拼接时更具优势,是目前序列拼接的重要研究方向。在Euler路径算法中,一个关键步骤是de Bruijn图的构建,一直以来,构建de Bruijn图的方式都没有改变过,总是让后一个k-mer与前一个k-mer之间有k-1个碱基的交叠,相邻的两个k-mer之间相互错开一位。但本文的研究发现,如果让有边连接的两个k-mer之间相互错开两位或者更多位数的碱基,使他们之间有k-2个或者更少的碱基相交叠,会对de Bruijn图结构的复杂性产生重要影响。本文针对这些影响进行详细分析,并设计了一个可以对错位数与de Bruijn图结构关联性信息进行查询的系统。系统运行结果表明,k-mer之间的错位数变化对de Bruijn图结构复杂性确有显著影响,已有的算法如能考虑到错位数的影响,选择合适的错位数来构建结构更加简单的de Bruijn图,并在拼接算法中考虑错位数因素,会得到更好的拼接效果。

全文目录

摘要  4-5
Abstract  5-8
第1章绪论  8-12
  1.1 课题背景  8
  1.2 国内外研究现状  8-10
  1.3 本文的主要研究内容及意义  10-12
第2章基因组测序技术与序列拼接技术  12-22
  2.1 引言  12
  2.2 DNA 测序技术  12-18
    2.2.1 第一代测序技术  12-13
    2.2.2 第二代测序技术  13-17
    2.2.3 第三代测序技术  17
    2.2.4 三代测序技术比较  17-18
  2.3 序列拼接技术  18-21
    2.3.1 贪心算法  18
    2.3.2 Hamilton 路径算法  18-19
    2.3.3 Euler 路径算法  19-20
    2.3.4 拼接算法比较  20-21
  2.4 本章小结  21-22
第3章错位数与DE BRUIJN 图结构的关联性  22-33
  3.1 引言  22
  3.2 DE BRUIJN 图中的分支结构  22-24
  3.3 错位数改变对DE BRUIJN 图中分支结构的影响  24-31
  3.4 错位数改变对拼接算法的时间和空间复杂性的影响  31-32
    3.4.1 错位数改变对拼接算法空间复杂性的影响  31
    3.4.2 错位数改变对拼接算法时间复杂性的影响  31-32
  3.5 本章小结  32-33
第4章错位数对DE BRUIJN 图中REPEAT 结构的影响  33-39
  4.1 引言  33
  4.2 错位数对DE BRUIJN 图中的REPEAT 数目影响的直观分析  33
  4.3 建立数学模型  33-38
    4.3.1 确定de Bruijn 图中的顶点的数目  34-35
    4.3.2 确定de Bruijn 图中以分岔点为起点的有向边的数目  35-38
  4.4 本章小结  38-39
第5章错位数与DE BRUIJN 图结构关联性信息查询系统  39-49
  5.1 引言  39
  5.2 错位数与DE BRUIJN 图结构关联性信息查询系统  39-44
    5.2.1 系统意义与原理  39
    5.2.2 Servlet 与JSP 技术  39-41
    5.2.3 系统体系结构  41-42
    5.2.4 系统核心算法  42-44
  5.3 系统运行所需的配置及系统使用方法  44
  5.4 系统功能测试  44-48
  5.5 本章小结  48-49
结论  49-50
参考文献  50-54
致谢  54

DNA序列拼接中deBruijn图结构的研究

内容摘要

全文目录

相似论文