标题:Approximation and Nonapproximability for the One-Sided Scaffold Filling Problem
作者:Jiang, Haitao; Ma, Jingjing; Luan, Junfeng; Zhu, Daming
通讯作者:Jiang, Haitao
作者机构:[Jiang, Haitao; Ma, Jingjing; Luan, Junfeng; Zhu, Daming] Shandong Univ, Sch Comp Sci & Technol, Jinan 250101, Peoples R China.
会议名称:21st International Computing and Combinatorics Conference (COCOON)
会议日期:AUG 04-06, 2015
来源:COMPUTING AND COMBINATORICS
出版年:2015
卷:9198
页码:251-263
DOI:10.1007/978-3-319-21398-9_20
摘要:Scaffold filling is an interesting combinatorial optimization problem from genome sequencing. The one-sided scaffold filling problem can be stated as: given an incomplete scaffold with some genes missing and a reference scaffold, the purpose is to insert the missing genes back into the incomplete scaffold(called "filling the scaffold"), such that the number of common adjacencies between the filled scaffold and the reference scaffold is maximized. This problem is NP-hard for genome with duplicated genes, and can be approximated within 1.25 by a very complicated combinatorial method. In this paper, we firstly improve the approximation factor to 6/5 by not-oblivious local search; then we show that this problem is MAX-SNP-complete.
收录类别:CPCI-S;EI;SCOPUS
WOS核心被引频次:3
Scopus被引频次:5
资源类型:会议论文;期刊论文
原文链接:https://www.scopus.com/inward/record.uri?eid=2-s2.0-84951115027&doi=10.1007%2f978-3-319-21398-9_20&partnerID=40&md5=889e06c0fc0812de91856f52ba1a2435
TOP