Randomized Fixed-Parameter Algorithms for the Closest String Problem View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2014-10-28

AUTHORS

Zhi-Zhong Chen, Bin Ma, Lusheng Wang

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
  • 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: 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, 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", 
            "volumeNumber": "74"
          }
        ], 
        "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", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "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"
      }
    ]
     

    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/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'

    Turtle is a human-readable linked data format.

    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
    1 sg:pub.10.1007/s00453-014-9952-y schema:about anzsrc-for:08
    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
    28 N780c3e702c0a4bf4ba0506155ecad00b
    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
    64 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    65 schema:sdPublisher N46531cfee968450383c9e5c3920224e5
    66 schema:url https://doi.org/10.1007/s00453-014-9952-y
    67 sgo:license sg:explorer/license/
    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
    78 N780c3e702c0a4bf4ba0506155ecad00b schema:volumeNumber 74
    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
     




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


    ...