Space-efficient and exact de Bruijn graph representation based on a Bloom filter

作者：Chikhi Rayan^*; Rizk Guillaume

来源：Algorithms for Molecular Biology, 2013, 8(1): 22.

DOI：10.1186/1748-7188-8-22

• de novo assembly
• de Bruijn graph
• Bloom filter

Background: 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).
Results: 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.
Conclusions: 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.

• 出版日期2013-9-16