# A Three-String Approach to the Closest String Problem

Ontology type: schema:Chapter

### Chapter Info

DATE

2010

AUTHORS ABSTRACT

Given a set of n strings of length L and a radius d, the closest string problem asks for a new string tsol that is within a Hamming distance of d to each of the given strings. It is known that the problem is NP-hard and its optimization version admits a polynomial time approximation scheme (PTAS). Parameterized algorithms have been then developed to solve the problem when d is small. In this paper, with a new approach (called the 3-string approach), we first design a parameterized algorithm for binary strings that runs in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O\left(nL + nd^3 6.731^d\right)$\end{document} time, while the previous best runs in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O\left(nL + nd 8^d\right)$\end{document} time. We then extend the algorithm to arbitrary alphabet sizes, obtaining an algorithm that runs in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O \left( nL + nd 1.612^d \left( \alpha^2 +1 - 2 \alpha^{-1} + \alpha^{-2} \right) ^{3d}\right)$\end{document} time, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\alpha = \sqrt[3]{\mathstrut \sqrt{|\Sigma|-1}+1 }$\end{document}. This new time bound is better than the previous best for small alphabets, including the very important case where |Σ| = 4 (i.e., the case of DNA strings). More... »

PAGES

449-458

### Book

TITLE

Computing and Combinatorics

ISBN

978-3-642-14030-3
978-3-642-14031-0

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-14031-0_48

DOI

http://dx.doi.org/10.1007/978-3-642-14031-0_48

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1016511591

Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Information and Computing Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Computation Theory and Mathematics",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, 350-0394, Saitama, Japan",
"id": "http://www.grid.ac/institutes/grid.412773.4",
"name": [
"Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, 350-0394, Saitama, Japan"
],
"type": "Organization"
},
"familyName": "Chen",
"givenName": "Zhi-Zhong",
"id": "sg:person.015654265661.98",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "School of Computer Science, University of Waterloo, 200 University Ave. W, N2L3G1, Waterloo, ON, Canada",
"id": "http://www.grid.ac/institutes/grid.46078.3d",
"name": [
"School of Computer Science, University of Waterloo, 200 University Ave. W, N2L3G1, Waterloo, ON, Canada"
],
"type": "Organization"
},
"familyName": "Ma",
"givenName": "Bin",
"id": "sg:person.01221430663.16",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01221430663.16"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR",
"id": "http://www.grid.ac/institutes/None",
"name": [
"Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR"
],
"type": "Organization"
},
"familyName": "Wang",
"givenName": "Lusheng",
"id": "sg:person.01105113721.52",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01105113721.52"
],
"type": "Person"
}
],
"datePublished": "2010",
"datePublishedReg": "2010-01-01",
"description": "Given a set of n strings of length L and a radius d, the closest string problem asks for a new string tsol that is within a Hamming distance of d to each of the given strings. It is known that the problem is NP-hard and its optimization version admits a polynomial time approximation scheme (PTAS). Parameterized algorithms have been then developed to solve the problem when d is small. In this paper, with a new approach (called the 3-string approach), we first design a parameterized algorithm for binary strings that runs in \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$O\\left(nL + nd^3 6.731^d\\right)$\\end{document} time, while the previous best runs in \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$O\\left(nL + nd 8^d\\right)$\\end{document} time. We then extend the algorithm to arbitrary alphabet sizes, obtaining an algorithm that runs in \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$O \\left( nL + nd 1.612^d \\left( \\alpha^2 +1 - 2 \\alpha^{-1} + \\alpha^{-2} \\right) ^{3d}\\right)$\\end{document} time, where \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\alpha = \\sqrt[3]{\\mathstrut \\sqrt{|\\Sigma|-1}+1 }$\\end{document}. This new time bound is better than the previous best for small alphabets, including the very important case where |\u03a3|\u2009=\u20094 (i.e., the case of DNA strings).",
"editor": [
{
"familyName": "Thai",
"givenName": "My T.",
"type": "Person"
},
{
"familyName": "Sahni",
"givenName": "Sartaj",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-642-14031-0_48",
"inLanguage": "en",
"isAccessibleForFree": false,
"isPartOf": {
"isbn": [
"978-3-642-14030-3",
"978-3-642-14031-0"
],
"name": "Computing and Combinatorics",
"type": "Book"
},
"keywords": [
"polynomial time approximation scheme",
"string problem",
"time approximation scheme",
"Closest String Problem",
"closest string problem",
"optimization version",
"Parameterized Algorithms",
"Hamming distance",
"algorithm",
"binary strings",
"small alphabets",
"good run",
"alphabet size",
"approximation scheme",
"new approach",
"arbitrary alphabet sizes",
"strings",
"NPs",
"scheme",
"set",
"alphabet",
"important case",
"time",
"version",
"new time",
"run",
"distance",
"size",
"cases",
"length L",
"problem",
"paper",
"approach",
"Tsol"
],
"name": "A Three-String Approach to the Closest String Problem",
"pagination": "449-458",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1016511591"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-642-14031-0_48"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-642-14031-0_48",
"https://app.dimensions.ai/details/publication/pub.1016511591"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-05-20T07:48",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_435.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-642-14031-0_48"
}
]

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-14031-0_48'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-14031-0_48'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-14031-0_48'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-14031-0_48'

