title: Exploiting sparseness in de novo genome assembly.
abstract: BACKGROUND
  The very large memory requirements for the construction of assembly graphs for de novo genome assembly limit current algorithms to super-computing environments.
  
  
  METHODS
  In this paper, we demonstrate that constructing a sparse assembly graph which stores only a small fraction of the observed k-mers as nodes and the links between these nodes allows the de novo assembly of even moderately-sized genomes (~500 M) on a typical laptop computer.
  
  
  RESULTS
  We implement this sparse graph concept in a proof-of-principle software package, SparseAssembler, utilizing a new sparse k-mer graph structure evolved from the de Bruijn graph. We test our SparseAssembler with both simulated and real data, achieving ~90% memory savings and retaining high assembly accuracy, without sacrificing speed in comparison to existing de novo assemblers.
authors.affiliation: Ecology & Evolution of Plant-Animal Interaction Group, Xishuangbanna Tropical Botanic Garden, Chinese Academy of Sciences, Menglun, Yunnan 666303 China. cxy@umd.edu
authors.forename: Chengxi
authors.initials: C
authors.lastname: Ye
authors.forename: Zhanshan Sam
authors.initials: ZS
authors.lastname: Ma
authors.forename: Charles H
authors.initials: CH
authors.lastname: Cannon
authors.forename: Mihai
authors.initials: M
authors.lastname: Pop
authors.forename: Douglas W
authors.initials: DW
authors.lastname: Yu
mesh_terms: D000465:Algorithms; D016248:Computer Storage Devices; D004926:Escherichia coli / Q000235:genetics; D016678:Genome; D015894:Genome, Human; D059014:High-Throughput Nucleotide Sequencing; D006801:Humans; D017422:Sequence Analysis, DNA; D012984:Software