Inferring (Biological) Signal Transduction Networks via Transitive Reductions of Directed Graphs View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2007-10-09

AUTHORS

Réka Albert, Bhaskar DasGupta, Riccardo Dondi, Eduardo Sontag

ABSTRACT

In this paper we consider the p-ary transitive reduction (TRp) problem where p>0 is an integer; for p=2 this problem arises in inferring a sparsest possible (biological) signal transduction network consistent with a set of experimental observations with a goal to minimize false positive inferences even if risking false negatives. Special cases of TRp have been investigated before in different contexts; the best previous results are as follows: The minimum equivalent digraph problem, that correspond to a special case of TR1 with no critical edges, is known to be MAX-SNP-hard, admits a polynomial time algorithm with an approximation ratio of 1.617+ε for any constant ε>0 (Chiu and Liu in Sci. Sin. 4:1396–1400, 1965) and can be solved in linear time for directed acyclic graphs (Aho et al. in SIAM J. Comput. 1(2):131–137, 1972). A 2-approximation algorithm exists for TR1 (Frederickson and JàJà in SIAM J. Comput. 10(2):270–283, 1981; Khuller et al. in 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 937–938, 1999). In this paper, our contributions are as follows: We observe that TRp, for any integer p>0, can be solved in linear time for directed acyclic graphs using the ideas in Aho et al. (SIAM J. Comput. 1(2):131–137, 1972). We provide a 1.78-approximation for TR1 that improves the 2-approximation mentioned in (2) above. We provide a 2+o(1)-approximation for TRp on general graphs for any fixed prime p>1. More... »

PAGES

129-159

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00453-007-9055-0

DOI

http://dx.doi.org/10.1007/s00453-007-9055-0

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Physics, Pennsylvania State University, 16802, University Park, PA, USA", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Department of Physics, Pennsylvania State University, 16802, University Park, PA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Albert", 
        "givenName": "R\u00e9ka", 
        "id": "sg:person.01017036620.03", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01017036620.03"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Illinois at Chicago, 60607, Chicago, IL, USA", 
          "id": "http://www.grid.ac/institutes/grid.185648.6", 
          "name": [
            "Department of Computer Science, University of Illinois at Chicago, 60607, 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 Scienze dei Linguaggi, della Comunicazione e degli Studi Culturali, Universit\u00e0 degli Studi di Bergamo, 24129, Bergamo, Italy", 
          "id": "http://www.grid.ac/institutes/grid.33236.37", 
          "name": [
            "Dipartimento di Scienze dei Linguaggi, della Comunicazione e degli Studi Culturali, Universit\u00e0 degli Studi di Bergamo, 24129, Bergamo, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Dondi", 
        "givenName": "Riccardo", 
        "id": "sg:person.013111453243.48", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013111453243.48"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Mathematics, Rutgers University, 08903, New Brunswick, NJ, USA", 
          "id": "http://www.grid.ac/institutes/grid.430387.b", 
          "name": [
            "Department of Mathematics, Rutgers University, 08903, New Brunswick, NJ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sontag", 
        "givenName": "Eduardo", 
        "id": "sg:person.0714217520.83", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0714217520.83"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/978-1-4613-1161-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014027374", 
          "https://doi.org/10.1007/978-1-4613-1161-4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1038/nature02555", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011649705", 
          "https://doi.org/10.1038/nature02555"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11764298_23", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013605920", 
          "https://doi.org/10.1007/11764298_23"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2007-10-09", 
    "datePublishedReg": "2007-10-09", 
    "description": "Abstract\nIn this paper we consider the p-ary transitive reduction (TRp) problem where p>0 is an integer; for p=2 this problem arises in inferring a sparsest possible (biological) signal transduction network consistent with a set of experimental observations with a goal to minimize false positive inferences even if risking false negatives. Special cases of TRp have been investigated before in different contexts; the best previous results are as follows: \nThe minimum equivalent digraph problem, that correspond to a special case of TR1 with no critical edges, is known to be MAX-SNP-hard, admits a polynomial time algorithm with an approximation ratio of 1.617+\u03b5 for any constant \u03b5>0 (Chiu and Liu in Sci. Sin. 4:1396\u20131400, 1965) and can be solved in linear time for directed acyclic graphs (Aho et al. in SIAM J. Comput. 1(2):131\u2013137, 1972).\n\nA 2-approximation algorithm exists for TR1 (Frederickson and J\u00e0J\u00e0 in SIAM J. Comput. 10(2):270\u2013283, 1981; Khuller et al. in 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pp.\u00a0937\u2013938, 1999).\n In this paper, our contributions are as follows: \nWe observe that TRp, for any integer p>0, can be solved in linear time for directed acyclic graphs using the ideas in Aho et al. (SIAM J. Comput. 1(2):131\u2013137, 1972).\n\nWe provide a 1.78-approximation for TR1 that improves the 2-approximation mentioned in (2) above.\n\nWe provide a 2+o(1)-approximation for TRp on general graphs for any fixed prime p>1.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s00453-007-9055-0", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isFundedItemOf": [
      {
        "id": "sg:grant.3044434", 
        "type": "MonetaryGrant"
      }
    ], 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "51"
      }
    ], 
    "keywords": [
      "special case", 
      "linear time", 
      "false-positive inferences", 
      "acyclic graph", 
      "digraph problems", 
      "polynomial time algorithm", 
      "general graphs", 
      "reduction problem", 
      "Directed Graphs", 
      "approximation ratio", 
      "best previous results", 
      "signal transduction networks", 
      "transitive reduction", 
      "MAX SNP", 
      "time algorithm", 
      "graph", 
      "transduction networks", 
      "previous results", 
      "critical edge", 
      "Aho et al", 
      "problem", 
      "algorithm", 
      "approximation", 
      "experimental observations", 
      "positive inferences", 
      "et al", 
      "integers", 
      "inference", 
      "network", 
      "set", 
      "edge", 
      "cases", 
      "idea", 
      "al", 
      "time", 
      "observations", 
      "results", 
      "contribution", 
      "false negatives", 
      "different contexts", 
      "goal", 
      "ratio", 
      "context", 
      "reduction", 
      "negatives", 
      "TR1", 
      "paper", 
      "Trp"
    ], 
    "name": "Inferring (Biological) Signal Transduction Networks via Transitive Reductions of Directed Graphs", 
    "pagination": "129-159", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1026603604"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00453-007-9055-0"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00453-007-9055-0", 
      "https://app.dimensions.ai/details/publication/pub.1026603604"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-05-20T07:24", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/article/article_445.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s00453-007-9055-0"
  }
]
 

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/s00453-007-9055-0'

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/s00453-007-9055-0'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-007-9055-0'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-007-9055-0'


 

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

