标题：The algorithm for the two-sided scaffold filling problem
作者：Liu, Nan ;Zhu, Daming
作者机构：[Liu, Nan ;Zhu, Daming ] School of Computer Science and Technology, Shandong University, Jinan, China;[Liu, Nan ] School of Computer Science and Techn 更多
会议名称：10th International Conference on Theory and Applications of Models of Computation, TAMC 2013
会议日期：20 May 2013 through 22 May 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 and can improve the accuracy of the sequencing results. The two-sided Scaffold Filling to Maximize the Number of String Adjacencies(SF-MNSA) problem can be described as: given two incomplete gene sequences A and B, respectively fill the missing genes into A and B such that the number of adjacencies between the resulting sequences A′ and B′ is maximized. The two-sided scaffold filling problem is NP-complete for genomes with duplicated genes and there is no effective approximation algorithm. In this paper, we propose a new version problem that symbol # is added to each end of each input sequence for any instance of two-sided SF-MNSA problem and design a polynomial algorithm for one special case of this new version problem. For any instance, we present a better lower bound of the optimal solution and devise a factor-1.5 approximation algorithm by exploiting greedy strategy. © Springer-Verlag Berlin Heidelberg 2013.