title: Assembly complexity of prokaryotic genomes using short reads.
abstract: BACKGROUND
  De Bruijn graphs are a theoretical framework underlying several modern genome assembly programs, especially those that deal with very short reads. We describe an application of de Bruijn graphs to analyze the global repeat structure of prokaryotic genomes.
  
  
  RESULTS
  We provide the first survey of the repeat structure of a large number of genomes. The analysis gives an upper-bound on the performance of genome assemblers for de novo reconstruction of genomes across a wide range of read lengths. Further, we demonstrate that the majority of genes in prokaryotic genomes can be reconstructed uniquely using very short reads even if the genomes themselves cannot. The non-reconstructible genes are overwhelmingly related to mobile elements (transposons, IS elements, and prophages).
  
  
  CONCLUSIONS
  Our results improve upon previous studies on the feasibility of assembly with short reads and provide a comprehensive benchmark against which to compare the performance of the short-read assemblers currently being developed.
authors.affiliation: Department of Computer Science, Institute for Advanced Computer Studies, University of Maryland, College Park, MD, USA. carlk@cs.umd.edu
authors.forename: Carl
authors.initials: C
authors.lastname: Kingsford
authors.forename: Michael C
authors.initials: MC
authors.lastname: Schatz
authors.forename: Mihai
authors.initials: M
authors.lastname: Pop
mesh_terms: D019295:Computational Biology / Q000379:methods*; D004251:DNA Transposable Elements / Q000235:genetics; D030541:Databases, Genetic; D016678:Genome; D011387:Prokaryotic Cells; D039002:Prophages / Q000235:genetics; D017422:Sequence Analysis, DNA / Q000379:methods
chemical_list: D004251:DNA Transposable Elements