标题：An improved approximation algorithm for scaffold filling to maximize the common adjacencies
作者：Liu, Nan ;Jiang, Haitao ;Zhu, Daming ;Zhu, Binhai
作者机构：[Liu, Nan ;Jiang, Haitao ;Zhu, Daming ] School of Computer Science and Technology, Shandong University, Jinan, China;[Jiang, Haitao ] School of Mathem 更多
会议名称：19th International Computing and Combinatorics Conference, COCOON 2013
会议日期：21 June 2013 through 21 June 2013
来源：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
摘要：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. © 2013 Springer-Verlag Berlin Heidelberg.