基于de Bruijn图模型的基因组序列映射算法研究

论文摘要

随着高通量测序技术的快速发展和测序成本的逐渐降低,个体基因组测序已成为研究不同物种的基因型,变异情况和相关疾病的重要手段。生物信息学为人类探索生命体活动规律,疾病产生机制与治疗提供了新思路,极大推动了分子生物学,基因组学,遗传学和医学的发展。基因组序列映射（Mapping）作为基因组数据分析的基础对变异识别（Variant Calling）,基因表达量分析,选择性剪切分析和生物网络计算等研究方向有重要意义。还原测序数据在基因组上的真实位置是下游的生物信息计算的基础。然而,由于基因组上的大量重复序列和高变异区域,日益增大的测序数据量以及测序技术的局限等因素,如何准确且快速地将大量测序数据比对到参考基因组面临巨大挑战。本文围绕着基因组序列映射与序列比对为重点展开研究。本文的研究目的是通过分析现有比对方法的特性和不足之处,提出了基因组非线性的图模型组织表示方法。本文设计了基于de Bruijn图模型的基因组索引模型来有效组织和表达基因组上的大量重复片段。同时,为提高图模型的应用价值,提出针对大规模数据集的de Bruijn图模型构建算法。另外,本文实现了基于图模型的序列比对算法,达到了更高准确性,敏感性和更快的速度。并且,提出结合变异信息的序列比对算法进一步改进复杂变异区域的比对结果。本文的主要研究内容如下:（1）阐述基于哈希表模型思想的基因组序列数据的存储和索引方法。说明基于seed-and-extension思想的基本比对思路。提出一个基于de Bruijn图模型的索引模型（RdBG）以及该索引的三层结构数据存储方式。分析该索引模型的特性并提出两种种子合并的基本操作。该索引模型利用图模型特性可以有效组织基因组上的重复序列,从而极大地减少候选种子数量。（2）针对如宏基因组等多物种基因组数据和不断增加的测序数据,提出一个基于外部排序思想的de Bruijn图模型索引构建算法deGSM。deGSM解决了传统方法由于内存消耗大而限制图模型的数据量的问题,实现在任意内存占用下对任意大小数据完成图构建。同时,利用后缀树和de Bruijn图之间的关系,提出unitigs序列向BWT（Burrows-Wheeler变换）序列的转换方法。deGSM对基于de Bruijn图模型的大规模数据分析和数据压缩方法研究有重要意义。（3）根据de Bruijn图模型提出基于seed-and-extension思想的序列比对算法并实现序列比对软件deBGA。首先,介绍deBGA的整体算法流程和基于启发式的循环过程。然后,提出Uni-MEM种子的概念以及不同情况下种子合并和筛选的计算模型。同时,完成deBGA在相同物种和不同物种的多基因组数据集上,以及人类基因组的模拟和真实数据集上的测试。比较分析deBGA和其他比对软件在不同数据集上和不同参数下的比对结果。其次,比较分析deBGA对下游的变异识别计算的作用。结果显示基于RdBG索引的比对算法表现出更好的准确度,敏感度和更快的速度。deBGA可以作为基因组序列比对的候选工具。（4）提出结合变异信息的序列比对算法。首先,设计包含不同类型的变异信息的基因组索引模型实现变异信息的快速查找。其次,设计一个由所有局部序列和相关变异数据组成的伪树结构支持extension步骤计算。然后,利用Landau-Vishkin比对算法的思想提出一个基于此树结构的局部序列比对算法VAVA。相对于传统的内存消耗极大的变异图（Variant Graph）模型方法,该算法提供了一个轻量级的比对思路和解决方案。将VARA整合进deBGA实现全新的结合变异信息的序列映射系统deBGA-VARA。实验表明deBGA-VARA相比其他方法速度更快,并实现更高的准确度和敏感度。本文全面总结了基因组序列比对的基本方法,提出了de Bruijn图模型的索引模型来组织基因组重复序列。为解决对大数据构建图模型的内存瓶颈问题,本文提出基于外部排序思想的de Bruijn图模型构建算法,对索引模型和拼接算法的研究具有重要意义。同时,提出基于图模型的序列比对算法并通过大量实验证明该算法在不同数据集上都有很好效果,具有很高的实际意义;提出结合变异信息的局部序列比对算法,进一步提高了比对结果的准确性和敏感性,对基因组变异图模型和比对算法的研究具有理论和使用价值。

