ScaffoldScaffolder: solving contig orientation via bidirected to directed graph reduction

• DOI: 10.1093/bioinformatics/btv548
• Publication Date: 2015-09-18T08:26:51Z
• Authors: Paul M. Bodily; M. Stanley Fujimoto; Quinn Snell; Dan Ventura; Mark J. Clement
• Keywords: 0301 basic medicine; Contig Mapping; 03 medical and health sciences; Algorithms

Abstract 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: [e-mail] Supplementary information: Supplementary data are available at Bioinformatics online.