新一代基因测序技术(NGS)的出现使得测序成本飞速下降,随之而来的是大量的短读序列需要更快速准确的比对程序来处理。第一代基于散列表技术的序列比对算法如Bowtie等能够快速准确的完成比对工作,但其不支持gap比对的特性使得在短读序列(short reads)过长导致indel出现频繁时,比对的精度也随之下降。另一方面,近年来压缩索引(BWT,CSA,FM-index)领域的相关研究使得在较小内存中索引人类基因组这样的大规模序列成为可能。这导致近年来出现了很多基于压缩索引的短读比对算法,如BWA,Bowtie等。本文提出了一种基于压缩后缀数组和后向搜索实现近似匹配的算法来实现短读比对,在比对时间和空间以及比对精度上都取得了很好的效果。基于压缩后缀数组的短读比对算法(CSAA),采用了压缩后缀数组来构建参考序列的索引,并使用后向搜索来做匹配。通过引入搜索树,CSAA实现了近似匹配算法,从而支持完全的gap比对。此外CSAA在搜索树上使用了一种类似堆的优先堆数据结构,大大减小了搜索空间。而且每一次的搜索方向都能保证是最优的。最后结合罚分机制以及difference距离,定义seed等方法,进一步降低搜索空间,提高了CSAA的比对速度和精度。CSAA的高效体现在三个方面。一是空间高效的索引方法;二是基于后向搜索的高效的近似匹配方法;三是seed策略和多线程比对技术的利用。本文采用了增量法进行压缩后缀数组索引的构建,从而跳过后缀数组的构建,降低了对内存的需求。而在比对时,seed的引入使得在比对短读的前几十个核苷酸就可以放弃大部分无效的搜索方向。多个短读比对的相互独立使得并行化成为可能,使得CSAA使用多线程时可以获得数倍的加速优势,从而可以根据计算机的cpu核数指定多个线程,以取得最优的比对速度。CSAA支持单端和双端序列比对,以Fastq格式输入,输出为标准的SAM(Sequence Alignment Map)格式。