Introduction

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.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.http://bioresearch.byu.edu/scaffoldscaffolder.paulmbodily@gmail.comSupplementary data are available at Bioinformatics online.

Publications

  1. ScaffoldScaffolder: solving contig orientation via bidirected to directed graph reduction.
    Cite this
    Bodily PM, Fujimoto MS, Snell Q, Ventura D, Clement MJ, 2016-01-01 - Bioinformatics (Oxford, England)

Credits

  1. Paul M Bodily
    Developer

    Computational Sciences Laboratory, Department of Computer Science, United States of America

  2. M Stanley Fujimoto
    Developer

    Computational Sciences Laboratory, Department of Computer Science, United States of America

  3. Quinn Snell
    Developer

    Computational Sciences Laboratory, Department of Computer Science, United States of America

  4. Dan Ventura
    Developer

    Computational Sciences Laboratory, Department of Computer Science, United States of America

  5. Mark J Clement
    Investigator

    Computational Sciences Laboratory, Department of Computer Science, United States of America

Community Ratings

UsabilityEfficiencyReliabilityRated By
0 user
Sign in to rate
Summary
AccessionBT006417
Tool TypeApplication
Category
PlatformsLinux/Unix
Technologies
User InterfaceTerminal Command Line
Download Count0
Country/RegionUnited States of America
Submitted ByMark J Clement