A New Approximation Algorithm for Contig-based Genomic Scaffold Filling

Abstract Genomic Scaffold Filling problem forms an important class of problems, and has been paid lots of attention in the literature. In this paper, we study one of the Genomic Scaffold Filling problems, called One-sided-GSF-max-BC problem. The previous approximation ratio for the problem is 2. However, the ratio 2 algorithm in the literature can only deal with special instances of the problem, not really solve the One-sided-GSF-max-BC problem. In this paper, we give a new approximation algorithm for the problem. For any given instance of the One-sided-GSF-max-BC problem, auxiliary graphs are constructed based on the given instance and the relation between maximum matching in auxiliary graphs and optimal solution is studied, which results in an approximation algorithm with ratio 2.57.