面向大规模测序数据集的序列比对算法研究

论文摘要

随着下一代基因测序技术的发展,测序成本以超过摩尔定律的速度急剧下降,与此同时测序速度也大幅提升。这一系列进步导致了测序数据爆炸性的增长,从而使得测序数据的分析成为相关研究中的一个主要瓶颈。在大多数测序数据分析中,第一步均是测序序列比对,即找出测序片段在参考基因组上出现的位置。由于测序序列比对的重要性,长久以来其一直是生物信息学中的的一个关键而基础性问题。而面对下一代测序技术所产生的海量的测序数据,开发出高效的测序序列比对算法变得迫在眉睫。序列比对问题本质上是计算机中的字符串近似匹配问题。但不同于经典的字符串近似匹配方法,现代测序序列比对方法涉及的关键技术主要包括算法设计、索引方法研究和并行化加速。本文主要基于以上三个方面,并结合不同应用,研究测序序列比对方法中的算法理论和高效实现技术。具体来说,本文的主要工作和贡献如下;1.FM-index索引方法中定位过程设计及优化作为一种压缩的全文本索引,FM-index是众多序列比对算法中的关键数据结构,其性能的好坏直接影响整个算法的效率。相比于传统的索引,FM-index仅存储少量采样位置以降低空间开销。然而,对于非采样位置,FM-index需要通过计算代价较高的定位操作逐个还原出来。本文提出了一种全新的定位算法FMtree,当处理基因数据时,能够成组的还原非采样位置。其将FM-index的定位操作的搜索空间组织成一棵四叉树,从而通过遍历该四叉树,非采样位置能够被成组的恢复出来,而不是像现有算法一样逐个计算。此外,本文也提出了一些剪枝策略,以进一步提升FMtree的性能。实验结果表明,当处理包含多达数十亿碱基的人类基因组和小鼠基因组时,FMtree能够比现有的压缩索引上的定位算法快一个数量级,且依然保持较小的空间开销。2.找全比对算法优化找全比对算法用于找到每个测序片段在参考基因组上所有近似匹配位置,其在一些特定的下游应用中发挥着重要的作用。相比于仅需报告少量匹配位置的最佳比对算法,找全比对算法更为耗时,所以其难以高效的处理大规模测序数据集。在目前主流的找全比对算法中,最耗时的阶段是动态规划验证阶段。在该阶段时,找全比对算法需要执行大量编辑距离计算,以找出测序片段在参考基因组上真正的匹配位置。本文提出了一种高效的找全比对算法BitMapper,其采用了全新的向量化位并行算法以加速编辑距离计算。我们提出的向量化位并行算法能够同时执行多个编辑距离计算任务,而现有的方法只能逐个计算。实验结果表明,基于该向量化位并行算法的BitMapper,能够比目前最快的找全比对算法快大约3到4倍。3.找全比对算法的GPU加速GPU包含大量的计算核心,能够提供强大的并行计算能力。由于找全比对算法需要处理海量的测序片段,且不同测序片段之间无数据关联,所以找全比对算法非常适合于利用GPU进行并行化。但是现有序列比对算法中常用的FM-index和q-gram index均不适合于GPU的体系结构。基于FM-index的字符串匹配算法数据局部性较差且分支较多,而q-gram index巨大的空间开销使得其无法整体存储在GPU全局存储器。本文参考FM-index的压缩策略,提出了一种针对GPU体系结构的稀疏q-gram index,并在此基础上设计了基于GPU的找全比对算法BitMapper2。实验结果表明,BitMapper2比现有基于CPU和GPU的比对算法均快7到8倍。4.基于改进FM-index的甲基化序列比对算法设计作为甲基化检测的金标准,重亚硫酸盐测序将非甲基化的胞嘧啶（C）转换成胸腺嘧啶（T）,而甲基化的胞嘧啶（C）保持不变。甲基化序列比对算法是一类特殊的测序序列比对算法,其目的是为了发现甲基化的C。传统算法没有利用重亚硫酸盐测序将大量的C转化为了T这一特性,因此存在可优化的空间。本文提出了基于重亚硫酸盐测序的甲基化序列比对算法BitMapperBS,其包含一个全新的针对重亚硫酸盐测序数据做高度优化的FM-index。与此同时,BitMapperBS也采用了向量化位并行算法以加速比对结果的详细验证过程。实验结果表明BitMapperBS能够在较小的空间开销下,数十到数百倍快于目前主流的甲基化比对算法,同时保持相当或更好的敏感性和准确率。BitMapperB能够在10分钟内将2亿条测序片段比对到人类参考基因组上,而目前常用的甲基化比对算法需要数十个小时。以上四项研究工作可以分为算法理论和高效实现两个方面。其中算法理论包括FM-index索引方法中定位过程设计及优化和基于改进FM-index的甲基化序列比对算法设计,而高效实现包括找全比对算法优化和找全比对算法的GPU加速。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
•   1.1 研究背景及意义
•   1.2 相关概念
•     1.2.1 测序技术简介
•     1.2.2 测序序列比对相关名词介绍
•     1.2.3 测序序列比对问题定义及评价标准
•   1.3 研究现状
•     1.3.1 序列比对算法的索引技术
•     1.3.2 序列比对算法设计
•     1.3.3 序列比对算法并行化
•   1.4 本文研究内容
•     1.4.1 FM-index索引方法中定位过程设计及优化
•     1.4.2 找全比对算法优化
•     1.4.3 找全比对算法的GPU加速
•     1.4.4 基于改进FM-index的甲基化序列比对算法设计
•   1.5 论文组织
• 第2章 FM-index索引方法中定位过程设计及优化
•   2.1 引言
•   2.2 背景知识及相关概念
•     2.2.1 相关定义和概念
•     2.2.2 FM-index简介
•     2.2.3 FM-index定位算法的的瓶颈
•   2.3 高效的FM-index定位算法:FMtree
•     2.3.1 FMtree算法基本思路
•     2.3.2 进一步优化:剪枝策略
•     2.3.3 FMtree完整算法
•   2.4 实验结果与分析
•     2.4.1 小数据集上的实验结果
•     2.4.2 大数据集上的实验结果
•   2.5 本章小结
• 第3章 找全比对算法优化
•   3.1 引言
•   3.2 背景知识及相关概念
•     3.2.1 问题定义及相关概念
•     3.2.2 过滤阶段
•     3.2.3 验证阶段
•   3.3 基于向量化位并行算法的找全比对算法
•     3.3.1 受限编辑距离计算
•     3.3.2 向量化位并行算法
•     3.3.3 模式串数量对向量化位并行算法的影响
•     3.3.4 向量化验证框架
•   3.4 实验结果与分析
•     3.4.1 不同序列比对算法敏感性比较
•     3.4.2 不同序列比对算法在大数据集上的结果
•   3.5 本章小结
• 第4章 找全比对算法的GPU加速
•   4.1 引言
•   4.2 背景知识及相关概念
•     4.2.1 找全比对算法流程
•     4.2.2 GPU体系结构及编程模型
•     4.2.3 GPU加速找全比对算法瓶颈
•   4.3 基于稀疏q-gram index的GPU加速的找全比对算法
•     4.3.1 稀疏q-gram index
•     4.3.2 GPU加速的BitMapper2算法设计
•   4.4 实验结果与分析
•     4.4.1 模拟数据集上敏感性结果
•     4.4.2 大规模真实数据集上性能比较
•   4.5 本章小结
• 第5章 基于改进FM-index的甲基化序列比对算法设计
•   5.1 引言
•   5.2 背景知识和相关概念
•     5.2.1 相关概念和定义
•     5.2.2 FM-index基础知识
•   5.3 基于改进FM-index的甲基化序列比对算法
•     5.3.1 BitMapperBS简介
•     5.3.2 三字符FM-index
•     5.3.3 针对FM-index的进一步优化
•     5.3.4 种子与扩展策略
•   5.4 实验结果与分析
•     5.4.1 模拟数据上比对结果
•     5.4.2 真实数据上比对结果
•     5.4.3 比对算法在大规模数据集上的效率
•   5.5 本章小结
• 第6章 总结
•   6.1 本文工作
•   6.2 本文贡献与创新之处
•   6.3 进一步工作
• 参考文献
• 致谢
• 在读期间发表的学术论文与取得的研究成果
• 攻读学位期间参加的科研项目

文章来源

类型: 博士论文

作者: 程昊宇

导师: 徐云

关键词: 生物信息学,测序序列比对,甲基化,并行算法

来源: 中国科学技术大学

年度: 2019

分类: 基础科学

专业: 生物学

单位: 中国科学技术大学

分类号: Q811.4

总页数: 137

文件大小: 9541K

下载量: 275