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

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)....

Full description

Saved in:
Bibliographic Details
Published in:Algorithms for molecular biology 2013-09, Vol.8 (1), p.22-22, Article 22
Main Authors: Chikhi, Rayan, Rizk, Guillaume
Format: Article
Language:English
Subjects:
Algorithms
Biochemistry, Molecular Biology
Genomes
Genomics
Life Sciences
Molecular biology
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1748-7188
1748-7188
DOI:10.1186/1748-7188-8-22