title: GRASS: a generic algorithm for scaffolding next-generation sequencing assemblies.
abstract: BACKGROUND
  The increasing availability of second-generation high-throughput sequencing (HTS) technologies has sparked a growing interest in de novo genome sequencing. This in turn has fueled the need for reliable means of obtaining high-quality draft genomes from short-read sequencing data. The millions of reads usually involved in HTS experiments are first assembled into longer fragments called contigs, which are then scaffolded, i.e. ordered and oriented using additional information, to produce even longer sequences called scaffolds. Most existing scaffolders of HTS genome assemblies are not suited for using information other than paired reads to perform scaffolding. They use this limited information to construct scaffolds, often preferring scaffold length over accuracy, when faced with the tradeoff.
  
  
  RESULTS
  We present GRASS (GeneRic ASsembly Scaffolder)-a novel algorithm for scaffolding second-generation sequencing assemblies capable of using diverse information sources. GRASS offers a mixed-integer programming formulation of the contig scaffolding problem, which combines contig order, distance and orientation in a single optimization objective. The resulting optimization problem is solved using an expectation-maximization procedure and an unconstrained binary quadratic programming approximation of the original problem. We compared GRASS with existing HTS scaffolders using Illumina paired reads of three bacterial genomes. Our algorithm constructs a comparable number of scaffolds, but makes fewer errors. This result is further improved when additional data, in the form of related genome sequences, are used.
  
  
  BACKGROUND
  GRASS source code is freely available from http://code.google.com/p/tud-scaffolding/.
  
  
  BACKGROUND
  Supplementary data are available at Bioinformatics online.
authors.affiliation: The Delft Bioinformatics Lab, Department of Mediamatics, Delft University of Technology, Mekelweg 4, Delft. a.gritsenko@tudelft.nl
authors.forename: Alexey A
authors.initials: AA
authors.lastname: Gritsenko
authors.forename: Jurgen F
authors.initials: JF
authors.lastname: Nijkamp
authors.forename: Marcel J T
authors.initials: MJ
authors.lastname: Reinders
authors.forename: Dick
authors.initials: D
authors.lastname: de Ridder
mesh_terms: D000465:Algorithms; D020451:Contig Mapping; D004926:Escherichia coli / Q000235:genetics; D016680:Genome, Bacterial; D059014:High-Throughput Nucleotide Sequencing / Q000379:methods*; D044224:Pseudomonas syringae / Q000235:genetics; D017422:Sequence Analysis, DNA / Q000379:methods*; D044166:Xanthomonadaceae / Q000235:genetics