一种基于De Bruijn图的并行基因拼接方法

摘要

本发明涉及基因测序技术领域，提供了一种基于De Bruijn图的并行基因拼接方法，包括：S1、并行构建分布式De Bruijn图；S2、剔除错误路径；S3、基于深度图遍历方法对De Bruijn图进行化简；S4、合并contig，生成scaffold；S5、输出scaffold。本发明基于集群系统，并行构造De Bruijn图，解决了大基因组拼接时由于其数据量太大，传统单机串行的基因拼接算法无法构图和无法进一步处理的问题；同时，在化简过程中，进行基于深度图遍历的并行化简，图化简过程简单，并行度高，拼接速度快。

主权项

一种基于De Bruijn图的并行基因拼接方法，其特征在于，包括：S1、并行构建分布式De Bruijn图；S2、剔除错误路径；S3、基于深度图遍历方法对De Bruijn图进行化简；所述步骤S3具体包括：S31、初始化，将De Bruijn图分布存储在每个处理器的locationMap中，同时新建一个subGraphMap；S32、所有处理器并行从本地的locationMap中的端节点出发遍历单链；S33、将所有的单链进行化简；S34、判断是否有未访问的端节点，若有，返回执行步骤S32，否则，执行步骤S35；S35、图化简完成，生成contig；S4、合并contig，生成scaffold；S5、输出scaffold。