使用分布式De Bruijn图遍历基因拼接并行构建和化简/Parallelized De Bruijn graph construction and simplification for genome assembly

	使用分布式De Bruijn图遍历基因拼接并行构建和化简/Parallelized De Bruijn graph construction and simplification for genome assembly
	曾理; 成杰峰; 孟金涛; 涂志兵; 冯圣中
刊名	软件学报Journal of Software
	2013
英文摘要	目前基因拼接软件中应用最广泛的技术是基于De Bruijn图的基因拼接算法，需要对长达数十亿BP长度的基因组测序数据进行处理.针对海量的基因测序数据，快速、高效和可扩展的基因拼接算法非常重要.虽然已出现一些并行拼接算法（如YAGA）开始研究这些问题，但是拼接过程中时间、空间消耗较大的构图和单链化简这两大步骤在海量数据的挑战下仍然是最主要的计算瓶颈.这是因为现有工作在处理这几个步骤时通常使用了并行的表排序（list ranking），而该方法需要多次对De Bruijn图的海量顶点信息进行分布式的排序，产生了大量的计算节点间的通信.单链化简可由1次De Bruijn 图深度优先遍历完成而不再需要表排序，于是提出一种基于分布式海量图遍历方法对单链化简进行优化，极大地减少了处理器间的通信和计算节点之间的数据移动，因而取得较好的扩展性，其算法复杂度为O（g/p），通信复杂度为O（g），这里g为参考序列的长度，p为处理器的核数.当对E.coli和Yeast数据集进行测试，处理器的核数从8个增加到512个时，算法可以得到13倍和10倍的加速比;当对C.elegans和人类1号染色体（chr1）数据集进行测试，处理器的核数从32个增加到512个时，算法可以得到7倍和10倍的加速比.
收录类别	EI
原文出处	http://www.jos.org.cn/1000-9825/13032.htm
语种	中文
内容类型	期刊论文
源URL	[http://ir.siat.ac.cn:8080/handle/172644/5056]
专题	深圳先进技术研究院_数字所
作者单位	软件学报Journal of Software
推荐引用方式 GB/T 7714	曾理,成杰峰,孟金涛,等. 使用分布式De Bruijn图遍历基因拼接并行构建和化简/Parallelized De Bruijn graph construction and simplification for genome assembly[J]. 软件学报Journal of Software,2013.
APA	曾理,成杰峰,孟金涛,涂志兵,&冯圣中.(2013).使用分布式De Bruijn图遍历基因拼接并行构建和化简/Parallelized De Bruijn graph construction and simplification for genome assembly.软件学报Journal of Software.
MLA	曾理,et al."使用分布式De Bruijn图遍历基因拼接并行构建和化简/Parallelized De Bruijn graph construction and simplification for genome assembly".软件学报Journal of Software (2013).