title: An improved approximation algorithm for scaffold filling to maximize the common adjacencies.
abstract: Scaffold filling is a new combinatorial optimization problem in genome sequencing. The one-sided scaffold filling problem can be described as given an incomplete genome I and a complete (reference) genome G, fill the missing genes into I such that the number of common (string) adjacencies between the resulting genome I' and G is maximized. This problem is NP-complete for genome with duplicated genes and the best known approximation factor is 1.33, which uses a greedy strategy. In this paper, we prove a better lower bound of the optimal solution, and devise a new algorithm by exploiting the maximum matching method and a local improvement technique, which improves the approximation factor to 1.25. For genome with gene repetitions, this is the only known NP-complete problem which admits an approximation with a small constant factor (less than 1.5).
authors: Shandong University, Jinan.
authors: Nan
authors: N
authors: Liu
authors: Shandong University, Jinan.
authors: Haitao
authors: H
authors: Jiang
authors: Shandong University, Jinan.
authors: Daming
authors: D
authors: Zhu
authors: Montana State University, Bozeman.
authors: Binhai
authors: B
authors: Zhu
mesh_terms: D000465:Algorithms; D016678:Genome; D023281:Genomics / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*