Better Approximation Algorithms for Scaffolding Problems

Abstract

Scaffolding is one of the main stages in genome assembly. During this stage, we want to merge contigs assembled from the paired-end reads into bigger chains called scaffolds. For this purpose, the following graph-theoretical problem has been proposed: Given an edge-weighted complete graph G and a perfect matching D of G, we wish to find a Hamiltonian path P in G such that all edges of D appear in P and the total weight of edges in P but not in D is maximized. This problem is NP-hard and the previously best polynomial-time approximation algorithm for it achieves a ratio of ${\frac{1}{2}}$. In this paper, we design a new polynomial-time approximation algorithm achieving a ratio of ${\frac{5-5{\epsilon }}{9-8{\epsilon }}}$ for any constant $0< {\epsilon } < 1$. Several generalizations of the problem have also been introduced in the literature and we present polynomial-time approximation algorithms for them that achieve better approximation ratios than the previous bests. In particular, one of the algorithms answers an open question.