随着下一代测序技术快速发展,日益增长的海量测序数据给序列比对带来了巨大挑战。序列近似比对是生物信息学领域中核心的基础问题之一,处于序列数据分析流程中的上游。针对k个替换错误的近似匹配问题,主流的比对软件如Bowtie1使用了启发式搜索的策略,基于Burrows-Wheeler transform(BWT)的索引技术,牺牲一定的比对精度来提高比对速度,但不能处理比对中存在很多替换错误的情况。本文对BWT进行了深入研究,提出了新颖的可逆性变换方法spaced Burrows-Wheeler transform(SBWT),采用种子和扩展的技术,设计了高精度的快速比对算法。SBWT使用了间隔种子技术,相对于连续的种子,它提高了过滤的特异度和灵敏度。在比对扩展阶段,利用二级索引技术和二进制编码技术加速了候选区域的验证速度。与传统的比对软件Bowtie1、BWA和SOAPv2等相比,SBWT在不损失比对精度的情况下,牺牲一定的空间复杂度,比对速度提高了5-21倍。本文的成果以及创新点主要体现在以下三个方面。首先,本文提出了新颖序列重排变换:SBWT。同BWT类似,它具有可逆性和LF Mapping特性,可用于解决序列匹配问题。SBWT构建的索引是后缀树结构的一类变体,BWT是其周期为1的特殊变换方法。与BWT不同的地方是:序列尾端添补的$数目与变换周期和序列长度有关;在间隔后缀序列排序过程中,使用改进的多键值快速排序算法进行周期性地排序;旋转字符矩阵的右起第(变换周期)列序列是变换后的序列。结合鸽巢引理,SBWT可以解决序列任意长度替换错误的近似匹配问题。基于SBWT间隔种子的特异性,本文设计了高精度的快速比对算法。通过对人类基因组的重复序列进行统计分析,本文发现连续种子的重复拷贝位点占比接近1/7,且存在长尾分布,而间隔种子的重复拷贝位点仅占全部的1/21左右。基于BWT的比对算法(Bowtie1和BWA等)使用连续种子技术,而SBWT使用的间隔种子技术具有更加广阔的分布域、更高的特异度,种子过滤的假阳性率也更低。设计二级索引结构驱动比对扩展。比对算法中的最后一步是比对扩展,对种子命中的候选区域进行验证,筛选符合比对条件的位点。SBWT有独特的同质间隔后缀区,可以设计特殊映射关系的数据结构,建立二级索引结构。相对于线性扫描的方法,本文使用二分查找算法可有效地处理候选区域过大的情况,驱动了比对扩展。此外,本文改进了碱基序列的信息编码和压缩的方法,提高了汉明距离的计算速度。