Inapproximability results for the lateral gene transfer problem View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2006-05-17

AUTHORS

Bhaskar Dasgupta, Sergio Ferrarini, Uthra Gopalakrishnan, Nisha Raj Paryani

ABSTRACT

This paper concerns the Lateral Gene Transfer Problem. This minimization problem, defined by Hallett and Lagergren (2001), is that of finding the most parsimonious lateral gene transfer scenario for a given pair of gene and species trees. Our main results are the following: We show that it is not possible to approximate the problem in polynomial time within an approximation ratio of 1 + ε, for some constant ε > 0 unless P = NP. We also provide explicit values of ε for the above claim.We provide an upper bound on the cost of any 1-active scenario and prove the tightness of this bound. More... »

PAGES

387-405

References to SciGraph publications

  • 2003-02. Ancient horizontal gene transfer in NATURE REVIEWS GENETICS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s10878-006-8212-8

    DOI

    http://dx.doi.org/10.1007/s10878-006-8212-8

    DIMENSIONS

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


    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/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Pure Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Applied Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0103", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Numerical and Computational Mathematics", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Department of Computer Science, University of Illinois at Chicago, 60607-7053, Chicago, IL", 
              "id": "http://www.grid.ac/institutes/grid.185648.6", 
              "name": [
                "Department of Computer Science, University of Illinois at Chicago, 60607-7053, Chicago, IL"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Dasgupta", 
            "givenName": "Bhaskar", 
            "id": "sg:person.0763403270.10", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0763403270.10"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Dipartimento di Elettronica e Informazione, Politecnico di Milano, Piazza Leonardo da Vinci 32, 20133, Milano, Italy", 
              "id": "http://www.grid.ac/institutes/grid.4643.5", 
              "name": [
                "Dipartimento di Elettronica e Informazione, Politecnico di Milano, Piazza Leonardo da Vinci 32, 20133, Milano, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Ferrarini", 
            "givenName": "Sergio", 
            "id": "sg:person.016610510315.85", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016610510315.85"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Computer Science, University of Illinois at Chicago, 60607-7053, Chicago, IL", 
              "id": "http://www.grid.ac/institutes/grid.185648.6", 
              "name": [
                "Department of Computer Science, University of Illinois at Chicago, 60607-7053, Chicago, IL"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Gopalakrishnan", 
            "givenName": "Uthra", 
            "id": "sg:person.010703017515.64", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010703017515.64"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Computer Science, University of Illinois at Chicago, 60607-7053, Chicago, IL", 
              "id": "http://www.grid.ac/institutes/grid.185648.6", 
              "name": [
                "Department of Computer Science, University of Illinois at Chicago, 60607-7053, Chicago, IL"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Paryani", 
            "givenName": "Nisha Raj", 
            "id": "sg:person.013073341115.27", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013073341115.27"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1038/nrg1000", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032410834", 
              "https://doi.org/10.1038/nrg1000"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2006-05-17", 
        "datePublishedReg": "2006-05-17", 
        "description": "This paper concerns the Lateral Gene Transfer Problem. This minimization problem, defined by Hallett and Lagergren (2001), is that of finding the most parsimonious lateral gene transfer scenario for a given pair of gene and species trees. Our main results are the following:\nWe show that it is not possible to approximate the problem in polynomial time within an approximation ratio of 1 + \u03b5, for some constant \u03b5 > 0 unless P = NP. We also provide explicit values of \u03b5 for the above claim.We provide an upper bound on the cost of any 1-active scenario and prove the tightness of this bound.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s10878-006-8212-8", 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1036683", 
            "issn": [
              "1382-6905", 
              "1573-2886"
            ], 
            "name": "Journal of Combinatorial Optimization", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "4", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "11"
          }
        ], 
        "keywords": [
          "polynomial time", 
          "approximation ratio", 
          "transfer problem", 
          "minimization problem", 
          "Lagergren", 
          "transfer scenarios", 
          "scenarios", 
          "pairs of genes", 
          "genes", 
          "species tree", 
          "trees", 
          "NPs", 
          "explicit values", 
          "above claims", 
          "cost", 
          "inapproximability results", 
          "problem", 
          "Hallett", 
          "pairs", 
          "main results", 
          "results", 
          "time", 
          "ratio", 
          "values", 
          "claims", 
          "tightness", 
          "paper"
        ], 
        "name": "Inapproximability results for the lateral gene transfer problem", 
        "pagination": "387-405", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1017987882"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s10878-006-8212-8"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s10878-006-8212-8", 
          "https://app.dimensions.ai/details/publication/pub.1017987882"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-12-01T06:25", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20221201/entities/gbq_results/article/article_418.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s10878-006-8212-8"
      }
    ]
     

    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/s10878-006-8212-8'

    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/s10878-006-8212-8'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10878-006-8212-8'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10878-006-8212-8'


     

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

    120 TRIPLES      21 PREDICATES      54 URIs      43 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s10878-006-8212-8 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 anzsrc-for:0102
    4 anzsrc-for:0103
    5 schema:author N38c875eab7b74363b029e1a8085059ed
    6 schema:citation sg:pub.10.1038/nrg1000
    7 schema:datePublished 2006-05-17
    8 schema:datePublishedReg 2006-05-17
    9 schema:description This paper concerns the Lateral Gene Transfer Problem. This minimization problem, defined by Hallett and Lagergren (2001), is that of finding the most parsimonious lateral gene transfer scenario for a given pair of gene and species trees. Our main results are the following: We show that it is not possible to approximate the problem in polynomial time within an approximation ratio of 1 + ε, for some constant ε > 0 unless P = NP. We also provide explicit values of ε for the above claim.We provide an upper bound on the cost of any 1-active scenario and prove the tightness of this bound.
    10 schema:genre article
    11 schema:isAccessibleForFree true
    12 schema:isPartOf Nca6bbc882215475dae4dad7fd34356ef
    13 Ndee9e1d5556c4b01a848849e2217f5b4
    14 sg:journal.1036683
    15 schema:keywords Hallett
    16 Lagergren
    17 NPs
    18 above claims
    19 approximation ratio
    20 claims
    21 cost
    22 explicit values
    23 genes
    24 inapproximability results
    25 main results
    26 minimization problem
    27 pairs
    28 pairs of genes
    29 paper
    30 polynomial time
    31 problem
    32 ratio
    33 results
    34 scenarios
    35 species tree
    36 tightness
    37 time
    38 transfer problem
    39 transfer scenarios
    40 trees
    41 values
    42 schema:name Inapproximability results for the lateral gene transfer problem
    43 schema:pagination 387-405
    44 schema:productId N82afcf1f2ba74e02a0753f82a876b983
    45 Nd8396cc1b73a46359decfb70a770c8d7
    46 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017987882
    47 https://doi.org/10.1007/s10878-006-8212-8
    48 schema:sdDatePublished 2022-12-01T06:25
    49 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    50 schema:sdPublisher N7e4e03fc664e418296faf81b1b593950
    51 schema:url https://doi.org/10.1007/s10878-006-8212-8
    52 sgo:license sg:explorer/license/
    53 sgo:sdDataset articles
    54 rdf:type schema:ScholarlyArticle
    55 N38c875eab7b74363b029e1a8085059ed rdf:first sg:person.0763403270.10
    56 rdf:rest N5920b0e80b58467fac7bd76a310449f4
    57 N5920b0e80b58467fac7bd76a310449f4 rdf:first sg:person.016610510315.85
    58 rdf:rest Nac54f007d22f402cb2f276a3c52944c5
    59 N7e4e03fc664e418296faf81b1b593950 schema:name Springer Nature - SN SciGraph project
    60 rdf:type schema:Organization
    61 N82afcf1f2ba74e02a0753f82a876b983 schema:name doi
    62 schema:value 10.1007/s10878-006-8212-8
    63 rdf:type schema:PropertyValue
    64 Nac54f007d22f402cb2f276a3c52944c5 rdf:first sg:person.010703017515.64
    65 rdf:rest Nef9c881905b742c68bd15c48f499028e
    66 Nca6bbc882215475dae4dad7fd34356ef schema:issueNumber 4
    67 rdf:type schema:PublicationIssue
    68 Nd8396cc1b73a46359decfb70a770c8d7 schema:name dimensions_id
    69 schema:value pub.1017987882
    70 rdf:type schema:PropertyValue
    71 Ndee9e1d5556c4b01a848849e2217f5b4 schema:volumeNumber 11
    72 rdf:type schema:PublicationVolume
    73 Nef9c881905b742c68bd15c48f499028e rdf:first sg:person.013073341115.27
    74 rdf:rest rdf:nil
    75 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    76 schema:name Mathematical Sciences
    77 rdf:type schema:DefinedTerm
    78 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    79 schema:name Pure Mathematics
    80 rdf:type schema:DefinedTerm
    81 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
    82 schema:name Applied Mathematics
    83 rdf:type schema:DefinedTerm
    84 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
    85 schema:name Numerical and Computational Mathematics
    86 rdf:type schema:DefinedTerm
    87 sg:journal.1036683 schema:issn 1382-6905
    88 1573-2886
    89 schema:name Journal of Combinatorial Optimization
    90 schema:publisher Springer Nature
    91 rdf:type schema:Periodical
    92 sg:person.010703017515.64 schema:affiliation grid-institutes:grid.185648.6
    93 schema:familyName Gopalakrishnan
    94 schema:givenName Uthra
    95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010703017515.64
    96 rdf:type schema:Person
    97 sg:person.013073341115.27 schema:affiliation grid-institutes:grid.185648.6
    98 schema:familyName Paryani
    99 schema:givenName Nisha Raj
    100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013073341115.27
    101 rdf:type schema:Person
    102 sg:person.016610510315.85 schema:affiliation grid-institutes:grid.4643.5
    103 schema:familyName Ferrarini
    104 schema:givenName Sergio
    105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016610510315.85
    106 rdf:type schema:Person
    107 sg:person.0763403270.10 schema:affiliation grid-institutes:grid.185648.6
    108 schema:familyName Dasgupta
    109 schema:givenName Bhaskar
    110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0763403270.10
    111 rdf:type schema:Person
    112 sg:pub.10.1038/nrg1000 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032410834
    113 https://doi.org/10.1038/nrg1000
    114 rdf:type schema:CreativeWork
    115 grid-institutes:grid.185648.6 schema:alternateName Department of Computer Science, University of Illinois at Chicago, 60607-7053, Chicago, IL
    116 schema:name Department of Computer Science, University of Illinois at Chicago, 60607-7053, Chicago, IL
    117 rdf:type schema:Organization
    118 grid-institutes:grid.4643.5 schema:alternateName Dipartimento di Elettronica e Informazione, Politecnico di Milano, Piazza Leonardo da Vinci 32, 20133, Milano, Italy
    119 schema:name Dipartimento di Elettronica e Informazione, Politecnico di Milano, Piazza Leonardo da Vinci 32, 20133, Milano, Italy
    120 rdf:type schema:Organization
     




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


    ...