An Efficient and Exact Algorithm for Scaffolding Contigs Using Exemplar Double-Cut-and-Join Distance

Reference-based scaffolding is an important process in chromosome-scale genome sequencing, which is to utilize a reference genome to scaffold (i.e., order and orient) the contigs generated by assembly tools for a target genome. The reference-based scaffolding was formulated as a rearrangement distance-based scaffolding problem, which is to scaffold the contigs in two given draft genomes, both containing duplicate markers and acting as references to each other, such that the rearrangement distance between the scaffolded genomes is minimized. In this work, we study this problem by considering exemplar double-cut-and-join (DCJ) distance. We show that the exemplar DCJ distance-based scaffolding problem is NP-hard and design an efficient integer linear programming (ILP)-based algorithm (denoted by EDCJ-scaffolder) to exactly solve it. We also use simulated and biological datasets to test EDCJ-scaffolder and compare its accuracy with that of another ILP-based scaffolding algorithm (denoted by EBP-scaffolder) we previously designed to solve the exemplar breakpoint distance-based scaffolding problem. Our experimental results finally show that EDCJ-scaffolder can more accurately scaffold the contigs of a draft genome as compared to EBP-scaffolder. Particularly, the sensitivity of EBP-scaffolder decreases as the rearrangement distance between target and reference genomes increases in simulated datasets, while the sensitivity of EDCJ-scaffolder remains high consistently.