DNA序列拼接中欧拉超路算法的新并行策略

摘要

序列拼接是全基因组测序的核心问题之一.基于"overlap-layout-consensus"的传统拼接软件虽然被人们应用于人类基因组拼接等项目,但它们始终不能有效解决全基因组重复序列的拼装问题.为了克服上述不足,Pevzner等提出了欧拉超路拼接算法.由于该算法要求构造一个复杂的de Bruijin图,因此用欧拉超路算法拼接大规模全基因组存在存储瓶颈问题.该文对欧拉超路拼接算法做了并行化研究并付诸实现,有效解决了欧拉超路算法中的存储瓶颈问题.测试结果表明,该并行算法具有良好的可扩缩性,能够解决较大规模全基因组的序列拼接.