面向第三代测序技术的基因组长序列片段比对算法研究

周佩霞

湖南师范大学

摘要：随着测序技术不断发展和改进,测得的基因组序列片段数据的特征也在不断变化。为适应当前第三代测序技术,基因组序列比对算法需要进行深入的研究和改进,以便更适合于处理第三代测序技术测得的长序列片段数据。本文重点研究分析了基于哈希和窗口哈希索引定位方法的序列比对算法,包括传统的基于哈希索引的序列比对方法SSAHA(Sequence search and alignment by hashing algorithm)和改进的基于窗口哈希索引的序列比对算法rHAT(Regional hashing-based alignment tool)。在此基础上,本文进行了进一步的改进,提出了基于窗口哈希双索引表和动态定位的长序列比对算法(WHDL)。WHDL算法在参考基因组索引表构建阶段同时建立窗口全局索引表和局部索引表。全局索引表与rHAT建立的窗口索引表相同,局部索引表则是应用于比对处理阶段,以减少重复处理。WHDL算法在命中定位阶段采用动态定位的新理念,在最后比对处理阶段也提出了对应的两种不同的处理方法(WHDL-1和WHDL-2),并应用了改进的SSAHA方法(SSAHA+),降低算法的复杂度。本文对算法进行了大量测试,测试结果显示,相比rHAT算法,WHDL-1算法能进一步减少运行时间,加快比对速度,提高处理效率。本文还简要讨论了算法进行并行化处理的可行性和粒度。本文最后还探讨了采用序列相似度比较的方法进行DNA序列比对定位,也探讨了从信号与噪声的角度来理解基因组规律和基因变异,并对此进行了简要的分析。还原

关键词：

长序列比对;窗口哈希索引;动态定位;信号噪声与基因变异;