基于分布De Bruijn图遍历的基因拼接算法的并行构建和化简方法
(0) 目前基因拼接软件中应用最广泛的技术是基于De Bruijn图的基因拼接算法.随着第二代基因测序仪的大量使用和基因测序在工业中的广泛应用,常常需要对长达数十亿bp长度的基因组测序数据进行处理.针对海量的基因测序数据,快速、高效和可扩展的基因拼接算法变得非常重要.虽然已出现了一些并行拼接算法,如YAGA,开始研究这些问题,但是拼接过程中时间空间消耗较大的构图和单链化简这两大步骤在海量数据的挑战下仍然是最主要的计算瓶颈.这是因为现有工作在处理这几个步骤时通常使用了并行的表排序(list ranking),而该方法需要多次对De Bruijn图的海量顶点信息作分布式的排序,产生了大量的计算顶点间的通信.发现单链化简可由一次De Bruijn图深度优先遍历完成而不再需要表排序,于是提出一种基于分布式海量图遍历方法对单链化简进行优化,极大的减少处理器间的通信和计算节点之前的数据移动,因而取得比较好的扩展性,其算法复杂度O(g),通讯复杂度为O(g),这里g为参考序列的长度.用Yeast和C.elegans数据集对算法进行测试,当处理器的核数从8个增加到128个时,该算法可以得到10倍的加速比.
基因拼接算法 并行计算 基因测序 生物信息学
ZENG Li 曾理 CHENG Jie-Feng 成杰峰 MENG Jin-Tao 孟金涛 TU Zhi-Bing 涂志兵 FENG Shen-Zhong 冯圣中
Shenzhen Institutes of Advanced Technology,Chinese Academy of Sciences,Shenzhen,518055,PR.China 中国科学院深圳先进技术研究院,广东省深圳市西丽深圳大学城 518055
国内会议
张家界
中文
1-9
2012-10-29（万方平台首次上网日期，不代表论文的发表时间）