# Randomized Fixed-Parameter Algorithms for the Closest String Problem

Ontology type: schema:ScholarlyArticle

### Article Info

DATE

2014-10-28

AUTHORS ABSTRACT

Given a set S={s1,s2,…,sn}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$S = \{s_1, s_2, \ldots , s_n\}$$\end{document} of strings of equal length L\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L$$\end{document} and an integer d\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$d$$\end{document}, the closest string problem (CSP) requires the computation of a string s\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$s$$\end{document} of length L\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L$$\end{document} such that d(s,si)≤d\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$d(s, s_i) \le d$$\end{document} for each si∈S\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$s_i \in S$$\end{document}, where d(s,si)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$d(s, s_i)$$\end{document} is the Hamming distance between s\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$s$$\end{document} and si\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$s_i$$\end{document}. The problem is NP-hard and has been extensively studied in the context of approximation algorithms and fixed-parameter algorithms. Fixed-parameter algorithms provide the most practical solutions to its real-life applications in bioinformatics. In this paper we develop the first randomized fixed-parameter algorithms for CSP. Not only are the randomized algorithms much simpler than their deterministic counterparts, their time complexities are also significantly better than the previously best known (deterministic) algorithms. More... »

PAGES

466-484

### References to SciGraph publications

• 2003-09. Fixed-Parameter Algorithms for CLOSEST STRING and Related Problems in ALGORITHMICA
• 2012. Randomized Techniques for Parameterized Algorithms in PARAMETERIZED AND EXACT COMPUTATION
• 2009. Detecting Motifs in a Large Data Set: Applying Probabilistic Insights to Motif Finding in BIOINFORMATICS AND COMPUTATIONAL BIOLOGY
• 2010. Swiftly Computing Center Strings in ALGORITHMS IN BIOINFORMATICS
• 2006-12-12. Degenerated primer design to amplify the heavy chain variable region from immunoglobulin cDNA in BMC BIOINFORMATICS
• 2013. Random Methods for Parameterized Problems in COMPUTING AND COMBINATORICS
• 2003. Complexity of Approximating Closest Substring Problems in FUNDAMENTALS OF COMPUTATION THEORY
• 2003. On Exact and Approximation Algorithms for Distinguishing Substring Selection in FUNDAMENTALS OF COMPUTATION THEORY
• 1997. A linear-time algorithm for the 1-mismatch problem in ALGORITHMS AND DATA STRUCTURES
• 2006-04. On The Parameterized Intractability Of Motif Search Problems* in COMBINATORICA
• 2009. Efficient Algorithms for the Closest String and Distinguishing String Selection Problems in FRONTIERS IN ALGORITHMICS
• 1997-04. On covering problems of codes in THEORY OF COMPUTING SYSTEMS
• 2006. Space and Time Efficient Algorithms for Planted Motif Search in COMPUTATIONAL SCIENCE – ICCS 2006
• 1997. Banishing bias from consensus sequences in COMBINATORIAL PATTERN MATCHING
• 2004. On the k-Closest Substring and k-Consensus Pattern Problems in COMBINATORIAL PATTERN MATCHING
• 2008-06-28. Improved Parameterized Set Splitting Algorithms: A Probabilistic Approach in ALGORITHMICA
• 2003-05-27. Complexities of the Centre and Median String Problems in COMBINATORIAL PATTERN MATCHING

TITLE

Algorithmica

ISSUE

1

VOLUME

74

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00453-014-9952-y

DOI

http://dx.doi.org/10.1007/s00453-014-9952-y

