On the Complexity of the Crossing Contact Map Pattern Matching Problem View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2006

AUTHORS

Shuai Cheng Li , Ming Li

ABSTRACT

Contact maps are concepts that are often used to represent structural information in molecular biology. The contact map pattern matching (CMPM) problem is to decide if a contact map (called the pattern) is a substructure of another contact map (called the target). In general, the problem is NP-hard, but when there are restrictions on the form of the pattern, the problem can, in some case, be solved in polynomial time. In particular, a polynomial time algorithm has been proposed [1] for the case when the patterns are so-called crossing contact maps. In this paper we show that the problem is actually NP-hard, and show a flaw in the proposed polynomial-time algorithm. Through the same method, we also show that a related problem, namely, the 2-interval patten matching problem with -structured patterns and disjoint interval ground set, is NP-hard. More... »

PAGES

231-241

References to SciGraph publications

  • 2004. New Results for the 2-Interval Pattern Problem in COMBINATORIAL PATTERN MATCHING
  • 2005. Approximating the 2-Interval Pattern Problem in ALGORITHMS – ESA 2005
  • Book

    TITLE

    Algorithms in Bioinformatics

    ISBN

    978-3-540-39583-6
    978-3-540-39584-3

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/11851561_22

    DOI

    http://dx.doi.org/10.1007/11851561_22

    DIMENSIONS

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


    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/0801", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Artificial Intelligence and Image Processing", 
            "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": [
                "David R. Cheriton School of Computer Science, University of Waterloo, N2L 3G1, Waterloo, ON, Canada"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Li", 
            "givenName": "Shuai Cheng", 
            "id": "sg:person.01314123720.90", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01314123720.90"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Waterloo", 
              "id": "https://www.grid.ac/institutes/grid.46078.3d", 
              "name": [
                "David R. Cheriton School of Computer Science, University of Waterloo, N2L 3G1, Waterloo, ON, Canada"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Li", 
            "givenName": "Ming", 
            "id": "sg:person.0621576316.79", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0621576316.79"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/11561071_39", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027973556", 
              "https://doi.org/10.1007/11561071_39"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11561071_39", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027973556", 
              "https://doi.org/10.1007/11561071_39"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2003.08.010", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030091127"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2003.08.010", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030091127"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-27801-6_23", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044250427", 
              "https://doi.org/10.1007/978-3-540-27801-6_23"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-27801-6_23", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044250427", 
              "https://doi.org/10.1007/978-3-540-27801-6_23"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tcbb.2004.35", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061540438"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sffcs.1999.814624", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095293918"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2006", 
        "datePublishedReg": "2006-01-01", 
        "description": "Contact maps are concepts that are often used to represent structural information in molecular biology. The contact map pattern matching (CMPM) problem is to decide if a contact map (called the pattern) is a substructure of another contact map (called the target). In general, the problem is NP-hard, but when there are restrictions on the form of the pattern, the problem can, in some case, be solved in polynomial time. In particular, a polynomial time algorithm has been proposed [1] for the case when the patterns are so-called crossing contact maps. In this paper we show that the problem is actually NP-hard, and show a flaw in the proposed polynomial-time algorithm. Through the same method, we also show that a related problem, namely, the 2-interval patten matching problem with -structured patterns and disjoint interval ground set, is NP-hard.", 
        "editor": [
          {
            "familyName": "B\u00fccher", 
            "givenName": "Philipp", 
            "type": "Person"
          }, 
          {
            "familyName": "Moret", 
            "givenName": "Bernard M. E.", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/11851561_22", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-540-39583-6", 
            "978-3-540-39584-3"
          ], 
          "name": "Algorithms in Bioinformatics", 
          "type": "Book"
        }, 
        "name": "On the Complexity of the Crossing Contact Map Pattern Matching Problem", 
        "pagination": "231-241", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1004622336"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/11851561_22"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "16067d91d19e2d4b1dbf3a975fda78a2734032b20e007245f58c6a325b5905d8"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/11851561_22", 
          "https://app.dimensions.ai/details/publication/pub.1004622336"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T07:26", 
        "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/0000000355_0000000355/records_52987_00000000.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F11851561_22"
      }
    ]
     

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

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

    Turtle is a human-readable linked data format.

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

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

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


     

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

    94 TRIPLES      23 PREDICATES      32 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/11851561_22 schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 schema:author Ne929186023cc4cca94e585c67568b72a
    4 schema:citation sg:pub.10.1007/11561071_39
    5 sg:pub.10.1007/978-3-540-27801-6_23
    6 https://doi.org/10.1016/j.tcs.2003.08.010
    7 https://doi.org/10.1109/sffcs.1999.814624
    8 https://doi.org/10.1109/tcbb.2004.35
    9 schema:datePublished 2006
    10 schema:datePublishedReg 2006-01-01
    11 schema:description Contact maps are concepts that are often used to represent structural information in molecular biology. The contact map pattern matching (CMPM) problem is to decide if a contact map (called the pattern) is a substructure of another contact map (called the target). In general, the problem is NP-hard, but when there are restrictions on the form of the pattern, the problem can, in some case, be solved in polynomial time. In particular, a polynomial time algorithm has been proposed [1] for the case when the patterns are so-called crossing contact maps. In this paper we show that the problem is actually NP-hard, and show a flaw in the proposed polynomial-time algorithm. Through the same method, we also show that a related problem, namely, the 2-interval patten matching problem with -structured patterns and disjoint interval ground set, is NP-hard.
    12 schema:editor Nec47ab7982ef44c69b99a4876733305f
    13 schema:genre chapter
    14 schema:inLanguage en
    15 schema:isAccessibleForFree false
    16 schema:isPartOf N725eef59d57446e09a8cebad3b62a5fc
    17 schema:name On the Complexity of the Crossing Contact Map Pattern Matching Problem
    18 schema:pagination 231-241
    19 schema:productId N47dc887f1e2c4fb8bd6ee96a334e9f98
    20 N55829d8ea2de448fada5f4a2920d0d76
    21 N5dc567775875446794a53fad8704e987
    22 schema:publisher Nc025ec034ee74c19830f42fcd0d1968c
    23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004622336
    24 https://doi.org/10.1007/11851561_22
    25 schema:sdDatePublished 2019-04-16T07:26
    26 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    27 schema:sdPublisher Ne261ac1e19f94fecbda740abcce0ac04
    28 schema:url https://link.springer.com/10.1007%2F11851561_22
    29 sgo:license sg:explorer/license/
    30 sgo:sdDataset chapters
    31 rdf:type schema:Chapter
    32 N1448fce8c2b04051bf9572cc380316da rdf:first Nc0848ceb3e0c41a49eb8c49f9a1e09b0
    33 rdf:rest rdf:nil
    34 N47dc887f1e2c4fb8bd6ee96a334e9f98 schema:name dimensions_id
    35 schema:value pub.1004622336
    36 rdf:type schema:PropertyValue
    37 N555fc78f377c46b7bea137a93acd4503 schema:familyName Bücher
    38 schema:givenName Philipp
    39 rdf:type schema:Person
    40 N55829d8ea2de448fada5f4a2920d0d76 schema:name doi
    41 schema:value 10.1007/11851561_22
    42 rdf:type schema:PropertyValue
    43 N5dc567775875446794a53fad8704e987 schema:name readcube_id
    44 schema:value 16067d91d19e2d4b1dbf3a975fda78a2734032b20e007245f58c6a325b5905d8
    45 rdf:type schema:PropertyValue
    46 N725eef59d57446e09a8cebad3b62a5fc schema:isbn 978-3-540-39583-6
    47 978-3-540-39584-3
    48 schema:name Algorithms in Bioinformatics
    49 rdf:type schema:Book
    50 Nb5b5f033083b4a1e9f7c368d24427f3e rdf:first sg:person.0621576316.79
    51 rdf:rest rdf:nil
    52 Nc025ec034ee74c19830f42fcd0d1968c schema:location Berlin, Heidelberg
    53 schema:name Springer Berlin Heidelberg
    54 rdf:type schema:Organisation
    55 Nc0848ceb3e0c41a49eb8c49f9a1e09b0 schema:familyName Moret
    56 schema:givenName Bernard M. E.
    57 rdf:type schema:Person
    58 Ne261ac1e19f94fecbda740abcce0ac04 schema:name Springer Nature - SN SciGraph project
    59 rdf:type schema:Organization
    60 Ne929186023cc4cca94e585c67568b72a rdf:first sg:person.01314123720.90
    61 rdf:rest Nb5b5f033083b4a1e9f7c368d24427f3e
    62 Nec47ab7982ef44c69b99a4876733305f rdf:first N555fc78f377c46b7bea137a93acd4503
    63 rdf:rest N1448fce8c2b04051bf9572cc380316da
    64 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    65 schema:name Information and Computing Sciences
    66 rdf:type schema:DefinedTerm
    67 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    68 schema:name Artificial Intelligence and Image Processing
    69 rdf:type schema:DefinedTerm
    70 sg:person.01314123720.90 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
    71 schema:familyName Li
    72 schema:givenName Shuai Cheng
    73 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01314123720.90
    74 rdf:type schema:Person
    75 sg:person.0621576316.79 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
    76 schema:familyName Li
    77 schema:givenName Ming
    78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0621576316.79
    79 rdf:type schema:Person
    80 sg:pub.10.1007/11561071_39 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027973556
    81 https://doi.org/10.1007/11561071_39
    82 rdf:type schema:CreativeWork
    83 sg:pub.10.1007/978-3-540-27801-6_23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044250427
    84 https://doi.org/10.1007/978-3-540-27801-6_23
    85 rdf:type schema:CreativeWork
    86 https://doi.org/10.1016/j.tcs.2003.08.010 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030091127
    87 rdf:type schema:CreativeWork
    88 https://doi.org/10.1109/sffcs.1999.814624 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095293918
    89 rdf:type schema:CreativeWork
    90 https://doi.org/10.1109/tcbb.2004.35 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061540438
    91 rdf:type schema:CreativeWork
    92 https://www.grid.ac/institutes/grid.46078.3d schema:alternateName University of Waterloo
    93 schema:name David R. Cheriton School of Computer Science, University of Waterloo, N2L 3G1, Waterloo, ON, Canada
    94 rdf:type schema:Organization
     




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


    ...