Introduction

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.

Publications

  1. Exploiting sparseness in de novo genome assembly.
    Cite this
    Ye C, Ma ZS, Cannon CH, Pop M, Yu DW, 2012-01-01 - BMC bioinformatics

Credits

  1. Chengxi Ye
    Developer

  2. Zhanshan Sam Ma
    Developer

  3. Charles H Cannon
    Developer

  4. Mihai Pop
    Developer

  5. Douglas W Yu
    Investigator

Community Ratings

UsabilityEfficiencyReliabilityRated By
0 user
Sign in to rate
Summary
AccessionBT000346
Tool TypeApplication
Category
PlatformsLinux/Unix
Technologies
User InterfaceTerminal Command Line
Download Count0
Submitted ByDouglas W Yu