标题: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)
出版年:2013
卷:7936 LNCS
页码:397-408
DOI:10.1007/978-3-642-38768-5_36
摘要: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.
收录类别:EI;SCOPUS
Scopus被引频次:1
资源类型:会议论文;期刊论文
原文链接:https://www.scopus.com/inward/record.uri?eid=2-s2.0-84884920076&doi=10.1007%2f978-3-642-38768-5_36&partnerID=40&md5=fdd0276a6c98ffd10e8743316e74965d
TOP