新一代测序技术产生的序列片段普遍在35bp~75bp且数据量巨大,原来的序列比对和组装软件不适合这么短的序列,这就给序列比对和序列组装提出了新的挑战。本文主要探讨了新一代测序技术中的短序列比对和短序列组装算法。主要工作如下:(1)深入分析了基于哈希表的短序列比对算法ELAND、MAQ、SOAP以及基于BWT的短序列比对算法BOWTIE、BWA、SOAP2,对它们的原理及具体实现步骤进行了详细的解释,最后从模拟数据和实验数据两个方面对它们的性能进行了比较,从实验结果看基于BWT的算法在时间上与空间上一般优于基于哈希表的算法,MAQ算法虽然运行时间比基于BWT的时间要长,但是其内存使用率较低,SOAP算法是所有算法中对内存要求最高的算法。(2)对短序列组装算法进行了分类归纳,对SSAKE、VCAKE、VELVET短序列组装算法的原理和实现也做了深入的分析,并使用乳酸菌基因组对它们的性能进行了比较。从实验结果看,VELVET算法的拼接性能最好,其次是VCAKE,而SSAKE运行的时间较长。(3)然后提出一种新的基于分块索引的比对算法,算法也是基于BWT,它采用对BWT分块索引压缩的方式,并在内存中建立缓冲区,按照最久不用的原则将最久不用的块调出,以减少内存的占用。从实验结果看,当算法的缓冲区越大的时候,执行速度越快,优与MAQ算法,当缓冲区越小的时候,执行时间较长,但内存使用明显低于BOWTIE等算法。(4)最后对SOAP比对算法提出了一些改进,将短序列分为A,B,C三段,使内存使用率降低,加快了比对速度。并通过实验与SOAP算法做了比较,其内存使用率和运行速度均优于SOAP算法。