Randomized and Parameterized Algorithms for the Closest String Problem View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2014

AUTHORS

Zhi-Zhong Chen , Bin Ma , Lusheng Wang

ABSTRACT

Given a set S = {s1, s2, …, sn} of strings of equal length L and an integer d, the closest string problem (CSP) requires the computation of a string s of length L such that d(s, si) ≤ d for each si ∈ S, where d(s, si) is the Hamming distance between s and si. The problem is NP-hard and has been extensively studied in the context of approximation algorithms and parameterized algorithms. Parameterized algorithms provide the most practical solutions to its real-life applications in bioinformatics. In this paper we develop the first randomized parameterized algorithms for CSP. Not only are the randomized algorithms much simpler than their deterministic counterparts, their expected-time complexities are also significantly better than the previously best known (deterministic) algorithms. More... »

PAGES

100-109

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-07566-2_11

DOI

http://dx.doi.org/10.1007/978-3-319-07566-2_11

DIMENSIONS

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


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: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "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, 350-0394, Hatoyama, Saitama, Japan", 
          "id": "http://www.grid.ac/institutes/grid.412773.4", 
          "name": [
            "Division of Information System Design, Tokyo Denki University, 350-0394, Hatoyama, 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": "2014", 
    "datePublishedReg": "2014-01-01", 
    "description": "Given a set S\u2009=\u2009{s1, s2, \u2026, sn} of strings of equal length L and an integer d, the closest string problem (CSP) requires the computation of a string s of length L such that d(s, si)\u2009\u2264\u2009d for each si\u2009\u2208\u2009S, where d(s, si) is the Hamming distance between s and si. The problem is NP-hard and has been extensively studied in the context of approximation algorithms and parameterized algorithms. Parameterized algorithms provide the most practical solutions to its real-life applications in bioinformatics. In this paper we develop the first randomized parameterized algorithms for CSP. Not only are the randomized algorithms much simpler than their deterministic counterparts, their expected-time complexities are also significantly better than the previously best known (deterministic) algorithms.", 
    "editor": [
      {
        "familyName": "Kulikov", 
        "givenName": "Alexander S.", 
        "type": "Person"
      }, 
      {
        "familyName": "Kuznetsov", 
        "givenName": "Sergei O.", 
        "type": "Person"
      }, 
      {
        "familyName": "Pevzner", 
        "givenName": "Pavel", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-07566-2_11", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-319-07565-5", 
        "978-3-319-07566-2"
      ], 
      "name": "Combinatorial Pattern Matching", 
      "type": "Book"
    }, 
    "keywords": [
      "closest string problem", 
      "Parameterized Algorithms", 
      "string problem", 
      "real-life applications", 
      "Closest String Problem", 
      "approximation algorithm", 
      "randomized algorithm", 
      "Hamming distance", 
      "algorithm", 
      "practical solution", 
      "string S", 
      "deterministic counterpart", 
      "computation", 
      "bioinformatics", 
      "complexity", 
      "NPs", 
      "applications", 
      "strings", 
      "solution", 
      "context", 
      "distance", 
      "counterparts", 
      "length L", 
      "problem", 
      "Si", 
      "S2", 
      "Sn", 
      "S1", 
      "paper"
    ], 
    "name": "Randomized and Parameterized Algorithms for the Closest String Problem", 
    "pagination": "100-109", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1025332012"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-07566-2_11"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-07566-2_11", 
      "https://app.dimensions.ai/details/publication/pub.1025332012"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:45", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_305.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-319-07566-2_11"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

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-319-07566-2_11'

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-319-07566-2_11'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-07566-2_11'

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-319-07566-2_11'


 

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

119 TRIPLES      23 PREDICATES      55 URIs      48 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-07566-2_11 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nca347a8df8644d269a727d9c7a72ab72
4 schema:datePublished 2014
5 schema:datePublishedReg 2014-01-01
6 schema:description Given a set S = {s1, s2, …, sn} of strings of equal length L and an integer d, the closest string problem (CSP) requires the computation of a string s of length L such that d(s, si) ≤ d for each si ∈ S, where d(s, si) is the Hamming distance between s and si. The problem is NP-hard and has been extensively studied in the context of approximation algorithms and parameterized algorithms. Parameterized algorithms provide the most practical solutions to its real-life applications in bioinformatics. In this paper we develop the first randomized parameterized algorithms for CSP. Not only are the randomized algorithms much simpler than their deterministic counterparts, their expected-time complexities are also significantly better than the previously best known (deterministic) algorithms.
7 schema:editor Nebd02a2f001045a5ae3800bc6fb6b423
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Ne296c022bc7c4a3a89e9710bbe394b7a
12 schema:keywords Closest String Problem
13 Hamming distance
14 NPs
15 Parameterized Algorithms
16 S1
17 S2
18 Si
19 Sn
20 algorithm
21 applications
22 approximation algorithm
23 bioinformatics
24 closest string problem
25 complexity
26 computation
27 context
28 counterparts
29 deterministic counterpart
30 distance
31 length L
32 paper
33 practical solution
34 problem
35 randomized algorithm
36 real-life applications
37 solution
38 string S
39 string problem
40 strings
41 schema:name Randomized and Parameterized Algorithms for the Closest String Problem
42 schema:pagination 100-109
43 schema:productId N3f9bb81091ad4ac299dcc5703e618273
44 Nfac97166089b44268b6bb2c8a15577ba
45 schema:publisher N8a42887fab284bc29919b451d528c93e
46 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025332012
47 https://doi.org/10.1007/978-3-319-07566-2_11
48 schema:sdDatePublished 2022-05-20T07:45
49 schema:sdLicense https://scigraph.springernature.com/explorer/license/
50 schema:sdPublisher N25bf5105c93c42f3b45fc4965b0054f6
51 schema:url https://doi.org/10.1007/978-3-319-07566-2_11
52 sgo:license sg:explorer/license/
53 sgo:sdDataset chapters
54 rdf:type schema:Chapter
55 N25bf5105c93c42f3b45fc4965b0054f6 schema:name Springer Nature - SN SciGraph project
56 rdf:type schema:Organization
57 N3f9bb81091ad4ac299dcc5703e618273 schema:name dimensions_id
58 schema:value pub.1025332012
59 rdf:type schema:PropertyValue
60 N4ad7d10653d34ac2b8c4775c9163b562 schema:familyName Kuznetsov
61 schema:givenName Sergei O.
62 rdf:type schema:Person
63 N535f3f8f8b1e41308d5e5aeed0c9ddf5 rdf:first N4ad7d10653d34ac2b8c4775c9163b562
64 rdf:rest N90a0edb6ece84368813022fcb1965f4f
65 N70920187a88c4db692818dc567beb784 schema:familyName Kulikov
66 schema:givenName Alexander S.
67 rdf:type schema:Person
68 N8a42887fab284bc29919b451d528c93e schema:name Springer Nature
69 rdf:type schema:Organisation
70 N8ff3dd8b118b4b4a93f2a3e1f14f9064 rdf:first sg:person.01105113721.52
71 rdf:rest rdf:nil
72 N90a0edb6ece84368813022fcb1965f4f rdf:first Nfe032c9eb5dc43f5bedea78b9f026026
73 rdf:rest rdf:nil
74 Nca347a8df8644d269a727d9c7a72ab72 rdf:first sg:person.015654265661.98
75 rdf:rest Ndaf70856f1134adfa92e7416699855d4
76 Ndaf70856f1134adfa92e7416699855d4 rdf:first sg:person.01221430663.16
77 rdf:rest N8ff3dd8b118b4b4a93f2a3e1f14f9064
78 Ne296c022bc7c4a3a89e9710bbe394b7a schema:isbn 978-3-319-07565-5
79 978-3-319-07566-2
80 schema:name Combinatorial Pattern Matching
81 rdf:type schema:Book
82 Nebd02a2f001045a5ae3800bc6fb6b423 rdf:first N70920187a88c4db692818dc567beb784
83 rdf:rest N535f3f8f8b1e41308d5e5aeed0c9ddf5
84 Nfac97166089b44268b6bb2c8a15577ba schema:name doi
85 schema:value 10.1007/978-3-319-07566-2_11
86 rdf:type schema:PropertyValue
87 Nfe032c9eb5dc43f5bedea78b9f026026 schema:familyName Pevzner
88 schema:givenName Pavel
89 rdf:type schema:Person
90 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
91 schema:name Information and Computing Sciences
92 rdf:type schema:DefinedTerm
93 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
94 schema:name Computation Theory and Mathematics
95 rdf:type schema:DefinedTerm
96 sg:person.01105113721.52 schema:affiliation grid-institutes:None
97 schema:familyName Wang
98 schema:givenName Lusheng
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01105113721.52
100 rdf:type schema:Person
101 sg:person.01221430663.16 schema:affiliation grid-institutes:grid.46078.3d
102 schema:familyName Ma
103 schema:givenName Bin
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01221430663.16
105 rdf:type schema:Person
106 sg:person.015654265661.98 schema:affiliation grid-institutes:grid.412773.4
107 schema:familyName Chen
108 schema:givenName Zhi-Zhong
109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98
110 rdf:type schema:Person
111 grid-institutes:None schema:alternateName Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR
112 schema:name Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR
113 rdf:type schema:Organization
114 grid-institutes:grid.412773.4 schema:alternateName Division of Information System Design, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan
115 schema:name Division of Information System Design, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan
116 rdf:type schema:Organization
117 grid-institutes:grid.46078.3d schema:alternateName School of Computer Science, University of Waterloo, 200 University Ave. W, N2L3G1, Waterloo, ON, Canada
118 schema:name School of Computer Science, University of Waterloo, 200 University Ave. W, N2L3G1, Waterloo, ON, Canada
119 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...