An Integer Linear Programming Approach for Scaffolding Based on Exemplar Breakpoint Distance

Area of Science:

• Genomics
• Bioinformatics
• Computational Biology

Background:

• Reference-based scaffolding orders and orients genome contigs using a known reference genome.
• Genomic sequencing draft assembly presents challenges in contig ordering and orientation.
• Duplicate genes complicate genome scaffolding processes.

Purpose of the Study:

• To formulate reference-based scaffolding as an exemplar breakpoint distance (EBD) minimization problem.
• To develop an exact algorithm for solving the NP-hard EBD-based scaffolding problem.
• To evaluate the algorithm's performance, particularly considering duplicate genes.

Main Methods:

• Formulation of reference-based scaffolding as an exemplar breakpoint distance (EBD) problem.
• Development of an integer linear programming (ILP) based algorithm to solve the EBD problem.
• Experimental validation using simulated and biological datasets, comparing with alignment-based scaffolders.

Main Results:

• The ILP-based scaffolding algorithm accurately and efficiently scaffolds draft genomes using a reference.
• Accounting for duplicate genes significantly improves the accuracy of the ILP scaffolding algorithm.
• The proposed ILP algorithm demonstrates superior accuracy compared to the state-of-the-art RaGOO scaffolder on biological data.

Conclusions:

• The ILP-based approach provides an exact solution for EBD-based scaffolding.
• Duplicate genes are valuable for improving reference-based scaffolding accuracy.
• This novel method offers enhanced accuracy for genomic scaffolding, particularly in complex genomes.