使用分布式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). |
入库方式： OAI收割
来源：深圳先进技术研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。