ScaffoldScaffolder: solving contig orientation via bidirected to directed graph reduction.

Motivation: 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.

Availability And Implementation: http://bioresearch.byu.edu/scaffoldscaffolder.

Contact: paulmbodily@gmail.com

Supplementary Information: Supplementary data are available at Bioinformatics online.