On the k-closest substring and k-consensus pattern problems

	On the k-closest substring and k-consensus pattern problems
	Jiao, YS; Xu, JY; Li, M
	2004
发表期刊	COMBINATORIAL PATTERN MATCHING, PROCEEDINGS
ISSN	0302-9743
卷号	3109 页码:130-144
摘要	Given a set S = {s(1), s(2), ..., s(n)} of strings each of length m, and an integer L, we study the following two problems. k-CLOSEST SUBSTRING problem: find k center strings c(1), c(2), ..., c(k) of length L minimizing d such that for each s(j) is an element of S, there is a length-L substring t(j) (closest substring) of s(j) with min(1less than or equal toiless than or equal tok) d(c(i), t(j)) less than or equal to d. We give a PTAS for this problem, for k = O(1). k-CONSENSUS PATTERN problem: find k median strings c(1), c(2), ..., c(k) of length L and a substring tj (consensus pattern) of length L from each s(j) minimizing the total cost w = Sigma(j=1)(n) min(1less than or equal toiless than or equal tok) d(c(i), t(j)). We give a PTAS for this problem, for k = O(1). Our results improve recent results of [10] and [16] both of which depended on the random linear transformation technique in [16]. As for general k case, we give an alternative and direct proof of the NP-hardness of (2-epsilon)-approximation of the HAMMING RADIUS k-CLUSTERING problem, a special case of the k-CLOSEST SUBSTRING problem restricted to L = m.
关键词	k-center problems closest string and substrings consensus pattern polynomial time approximation scheme
收录类别	SCI
语种	英语
WOS研究方向	Computer Science
WOS类目	Computer Science, Theory & Methods
WOS记录号	WOS:000222627600010
出版者	SPRINGER-VERLAG BERLIN
引用统计	被引频次：10[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/13800
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Jiao, YS
作者单位	Chinese Acad Sci, Bioinformat Lab, Comp Technol Inst, Beijing, Peoples R China
推荐引用方式 GB/T 7714	Jiao, YS,Xu, JY,Li, M. On the k-closest substring and k-consensus pattern problems[J]. COMBINATORIAL PATTERN MATCHING, PROCEEDINGS,2004,3109:130-144.
APA	Jiao, YS,Xu, JY,&Li, M.(2004).On the k-closest substring and k-consensus pattern problems.COMBINATORIAL PATTERN MATCHING, PROCEEDINGS,3109,130-144.
MLA	Jiao, YS,et al."On the k-closest substring and k-consensus pattern problems".COMBINATORIAL PATTERN MATCHING, PROCEEDINGS 3109(2004):130-144.