基因拼接是生物信息学领域研究的基础课题之一,也是一个难度较大但十分有意义的研究课题。基因拼接是指从给定的基因序列集合出发,利用计算机技术,再重新构造出该生物DNA序列的过程。新一代测序技术的出现和发展大大改变了基因研究领域并加快了生物学和医学研究的进程。新一代测序技术一次可以获得几百万条序列信息,能在短时间内完成整个基因组数据的测定,但相比于传统测序技术,成本却下将了数十倍。目前,基因研究工作面临最大的挑战是新测序的基因序列数据无法得到及时的计算和分析,后续的研究工作也无法开展。高效的基因拼接算法的研究,将对当前生物信息学的发展起到关键性的推动作用。目前基于新一代测序技术产出的短基因序列进行基因拼接的,主要有Greedy-extension, Overlap图和De Bruijn图三种方法。De Bruijn图方法需要寻找的是一条Euler路径,而Euler路径问题的时间复杂度在理想情况下是线性的。De Bruijn图方法另外一个吸引人的特性是其可以将基因中的重复区域进行收缩,并且不会产生错误的重叠。在本文中,我们使用了动态哈希技术来构建De Bruijn图。由于设计了性能良好的哈希函数及有效的解决冲突的方法,并选择了合适的装填因子,算法中哈希表的插入和查找操作的时间复杂度较低。由于在拼接过程中查找是一个频繁的操作,查找操作时间复杂度的下降,对整体性能的提高起到了很重要的作用。同时哈希表的动态扩展使得算法可以适用于不同大小的生物数据的拼接。由于生物的基因数据很大,作为拼接算法的输入,基因文件往往可以达到数百GB甚至TB级别,这样文件I/O时间在算法总时间中所占的比例会很大。为了有效的减少文件I/O的时间,本文提出了并行I/O思路。在算法的开始,基因文件会被平均的分割成更小的子文件,这些子文件又会被平均的分配给每一个进程。然后每个进程并行的读取各自的子文件,并通过进程间通信来交换彼此需要的连接信息。本文在对de bruijn图进行充分分析的基础上,在生成contig和scaffold的步骤中,同时使用了基于共享内存多线程技术和基于分布式内存的多进程技术,充分利用了分布式集群的资源。通过实际拼接三个双末端的基因数据与一个人类基因组数据,并与PASHA和ABySS两个软件作比较,可以发现我们的算法在保证了拼接质量的前提下,获得了较好的性能。当使用64个CPU核来进行实验时,我们的算法获得了将近7倍的加速比。