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

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

论文摘要

生物信息学是研究对生物数据进行获取、存储、分析等多个方面的一门综合性学科,是生命科学研究的重要组成部分。基因组测序是生物信息学中最基本的研究方向之一,然而大多数生物的基因组都不可能在实验中一次性测得,需要利用序列拼接技术对实验中获得的零散的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图,并在拼接算法中考虑错位数因素,会得到更好的拼接效果。

论文目录

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

    标签:;  ;  ;  

    DNA序列拼接中deBruijn图结构的研究
    下载Doc文档

    猜你喜欢