ScaffoldScaffolder: solving contig orientation via bidirected to directed graph reduction

Area of Science:

• Computational Biology
• Genomics
• Bioinformatics

Background:

• The contig orientation problem, formally defined as MAX-DIR, has been addressed with heuristics.
• This problem is crucial for genome assembly and understanding genetic variations.

Purpose of the Study:

• To formally define and prove the computational complexity of the contig orientation problem (MAX-DIR).
• To develop and evaluate a novel greedy heuristic algorithm for solving MAX-DIR.
• To identify inverted repeats and inversion variants that challenge standard assembly assumptions.

Main Methods:

• Linear-time reduction from MAX-CUT problem to MAX-DIR problem to establish NP-completeness.
• Development and comparison of a novel greedy heuristic algorithm against existing methods.
• Utilizing scaffold graphs to analyze contig orientation and identify structural variations.

Main Results:

• The MAX-DIR problem is proven to be NP-complete.
• The novel greedy heuristic algorithm demonstrates superior performance compared to other heuristics.
• A new method effectively identifies inverted repeats and inversion variants, which are often difficult to detect.
• These inversions are implicated in the genetic mechanisms of several diseases.

Conclusions:

• The MAX-DIR problem is computationally complex, necessitating efficient heuristic solutions.
• The proposed greedy algorithm offers an effective and high-performing approach for contig orientation.
• The developed method enhances the detection of genetic variations like inversions, aiding disease research.