DNA序列拼接是基因组测序的核心问题之一。从1977年Sanger测序技术发明开始,到2005年第二代测序技术问世这段时间,DNA测序主要采用Sanger测序技术。Sanger测序技术测得的DNA片段长度能达到1000bp,并且准确率能够达到99.999%。Sanger测序技术得到的DNA片段通常用交叠-排列-生成一致序列算法进行拼接。 与第一代测序技术相比,第二代测序技术测得的DNA片段具有长度较短、错误率较高以及通量大等特点。针对这些序列的特点,第二代测序技术当前有三种拼接策略:贪心算法,交叠-排列-生成一致序列算法,以及基于de Bruijn图的欧拉路径算法。这三者中前两者需要计算所有DNA片段的共有序列,具有较高的时间复杂度。基于de Bruijn图的欧拉路径算法通过将read拆分为k-mer将DNA拼接问题转换为求欧拉路径问题。欧拉路径问题有线性时间算法。 本文采用欧拉路径算法作为作DNA序列拼接算法。第二代测序技术的通量很高。第二代测序技术在一次运行能产生几G字节的read数据,基于de Bruijn图欧拉拼接算法将面临空间的瓶颈。本文描述一个基于de Bruijn图的并行拼接算法,该算法通过将由read拆分产生的k-mer分布存储在多个进程的哈希表中,并对k-mer编码降低内存消耗。DNA拼接并行执行,并通过发送和接收数据包在各个拼接进程之间共享数据。实验结果表明,该并行拼接算法具有近似线性的时间复杂度与空间复杂度,因而具有良好的可扩展性,能够解决较大规模基因组的序列拼接问题。