{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,2]],"date-time":"2025-12-02T15:17:32Z","timestamp":1764688652539},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2007,10,9]],"date-time":"2007-10-09T00:00:00Z","timestamp":1191888000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2008,6]]},"DOI":"10.1007\/s00453-007-9055-0","type":"journal-article","created":{"date-parts":[[2007,10,8]],"date-time":"2007-10-08T16:35:02Z","timestamp":1191861302000},"page":"129-159","source":"Crossref","is-referenced-by-count":19,"title":["Inferring (Biological) Signal Transduction Networks via\u00a0Transitive Reductions of Directed Graphs"],"prefix":"10.1007","volume":"51","author":[{"given":"R\u00e9ka","family":"Albert","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bhaskar","family":"DasGupta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Riccardo","family":"Dondi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eduardo","family":"Sontag","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,10,9]]},"reference":[{"issue":"2","key":"9055_CR1","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1137\/0201008","volume":"1","author":"A. Aho","year":"1972","unstructured":"Aho, A., Garey, M.R., Ullman, J.D.: The transitive reduction of a directed graph. SIAM J. Comput. 1(2), 131\u2013137 (1972)","journal-title":"SIAM J. Comput."},{"key":"9055_CR2","volume-title":"Molecular Biology of the Cell","author":"B. Alberts","year":"1994","unstructured":"Alberts, B.: Molecular Biology of the Cell. Garland, New York (1994)"},{"key":"9055_CR3","first-page":"1396","volume":"4","author":"Y. Chu","year":"1965","unstructured":"Chu, Y., Liu, T.: On the shortest arborescence of a directed graph. Sci. Sin. 4, 1396\u20131400 (1965)","journal-title":"Sci. Sin."},{"key":"9055_CR4","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge (2001)"},{"key":"9055_CR5","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1007\/11764298_23","volume-title":"5th International Workshop Experimental Algorithms","author":"B. DasGupta","year":"2006","unstructured":"DasGupta, B., Enciso, G.A., Sontag, E.D., Zhang, Y.: Algorithmic and complexity results for decompositions of biological networks into monotone subsystems. In: 5th International Workshop Experimental Algorithms. LNCS, vol. 4007, pp. 253\u2013264. Springer, Berlin (2006)"},{"key":"9055_CR6","doi-asserted-by":"crossref","first-page":"16314","DOI":"10.1073\/pnas.252461999","volume":"99","author":"R. Desikan","year":"2002","unstructured":"Desikan, R., Griffiths, R., Hancock, J., Neill, S.: A new role for an old enzyme: nitrate reductase-mediated nitric oxide generation is required for abscisic acid-induced stomatal closure in Arabidopsis thaliana. Proc. Natl. Acad. Sci. USA 99, 16314\u201316318 (2002)","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"9055_CR7","series-title":"Am. Math. Soc. Lectures Appl. Math.","first-page":"335","volume-title":"Mathematics and the Decision Sciences, Part 1","author":"J. Edmonds","year":"1968","unstructured":"Edmonds, J.: Optimum branchings. In: Dantzig, G.B. (ed.) Mathematics and the Decision Sciences, Part 1. Am. Math. Soc. Lectures Appl. Math., vol. 11, pp. 335\u2013345. Am. Math. Soc., Providence (1968)"},{"key":"9055_CR8","volume-title":"Computational Cell Biology","author":"C.P. Fall","year":"2002","unstructured":"Fall, C.P., Marland, E.S., Wagner, J.M., Tyson, J.J.: Computational Cell Biology. Springer, New York (2002)"},{"issue":"2","key":"9055_CR9","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1137\/0210019","volume":"10","author":"G.N. Frederickson","year":"1981","unstructured":"Frederickson, G.N., J\u00e0J\u00e0, J.: Approximation algorithms for several graph augmentation problems. SIAM J. Comput. 10(2), 270\u2013283 (1981)","journal-title":"SIAM J. Comput."},{"key":"9055_CR10","doi-asserted-by":"crossref","first-page":"1727","DOI":"10.1126\/science.1090289","volume":"302","author":"L. Giot","year":"2003","unstructured":"Giot, L., Bader, J.S., et al.: A protein interaction map of Drosophila melanogaster. Science 302, 1727\u20131736 (2003)","journal-title":"Science"},{"key":"9055_CR11","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1038\/nature02555","volume":"430","author":"J.D. Han","year":"2004","unstructured":"Han, J.D., Bertin, N., et al.: Evidence for dynamically organized modularity in the yeast protein-protein interaction network. Nature 430, 88\u201393 (2004)","journal-title":"Nature"},{"key":"9055_CR12","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-1161-4","volume-title":"The Regulation of Cellular Systems","author":"R. Heinrich","year":"1996","unstructured":"Heinrich, R., Schuster, S.: The Regulation of Cellular Systems. Chapman & Hall, New York (1996)"},{"issue":"4","key":"9055_CR13","doi-asserted-by":"crossref","first-page":"859","DOI":"10.1137\/S0097539793256685","volume":"24","author":"S. Khuller","year":"1995","unstructured":"Khuller, S., Raghavachari, B., Young, N.: Approximating the minimum equivalent digraph. SIAM J. Comput. 24(4), 859\u2013872 (1995)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9055_CR14","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/0166-218X(95)00105-Z","volume":"69","author":"S. Khuller","year":"1996","unstructured":"Khuller, S., Raghavachari, B., Young, N.: On strongly connected digraphs with bounded cycle length. Discrete Appl. Math. 69(3), 281\u2013289 (1996)","journal-title":"Discrete Appl. Math."},{"key":"9055_CR15","unstructured":"Khuller, S., Raghavachari, B., Zhu, A.: A uniform framework for approximating weighted connectivity problems. In: 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 937\u2013938, 1999"},{"key":"9055_CR16","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"E. Lawler","year":"2000","unstructured":"Lawler, E.: Combinatorial Optimization: Networks and Matroids. Dover, New York (2000)"},{"key":"9055_CR17","doi-asserted-by":"crossref","first-page":"799","DOI":"10.1126\/science.1075090","volume":"298","author":"T.I. Lee","year":"2002","unstructured":"Lee, T.I., Rinaldi, N.J., et al.: Transcriptional regulatory networks in Saccharomyces cerevisiae. Science 298, 799\u2013804 (2002)","journal-title":"Science"},{"key":"9055_CR18","doi-asserted-by":"crossref","first-page":"540","DOI":"10.1126\/science.1091403","volume":"303","author":"S. Li","year":"2004","unstructured":"Li, S., Armstrong, C.M., et al.: A map of the interactome network of the metazoan C. elegans. Science 303, 540\u2013543 (2004)","journal-title":"Science"},{"key":"9055_CR19","doi-asserted-by":"crossref","unstructured":"Li, S., Assmann, S.M., Albert, R.: Predicting essential components of signal transduction networks: a dynamic model of guard cell signaling. PLoS Biology 4(10) (October 2006)","DOI":"10.1371\/journal.pbio.0040312"},{"key":"9055_CR20","doi-asserted-by":"crossref","first-page":"3089","DOI":"10.1105\/tpc.007906","volume":"14","author":"A.C. Mustilli","year":"2002","unstructured":"Mustilli, A.C., Merlot, S., Vavasseur, A., Fenzi, F., Giraudat, J.: Arabidopsis OST1 protein kinase mediates the regulation of stomatal aperture by abscisic acid and acts upstream of reactive oxygen species production. Plant Cell 14, 3089\u20133099 (2002)","journal-title":"Plant Cell"},{"key":"9055_CR21","doi-asserted-by":"crossref","first-page":"1616","DOI":"10.1105\/tpc.020321","volume":"16","author":"S. Pandey","year":"2004","unstructured":"Pandey, S., Assmann, S.M.: The Arabidopsis putative G protein-coupled receptor GCR1 interacts with the G protein alpha subunit GPA1 and regulates abscisic acid signaling. Plant Cell 16, 1616\u20131632 (2004)","journal-title":"Plant Cell"},{"key":"9055_CR22","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1049\/sb:20045006","volume":"1","author":"E.D. Sontag","year":"2004","unstructured":"Sontag, E.D.: Some new directions in control theory inspired by systems biology. Syst. Biol. 1, 9\u201318 (2004)","journal-title":"Syst. Biol."},{"key":"9055_CR23","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1002\/net.3230070103","volume":"7","author":"R. Tarjan","year":"1977","unstructured":"Tarjan, R.: Finding optimum branchings. Networks 7, 25\u201335 (1977)","journal-title":"Networks"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9055-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-007-9055-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9055-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:00Z","timestamp":1559137500000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-007-9055-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,10,9]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,6]]}},"alternative-id":["9055"],"URL":"https:\/\/doi.org\/10.1007\/s00453-007-9055-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,10,9]]}}}