Chikhi Rayan, Limasset Antoine, Jackman Shaun, Simpson Jared T, Medvedev Paul
1 Department of Computer Science and Engineering, The Pennsylvania State University , State College, Pennsylvania.
J Comput Biol. 2015 May;22(5):336-52. doi: 10.1089/cmb.2014.0160. Epub 2015 Jan 28.
The de Bruijn graph plays an important role in bioinformatics, especially in the context of de novo assembly. However, the representation of the de Bruijn graph in memory is a computational bottleneck for many assemblers. Recent papers proposed a navigational data structure approach in order to improve memory usage. We prove several theoretical space lower bounds to show the limitations of these types of approaches. We further design and implement a general data structure (dbgfm) and demonstrate its use on a human whole-genome dataset, achieving space usage of 1.5 GB and a 46% improvement over previous approaches. As part of dbgfm, we develop the notion of frequency-based minimizers and show how it can be used to enumerate all maximal simple paths of the de Bruijn graph using only 43 MB of memory. Finally, we demonstrate that our approach can be integrated into an existing assembler by modifying the ABySS software to use dbgfm.
德布鲁因图在生物信息学中起着重要作用，尤其是在从头组装的背景下。然而，德布鲁因图在内存中的表示对于许多组装器来说是一个计算瓶颈。最近的论文提出了一种导航数据结构方法，以提高内存使用效率。我们证明了几个理论空间下限，以展示这些类型方法的局限性。我们进一步设计并实现了一种通用数据结构（dbgfm），并在人类全基因组数据集上展示了它的使用情况，实现了1.5GB的空间使用量，比以前的方法提高了46%。作为dbgfm的一部分，我们提出了基于频率的最小化器的概念，并展示了如何仅使用43MB的内存来枚举德布鲁因图的所有最大简单路径。最后，我们证明了我们的方法可以通过修改ABySS软件以使用dbgfm集成到现有的组装器中。
