General Information
| Description | Solving contig orientation via bidirected to directed graph reduction |
| Homepage | http://bioresearch.byu.edu/scaffoldscaffolder |
Publications
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.
Related Tools
Scoring-and-unfolding trimmed tree assembler
Published November 2010
Concepts, constructs and comparisons
GRASS
Published April 2012
A generic algorithm for scaffolding next-generation sequencing assemblies
CAMPways
Published June 2013
Constrained alignment framework for the comparative analysis of a pair of metabolic pathways
SRinversion
Published August 2016
A tool for detecting short inversions by splitting and re-aligning poorly mapped and unmapped sequencing reads
FAIR Evaluation
Sorry, you must be signed in to evaluate this object.
