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

摘要：

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

关键词：序列拼接、欧拉超路、并行拼接、哈希表

所属期刊栏目：29

分类号：TP301(计算技术、计算机技术)

资助基金：中国科学院资助项目60273007;60131160743;ChinaGrid项目60273007;60131160743

在线出版日期：2006-03-30（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：139-144