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

论文摘要

随着测序技术不断发展和改进,测得的基因组序列片段数据的特征也在不断变化。为适应当前第三代测序技术,基因组序列比对算法需要进行深入的研究和改进,以便更适合于处理第三代测序技术测得的长序列片段数据。本文重点研究分析了基于哈希和窗口哈希索引定位方法的序列比对算法,包括传统的基于哈希索引的序列比对方法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序列比对定位,也探讨了从信号与噪声的角度来理解基因组规律和基因变异,并对此进行了简要的分析。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
•   1.1 课题背景
•   1.2 国内外研究现状和分析
•   1.3 本文的研究内容
•   1.4 本文的创新点
•   1.5 本文的组织结构
• 第二章 基于哈希索引定位的序列比对算法
•   2.1 SSAHA算法原理与分析
•     2.1.1 SSAHA算法流程概览
•     2.1.2 第一阶段索引构建
•     2.1.3 第二阶段命中
•     2.1.4 第三阶段分析处理
•     2.1.5 SSAHA算法分析
•   2.2 rHAT算法原理与分析
•     2.2.1 rHAT算法流程概览
•     2.2.2 第一阶段索引构建
•     2.2.3 第二阶段命中定位
•     2.2.4 第三阶段比对处理
•     2.2.5 rHAT算法分析
•   2.3 本章小结
• 第三章 基于窗口双索引表和动态定位的长序列比对算法
•   3.1 WHDL算法的原理详解
•     3.1.1 WHDL算法流程概览
•     3.1.2 第一阶段索引构建
•     3.1.3 第二阶段命中定位
•     3.1.4 第三阶段比对处理
•   3.2 WHDL算法分析与小结
• 第四章 算法实验结果和分析
•   4.1 模拟数据实验结果比较与分析
•   4.2 真实数据实验结果比较与分析
•   4.3 结论
• 第五章 总结与探讨
•   5.1 总结
•   5.2 探讨
•     5.2.1 采用序列相似度比较进行序列比对定位
•     5.2.2 基于信号与噪声的基因变异处理构想
• 参考文献
• 致谢

文章来源

类型: 硕士论文

作者: 周佩霞

导师: 谢民主

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

来源: 湖南师范大学

年度: 2019

分类: 基础科学,信息科技

专业: 生物学,生物学,计算机软件及计算机应用

单位: 湖南师范大学

分类号: Q811.4;TP301.6

总页数: 65

文件大小: 1497K

下载量: 119