title: ScaffoldScaffolder: solving contig orientation via bidirected to directed graph reduction.
abstract: BACKGROUND
  The contig orientation problem, which we formally define as the MAX-DIR problem, has at times been addressed cursorily and at times using various heuristics. In setting forth a linear-time reduction from the MAX-CUT problem to the MAX-DIR problem, we prove the latter is NP-complete. We compare the relative performance of a novel greedy approach with several other heuristic solutions.
  
  
  RESULTS
  Our results suggest that our greedy heuristic algorithm not only works well but also outperforms the other algorithms due to the nature of scaffold graphs. Our results also demonstrate a novel method for identifying inverted repeats and inversion variants, both of which contradict the basic single-orientation assumption. Such inversions have previously been noted as being difficult to detect and are directly involved in the genetic mechanisms of several diseases.
  
  
  METHODS
  http://bioresearch.byu.edu/scaffoldscaffolder.
  
  
  BACKGROUND
  paulmbodily@gmail.com
  
  
  BACKGROUND
  Supplementary data are available at Bioinformatics online.
authors.affiliation: Computational Sciences Laboratory, Department of Computer Science, Brigham Young University, Provo, UT 84602-6576, USA.
authors.forename: Paul M
authors.initials: PM
authors.lastname: Bodily
authors.affiliation: Computational Sciences Laboratory, Department of Computer Science, Brigham Young University, Provo, UT 84602-6576, USA.
authors.forename: M Stanley
authors.initials: MS
authors.lastname: Fujimoto
authors.affiliation: Computational Sciences Laboratory, Department of Computer Science, Brigham Young University, Provo, UT 84602-6576, USA.
authors.forename: Quinn
authors.initials: Q
authors.lastname: Snell
authors.affiliation: Computational Sciences Laboratory, Department of Computer Science, Brigham Young University, Provo, UT 84602-6576, USA.
authors.forename: Dan
authors.initials: D
authors.lastname: Ventura
authors.affiliation: Computational Sciences Laboratory, Department of Computer Science, Brigham Young University, Provo, UT 84602-6576, USA.
authors.forename: Mark J
authors.initials: MJ
authors.lastname: Clement
mesh_terms: D000465:Algorithms; D020451:Contig Mapping / Q000379:methods*