DIMENSIONS

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

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": "Division of Information System Design, Tokyo Denki University, Ishizaka, Hatoyama, Hiki, 350-0394, Saitama, Japan",
"id": "http://www.grid.ac/institutes/grid.412773.4",
"name": [
"Division of Information System Design, Tokyo Denki University, Ishizaka, Hatoyama, Hiki, 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"
}
],
"citation": [
{
"id": "sg:pub.10.1007/978-3-540-45077-1_20",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1002242230",
"https://doi.org/10.1007/978-3-540-45077-1_20"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-44888-8_23",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1021657463",
"https://doi.org/10.1007/3-540-44888-8_23"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-15294-8_27",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1047167366",
"https://doi.org/10.1007/978-3-642-15294-8_27"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-33293-7_2",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1047655748",
"https://doi.org/10.1007/978-3-642-33293-7_2"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf02679443",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1037262625",
"https://doi.org/10.1007/bf02679443"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00453-008-9206-y",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1001366050",
"https://doi.org/10.1007/s00453-008-9206-y"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11758525_110",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1005767417",
"https://doi.org/10.1007/11758525_110"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-27801-6_10",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1042631196",
"https://doi.org/10.1007/978-3-540-27801-6_10"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00453-003-1028-3",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1033688536",
"https://doi.org/10.1007/s00453-003-1028-3"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-63307-3_53",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1032079776",
"https://doi.org/10.1007/3-540-63307-3_53"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-63220-4_63",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1040283480",
"https://doi.org/10.1007/3-540-63220-4_63"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1186/1471-2105-7-s4-s9",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1018157902",
"https://doi.org/10.1186/1471-2105-7-s4-s9"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-00727-9_15",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1048272489",
"https://doi.org/10.1007/978-3-642-00727-9_15"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-02270-8_27",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1004246225",
"https://doi.org/10.1007/978-3-642-02270-8_27"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00493-006-0011-4",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1001598984",
"https://doi.org/10.1007/s00493-006-0011-4"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-38768-5_10",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1030734749",
"https://doi.org/10.1007/978-3-642-38768-5_10"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-45077-1_19",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1039167877",
"https://doi.org/10.1007/978-3-540-45077-1_19"
],
"type": "CreativeWork"
}
],
"datePublished": "2014-10-28",
"datePublishedReg": "2014-10-28",
"description": "Given a set S={s1,s2,\u2026,sn}\\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}$$S = \\{s_1, s_2, \\ldots , s_n\\}$$\\end{document} of strings of equal length L\\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}$$L$$\\end{document} and an integer d\\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}$$d$$\\end{document}, the closest string problem (CSP) requires the computation of a string s\\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}$$s$$\\end{document} of length L\\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}$$L$$\\end{document} such that d(s,si)\u2264d\\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}$$d(s, s_i) \\le d$$\\end{document} for each si\u2208S\\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}$$s_i \\in S$$\\end{document}, where d(s,si)\\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}$$d(s, s_i)$$\\end{document} is the Hamming distance between s\\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}$$s$$\\end{document} and si\\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}$$s_i$$\\end{document}. The problem is NP-hard and has been extensively studied in the context of approximation algorithms and fixed-parameter algorithms. Fixed-parameter algorithms provide the most practical solutions to its real-life applications in bioinformatics. In this paper we develop the first randomized fixed-parameter algorithms for CSP. Not only are the randomized algorithms much simpler than their deterministic counterparts, their time complexities are also significantly better than the previously best known (deterministic) algorithms.",
"genre": "article",
"id": "sg:pub.10.1007/s00453-014-9952-y",
"inLanguage": "en",
"isAccessibleForFree": false,
"isFundedItemOf": [
{
"id": "sg:grant.6078852",
"type": "MonetaryGrant"
},
{
"id": "sg:grant.8293592",
"type": "MonetaryGrant"
}
],
"isPartOf": [
{
"id": "sg:journal.1047644",
"issn": [
"0178-4617",
"1432-0541"
],
"name": "Algorithmica",
"publisher": "Springer Nature",
"type": "Periodical"
},
{
"issueNumber": "1",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
}
],
"keywords": [
"strings",
"problem",
"context",
"real-life applications",
"equal length",
"practical solution",
"paper",
"counterparts",
"complexity",
"length",
"closest string problem",
"string problem",
"computation",
"Hamming distance",
"distance",
"NPs",
"approximation algorithm",
"algorithm",
"fixed-parameter algorithm",
"solution",
"applications",
"randomized algorithm",
"deterministic counterpart",
"time complexity",
"Fixed-Parameter Algorithms",
"Closest String Problem",
"bioinformatics"
],
"name": "Randomized Fixed-Parameter Algorithms for the Closest String Problem",
"pagination": "466-484",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1019978652"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s00453-014-9952-y"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s00453-014-9952-y",
"https://app.dimensions.ai/details/publication/pub.1019978652"
],
"sdDataset": "articles",
"sdDatePublished": "2022-05-10T10:13",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/article/article_648.jsonl",
"type": "ScholarlyArticle",
"url": "https://doi.org/10.1007/s00453-014-9952-y"
}
]

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/s00453-014-9952-y'

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/s00453-014-9952-y'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-014-9952-y'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-014-9952-y'

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

