论文部分内容阅读
在过去的数年中,高通量测序在极大的拓展了测序技术应用领域的同时也产生了海量的测序数据集。如何将这些海量的测序序列数据快速的比对到基因组上,准确的找出它们的原始位置是许多生物医学领域研究的前提和至关重要的一步,因此已有许多序列比对工具被开发出来专门用于短序列比对。然而随着高通量测序技术的不断发展,生成的序列长度已由最初的36bp增加到100~150bp,一些针对短序列开发出的基于BWT索引结构的比对工具在使用回溯算法实现模糊比对时会带来候选解占用空间过大,搜索替换占用时间过长的问题。因此,一些后期开发的高通量测序比对软件普遍开始通过从序列中选取种子优先进行比对的策略来寻找整个序列在基因组上的比对位置。然而由于一般情况下种子的长度较短,在参考基因组上拥有大量的候选位置,因此或是需要耗费数倍于参考基因组大小的空间来存储这些数据或是需要相当的时间进行反复查找。为了更好的满足高通量测序序列比对的新要求,我们在BWT索引结构的基础上结合了哈希索引的策略,提出了一种基于改进索引结构的比对算法,能够很好的达到时间与空间的平衡。具体工作如下:(1)本文首先对近几年发布的,面向100~150bp长度的序列比对工具进行研究和分析,发现其内存空间需求较大的原因是所建立的哈希索引需要储存种子在参考基因组上的所有候选位置。利用BWT索引结构内存占用小的特点,我们提出将两者的优势相结合,首先建立一个关于参考基因组的BWT索引,将遍历生成的所有长度为13bp的种子序列利用BWT索引计算得到辅助数据sp,ep值。有了sp,ep值可以在任何需要的时候利用FM-Index计算出所有候选位置,而储存时只需要用两个值即可代替所有候选位置,大大减少了空间消耗。(2)在对传统的FM-Index分析过程中,发现其为了限制空间消耗,采用了采样存储的方式,这使得其在利用sp,ep值进行查找定位时存在访存次数多,计算量大的缺点,特别是候选位置规模较大时,计算耗费时间更加突出。为此我们设计了一种树形结构结合广度优先搜索的算法,优化了这一过程,大大减少了时间消耗。(3)按照下游分析需要的不同,比对模式可以分为两类,找全的比对模式和找最佳的比对模式。而本文重点研究找最佳比对模式。在候选位置筛选阶段,我们提出了一种不同于种子扩展策略的新筛选方法。这种方法的不同之处有两点:1)种子长度更短数量更多,并且只做精确匹配;2)结合最优路径覆盖算法筛选出聚类后种子位置集得分较高的位置。通过实验,我们首先验证了改进的索引结构的有效性。之后,我们利用模拟数据与NCBI网站上的真实测序数据在相同的实验环境下对所提出的优化算法与现有的一些主流比对算法进行了比较与评估。实验结果表明本文能在较小空间需求下更好的满足中长序列比对的需要,同时在时间效率上有所提高,并且获得了较为满意的比对结果。