A 2.57-Approximation Algorithm for Contig-Based Genomic Scaffold Filling

摘要

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 problem, called One-sided-GSF-max-BC problem. The previous approximation ratio for the problem is 2. However, as we pointed out in the introduction part, 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 an approximation algorithm of ratio 2.57 for the One-sided-GSF-max-BC problem. Our method is based on auxiliary graphs constructed and two applications of finding maximum matching in auxiliary graphs.