Improved Inapproximability Gap and Approximation Algorithm for Scaffold Filling to Maximize Increased Duo-Preservations

Scaffold filling is a critical step in DNA assembly. In the scaffold filling problem, we are given a reference (complete) genome, and a scaffold composed of contigs which are matched to fix positions on the reference genome, as well as some unmatched fragments, the purpose is to insert the unmatched fragments between the contigs in the scaffold, such that the resulting genome is similar to the reference genome. Let M be a one-to-one matching between common letters of the scaffold and the reference genome. A duo-preservation is an ordered pair of consecutive letters in the scaffold, which are matched to two consecutive letters in the reference genome based on M. The problem of scaffold filling to maximize increased duo-preservations is described as: given an incomplete scaffold with some fragments missing and a reference genome, inserting the missing fragments back into the incomplete scaffold to maximize the number of increased duo-preservations between the filled scaffold and the reference genome. In [19], this problem was shown to be MAX-SNP-complete and can not be approximated within \(\frac{16263}{16262}\) . In this paper, we firstly improve the inapproximability gap to \(\frac{2363}{2362}\) , then we devise a new approximation algorithm with an approximation factor of \(\frac{3}{2} + \epsilon \) by a local search method. The running time of the approximation algorithm is \(O(n^{O(\frac{1}{\epsilon })})\) , where \(\epsilon \) is an arbitrary small constant. Finally, we apply our algorithm to simulated genomic data, yielding the average approximation factors of 1.034 for \(s=1\) and 1.030 for \(s=2\) , where s denotes the range of local search, indicating the maximum number of elements substituted in the current solution per iteration. The experimental findings show that our algorithm’s approximation factor primarily reflects a theoretical worst-case. However, practical datasets rarely encounter such extremes cases. Therefore, our approximation algorithm shows exceptional performance in real-world datasets compared with the theoretical bound.