使用分布式debruijn图遍历基因拼接并行构建和化简

目前基因拼接软件中应用最广泛的技术是基于debruijn图的基因拼接算法，需要对长达数十亿bp长度的基因组测序数据进行处理.针对海量的基因测序数据，快速、高效和可扩展的基因拼接算法非常重要.虽然已出现一些并行拼接算法（如yaga）开始研究这些问题，但是拼接过程中时间、空间消耗较大的构图和单链化简这两大步骤在海量数据的挑战下仍然是最主要的计算瓶颈.这是因为现有工作在处理这几个步骤时通常使用了并行的表排序（listranking），而该方法需要多次对debruijn图的海量顶点信息进行分布式的排序，产生了大量的计算节点间的通信.单链化简可由1次debruijn图深度优先遍历完成而不再需要表排序，于是提出一种基于分布式海量图遍历方法对单链化简进行优化，极大地减少了处理器间的通信和计算节点之间的数据移动，因而取得较好的扩展性，其算法复杂度为o（g/p），通信复杂度为o（g），这里g为参考序列的长度，p为处理器的核数.当对e.coli和yeast数据集进行测试，处理器的核数从8个增加到512个时，算法可以得到13倍和10倍的加速比;当对c.elegans和人类1号染色体（chr1）数据集进行测试，处理器的核数从32个增加到512个时，算法可以得到7倍和10倍的加速比.