title: Fast scaffolding with small independent mixed integer programs.
abstract: BACKGROUND
  Assembling genomes from short read data has become increasingly popular, but the problem remains computationally challenging especially for larger genomes. We study the scaffolding phase of sequence assembly where preassembled contigs are ordered based on mate pair data.
  
  
  RESULTS
  We present MIP Scaffolder that divides the scaffolding problem into smaller subproblems and solves these with mixed integer programming. The scaffolding problem can be represented as a graph and the biconnected components of this graph can be solved independently. We present a technique for restricting the size of these subproblems so that they can be solved accurately with mixed integer programming. We compare MIP Scaffolder to two state of the art methods, SOPRA and SSPACE. MIP Scaffolder is fast and produces better or as good scaffolds as its competitors on large genomes.
  
  
  BACKGROUND
  The source code of MIP Scaffolder is freely available at http://www.cs.helsinki.fi/u/lmsalmel/mip-scaffolder/.
  
  
  BACKGROUND
  leena.salmela@cs.helsinki.fi.
authors: Department of Computer Science, Helsinki Institute for Information Technology, University of Helsinki, Helsinki, Finland. leena.salmela@cs.helsinki.fi
authors: Leena
authors: L
authors: Salmela
authors: Veli
authors: V
authors: Mäkinen
authors: Niko
authors: N
authors: Välimäki
authors: Johannes
authors: J
authors: Ylinen
authors: Esko
authors: E
authors: Ukkonen
mesh_terms: D000465:Algorithms; D000818:Animals; D017173:Caenorhabditis elegans / Q000235:genetics; D004926:Escherichia coli / Q000235:genetics; D016678:Genome; D059014:High-Throughput Nucleotide Sequencing; D044224:Pseudomonas syringae / Q000235:genetics; D017422:Sequence Analysis, DNA / Q000379:methods*; D012984:Software