.png){kind=icon}
返回
Fast de Bruijn Graph Compaction in Distributed Memory Environments
.png){kind=icon}
OA
AI
DOI：10.1109/TCBB.2018.2858797.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
De Bruijn graph based genome assembly has gained popularity as short read sequencers become ubiquitous. A core assembly operation is the generation of unitigs, which are sequences corresponding to chains in the graph. Unitigs are used as building blocks for generating longer sequences in many assemblers, and can facilitate graph compression. Chain compaction, by which unitigs are generated, remains a critical computational task. In this paper, we present a distributed memory parallel algorithm for simultaneous compaction of all chains in bi-directed de Bruijn graphs. The key advantages of our algorithm include bounding the chain compaction run-time to logarithmic number of iterations in the length of the longest chain, and ability to differentiate cycles from chains within logarithmic number of iterations in the length of the longest cycle. Our algorithm scales to thousands of computational cores, and can compact a whole genome de Bruijn graph from a human sequence read set in 7.3 seconds using 7680 distributed memory cores, and in 12.9 minutes using 64 shared memory cores. It is 3.7 x and 2.0x faster than equivalent steps in the state-of-the-art tools for distributed and shared memory environments, respectively. An implementation of the algorithm is available at https://github.com/ParBLiSS/bruno.
Keyword:
De Bruijn graph
genome assembly
graph compaction
parallel algorithms
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
I
IF:
3.4
论文数:
3.3K
被引数:
6.4K
机构
引用论文
分享收藏Velvet: Algorithms for de novo short read assembly using de Bruijn graphsVelvet: 使用de Bruijn图进行从头短读组装的算法.png)
GENOME RESEARCHOAAI
GENOME RESEARCHIF5.5
OAAI分享收藏GridPix: An integrated readout system for gaseous detectors with a pixel chip as anodeGridPix: 用于以像素芯片为阳极的气体探测器的集成读出系统
PREAI
分享收藏Efficient de novo assembly of large genomes using compressed data structuresGENOME RESEARCHOAAI
GENOME RESEARCHIF5.5
OAAI分享收藏
分享收藏
查看更多内容