On the k-closest substring and k-consensus pattern problems
文献类型：期刊论文
| 作者 | Jiao, YS; Xu, JY; Li, M |
| 刊名 | COMBINATORIAL PATTERN MATCHING, PROCEEDINGS
 |
| 出版日期 | 2004 |
| 卷号 | 3109页码:130-144 |
| 关键词 | k-center problems closest string and substrings consensus pattern polynomial time approximation scheme |
| ISSN号 | 0302-9743 |
| 英文摘要 | 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. |
| WOS研究方向 | Computer Science |
| 语种 | 英语 |
| WOS记录号 | WOS:000222627600010 |
| 出版者 | SPRINGER-VERLAG BERLIN |
| 源URL | [http://119.78.100.204/handle/2XEOYT63/13799]  |
| 专题 | 中国科学院计算技术研究所期刊论文_英文 |
| 通讯作者 | 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. |
入库方式： OAI收割
来源：计算技术研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。