基于BWT的DNA重叠群序列合并算法研究

摘要

自1977年基因测序技术的产生发展之后,人们对基因分子生物学的研究和探索的热情日益高涨,分子生物学迅猛发展,第二代测序技术的产生使基因分子生物学的发展产生巨大变革。随之第三代测序技术不断发展,人们能够更容易的获得大量的基因测序数据。不同于第一代测序技术产生的较长序列片段,新一代测序的数据片段相对较短,错误率也较高,同时,新一代测序技术的拥有的显著优点就是高通量,成本低,其显著优点促使研究人员对基因组拼接组装算法的研究产生更大的热情。生物测序技术革命性的飞跃,使基因的拼接合并技术面临新的挑战。
　　本文将要探讨的DNA重叠群序列的合并算法,是全基因组拼接组装算法的一个重要过程,即为全基因组组装过程,但是在很多研究中,基因的组装过程都只是在基因拼接之后的一个拼接优化过程。研究独立于全基因组拼接组装并高效率的处理海量测序数据的重叠群序列合并算法是非常值得深入探讨的。
　　本文提出了一种新的DNA重叠群序列的合并算法。该算法是基于BWT方法,建立关于DNA重叠群参考序列的索引结构。利用现有的配对信息数据库,将配对信息与DNA重叠群之间的位置关系搜索过程转化为BWT索引的序列匹配过程,这种方法能提高处理海量测序数据的时间效率。同时采用抽样保存 BWT的索引信息方法,降低算法实现的内存占有率。实验中,将参考序列的BWT索引得到的与配对信息的位置关系信息保存在数据结构中,同时对重叠群序列之间的匹配关系进行比较删除,得到关联性最高的重叠群序列,将其进行合并,最后得到具有较高质量的重叠群序列合并成更长的碱基序列。同时考虑相邻重叠群序列之间的两种位置关系,对重叠群序列合并结果进行优化更新,修正重复的序列片段并填充空隙,最终输出重叠群序列合并结果序列。
　　本文提出的重叠群序列合并算法,是独立于基因拼接组装技术的针对重叠群序列处理的算法,利用BWT结构的快速序列匹配功能,降低内存空间的占用,提高算法运行的速度,实现重叠群序列的合并。最后通过对重叠群序列合并结果序列的完善,充分考虑重叠群序列之间存在的重复序列片段和空隙情况,将84％的重叠群完成合并,输出结果碱基序列。

目录

基于BWT的DNA重叠群序列合并算法研究

Algorithm Research of DNA Contig Merger Based on BWT

摘 要

Abstract

第1章 绪 论

1.1 课题背景

1.2 研究目的及意义

1.3 国内外研究现状

1.4 本文主要研究内容

第2章 BWT索引

2.1 BWT的序列匹配原理

2.2 配对信息数据处理

2.3 Contig及其参考序列

2.4 BWT后缀数组

2.5 本章小结

第3章 查找contig间最优关联算法

3.1 Contig的BWT索引结构

3.2 查找contig 间末端关联性

3.3 Contig间末端匹配

3.4 本章小结

第4章 Contig合并算法

4.1 Contig间关联结构

4.2 Contig间合并

4.3 Overlap处理

4.4 Gap填充

4.5 本章小结

第5章 系统的运行结果及评价

5.1 程序运行结果

5.2 质量与长度评价

5.3 算法性能评价

5.4 本章小结

结 论

参考文献

哈尔滨工业大学学位论文原创性声明及使用授权说明

致 谢