This table displays all metadata directly associated to this object as RDF triples.

120 TRIPLES      23 PREDICATES      61 URIs      54 LITERALS      7 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0802
3 schema:author N0e5e37dbf0cd4258b363efe5d204b45a
4 schema:datePublished 2010
5 schema:datePublishedReg 2010-01-01
6 schema:description Given a set of n strings of length L and a radius d, the closest string problem asks for a new string tsol that is within a Hamming distance of d to each of the given strings. It is known that the problem is NP-hard and its optimization version admits a polynomial time approximation scheme (PTAS). Parameterized algorithms have been then developed to solve the problem when d is small. In this paper, with a new approach (called the 3-string approach), we first design a parameterized algorithm for binary strings that runs in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O\left(nL + nd^3 6.731^d\right)$\end{document} time, while the previous best runs in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O\left(nL + nd 8^d\right)$\end{document} time. We then extend the algorithm to arbitrary alphabet sizes, obtaining an algorithm that runs in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O \left( nL + nd 1.612^d \left( \alpha^2 +1 - 2 \alpha^{-1} + \alpha^{-2} \right) ^{3d}\right)$\end{document} time, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\alpha = \sqrt[3]{\mathstrut \sqrt{|\Sigma|-1}+1 }$\end{document}. This new time bound is better than the previous best for small alphabets, including the very important case where |Σ| = 4 (i.e., the case of DNA strings).
7 schema:editor N7454eff8334d498ab90924a89bc31baf
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N7ec93ebe85cd4753b8c8ce3ffd53884f
12 schema:keywords Closest String Problem
13 Hamming distance
14 NPs
15 Parameterized Algorithms
16 Tsol
17 algorithm
18 alphabet
19 alphabet size
20 approach
21 approximation scheme
22 arbitrary alphabet sizes
23 binary strings
24 cases
25 closest string problem
26 distance
27 good run
28 important case
29 length L
30 new approach
31 new time
32 optimization version
33 paper
34 polynomial time approximation scheme
35 problem
37 run
38 scheme
39 set
40 size
41 small alphabets
42 string problem
43 strings
44 time
45 time approximation scheme
46 version
47 schema:name A Three-String Approach to the Closest String Problem
48 schema:pagination 449-458
49 schema:productId N2bd61818e7cb4cf3aa9a56205130a211
50 N2dc62fbfd666443f8564a171b928c4de
51 schema:publisher Nb02494736dd94f6faf90d8476e7cdacf
52 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016511591
53 https://doi.org/10.1007/978-3-642-14031-0_48
54 schema:sdDatePublished 2022-05-20T07:48
56 schema:sdPublisher N2d05582f5680453691dc7eec964e5b14
57 schema:url https://doi.org/10.1007/978-3-642-14031-0_48
59 sgo:sdDataset chapters
60 rdf:type schema:Chapter
61 N0135bfe069bd458ab2ba0d4c2fcc9819 schema:familyName Thai
62 schema:givenName My T.
63 rdf:type schema:Person
64 N04d0c750ba16426cbfc2ae3bb78953ac rdf:first N2bd692384110464c86263023dd68de04
65 rdf:rest rdf:nil
66 N0e5e37dbf0cd4258b363efe5d204b45a rdf:first sg:person.015654265661.98
67 rdf:rest N3b362f15111e48cdbf3bc637bcd506cd
68 N2bd61818e7cb4cf3aa9a56205130a211 schema:name doi
69 schema:value 10.1007/978-3-642-14031-0_48
70 rdf:type schema:PropertyValue
71 N2bd692384110464c86263023dd68de04 schema:familyName Sahni
72 schema:givenName Sartaj
73 rdf:type schema:Person
74 N2d05582f5680453691dc7eec964e5b14 schema:name Springer Nature - SN SciGraph project
75 rdf:type schema:Organization
76 N2dc62fbfd666443f8564a171b928c4de schema:name dimensions_id
77 schema:value pub.1016511591
78 rdf:type schema:PropertyValue
79 N3b362f15111e48cdbf3bc637bcd506cd rdf:first sg:person.01221430663.16
80 rdf:rest N86037b5d52844869a4260897e0048e68
81 N7454eff8334d498ab90924a89bc31baf rdf:first N0135bfe069bd458ab2ba0d4c2fcc9819
82 rdf:rest N04d0c750ba16426cbfc2ae3bb78953ac
83 N7ec93ebe85cd4753b8c8ce3ffd53884f schema:isbn 978-3-642-14030-3
84 978-3-642-14031-0
85 schema:name Computing and Combinatorics
86 rdf:type schema:Book
87 N86037b5d52844869a4260897e0048e68 rdf:first sg:person.01105113721.52
88 rdf:rest rdf:nil
89 Nb02494736dd94f6faf90d8476e7cdacf schema:name Springer Nature
90 rdf:type schema:Organisation
91 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
92 schema:name Information and Computing Sciences
93 rdf:type schema:DefinedTerm
94 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
95 schema:name Computation Theory and Mathematics
96 rdf:type schema:DefinedTerm
97 sg:person.01105113721.52 schema:affiliation grid-institutes:None
98 schema:familyName Wang
99 schema:givenName Lusheng
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01105113721.52
101 rdf:type schema:Person
102 sg:person.01221430663.16 schema:affiliation grid-institutes:grid.46078.3d
103 schema:familyName Ma
104 schema:givenName Bin
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01221430663.16
106 rdf:type schema:Person
107 sg:person.015654265661.98 schema:affiliation grid-institutes:grid.412773.4
108 schema:familyName Chen
109 schema:givenName Zhi-Zhong
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98
111 rdf:type schema:Person
112 grid-institutes:None schema:alternateName Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR
113 schema:name Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR
114 rdf:type schema:Organization
115 grid-institutes:grid.412773.4 schema:alternateName Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, 350-0394, Saitama, Japan
116 schema:name Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, 350-0394, Saitama, Japan
117 rdf:type schema:Organization
118 grid-institutes:grid.46078.3d schema:alternateName School of Computer Science, University of Waterloo, 200 University Ave. W, N2L3G1, Waterloo, ON, Canada
119 schema:name School of Computer Science, University of Waterloo, 200 University Ave. W, N2L3G1, Waterloo, ON, Canada
120 rdf:type schema:Organization