Sharper Upper and Lower Bounds for an Approximation Scheme for Consensus-Pattern View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2005

AUTHORS

Broňa Brejová , Daniel G. Brown , Ian M. Harrower , Alejandro López-Ortiz , Tomáš Vinař

ABSTRACT

We present sharper upper and lower bounds for a known polynomial-time approximation scheme due to Li, Ma and Wang [7] for the Consensus-Pattern problem. This NP-hard problem is an abstraction of motif finding, a common bioinformatics discovery task. The PTAS due to Li et al. is simple, and a preliminary implementation [8] gave reasonable results in practice. However, the previously known bounds on its performance are useless when runtimes are actually manageable. Here, we present much sharper lower and upper bounds on the performance of this algorithm that partially explain why its behavior is so much better in practice than what was previously predicted in theory. We also give specific examples of instances of the problem for which the PTAS performs poorly in practice, and show that the asymptotic performance bound given in the original proof matches the behaviour of a simple variant of the algorithm on a particularly bad instance of the problem. More... »

PAGES

1-10

References to SciGraph publications

  • 1997. Theory of Sample Surveys in NONE
  • Book

    TITLE

    Combinatorial Pattern Matching

    ISBN

    978-3-540-26201-5
    978-3-540-31562-9

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/11496656_1

    DOI

    http://dx.doi.org/10.1007/11496656_1

    DIMENSIONS

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


    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/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "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"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "University of Waterloo", 
              "id": "https://www.grid.ac/institutes/grid.46078.3d", 
              "name": [
                "School of Computer Science, University of Waterloo"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Brejov\u00e1", 
            "givenName": "Bro\u0148a", 
            "id": "sg:person.0642141060.90", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0642141060.90"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Waterloo", 
              "id": "https://www.grid.ac/institutes/grid.46078.3d", 
              "name": [
                "School of Computer Science, University of Waterloo"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Brown", 
            "givenName": "Daniel G.", 
            "id": "sg:person.0642727740.54", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0642727740.54"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Waterloo", 
              "id": "https://www.grid.ac/institutes/grid.46078.3d", 
              "name": [
                "School of Computer Science, University of Waterloo"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Harrower", 
            "givenName": "Ian M.", 
            "id": "sg:person.01203526716.95", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01203526716.95"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Waterloo", 
              "id": "https://www.grid.ac/institutes/grid.46078.3d", 
              "name": [
                "School of Computer Science, University of Waterloo"
              ], 
              "type": "Organization"
            }, 
            "familyName": "L\u00f3pez-Ortiz", 
            "givenName": "Alejandro", 
            "id": "sg:person.011531402673.02", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011531402673.02"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Waterloo", 
              "id": "https://www.grid.ac/institutes/grid.46078.3d", 
              "name": [
                "School of Computer Science, University of Waterloo"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Vina\u0159", 
            "givenName": "Tom\u00e1\u0161", 
            "id": "sg:person.01041305251.67", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01041305251.67"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1145/369133.369172", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018080948"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/369133.369172", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018080948"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1006/jcss.2002.1823", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024001192"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1093/bioinformatics/15.7.563", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030639875"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1093/bioinformatics/18.10.1382", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046206875"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1093/bioinformatics/18.10.1374", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048043849"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1126/science.8211139", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062653653"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://app.dimensions.ai/details/publication/pub.1082424111", 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4899-2885-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1109705819", 
              "https://doi.org/10.1007/978-1-4899-2885-6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4899-2885-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1109705819", 
              "https://doi.org/10.1007/978-1-4899-2885-6"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2005", 
        "datePublishedReg": "2005-01-01", 
        "description": "We present sharper upper and lower bounds for a known polynomial-time approximation scheme due to Li, Ma and Wang [7] for the Consensus-Pattern problem. This NP-hard problem is an abstraction of motif finding, a common bioinformatics discovery task. The PTAS due to Li et al. is simple, and a preliminary implementation [8] gave reasonable results in practice. However, the previously known bounds on its performance are useless when runtimes are actually manageable. Here, we present much sharper lower and upper bounds on the performance of this algorithm that partially explain why its behavior is so much better in practice than what was previously predicted in theory. We also give specific examples of instances of the problem for which the PTAS performs poorly in practice, and show that the asymptotic performance bound given in the original proof matches the behaviour of a simple variant of the algorithm on a particularly bad instance of the problem.", 
        "editor": [
          {
            "familyName": "Apostolico", 
            "givenName": "Alberto", 
            "type": "Person"
          }, 
          {
            "familyName": "Crochemore", 
            "givenName": "Maxime", 
            "type": "Person"
          }, 
          {
            "familyName": "Park", 
            "givenName": "Kunsoo", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/11496656_1", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-540-26201-5", 
            "978-3-540-31562-9"
          ], 
          "name": "Combinatorial Pattern Matching", 
          "type": "Book"
        }, 
        "name": "Sharper Upper and Lower Bounds for an Approximation Scheme for Consensus-Pattern", 
        "pagination": "1-10", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1031528905"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/11496656_1"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "9632d6f104f92f989fae68344d0f96631cff9aadb784c3b49c3b896404dd51a6"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/11496656_1", 
          "https://app.dimensions.ai/details/publication/pub.1031528905"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T08:27", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000363_0000000363/records_70061_00000001.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F11496656_1"
      }
    ]
     

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

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

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11496656_1'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11496656_1'


     

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

    127 TRIPLES      23 PREDICATES      35 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/11496656_1 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N279a8808bd3346e2adcd98a13ab3ec93
    4 schema:citation sg:pub.10.1007/978-1-4899-2885-6
    5 https://app.dimensions.ai/details/publication/pub.1082424111
    6 https://doi.org/10.1006/jcss.2002.1823
    7 https://doi.org/10.1093/bioinformatics/15.7.563
    8 https://doi.org/10.1093/bioinformatics/18.10.1374
    9 https://doi.org/10.1093/bioinformatics/18.10.1382
    10 https://doi.org/10.1126/science.8211139
    11 https://doi.org/10.1145/369133.369172
    12 schema:datePublished 2005
    13 schema:datePublishedReg 2005-01-01
    14 schema:description We present sharper upper and lower bounds for a known polynomial-time approximation scheme due to Li, Ma and Wang [7] for the Consensus-Pattern problem. This NP-hard problem is an abstraction of motif finding, a common bioinformatics discovery task. The PTAS due to Li et al. is simple, and a preliminary implementation [8] gave reasonable results in practice. However, the previously known bounds on its performance are useless when runtimes are actually manageable. Here, we present much sharper lower and upper bounds on the performance of this algorithm that partially explain why its behavior is so much better in practice than what was previously predicted in theory. We also give specific examples of instances of the problem for which the PTAS performs poorly in practice, and show that the asymptotic performance bound given in the original proof matches the behaviour of a simple variant of the algorithm on a particularly bad instance of the problem.
    15 schema:editor Na07a0dadae8d4f1abca7fc47ee42631a
    16 schema:genre chapter
    17 schema:inLanguage en
    18 schema:isAccessibleForFree false
    19 schema:isPartOf Nbfb056d1ac614925b3854c0e00cf8a69
    20 schema:name Sharper Upper and Lower Bounds for an Approximation Scheme for Consensus-Pattern
    21 schema:pagination 1-10
    22 schema:productId N120039542fbe410cb23e0501a1a1aea0
    23 N739e7b14b06747d58909a35e2b9da789
    24 Nad52ced0a66943b9a35a8cfba1e1a443
    25 schema:publisher Na88e9b32d9484923ac5540c47632a6e9
    26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031528905
    27 https://doi.org/10.1007/11496656_1
    28 schema:sdDatePublished 2019-04-16T08:27
    29 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    30 schema:sdPublisher N9ac6825fd3ae41d5806e117049406a99
    31 schema:url https://link.springer.com/10.1007%2F11496656_1
    32 sgo:license sg:explorer/license/
    33 sgo:sdDataset chapters
    34 rdf:type schema:Chapter
    35 N0723ae9cd3724798a5d4c37f403df4f6 rdf:first sg:person.0642727740.54
    36 rdf:rest N78d2bbca7b9349b2b06bfbaab88dbbc8
    37 N120039542fbe410cb23e0501a1a1aea0 schema:name doi
    38 schema:value 10.1007/11496656_1
    39 rdf:type schema:PropertyValue
    40 N279a8808bd3346e2adcd98a13ab3ec93 rdf:first sg:person.0642141060.90
    41 rdf:rest N0723ae9cd3724798a5d4c37f403df4f6
    42 N2f404a38a63948a28ef1a083e2e16e19 schema:familyName Apostolico
    43 schema:givenName Alberto
    44 rdf:type schema:Person
    45 N3f6d8d590a524461842007b95af1f7ff rdf:first N475db73801564ea1947a1f910acb61b8
    46 rdf:rest N732b4968109c4116b8c615981d812017
    47 N475db73801564ea1947a1f910acb61b8 schema:familyName Crochemore
    48 schema:givenName Maxime
    49 rdf:type schema:Person
    50 N4cf68ce96a10436780945dbd16946abd rdf:first sg:person.011531402673.02
    51 rdf:rest N667225e3c87c4c6fbdad9c7f7707c121
    52 N667225e3c87c4c6fbdad9c7f7707c121 rdf:first sg:person.01041305251.67
    53 rdf:rest rdf:nil
    54 N732b4968109c4116b8c615981d812017 rdf:first Nb54302e8878e47f683c81aabf4094601
    55 rdf:rest rdf:nil
    56 N739e7b14b06747d58909a35e2b9da789 schema:name dimensions_id
    57 schema:value pub.1031528905
    58 rdf:type schema:PropertyValue
    59 N78d2bbca7b9349b2b06bfbaab88dbbc8 rdf:first sg:person.01203526716.95
    60 rdf:rest N4cf68ce96a10436780945dbd16946abd
    61 N9ac6825fd3ae41d5806e117049406a99 schema:name Springer Nature - SN SciGraph project
    62 rdf:type schema:Organization
    63 Na07a0dadae8d4f1abca7fc47ee42631a rdf:first N2f404a38a63948a28ef1a083e2e16e19
    64 rdf:rest N3f6d8d590a524461842007b95af1f7ff
    65 Na88e9b32d9484923ac5540c47632a6e9 schema:location Berlin, Heidelberg
    66 schema:name Springer Berlin Heidelberg
    67 rdf:type schema:Organisation
    68 Nad52ced0a66943b9a35a8cfba1e1a443 schema:name readcube_id
    69 schema:value 9632d6f104f92f989fae68344d0f96631cff9aadb784c3b49c3b896404dd51a6
    70 rdf:type schema:PropertyValue
    71 Nb54302e8878e47f683c81aabf4094601 schema:familyName Park
    72 schema:givenName Kunsoo
    73 rdf:type schema:Person
    74 Nbfb056d1ac614925b3854c0e00cf8a69 schema:isbn 978-3-540-26201-5
    75 978-3-540-31562-9
    76 schema:name Combinatorial Pattern Matching
    77 rdf:type schema:Book
    78 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    79 schema:name Information and Computing Sciences
    80 rdf:type schema:DefinedTerm
    81 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    82 schema:name Computation Theory and Mathematics
    83 rdf:type schema:DefinedTerm
    84 sg:person.01041305251.67 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
    85 schema:familyName Vinař
    86 schema:givenName Tomáš
    87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01041305251.67
    88 rdf:type schema:Person
    89 sg:person.011531402673.02 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
    90 schema:familyName López-Ortiz
    91 schema:givenName Alejandro
    92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011531402673.02
    93 rdf:type schema:Person
    94 sg:person.01203526716.95 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
    95 schema:familyName Harrower
    96 schema:givenName Ian M.
    97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01203526716.95
    98 rdf:type schema:Person
    99 sg:person.0642141060.90 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
    100 schema:familyName Brejová
    101 schema:givenName Broňa
    102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0642141060.90
    103 rdf:type schema:Person
    104 sg:person.0642727740.54 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
    105 schema:familyName Brown
    106 schema:givenName Daniel G.
    107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0642727740.54
    108 rdf:type schema:Person
    109 sg:pub.10.1007/978-1-4899-2885-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1109705819
    110 https://doi.org/10.1007/978-1-4899-2885-6
    111 rdf:type schema:CreativeWork
    112 https://app.dimensions.ai/details/publication/pub.1082424111 schema:CreativeWork
    113 https://doi.org/10.1006/jcss.2002.1823 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024001192
    114 rdf:type schema:CreativeWork
    115 https://doi.org/10.1093/bioinformatics/15.7.563 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030639875
    116 rdf:type schema:CreativeWork
    117 https://doi.org/10.1093/bioinformatics/18.10.1374 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048043849
    118 rdf:type schema:CreativeWork
    119 https://doi.org/10.1093/bioinformatics/18.10.1382 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046206875
    120 rdf:type schema:CreativeWork
    121 https://doi.org/10.1126/science.8211139 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062653653
    122 rdf:type schema:CreativeWork
    123 https://doi.org/10.1145/369133.369172 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018080948
    124 rdf:type schema:CreativeWork
    125 https://www.grid.ac/institutes/grid.46078.3d schema:alternateName University of Waterloo
    126 schema:name School of Computer Science, University of Waterloo
    127 rdf:type schema:Organization
     




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


    ...