177 TRIPLES      22 PREDICATES      69 URIs      44 LITERALS      6 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0802
3 schema:author Nc6d7eaed529e41b298dd651f64a05ca5
4 schema:citation sg:pub.10.1007/11758525_110
5 sg:pub.10.1007/3-540-44888-8_23
6 sg:pub.10.1007/3-540-63220-4_63
7 sg:pub.10.1007/3-540-63307-3_53
8 sg:pub.10.1007/978-3-540-27801-6_10
9 sg:pub.10.1007/978-3-540-45077-1_19
10 sg:pub.10.1007/978-3-540-45077-1_20
11 sg:pub.10.1007/978-3-642-00727-9_15
12 sg:pub.10.1007/978-3-642-02270-8_27
13 sg:pub.10.1007/978-3-642-15294-8_27
14 sg:pub.10.1007/978-3-642-33293-7_2
15 sg:pub.10.1007/978-3-642-38768-5_10
16 sg:pub.10.1007/bf02679443
17 sg:pub.10.1007/s00453-003-1028-3
18 sg:pub.10.1007/s00453-008-9206-y
19 sg:pub.10.1007/s00493-006-0011-4
20 sg:pub.10.1186/1471-2105-7-s4-s9
21 schema:datePublished 2014-10-28
22 schema:datePublishedReg 2014-10-28
23 schema:description Given a set S={s1,s2,…,sn}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$S = \{s_1, s_2, \ldots , s_n\}$$\end{document} of strings of equal length L\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L$$\end{document} and an integer d\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$d$$\end{document}, the closest string problem (CSP) requires the computation of a string s\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$s$$\end{document} of length L\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L$$\end{document} such that d(s,si)≤d\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$d(s, s_i) \le d$$\end{document} for each si∈S\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$s_i \in S$$\end{document}, where d(s,si)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$d(s, s_i)$$\end{document} is the Hamming distance between s\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$s$$\end{document} and si\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$s_i$$\end{document}. The problem is NP-hard and has been extensively studied in the context of approximation algorithms and fixed-parameter algorithms. Fixed-parameter algorithms provide the most practical solutions to its real-life applications in bioinformatics. In this paper we develop the first randomized fixed-parameter algorithms for CSP. Not only are the randomized algorithms much simpler than their deterministic counterparts, their time complexities are also significantly better than the previously best known (deterministic) algorithms.
24 schema:genre article
25 schema:inLanguage en
26 schema:isAccessibleForFree false
27 schema:isPartOf N20e6cf7fa1a44c1e81a413ab7fb1ae8a
29 sg:journal.1047644
30 schema:keywords Closest String Problem
31 Fixed-Parameter Algorithms
32 Hamming distance
33 NPs
34 algorithm
35 applications
36 approximation algorithm
37 bioinformatics
38 closest string problem
39 complexity
40 computation
41 context
42 counterparts
43 deterministic counterpart
44 distance
45 equal length
46 fixed-parameter algorithm
47 length
48 paper
49 practical solution
50 problem
51 randomized algorithm
52 real-life applications
53 solution
54 string problem
55 strings
56 time complexity
57 schema:name Randomized Fixed-Parameter Algorithms for the Closest String Problem
58 schema:pagination 466-484
59 schema:productId N87976b9fdb4b409988948b70a3fb3b61
60 Nc8bce39bdb6642dfa638c0a2768f0d40
61 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019978652
62 https://doi.org/10.1007/s00453-014-9952-y
63 schema:sdDatePublished 2022-05-10T10:13
65 schema:sdPublisher N46531cfee968450383c9e5c3920224e5
66 schema:url https://doi.org/10.1007/s00453-014-9952-y
68 sgo:sdDataset articles
69 rdf:type schema:ScholarlyArticle
70 N18557e58d1294aa3b2da8e29b230007f rdf:first sg:person.01221430663.16
71 rdf:rest N425e575816574fb59dc2b5c1f197f6bc
72 N20e6cf7fa1a44c1e81a413ab7fb1ae8a schema:issueNumber 1
73 rdf:type schema:PublicationIssue
74 N425e575816574fb59dc2b5c1f197f6bc rdf:first sg:person.01105113721.52
75 rdf:rest rdf:nil
76 N46531cfee968450383c9e5c3920224e5 schema:name Springer Nature - SN SciGraph project
77 rdf:type schema:Organization
79 rdf:type schema:PublicationVolume
80 N87976b9fdb4b409988948b70a3fb3b61 schema:name doi
81 schema:value 10.1007/s00453-014-9952-y
82 rdf:type schema:PropertyValue
83 Nc6d7eaed529e41b298dd651f64a05ca5 rdf:first sg:person.015654265661.98
84 rdf:rest N18557e58d1294aa3b2da8e29b230007f
85 Nc8bce39bdb6642dfa638c0a2768f0d40 schema:name dimensions_id
86 schema:value pub.1019978652
87 rdf:type schema:PropertyValue
88 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
89 schema:name Information and Computing Sciences
90 rdf:type schema:DefinedTerm
91 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
92 schema:name Computation Theory and Mathematics
93 rdf:type schema:DefinedTerm
94 sg:grant.6078852 http://pending.schema.org/fundedItem sg:pub.10.1007/s00453-014-9952-y
95 rdf:type schema:MonetaryGrant
96 sg:grant.8293592 http://pending.schema.org/fundedItem sg:pub.10.1007/s00453-014-9952-y
97 rdf:type schema:MonetaryGrant
98 sg:journal.1047644 schema:issn 0178-4617
99 1432-0541
100 schema:name Algorithmica
101 schema:publisher Springer Nature
102 rdf:type schema:Periodical
103 sg:person.01105113721.52 schema:affiliation grid-institutes:None
104 schema:familyName Wang
105 schema:givenName Lusheng
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01105113721.52
107 rdf:type schema:Person
108 sg:person.01221430663.16 schema:affiliation grid-institutes:grid.46078.3d
109 schema:familyName Ma
110 schema:givenName Bin
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01221430663.16
112 rdf:type schema:Person
113 sg:person.015654265661.98 schema:affiliation grid-institutes:grid.412773.4
114 schema:familyName Chen
115 schema:givenName Zhi-Zhong
116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98
117 rdf:type schema:Person
118 sg:pub.10.1007/11758525_110 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005767417
119 https://doi.org/10.1007/11758525_110
120 rdf:type schema:CreativeWork
121 sg:pub.10.1007/3-540-44888-8_23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021657463
122 https://doi.org/10.1007/3-540-44888-8_23
123 rdf:type schema:CreativeWork
124 sg:pub.10.1007/3-540-63220-4_63 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040283480
125 https://doi.org/10.1007/3-540-63220-4_63
126 rdf:type schema:CreativeWork
127 sg:pub.10.1007/3-540-63307-3_53 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032079776
128 https://doi.org/10.1007/3-540-63307-3_53
129 rdf:type schema:CreativeWork
130 sg:pub.10.1007/978-3-540-27801-6_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042631196
131 https://doi.org/10.1007/978-3-540-27801-6_10
132 rdf:type schema:CreativeWork
133 sg:pub.10.1007/978-3-540-45077-1_19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039167877
134 https://doi.org/10.1007/978-3-540-45077-1_19
135 rdf:type schema:CreativeWork
136 sg:pub.10.1007/978-3-540-45077-1_20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002242230
137 https://doi.org/10.1007/978-3-540-45077-1_20
138 rdf:type schema:CreativeWork
139 sg:pub.10.1007/978-3-642-00727-9_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048272489
140 https://doi.org/10.1007/978-3-642-00727-9_15
141 rdf:type schema:CreativeWork
142 sg:pub.10.1007/978-3-642-02270-8_27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004246225
143 https://doi.org/10.1007/978-3-642-02270-8_27
144 rdf:type schema:CreativeWork
145 sg:pub.10.1007/978-3-642-15294-8_27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047167366
146 https://doi.org/10.1007/978-3-642-15294-8_27
147 rdf:type schema:CreativeWork
148 sg:pub.10.1007/978-3-642-33293-7_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047655748
149 https://doi.org/10.1007/978-3-642-33293-7_2
150 rdf:type schema:CreativeWork
151 sg:pub.10.1007/978-3-642-38768-5_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030734749
152 https://doi.org/10.1007/978-3-642-38768-5_10
153 rdf:type schema:CreativeWork
154 sg:pub.10.1007/bf02679443 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037262625
155 https://doi.org/10.1007/bf02679443
156 rdf:type schema:CreativeWork
157 sg:pub.10.1007/s00453-003-1028-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033688536
158 https://doi.org/10.1007/s00453-003-1028-3
159 rdf:type schema:CreativeWork
160 sg:pub.10.1007/s00453-008-9206-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1001366050
161 https://doi.org/10.1007/s00453-008-9206-y
162 rdf:type schema:CreativeWork
163 sg:pub.10.1007/s00493-006-0011-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001598984
164 https://doi.org/10.1007/s00493-006-0011-4
165 rdf:type schema:CreativeWork
166 sg:pub.10.1186/1471-2105-7-s4-s9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018157902
167 https://doi.org/10.1186/1471-2105-7-s4-s9
168 rdf:type schema:CreativeWork
169 grid-institutes:None schema:alternateName Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR
170 schema:name Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR
171 rdf:type schema:Organization
172 grid-institutes:grid.412773.4 schema:alternateName Division of Information System Design, Tokyo Denki University, Ishizaka, Hatoyama, Hiki, 350-0394, Saitama, Japan
173 schema:name Division of Information System Design, Tokyo Denki University, Ishizaka, Hatoyama, Hiki, 350-0394, Saitama, Japan
174 rdf:type schema:Organization
175 grid-institutes:grid.46078.3d schema:alternateName School of Computer Science, University of Waterloo, 200 University Ave. W, N2L3G1, Waterloo, ON, Canada
176 schema:name School of Computer Science, University of Waterloo, 200 University Ave. W, N2L3G1, Waterloo, ON, Canada
177 rdf:type schema:Organization