论文目录

• 摘要
• Abstract
• 第1章 绪论
•   1.1 课题背景及研究的目的和意义
•     1.1.1 研究背景
•     1.1.2 研究的目的和意义
•   1.2 基因组序列比对的背景知识
•     1.2.1 高通量测序技术
•     1.2.2 参考基因组
•     1.2.3 基因组序列映射
•     1.2.4 变异识别
•     1.2.5 基因组数据存储格式
•     1.2.6 主要数据结构
•   1.3 研究现状
•     1.3.1 基于哈希表模型的序列比对方法
•     1.3.2 基于后缀树的序列比对方法
•     1.3.3 de Bruijn图模型构建方法
•     1.3.4 基因组图模型
•   1.4 本文的主要研究内容
• 第2章 基于de Bruijn图的索引模型研究
•   2.1 引言
•   2.2 基因组图模型特性
•   2.3 基于哈希表的索引模型
•     2.3.1 基于哈希表的数据存储方法
•     2.3.2 基于哈希表的序列比对方法
•     2.3.3 基于哈希表的索引存储方法
•   2.4 基于de Bruijn图的索引模型
•     2.4.1 图索引的组织结构
•     2.4.2 图索引模型构建方法
•     2.4.3 基于图索引的相似种子识别方法
•   2.5 基因组索引模型种子获取的实验结果与分析
•   2.6 本章小结
• 第3章 可扩展的大规模de Bruijn图模型构建算法
•   3.1 引言
•   3.2 可扩展的图模型构建算法
•     3.2.1 基本原理与整体计算流程
•     3.2.2 图模型节点排序方法
•     3.2.3 图模型节点类型识别方法
•     3.2.4 图模型路径排列方法
•     3.2.5 图模型路径集合重构方法
•     3.2.6 图模型节点筛选方法
•   3.3 图模型构建方法的实验结果与分析
•     3.3.1 数据集描述
•     3.3.2 基因组数据集上建图结果分析
•     3.3.3 测序数据集上建图结果分析
•   3.4 本章小结
• 第4章 基于de Bruijn图模型的序列映射算法
•   4.1 引言
•   4.2 基于图模型的序列比对算法
•     4.2.1 整体计算流程
•     4.2.2 种子生成方法
•     4.2.3 相同路径上的种子合并方法
•     4.2.4 不同路径间的种子合并方法
•     4.2.5 局部序列比对方法
•   4.3 基因组序列比对实验结果与分析
•     4.3.1 测序数据比对到多个基因组
•     4.3.2 测序数据比对到单基因组
•   4.4 本章小结
• 第5章 结合变异信息的序列比对算法
•   5.1 引言
•   5.2 结合变异信息的序列比对方法
•     5.2.1 整体计算流程
•     5.2.2 伪树结构基本概念与构建方法
•     5.2.3 Landau-Vishkin序列比对算法
•     5.2.4 基于伪树结构的序列比对算法
•     5.2.5 比对结果信息重构方法
•   5.3 结合变异信息的序列比对方法实验结果与分析
•     5.3.1 模拟数据集上序列比对结果分析
•     5.3.2 测序数据集上序列比对结果分析
•     5.3.3 MHC区域上序列比对结果分析
•   5.4 本章小结
• 结论
• 参考文献
• 攻读博士学位期间发表的论文
• 致谢
• 个人简历

文章来源

类型: 博士论文

作者: 国宏哲

导师: 王亚东

关键词: 高通量测序数据分析,序列比对,基因组序列索引构建

来源: 哈尔滨工业大学

年度: 2019

分类: 基础科学

专业: 数学,生物学

单位: 哈尔滨工业大学

分类号: Q811.4;O157.5

DOI: 10.27061/d.cnki.ghgdu.2019.000110

总页数: 125

文件大小: 11384K

下载量: 117