论文部分内容阅读
随着高通量测序技术的快速发展以及测序成本的下降,测序得到的短读序列规模越来越大,将大量的短读序列快速且准确地比对到参考基因组序列是一个具有挑战性的问题。针对基于哈希索引的短读序列比对算法运行内存较大、精确度较低的问题,本文提出了短读序列比对算法SSFA。设计了一种轻量化的哈希索引结构,比传统的基于哈希索引的比对算法占用更少的内存空间;设计了种子分组算法以及过滤算法,提升了比对的精确度和速度,其中过滤算法包括种子选择以及候选位置过滤,具体工作如下:轻量化的哈希索引结构。传统的基于哈希索引的短读序列比对算法在构建索引时,需要将参考基因组序列每个位置生成的定长子序列以及当前的位置信息存储到哈希索引中,导致了哈希索引占用较多的内存空间。为了解决这个问题,SSFA建立了轻量化的哈希索引结构,每隔固定的步长step,存储参考基因组序列上当前位置对应的定长子序列以及当前的位置信息。在构建的轻量化哈希索引结构中,使用键值表编码存储定长子序列,位置表存储子序列对应的位置信息。种子分组和过滤算法。为了处理轻量化的哈希索引缺失部分参考基因组序列位置信息的问题,在短读比对的过程中,本文提出了种子分组和过滤算法。首先,利用种子分组算法将短读序列生成的所有种子根据其在短读序列中的位置分为step个种子集合。然后,利用过滤算法对每个种子集合进行过滤得到短读序列所对应的候选位置。在过滤过程中,设计了基于动态规划的种子选择算法,从每个种子集合中选出d+a+1(d为汉明距离,a为额外非重叠种子的数量)个最优的非重叠种子,保证这d+a+1个非重叠的种子组合在参考基因组序列上出现频次之和最小,并通过设计的候选位置过滤算法筛掉d+a+1个种子出现在参考基因组序列上的冗余位置,将剩余的位置作为种子集合所对应的候选位置。最后,合并所有种子集合所对应的候选位置,并对合并后的所有候选位置使用Smith–Waterman算法进行比对,选出最恰当的位置作为结果输出。在NCBI上下载的真实数据集以及模拟数据集上测试了SSFA的召回率,准确率,敏感度,运行时间以及内存占用。实验结果表明,SSFA在准确率及敏感度上与主流算法相比上具有一定的优势,在召回率和运行时间上与主流算法相当,运行内存的消耗较其他基于哈希索引的比对算法减少了15%~24%。