随着下一代基因测序技术的发展,测序成本以超过摩尔定律的速度急剧下降,与此同时测序速度也大幅提升。这一系列进步导致了测序数据爆炸性的增长,从而使得测序数据的分析成为相关研究中的一个主要瓶颈。在大多数测序数据分析中,第一步均是测序序列比对,即找出测序片段在参考基因组上出现的位置。由于测序序列比对的重要性,长久以来其一直是生物信息学中的的一个关键而基础性问题。而面对下一代测序技术所产生的海量的测序数据,开发出高效的测序序列比对算法变得迫在眉睫。序列比对问题本质上是计算机中的字符串近似匹配问题。但不同于经典的字符串近似匹配方法,现代测序序列比对方法涉及的关键技术主要包括算法设计、索引方法研究和并行化加速。本文主要基于以上三个方面,并结合不同应用,研究测序序列比对方法中的算法理论和高效实现技术。具体来说,本文的主要工作和贡献如下;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加速。