Inapproximability Results for the Lateral Gene Transfer Problem View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2005

AUTHORS

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

ABSTRACT

This paper concerns the Lateral Gene Transfer Problem. This minimization problem, defined by Hallet and Lagergren [6], 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:– (a) 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.– (b) We provide an upper bound on the cost of any 1-active scenario and prove the tightness of this bound. More... »

PAGES

182-195

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11560586_15

DOI

http://dx.doi.org/10.1007/11560586_15

DIMENSIONS

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


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/06", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Biological Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0607", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Plant Biology", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Illinois at Chicago, 60607-7053, Chicago, IL, USA", 
          "id": "http://www.grid.ac/institutes/grid.185648.6", 
          "name": [
            "Department of Computer Science, University of Illinois at Chicago, 60607-7053, Chicago, IL, USA"
          ], 
          "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, USA", 
          "id": "http://www.grid.ac/institutes/grid.185648.6", 
          "name": [
            "Department of Computer Science, University of Illinois at Chicago, 60607-7053, Chicago, IL, USA"
          ], 
          "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, USA", 
          "id": "http://www.grid.ac/institutes/grid.185648.6", 
          "name": [
            "Department of Computer Science, University of Illinois at Chicago, 60607-7053, Chicago, IL, USA"
          ], 
          "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"
      }
    ], 
    "datePublished": "2005", 
    "datePublishedReg": "2005-01-01", 
    "description": "This paper concerns the Lateral Gene Transfer Problem. This minimization problem, defined by Hallet and Lagergren [6], 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:\u2013 (a) We 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.\u2013 (b) We provide an upper bound on the cost of any 1-active scenario and prove the tightness of this bound.", 
    "editor": [
      {
        "familyName": "Coppo", 
        "givenName": "Mario", 
        "type": "Person"
      }, 
      {
        "familyName": "Lodi", 
        "givenName": "Elena", 
        "type": "Person"
      }, 
      {
        "familyName": "Pinna", 
        "givenName": "G. Michele", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11560586_15", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-29106-0", 
        "978-3-540-32024-1"
      ], 
      "name": "Theoretical Computer Science", 
      "type": "Book"
    }, 
    "keywords": [
      "pairs of genes", 
      "species tree", 
      "transfer problem", 
      "transfer scenarios", 
      "genes", 
      "trees", 
      "polynomial time", 
      "approximation ratio", 
      "inapproximability results", 
      "problem", 
      "minimization problem", 
      "Hallet", 
      "Lagergren", 
      "scenarios", 
      "pairs", 
      "main results", 
      "results", 
      "time", 
      "ratio", 
      "NPs", 
      "explicit values", 
      "values", 
      "above claims", 
      "claims", 
      "cost", 
      "tightness", 
      "paper"
    ], 
    "name": "Inapproximability Results for the Lateral Gene Transfer Problem", 
    "pagination": "182-195", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1053207322"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11560586_15"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11560586_15", 
      "https://app.dimensions.ai/details/publication/pub.1053207322"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-10T10:55", 
    "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/chapter/chapter_84.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11560586_15"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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

