A note on the single genotype resolution problem View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2004-03

AUTHORS

Hao Lin, Ze-Feng Zhang, Qiang-Feng Zhang, Dong-Bo Bu, Ming Li

ABSTRACT

This note settles the complexity of the single genotype resolution problem showing it is NP-complete. This solves an open problem raised by P. Bonizzoni, G.D. Vedova, R. Dondi, and J. Li. The same proof also gives an alternative and simpler reduction of the NP-hardness of Maximum Resolution problem.

PAGES

254-257

References to SciGraph publications

  • 2003. Haplotype Inference by Pure Parsimony in COMBINATORIAL PATTERN MATCHING
  • 2003-11. The Haplotyping problem: An overview of computational models and solutions in JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/bf02944804

    DOI

    http://dx.doi.org/10.1007/bf02944804

    DIMENSIONS

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


    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": "Institute Of Computing Technology", 
              "id": "https://www.grid.ac/institutes/grid.424936.e", 
              "name": [
                "Bioinformatics Lab, Institute of Computing Technology, The Chinese Academy of Sciences, 100080, Beijing, P.R. China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Lin", 
            "givenName": "Hao", 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Institute Of Computing Technology", 
              "id": "https://www.grid.ac/institutes/grid.424936.e", 
              "name": [
                "Bioinformatics Lab, Institute of Computing Technology, The Chinese Academy of Sciences, 100080, Beijing, P.R. China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Zhang", 
            "givenName": "Ze-Feng", 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Science and Technology of China", 
              "id": "https://www.grid.ac/institutes/grid.59053.3a", 
              "name": [
                "University of Science and Technology of China, 230026, Hefei, P.R. China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Zhang", 
            "givenName": "Qiang-Feng", 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Institute Of Computing Technology", 
              "id": "https://www.grid.ac/institutes/grid.424936.e", 
              "name": [
                "Bioinformatics Lab, Institute of Computing Technology, The Chinese Academy of Sciences, 100080, Beijing, P.R. China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Bu", 
            "givenName": "Dong-Bo", 
            "id": "sg:person.01137000414.40", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01137000414.40"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Tsinghua University", 
              "id": "https://www.grid.ac/institutes/grid.12527.33", 
              "name": [
                "University of Waterloo, Canada", 
                "Tsinghua University, 100084, Beijing, P.R. China"
              ], 
              "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/bf02945456", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009679933", 
              "https://doi.org/10.1007/bf02945456"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1126/science.1069424", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010139737"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/640075.640101", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014262282"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-44888-8_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023740799", 
              "https://doi.org/10.1007/3-540-44888-8_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/640075.640088", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032258114"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1089/10665270152530863", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1059204892"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1126/science.1065573", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062445519"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1093/oxfordjournals.molbev.a040591", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1078302152"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2004-03", 
        "datePublishedReg": "2004-03-01", 
        "description": "This note settles the complexity of the single genotype resolution problem showing it is NP-complete. This solves an open problem raised by P. Bonizzoni, G.D. Vedova, R. Dondi, and J. Li. The same proof also gives an alternative and simpler reduction of the NP-hardness of Maximum Resolution problem.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/bf02944804", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1320078", 
            "issn": [
              "1666-6046", 
              "1666-6038"
            ], 
            "name": "Journal of Computer Science and Technology", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "2", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "19"
          }
        ], 
        "name": "A note on the single genotype resolution problem", 
        "pagination": "254-257", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "e9c5228d41fa291f9330a553e7bda7f2532e0ff4bf09e2d31131b65f13df9b03"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf02944804"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1049071798"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf02944804", 
          "https://app.dimensions.ai/details/publication/pub.1049071798"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T14: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/0000000373_0000000373/records_13069_00000001.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007%2FBF02944804"
      }
    ]
     

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

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

    Turtle is a human-readable linked data format.

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

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

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


     

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

    119 TRIPLES      21 PREDICATES      35 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf02944804 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N273982fd49c44bb083a84962adeb7a60
    4 schema:citation sg:pub.10.1007/3-540-44888-8_11
    5 sg:pub.10.1007/bf02945456
    6 https://doi.org/10.1089/10665270152530863
    7 https://doi.org/10.1093/oxfordjournals.molbev.a040591
    8 https://doi.org/10.1126/science.1065573
    9 https://doi.org/10.1126/science.1069424
    10 https://doi.org/10.1145/640075.640088
    11 https://doi.org/10.1145/640075.640101
    12 schema:datePublished 2004-03
    13 schema:datePublishedReg 2004-03-01
    14 schema:description This note settles the complexity of the single genotype resolution problem showing it is NP-complete. This solves an open problem raised by P. Bonizzoni, G.D. Vedova, R. Dondi, and J. Li. The same proof also gives an alternative and simpler reduction of the NP-hardness of Maximum Resolution problem.
    15 schema:genre research_article
    16 schema:inLanguage en
    17 schema:isAccessibleForFree true
    18 schema:isPartOf N0b20d7df361d4b099d88add5c1a4888c
    19 N2f3435dddee241b6a6c4522bedac7941
    20 sg:journal.1320078
    21 schema:name A note on the single genotype resolution problem
    22 schema:pagination 254-257
    23 schema:productId Nc386982b9d8c4932b518d4ad65a44124
    24 Nc8a385dc32904cb3ac9683a53ec6fa03
    25 Ne6e47146071a4080b806f30dd907de86
    26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049071798
    27 https://doi.org/10.1007/bf02944804
    28 schema:sdDatePublished 2019-04-11T14:26
    29 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    30 schema:sdPublisher Ndb87a168d858487e823b6491dd491159
    31 schema:url http://link.springer.com/10.1007%2FBF02944804
    32 sgo:license sg:explorer/license/
    33 sgo:sdDataset articles
    34 rdf:type schema:ScholarlyArticle
    35 N05fd56cc1f0341edba3aff5f291016aa rdf:first sg:person.0621576316.79
    36 rdf:rest rdf:nil
    37 N0b20d7df361d4b099d88add5c1a4888c schema:issueNumber 2
    38 rdf:type schema:PublicationIssue
    39 N1ec13296eb0d4ddfb012d8e3e8dd7fdf rdf:first N5de83695df594919854bb35608209f74
    40 rdf:rest Na5b1b11324b047d0a23410ac39a80701
    41 N273982fd49c44bb083a84962adeb7a60 rdf:first Ne5aa9c73bcb34783a069d6b6864b2837
    42 rdf:rest N5cb957ae05a14dfda31444baf8615b95
    43 N2f3435dddee241b6a6c4522bedac7941 schema:volumeNumber 19
    44 rdf:type schema:PublicationVolume
    45 N3ed9616c526e467ab491cff5ceb80e87 schema:affiliation https://www.grid.ac/institutes/grid.424936.e
    46 schema:familyName Zhang
    47 schema:givenName Ze-Feng
    48 rdf:type schema:Person
    49 N5cb957ae05a14dfda31444baf8615b95 rdf:first N3ed9616c526e467ab491cff5ceb80e87
    50 rdf:rest N1ec13296eb0d4ddfb012d8e3e8dd7fdf
    51 N5de83695df594919854bb35608209f74 schema:affiliation https://www.grid.ac/institutes/grid.59053.3a
    52 schema:familyName Zhang
    53 schema:givenName Qiang-Feng
    54 rdf:type schema:Person
    55 Na5b1b11324b047d0a23410ac39a80701 rdf:first sg:person.01137000414.40
    56 rdf:rest N05fd56cc1f0341edba3aff5f291016aa
    57 Nc386982b9d8c4932b518d4ad65a44124 schema:name doi
    58 schema:value 10.1007/bf02944804
    59 rdf:type schema:PropertyValue
    60 Nc8a385dc32904cb3ac9683a53ec6fa03 schema:name readcube_id
    61 schema:value e9c5228d41fa291f9330a553e7bda7f2532e0ff4bf09e2d31131b65f13df9b03
    62 rdf:type schema:PropertyValue
    63 Ndb87a168d858487e823b6491dd491159 schema:name Springer Nature - SN SciGraph project
    64 rdf:type schema:Organization
    65 Ne5aa9c73bcb34783a069d6b6864b2837 schema:affiliation https://www.grid.ac/institutes/grid.424936.e
    66 schema:familyName Lin
    67 schema:givenName Hao
    68 rdf:type schema:Person
    69 Ne6e47146071a4080b806f30dd907de86 schema:name dimensions_id
    70 schema:value pub.1049071798
    71 rdf:type schema:PropertyValue
    72 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    73 schema:name Information and Computing Sciences
    74 rdf:type schema:DefinedTerm
    75 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    76 schema:name Computation Theory and Mathematics
    77 rdf:type schema:DefinedTerm
    78 sg:journal.1320078 schema:issn 1666-6038
    79 1666-6046
    80 schema:name Journal of Computer Science and Technology
    81 rdf:type schema:Periodical
    82 sg:person.01137000414.40 schema:affiliation https://www.grid.ac/institutes/grid.424936.e
    83 schema:familyName Bu
    84 schema:givenName Dong-Bo
    85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01137000414.40
    86 rdf:type schema:Person
    87 sg:person.0621576316.79 schema:affiliation https://www.grid.ac/institutes/grid.12527.33
    88 schema:familyName Li
    89 schema:givenName Ming
    90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0621576316.79
    91 rdf:type schema:Person
    92 sg:pub.10.1007/3-540-44888-8_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023740799
    93 https://doi.org/10.1007/3-540-44888-8_11
    94 rdf:type schema:CreativeWork
    95 sg:pub.10.1007/bf02945456 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009679933
    96 https://doi.org/10.1007/bf02945456
    97 rdf:type schema:CreativeWork
    98 https://doi.org/10.1089/10665270152530863 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059204892
    99 rdf:type schema:CreativeWork
    100 https://doi.org/10.1093/oxfordjournals.molbev.a040591 schema:sameAs https://app.dimensions.ai/details/publication/pub.1078302152
    101 rdf:type schema:CreativeWork
    102 https://doi.org/10.1126/science.1065573 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062445519
    103 rdf:type schema:CreativeWork
    104 https://doi.org/10.1126/science.1069424 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010139737
    105 rdf:type schema:CreativeWork
    106 https://doi.org/10.1145/640075.640088 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032258114
    107 rdf:type schema:CreativeWork
    108 https://doi.org/10.1145/640075.640101 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014262282
    109 rdf:type schema:CreativeWork
    110 https://www.grid.ac/institutes/grid.12527.33 schema:alternateName Tsinghua University
    111 schema:name Tsinghua University, 100084, Beijing, P.R. China
    112 University of Waterloo, Canada
    113 rdf:type schema:Organization
    114 https://www.grid.ac/institutes/grid.424936.e schema:alternateName Institute Of Computing Technology
    115 schema:name Bioinformatics Lab, Institute of Computing Technology, The Chinese Academy of Sciences, 100080, Beijing, P.R. China
    116 rdf:type schema:Organization
    117 https://www.grid.ac/institutes/grid.59053.3a schema:alternateName University of Science and Technology of China
    118 schema:name University of Science and Technology of China, 230026, Hefei, P.R. China
    119 rdf:type schema:Organization
     




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


    ...