序列比对是生物信息学中的一个核心问题,它是一些生物学下游应用的基础。随着测序技术的发展以及千人基因组计划的执行,测序基因组的规模越来越大,序列比对耗时也越来越多。序列比对分为找最好和找全两类问题,其中后者是计算成本更耗时的问题。因此,找全序列比对算法也成为了一个重点研究方向,其主要评价标准为时间消耗和空间占用。过滤方法的好坏,直接决定了比对的总时间,现有的过滤方法过滤后候选位置较多,会消耗大量的验证时间,因而影响了序列比对算法的速度。选取的索引直接影响了内存占用和种子查找速度,但目前的哈希索引相对较大,且对变长种子的查找支持较差。为了加快比对的速度和减少内存占用,本文主要研究找全序列比对算法的过滤方法和索引的改造及优化,具体工作和贡献如下:(1)过滤方法设计及优化我们对目前已有过滤方法进行了分析和研究,发现经过过滤方法筛选后,仍有大量的候选位置不属于真正所要的匹配位置,但这些未匹配的位置仍会消耗大量的时间进行验证。本文提出了一种基于变长种子的动态规划过滤方法,变长种子可以明显减少定长种子的候选位置数量。为了解决变长种子带来的计算成本增加问题,我们采用了两种启发式的优化策略:限制种子长度变化范围和高频种子长度扩展,前者为降低计算成本而后者为降频处理。最后将该方法应用于目前速度最快的找全序列比对算法Bitmapper中,实验结果表明,在编辑距离为5时,相较于原Bitmapper,本文方法有约30%的加速。(2)索引改造及并行化现有的哈希索引空间较大,我们先利用稀疏化方法减少了哈希索引的空间。其次,原有适合定长种子的哈希索引技术需要为变长种子进行改造和优化。因此,本文设计了一种变长种子的方案,已应用在前面的Bitmapper算法实现中,该方案是以较长且固定长度为q的种子(即q-gram)为基索引,通过合并前缀来获取长度小于q的变长种子位置。随后,提出了一种索引改造和优化方法,减少了前缀合并的耗时操作,主要是在基索引的倒排表中加入后缀字符信息,并改进了求变长种子位置的计算方法,亦能很好适应稀疏哈希索引。最后,我们采用多线程对算法进行并行化加速。实验结果表明,将改造的索引和变长种子过滤方法相结合后,在编辑距离为5时,相比于原Bitmapper,计算时间和内存消耗均得到了有效减少;对于8线程,取得了约7倍的加速比。