121 TRIPLES      23 PREDICATES      53 URIs      46 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11560586_15 schema:about anzsrc-for:06
2 anzsrc-for:0607
3 schema:author N83acb964a13f49b283d6dc555a0ced7f
4 schema:datePublished 2005
5 schema:datePublishedReg 2005-01-01
6 schema:description This paper concerns the Lateral Gene Transfer Problem. This minimization problem, defined by Hallet and Lagergren [6], 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:– (a) 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.– (b) We provide an upper bound on the cost of any 1-active scenario and prove the tightness of this bound.
7 schema:editor N290aed493a4447ba83d24eb2e7b443f6
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N9807af64e5504920a510595d62324885
12 schema:keywords Hallet
13 Lagergren
14 NPs
15 above claims
16 approximation ratio
17 claims
18 cost
19 explicit values
20 genes
21 inapproximability results
22 main results
23 minimization problem
24 pairs
25 pairs of genes
26 paper
27 polynomial time
28 problem
29 ratio
30 results
31 scenarios
32 species tree
33 tightness
34 time
35 transfer problem
36 transfer scenarios
37 trees
38 values
39 schema:name Inapproximability Results for the Lateral Gene Transfer Problem
40 schema:pagination 182-195
41 schema:productId N468678b62c6846a99741baac99fb6688
42 N7c1974fd8de540ddaab5e7d55b73dbea
43 schema:publisher Nd4df1861296e46d680ddff87a1a2aaa6
44 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053207322
45 https://doi.org/10.1007/11560586_15
46 schema:sdDatePublished 2022-05-10T10:55
47 schema:sdLicense https://scigraph.springernature.com/explorer/license/
48 schema:sdPublisher Ne93c26d42f5e4935b0d37291d3d4bbd4
49 schema:url https://doi.org/10.1007/11560586_15
50 sgo:license sg:explorer/license/
51 sgo:sdDataset chapters
52 rdf:type schema:Chapter
53 N290aed493a4447ba83d24eb2e7b443f6 rdf:first N47d24b32299e4f6d9d8dd55c630ba40b
54 rdf:rest Nb4b5d370711e4418be6a2587a54980fd
55 N4282abd51541462aa488e478ae6ad2db rdf:first sg:person.013073341115.27
56 rdf:rest rdf:nil
57 N468678b62c6846a99741baac99fb6688 schema:name dimensions_id
58 schema:value pub.1053207322
59 rdf:type schema:PropertyValue
60 N47d24b32299e4f6d9d8dd55c630ba40b schema:familyName Coppo
61 schema:givenName Mario
62 rdf:type schema:Person
63 N7c1974fd8de540ddaab5e7d55b73dbea schema:name doi
64 schema:value 10.1007/11560586_15
65 rdf:type schema:PropertyValue
66 N83acb964a13f49b283d6dc555a0ced7f rdf:first sg:person.0763403270.10
67 rdf:rest Nabfcfbce27854765b5d1b66ee483f4ba
68 N9807af64e5504920a510595d62324885 schema:isbn 978-3-540-29106-0
69 978-3-540-32024-1
70 schema:name Theoretical Computer Science
71 rdf:type schema:Book
72 Na5c3ac6738744ec4be427034112996b9 schema:familyName Pinna
73 schema:givenName G. Michele
74 rdf:type schema:Person
75 Na9733d1517c948f6b3e2a5f496fbd78b rdf:first sg:person.010703017515.64
76 rdf:rest N4282abd51541462aa488e478ae6ad2db
77 Nabfcfbce27854765b5d1b66ee483f4ba rdf:first sg:person.016610510315.85
78 rdf:rest Na9733d1517c948f6b3e2a5f496fbd78b
79 Nb4b5d370711e4418be6a2587a54980fd rdf:first Ncd9a6dbe8cab4edbaa5eceff13a148c9
80 rdf:rest Nf865e45cf81d428fb0b3560b0bc5c747
81 Ncd9a6dbe8cab4edbaa5eceff13a148c9 schema:familyName Lodi
82 schema:givenName Elena
83 rdf:type schema:Person
84 Nd4df1861296e46d680ddff87a1a2aaa6 schema:name Springer Nature
85 rdf:type schema:Organisation
86 Ne93c26d42f5e4935b0d37291d3d4bbd4 schema:name Springer Nature - SN SciGraph project
87 rdf:type schema:Organization
88 Nf865e45cf81d428fb0b3560b0bc5c747 rdf:first Na5c3ac6738744ec4be427034112996b9
89 rdf:rest rdf:nil
90 anzsrc-for:06 schema:inDefinedTermSet anzsrc-for:
91 schema:name Biological Sciences
92 rdf:type schema:DefinedTerm
93 anzsrc-for:0607 schema:inDefinedTermSet anzsrc-for:
94 schema:name Plant Biology
95 rdf:type schema:DefinedTerm
96 sg:person.010703017515.64 schema:affiliation grid-institutes:grid.185648.6
97 schema:familyName Gopalakrishnan
98 schema:givenName Uthra
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010703017515.64
100 rdf:type schema:Person
101 sg:person.013073341115.27 schema:affiliation grid-institutes:grid.185648.6
102 schema:familyName Paryani
103 schema:givenName Nisha Raj
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013073341115.27
105 rdf:type schema:Person
106 sg:person.016610510315.85 schema:affiliation grid-institutes:grid.4643.5
107 schema:familyName Ferrarini
108 schema:givenName Sergio
109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016610510315.85
110 rdf:type schema:Person
111 sg:person.0763403270.10 schema:affiliation grid-institutes:grid.185648.6
112 schema:familyName DasGupta
113 schema:givenName Bhaskar
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0763403270.10
115 rdf:type schema:Person
116 grid-institutes:grid.185648.6 schema:alternateName Department of Computer Science, University of Illinois at Chicago, 60607-7053, Chicago, IL, USA
117 schema:name Department of Computer Science, University of Illinois at Chicago, 60607-7053, Chicago, IL, USA
118 rdf:type schema:Organization
119 grid-institutes:grid.4643.5 schema:alternateName Dipartimento di Elettronica e Informazione, Politecnico di Milano, Piazza Leonardo da Vinci 32, 20133, Milano, Italy
120 schema:name Dipartimento di Elettronica e Informazione, Politecnico di Milano, Piazza Leonardo da Vinci 32, 20133, Milano, Italy
121 rdf:type schema:Organization
 




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


...