title: SCARPA: scaffolding reads with practical algorithms.
abstract: BACKGROUND
  Scaffolding is the process of ordering and orienting contigs produced during genome assembly. Accurate scaffolding is essential for finishing draft assemblies, as it facilitates the costly and laborious procedures needed to fill in the gaps between contigs. Conventional formulations of the scaffolding problem are intractable, and most scaffolding programs rely on heuristic or approximate solutions, with potentially exponential running time.
  
  
  RESULTS
  We present SCARPA, a novel scaffolder, which combines fixed-parameter tractable and bounded algorithms with Linear Programming to produce near-optimal scaffolds. We test SCARPA on real datasets in addition to a simulated diploid genome and compare its performance with several state-of-the-art scaffolders. We show that SCARPA produces longer or similar length scaffolds that are highly accurate compared with other scaffolders. SCARPA is also capable of detecting misassembled contigs and reports them during scaffolding.
  
  
  BACKGROUND
  SCARPA is open source and available from http://compbio.cs.toronto.edu/scarpa.
authors.affiliation: Department of Computer Science, University of Toronto, Toronto, ON, Canada M5S 3E1. nild@cs.toronto.edu
authors.forename: Nilgun
authors.initials: N
authors.lastname: Donmez
authors.forename: Michael
authors.initials: M
authors.lastname: Brudno
mesh_terms: D000465:Algorithms; D001203:Ascomycota / Q000235:genetics; D020451:Contig Mapping / Q000379:methods*; D004926:Escherichia coli / Q000235:genetics; D023281:Genomics / Q000379:methods; D059014:High-Throughput Nucleotide Sequencing; D011382:Programming, Linear; D012984:Software