In this survey paper, we will present a number of core algorithmic questions concerning several transitive reduction problems on network that have applications in network synthesis and analysis involving cellular processes. Our starting point will be the so-called minimum equivalent digraph problem, a classic computational problem in combinatorial algorithms. We will subsequently consider a few non-trivial extensions or generalizations of this problem motivated by applications in systems biology. We will then discuss the applications of these algorithmic methodologies in the context of three major biological research questions: synthesizing and simplifying signal transduction networks, analyzing disease networks, and measuring redundancy of biological networks.
References
[1]
Moyles, D.M.; Thompson, G.L. Finding a minimum equivalent of a digraph. J. ACM 1969, 16, 455–460, doi:10.1145/321526.321534.
[2]
Garey, M.R.; Johnson, D.S. Computers and Intractability—A Guide to the Theory of NP-Completeness; W. H. Freeman & Co.: New York, NY, USA, 1979.
[3]
Aho, A.; Garey, M.R.; Ullman, J.D. The transitive reduction of a directed graph. SIAM J. Comput. 1972, 1, 131–137, doi:10.1137/0201008.
[4]
Albert, R.; DasGupta, B.; Dondi, R.; Sontag, E.D. Inferring (Biological) signal transduction networks via transitive reductions of directed graphs. Algorithmica 2008, 51, 129–159, doi:10.1007/s00453-007-9055-0.
[5]
Albert, R.; DasGupta, B.; Dondi, R.; Kachalo, S.; Sontag, E.D.; Zelikovsky, A.; Westbrooks, K. A novel method for signal transduction network inference from indirect experimental evidence. J. Comput. Biol. 2007, 14, 927–949, doi:10.1089/cmb.2007.0015.
[6]
Kachalo, S.; Zhang, R.; Sontag, E.D.; Albert, R.; DasGupta, B. NET-SYNTHESIS: A software for synthesis, inference and simplification of signal transduction networks. Bioinformatics 2008, 24, 293–295, doi:10.1093/bioinformatics/btm571.
[7]
Albert, R.; DasGupta, B.; Sontag, E.D. Inference of Signal Transduction Networks from Double Causal Evidence. In Methods in Molecular Biology: Topics in Computational Biology; Fenyo, D., Ed.; Springer Science + Business Media, LLC: New York, NY, USA, 2010; Volume 673.
[8]
Cormen, T.H.; Leiserson, C.E.; Rivest, R.L.; Stein, C. Introduction to Algorithms; MIT Press: Cambridge, MA, USA, 2001.
[9]
Gusfield, D. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology; Cambridge University Press: New York, NY, USA, 1997.
[10]
Pevzner, P.A. Computational Molecular Biology: An Algorithmic Approach; MIT Press: Cambridge, MA, USA, 2000.
[11]
Khuller, S.; Raghavachari, B.; Young, N. Approximating the minimum equivalent digraph. SIAM J. Comput. 1995, 24, 859–872, doi:10.1137/S0097539793256685.
[12]
Vetta, A. Approximating the minimum strongly connected subgraph via a matching lower bound. In Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms, Washington, DC, USA, 7–9 January 2001; pp. 417–426.
[13]
Berman, P.; DasGupta, B.; Karpinski, M. Approximating transitive reduction problems for directed networks. In Proceedings of the 11th Algorithms and Data Structures Symposium, Banff, AB, Canada, 21–23 August 2009; pp. 74–85.
[14]
Frederickson, G.N.; JàJà, J. Approximation algorithms for several graph augmentation problems. SIAM J. Comput. 1981, 10, 270–283, doi:10.1137/0210019.
[15]
Edmonds, J. Optimum branchings. In Mathematics and the Decision Sciences, Part 1; Dantzig, G.B., Veinott, A.F., Jr., Eds.; American Mathematical Society Lectures on Applied Mathematics: Providence, RI, USA, 1968; pp. 335–345.
[16]
Karp, R.M. A simple derivation of Edmonds’ algorithm for optimum branching. Networks 1972, 1, 265–272, doi:10.1002/net.3230010305.
[17]
Milanovíc, M.; Matíc, D.; Savíc, A.; Kratica, J. Two metaheuristic approaches to solving the p-ary transitive reduction problem. Appl. Comput. Math. 2011, 10, 294–308.
[18]
Papadimitriou, C. Computational Complexity; Addison-Wesley: New York, NY, USA, 1994; p. 212.
[19]
Khuller, S.; Raghavachari, B.; Young, N. On strongly connected digraphs with bounded cycle length. Discret. Appl. Math. 1996, 69, 281–289, doi:10.1016/0166-218X(95)00105-Z.
[20]
Chu, Y.; Liu, T. On the shortest arborescence of a directed graph. Sci. Sin. 1965, 4, 1396–1400.
[21]
Vazirani, V. Approximation Algorithms; Springer: New York, NY, USA, 2001.
[22]
Aho, A.; Hopcroft, J.E.; Ullman, J.D. The Design and Analysis of Computer Algorithms; Addison-Wesley: Reading, MA, USA, 1974.
[23]
Dubois, V.; Bothorel, C. Transitive reduction for social network analysis and visualization. In Proceedings of the IEEE/WIC/ACM International Conference on Web Intelligence, Compiègne, France, 19–22 September 2005; pp. 128–131.
[24]
Ma’ayan, A.; Jenkins, S.L.; Neves, S.; Hasseldine, A.; Grace, E.; Dubin-Thaler, B.; Eungdamrong, N.J.; Weng, G.; Ram, P.T.; Rice, J.J.; et al. Formation of regulatory patterns during signal propagation in a mammalian cellular network. Science 2005, 309, 1078–1083, doi:10.1126/science.1108876.
Giot, L.; Bader, J.S.; Brouwer, C.; Chaudhuri, A.; Kuang, B.; Li, Y.; Hao, Y.L.; Ooi, C.E.; Godwin, B.; Vitols, E.; et al. A protein interaction map of Drosophila melanogaster. Science 2003, 302, 1727–1736, doi:10.1126/science.1090289.
[30]
Han, J.-D.J.; Bertin, N.; Hao, T.; Goldberg, D.S.; Berriz, G.F.; Zhang, L.V.; Dupuy, D.; Walhout, A.J.M.; Cusick, M.E.; Roth, F.P.; et al. Evidence for dynamically organized modularity in the yeast protein-protein interaction network. Nature 2004, 430, 88–93, doi:10.1038/nature02555.
[31]
Li, S.; Armstrong, C.M.; Bertin, N.; Ge, H.; Milstein, S.; Boxem, M.; Vidalain, P.-O.; Han, J.-D.J.; Chesneau, A.; Hao, T.; et al. A map of the interactome network of the metazoan C. elegans. elegans. Science 2004, 303, 540–543.
[32]
Friedman, C.; Kra, P.; Yu, H.; Krauthammer, M.; Rzhetsky, A. GENIES: A natural-language processing system for the extraction of molecular pathways from journal articles. Bioinformatics 2001, 17, S74–S82, doi:10.1093/bioinformatics/17.suppl_1.S74.
[33]
Alberts, B. Molecular Biology of the Cell; Garland Publishing: New York, NY, USA, 1994.
[34]
Hetherington, A.M.; Woodward, F.I. The role of stomata in sensing and driving environmental change. Nature 2003, 424, 901–908, doi:10.1038/nature01843.
Blatt, M.R.; Grabov, A. Signal redundancy, gates and integration in the control of ion channels for stomatal movement. J. Exp. Bot. 1997, 48, 529–537, doi:10.1093/jxb/48.Special_Issue.529.
[37]
MacRobbie, E.A. Signal transduction and ion channels in guard cells. Philos. Trans. R. Soc. Lond. BBiol. Sci. 1998, 353, 1475–1488, doi:10.1098/rstb.1998.0303.
[38]
Li, S.; Assmann, S.M.; Albert, A. Predicting essential components of signal transduction networks: A dynamic model of guard cell abscisic acid signaling. PLoS Biol. 2006, doi:10.1371/journal.pbio.0040312.
[39]
Zhang, R.; Shah, M.V.; Yang, J.; Nyland, S.B.; Liu, X.; Yun, J.K.; Albert, R.; Loughran, T.P. Network model of survival signaling in LGL leukemia. Proc. Natl. Acad. Sci. USA 2008, 105, 16308–16313, doi:10.1073/pnas.0806447105.
[40]
Albert, R.; DasGupta, B.; Mobasheri, N. Some perspectives on network modeling in therapeutic target prediction. Biomed. Eng. Computat. Biol. 2013, 5, 17–24.
[41]
Kafri, R.; Bar-Even, A.; Pilpel, Y. Transcription control reprogramming in genetic backup circuits. Nat. Genet. 2005, 37, 295–299, doi:10.1038/ng1523.
[42]
Kolb, B.; Whishaw, I.Q. Fundamentals of Human Neuropsychology; Freeman: New York, NY, USA, 1996.
[43]
Tononi, G.; Sporns, O.; Edelman, G.M. Measures of degeneracy and redundancy in biological networks. Proc. Natl. Acad. Sci. USA 1999, 96, 3257–3262, doi:10.1073/pnas.96.6.3257.
[44]
Papin, A.; Palsson, B.O. Topological analysis of mass-balanced signaling networks: A framework to obtain network properties including crosstalk. J. Theor. Biol. 2004, 227, 283–297, doi:10.1016/j.jtbi.2003.11.016.
[45]
Beckage, N.; Smith, L.; Hills, T. Semantic network connectivity is related to vocabulary growth rate in children. In Proceedings of the 32nd Annual Conference of the Cognitive Science Society, Portland, OR, USA, 11–14 August 2010; pp. 2769–2774.
[46]
Dall’Astaa, L.; Alvarez-Hamelina, I.; Barrata, A.; Vázquezb, A.; Vespignania, A. Exploring networks with traceroute-like probes: Theory and simulations. Theor. Comput. Sci. 2006, 355, 6–24, doi:10.1016/j.tcs.2005.12.009.
[47]
Albert, R.; DasGupta, B.; Gitter, A.; Gürsoy, G.; Hegde, R.; Pal, P.; Sivanathan, G.S.; Sontag, E.D. A new computationally efficient measure of topological redundancy of biological and social networks. Phys. Rev. E 2011, 84, 036117, doi:10.1103/PhysRevE.84.036117.
[48]
Wagner, A. Estimating coarse gene network structure from large-scale gene perturbation data. Genome Res. 2002, 12, 309–315, doi:10.1101/gr.193902.
[49]
Chen, T.; Filkov, V.; Skiena, S. Identifying gene regulatory networks from experimental data. In Proceedings of the 3rd Annual International Conference on Computational Molecular Biology, Lyon, France, 11–14 April 1999; pp. 94–103.
[50]
Klamt, S.; Flassig, R.J.; Sundmacher, K. Transwesd: Inferring cellular networks with transitive reduction. Bioinformatics 2010, 26, 2160–2168, doi:10.1093/bioinformatics/btq342.
[51]
Bosnacki, D.; Odenbrett, M.R.; Wijs, A.; Ligtenberg, W.; Hilbers, P. Efficient reconstruction of biological networks via transitive reduction on general purpose graphics processors. BMC Bioinform. 2012, 13, 281, doi:10.1186/1471-2105-13-281.
[52]
Feizi, S.; Marbach, D.; Médard, M.; Kellis, M. Network deconvolution as a general method to distinguish direct dependencies in networks. Nat. Biotechnol. 2011, 31, 726–733.
