title: SAGE: String-overlap Assembly of GEnomes.
abstract: BACKGROUND
  De novo genome assembly of next-generation sequencing data is one of the most important current problems in bioinformatics, essential in many biological applications. In spite of significant amount of work in this area, better solutions are still very much needed.
  
  
  RESULTS
  We present a new program, SAGE, for de novo genome assembly. As opposed to most assemblers, which are de Bruijn graph based, SAGE uses the string-overlap graph. SAGE builds upon great existing work on string-overlap graph and maximum likelihood assembly, bringing an important number of new ideas, such as the efficient computation of the transitive reduction of the string overlap graph, the use of (generalized) edge multiplicity statistics for more accurate estimation of read copy counts, and the improved use of mate pairs and min-cost flow for supporting edge merging. The assemblies produced by SAGE for several short and medium-size genomes compared favourably with those of existing leading assemblers.
  
  
  CONCLUSIONS
  SAGE benefits from innovations in almost every aspect of the assembly process: error correction of input reads, string-overlap graph construction, read copy counts estimation, overlap graph analysis and reduction, contig extraction, and scaffolding. We hope that these new ideas will help advance the current state-of-the-art in an essential area of research in genomics.
authors.affiliation: Department of Computer Science, University of Western Ontario, N6A 5B7 London, Ontario, Canada. ilie@csd.uwo.ca.
authors.forename: Lucian
authors.initials: L
authors.lastname: Ilie
authors.forename: Bahlul
authors.initials: B
authors.lastname: Haider
authors.forename: Michael
authors.initials: M
authors.lastname: Molnar
authors.forename: Roberto
authors.initials: R
authors.lastname: Solis-Oba
mesh_terms: D000465:Algorithms; D003196:Computer Graphics; D059646:Genome Size; D023281:Genomics / Q000379:methods*; D059014:High-Throughput Nucleotide Sequencing / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*