Chikhi Rayan, Rizk Guillaume
Computer Science department, ENS Cachan / IRISA / INRIA, Rennes 35042, France.
Algorithms Mol Biol. 2013 Sep 16;8(1):22. doi: 10.1186/1748-7188-8-22.
The de Bruijn graph data structure is widely used in next-generation sequencing (NGS). Many programs, e.g. de novo assemblers, rely on in-memory representation of this graph. However, current techniques for representing the de Bruijn graph of a human genome require a large amount of memory (≥30 GB).
We propose a new encoding of the de Bruijn graph, which occupies an order of magnitude less space than current representations. The encoding is based on a Bloom filter, with an additional structure to remove critical false positives.
An assembly software implementing this structure, Minia, performed a complete de novo assembly of human genome short reads using 5.7 GB of memory in 23 hours.
德布鲁因图数据结构在下一代测序（NGS）中被广泛使用。许多程序，例如从头组装器，依赖于该图的内存表示。然而，目前用于表示人类基因组德布鲁因图的技术需要大量内存（≥30GB）。
我们提出了一种新的德布鲁因图编码方式，其占用的空间比当前表示方式少一个数量级。该编码基于布隆过滤器，并带有一个额外的结构来消除关键的误报。
一个实现这种结构的组装软件Minia，在23小时内使用5.7GB内存完成了人类基因组短读长的完整从头组装。
