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