论文部分内容阅读
生物DNA序列比对是生物信息学中的核心问题和基础研究,序列比对算法是常用的生物序列分析工具,也是RNA比对和个性化医疗等下游生物信息学研究的第一步。随着新一代高通量测序技术的飞速发展,产生了大规模测序序列,如何实现高精度的快速比对是生物信息学面临的严峻挑战。索引作为序列比对算法中处理大规模基因组和测序序列的重要技术,在绝大多数比对算法中广泛使用,是研究的关键环节和重点。本文对序列比对算法的主流索引技术BWT(Burrows-Wheeler Transform)和找全的序列比对算法进行了深入研究,主要内容和贡献包括：(1)基于双位索引的二阶BWT方法研究本文首先对逐位查找的传统一阶BWT技术进行了研究和分析,发现其存在访存次数较多、计算量较大的缺点,特别是数据规模较大时查找过程耗费时间更加突出。为此,我们设计了双位索引的二阶BWT方法,该方法在一阶BWT的辅助数据结构上实现了一次查找连续的两位字符(双位),显著地减少了序列比对索引算法中的循环遍历和计算次数,将序列比对算法中的索引查找复杂度降低了一半,提高了查找效率。实验结果表明,相比于传统的一阶BWT方法,二阶BWT方法提升了约35%的时间性能。为了进一步减少BWT中SA后缀数组的转换时间,我们又设计了一种编码方法,来加快双位索引串的匹配,实验结果表明改进后的方法能获得额外10%左右的性能提升。(2)BWT和Hash混合的索引技术及序列比对算法研究按照查找模式和应用场景的不同,序列比对问题可以分为两类：找全的比对问题和找最佳的比对问题。本文对找全的序列比对算法进行了分析,结合基于BWT的和基于Hash的两种索引方法的各自优点,提出了一种新的快速混合索引技术,取得了索引查找的时间和空间的较好平衡。在该混合索引的基础上,结合基于鸽巢原理的种子划分方法,给出了一个新的找全的序列比对算法。实验结果表明,相比已有的一些主流序列比对算法,本文算法比原序列比对算法时间减少30%以上且不影响查全率,而空间只增加3%。为了进一步提高速度,我们针对BWT转换阶段跳转过多、cache命中率低的缺点,设计了一种cache有效的分块读取转换方法。实验结果表明改进后的算法获得了额外10%左右的性能提升。