150 TRIPLES      22 PREDICATES      76 URIs      65 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00453-007-9055-0 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N86587d8ed8bf4e3992a4fd7bc789f361
4 schema:citation sg:pub.10.1007/11764298_23
5 sg:pub.10.1007/978-1-4613-1161-4
6 sg:pub.10.1038/nature02555
7 schema:datePublished 2007-10-09
8 schema:datePublishedReg 2007-10-09
9 schema:description Abstract In this paper we consider the p-ary transitive reduction (TRp) problem where p>0 is an integer; for p=2 this problem arises in inferring a sparsest possible (biological) signal transduction network consistent with a set of experimental observations with a goal to minimize false positive inferences even if risking false negatives. Special cases of TRp have been investigated before in different contexts; the best previous results are as follows: The minimum equivalent digraph problem, that correspond to a special case of TR1 with no critical edges, is known to be MAX-SNP-hard, admits a polynomial time algorithm with an approximation ratio of 1.617+ε for any constant ε>0 (Chiu and Liu in Sci. Sin. 4:1396–1400, 1965) and can be solved in linear time for directed acyclic graphs (Aho et al. in SIAM J. Comput. 1(2):131–137, 1972). A 2-approximation algorithm exists for TR1 (Frederickson and JàJà in SIAM J. Comput. 10(2):270–283, 1981; Khuller et al. in 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 937–938, 1999). In this paper, our contributions are as follows: We observe that TRp, for any integer p>0, can be solved in linear time for directed acyclic graphs using the ideas in Aho et al. (SIAM J. Comput. 1(2):131–137, 1972). We provide a 1.78-approximation for TR1 that improves the 2-approximation mentioned in (2) above. We provide a 2+o(1)-approximation for TRp on general graphs for any fixed prime p>1.
10 schema:genre article
11 schema:inLanguage en
12 schema:isAccessibleForFree false
13 schema:isPartOf N3ca66a8f9187463fbdbf943afe5797c0
14 Nbfd6ecd507d24c1f9a64371ac340aad3
15 sg:journal.1047644
16 schema:keywords Aho et al
17 Directed Graphs
18 MAX SNP
19 TR1
20 Trp
21 acyclic graph
22 al
23 algorithm
24 approximation
25 approximation ratio
26 best previous results
27 cases
28 context
29 contribution
30 critical edge
31 different contexts
32 digraph problems
33 edge
34 et al
35 experimental observations
36 false negatives
37 false-positive inferences
38 general graphs
39 goal
40 graph
41 idea
42 inference
43 integers
44 linear time
45 negatives
46 network
47 observations
48 paper
49 polynomial time algorithm
50 positive inferences
51 previous results
52 problem
53 ratio
54 reduction
55 reduction problem
56 results
57 set
58 signal transduction networks
59 special case
60 time
61 time algorithm
62 transduction networks
63 transitive reduction
64 schema:name Inferring (Biological) Signal Transduction Networks via Transitive Reductions of Directed Graphs
65 schema:pagination 129-159
66 schema:productId N3220f1d84bcc46e4a17e47582abdedad
67 N90e4e0a69b514b67ab0d3ee4396e387d
68 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026603604
69 https://doi.org/10.1007/s00453-007-9055-0
70 schema:sdDatePublished 2022-05-20T07:24
71 schema:sdLicense https://scigraph.springernature.com/explorer/license/
72 schema:sdPublisher N92bebada77db4076b7801781e050c291
73 schema:url https://doi.org/10.1007/s00453-007-9055-0
74 sgo:license sg:explorer/license/
75 sgo:sdDataset articles
76 rdf:type schema:ScholarlyArticle
77 N3220f1d84bcc46e4a17e47582abdedad schema:name doi
78 schema:value 10.1007/s00453-007-9055-0
79 rdf:type schema:PropertyValue
80 N3ca66a8f9187463fbdbf943afe5797c0 schema:issueNumber 2
81 rdf:type schema:PublicationIssue
82 N58f3a27e727b4a72bca8b0acf556b161 rdf:first sg:person.0763403270.10
83 rdf:rest Nf1dbf0def8124f6da67ae86b92ab8ce0
84 N86587d8ed8bf4e3992a4fd7bc789f361 rdf:first sg:person.01017036620.03
85 rdf:rest N58f3a27e727b4a72bca8b0acf556b161
86 N90e4e0a69b514b67ab0d3ee4396e387d schema:name dimensions_id
87 schema:value pub.1026603604
88 rdf:type schema:PropertyValue
89 N92bebada77db4076b7801781e050c291 schema:name Springer Nature - SN SciGraph project
90 rdf:type schema:Organization
91 Nb651ed305e384161b4c4ed5bff5f9272 rdf:first sg:person.0714217520.83
92 rdf:rest rdf:nil
93 Nbfd6ecd507d24c1f9a64371ac340aad3 schema:volumeNumber 51
94 rdf:type schema:PublicationVolume
95 Nf1dbf0def8124f6da67ae86b92ab8ce0 rdf:first sg:person.013111453243.48
96 rdf:rest Nb651ed305e384161b4c4ed5bff5f9272
97 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
98 schema:name Information and Computing Sciences
99 rdf:type schema:DefinedTerm
100 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
101 schema:name Computation Theory and Mathematics
102 rdf:type schema:DefinedTerm
103 sg:grant.3044434 http://pending.schema.org/fundedItem sg:pub.10.1007/s00453-007-9055-0
104 rdf:type schema:MonetaryGrant
105 sg:journal.1047644 schema:issn 0178-4617
106 1432-0541
107 schema:name Algorithmica
108 schema:publisher Springer Nature
109 rdf:type schema:Periodical
110 sg:person.01017036620.03 schema:affiliation grid-institutes:grid.29857.31
111 schema:familyName Albert
112 schema:givenName Réka
113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01017036620.03
114 rdf:type schema:Person
115 sg:person.013111453243.48 schema:affiliation grid-institutes:grid.33236.37
116 schema:familyName Dondi
117 schema:givenName Riccardo
118 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013111453243.48
119 rdf:type schema:Person
120 sg:person.0714217520.83 schema:affiliation grid-institutes:grid.430387.b
121 schema:familyName Sontag
122 schema:givenName Eduardo
123 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0714217520.83
124 rdf:type schema:Person
125 sg:person.0763403270.10 schema:affiliation grid-institutes:grid.185648.6
126 schema:familyName DasGupta
127 schema:givenName Bhaskar
128 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0763403270.10
129 rdf:type schema:Person
130 sg:pub.10.1007/11764298_23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013605920
131 https://doi.org/10.1007/11764298_23
132 rdf:type schema:CreativeWork
133 sg:pub.10.1007/978-1-4613-1161-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014027374
134 https://doi.org/10.1007/978-1-4613-1161-4
135 rdf:type schema:CreativeWork
136 sg:pub.10.1038/nature02555 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011649705
137 https://doi.org/10.1038/nature02555
138 rdf:type schema:CreativeWork
139 grid-institutes:grid.185648.6 schema:alternateName Department of Computer Science, University of Illinois at Chicago, 60607, Chicago, IL, USA
140 schema:name Department of Computer Science, University of Illinois at Chicago, 60607, Chicago, IL, USA
141 rdf:type schema:Organization
142 grid-institutes:grid.29857.31 schema:alternateName Department of Physics, Pennsylvania State University, 16802, University Park, PA, USA
143 schema:name Department of Physics, Pennsylvania State University, 16802, University Park, PA, USA
144 rdf:type schema:Organization
145 grid-institutes:grid.33236.37 schema:alternateName Dipartimento di Scienze dei Linguaggi, della Comunicazione e degli Studi Culturali, Università degli Studi di Bergamo, 24129, Bergamo, Italy
146 schema:name Dipartimento di Scienze dei Linguaggi, della Comunicazione e degli Studi Culturali, Università degli Studi di Bergamo, 24129, Bergamo, Italy
147 rdf:type schema:Organization
148 grid-institutes:grid.430387.b schema:alternateName Department of Mathematics, Rutgers University, 08903, New Brunswick, NJ, USA
149 schema:name Department of Mathematics, Rutgers University, 08903, New Brunswick, NJ, USA
150 rdf:type schema:Organization
 




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


...