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