title: Space-efficient and exact de Bruijn graph representation based on a Bloom filter.
abstract: 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.
authors.affiliation: Computer Science department, ENS Cachan / IRISA / INRIA, Rennes 35042, France. chikhi@irisa.fr.
authors.forename: Rayan
authors.initials: R
authors.lastname: Chikhi
authors.forename: Guillaume
authors.initials: G
authors.lastname: Rizk
references.citation: PLoS One. 2011 May 11;6(5):e19816
references.pmid: 21589938
references.citation: BMC Bioinformatics. 2010 Jan 12;11:21
references.pmid: 20064276
references.citation: Proc Natl Acad Sci U S A. 2012 Aug 14;109(33):13272-7
references.pmid: 22847406
references.citation: J Comput Biol. 1995 Summer;2(2):291-306
references.pmid: 7497130
references.citation: BMC Bioinformatics. 2012 Mar 23;13:48
references.pmid: 22443449
references.citation: Bioinformatics. 2013 Mar 1;29(5):652-3
references.pmid: 23325618
references.citation: Genome Res. 2010 Feb;20(2):265-72
references.pmid: 20019144
references.citation: Bioinformatics. 2011 Jul 1;27(13):i94-101
references.pmid: 21685107
references.citation: Bioinformatics. 2010 Oct 15;26(20):2534-40
references.pmid: 20739310
references.citation: BMC Bioinformatics. 2012 Apr 19;13 Suppl 6:S5
references.pmid: 22537044
references.citation: Nat Biotechnol. 2011 May 15;29(7):644-52
references.pmid: 21572440
references.citation: BMC Bioinformatics. 2012 Apr 19;13 Suppl 6:S1
references.pmid: 22537038
references.citation: Bioinformatics. 2011 Mar 15;27(6):764-70
references.pmid: 21217122
references.citation: Bioinformatics. 2011 Feb 15;27(4):479-86
references.pmid: 21245053
references.citation: Nat Genet. 2012 Jan 08;44(2):226-32
references.pmid: 22231483
references.citation: Genome Res. 2012 Mar;22(3):557-67
references.pmid: 22147368
references.citation: Genome Res. 2009 Jun;19(6):1117-23
references.pmid: 19251739
references.citation: Genomics. 2010 Jun;95(6):315-27
references.pmid: 20211242