title: Readjoiner: a fast and memory efficient string graph-based sequence assembler.
abstract: BACKGROUND
  Ongoing improvements in throughput of the next-generation sequencing technologies challenge the current generation of de novo sequence assemblers. Most recent sequence assemblers are based on the construction of a de Bruijn graph. An alternative framework of growing interest is the assembly string graph, not necessitating a division of the reads into k-mers, but requiring fast algorithms for the computation of suffix-prefix matches among all pairs of reads.
  
  
  RESULTS
  Here we present efficient methods for the construction of a string graph from a set of sequencing reads. Our approach employs suffix sorting and scanning methods to compute suffix-prefix matches. Transitive edges are recognized and eliminated early in the process and the graph is efficiently constructed including irreducible edges only.
  
  
  CONCLUSIONS
  Our suffix-prefix match determination and string graph construction algorithms have been implemented in the software package Readjoiner. Comparison with existing string graph-based assemblers shows that Readjoiner is faster and more space efficient. Readjoiner is available at http://www.zbh.uni-hamburg.de/readjoiner.
authors.affiliation: Center for Bioinformatics, University of Hamburg, Bundesstrasse 43, 20146 Hamburg, Germany.
authors.forename: Giorgio
authors.initials: G
authors.lastname: Gonnella
authors.forename: Stefan
authors.initials: S
authors.lastname: Kurtz
mesh_terms: D000465:Algorithms; D003198:Computer Simulation; D015894:Genome, Human / Q000235:genetics; D006801:Humans; D008957:Models, Genetic; D017422:Sequence Analysis, DNA / Q000379:methods; D012984:Software