通过区域筛选和简洁de Bruijn图比对高重复短序列

摘要

下一代测序平台产生的大量短序列（short reads）包含许多重复的子序列,这给求解短序列比对（short-read alignment）问题带来了挑战.如何处理包含重复子序列的基因组区域将影响后续基因组的分析.现有的利用de Bruijn图的短序列比对算法效果并不理想或者未考虑重复子序列的影响.针对包含许多重复子序列的短序列比对问题,依据种子预定义由给定的shape布局中生成的关键字建立hash索引,通过采用基于空位种子（gapped seeds）搜索策略的区域选择方法,通过搜索索引筛选候选位置以减少待比对的候选位置个数、减少搜索空间;运用Hough变换分组操作将种子命中聚集为粗对准形式,以降低后续比对验证时间;采用简洁de Bruijn图结构压缩存储和索引长度为k的序列片段（k-mer）,以降低比对所需的存储空间.分析与实验结果表明,与已有的代表性同类算法相比,本文的算法既保持或获得更高正确比对百分比,又降低了所需的运行时间和存储空间,尤其是对高重复率的序列进行比对,本文算法可获得更高的正确对准百分比.