Hostname: page-component-78c5997874-j824f Total loading time: 0 Render date: 2024-11-05T19:47:24.579Z Has data issue: false hasContentIssue false
  • English
  • Français

Node-independent elementary signaling modes: A measure of redundancy in Boolean signaling transduction networks

Published online by Cambridge University Press:  21 April 2016

ZHONGYAO SUN  and
RÉKA ALBERT
ZHONGYAO SUN
Affiliation:
Department of Physics, The Pennsylvania State University, University Park, PA 16802, USA (e-mail: [email protected])
RÉKA ALBERT
Affiliation:
Department of Physics, The Pennsylvania State University, University Park, PA 16802, USA (e-mail: [email protected]) Department of Biology, The Pennsylvania State University, University Park, PA 16802, USA (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

The redundancy of a system denotes the amount of duplicate components or mechanisms in it. For a network, especially one in which mass or information is being transferred from an origin to a destination, redundancy is related to the robustness of the system. Existing network measures of redundancy rely on local connectivity (e.g. clustering coefficients) or the existence of multiple paths. As in many systems there are functional dependencies between components and paths, a measure that not only characterizes the topology of a network, but also takes into account these functional dependencies, becomes most desirable.

We propose a network redundancy measure in a prototypical model that contains functionally dependent directed paths: a Boolean model of a signal transduction network. The functional dependencies are made explicit by using an expanded network and the concept of elementary signaling modes (ESMs). We define the redundancy of a Boolean signal transduction network as the maximum number of node-independent ESMs and develop a methodology for identifying all maximal node-independent ESM combinations. We apply our measure to a number of signal transduction network models and show that it successfully distills known properties of the systems and offers new functional insights. The concept can be easily extended to similar related forms, e.g. edge-independent ESMs.

Keywords

signal transduction networksignaling networkBoolean networkfunctional dependencyelementary signaling modenetwork redundancy
Type
Research Article
Information
Network Science , Volume 4 , Issue 3 , September 2016 , pp. 273 - 292
Copyright
Copyright © Cambridge University Press 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Adelson-Velsky, G. M., Gelbukh, A., & Levner, E. (2002). On fast path-finding algorithms in AND-OR graphs. Mathematical Problems in Engineering, 8 (4/5), 283–293.Google Scholar
Adelson-Velsky, G. M., & Levner, E. (2002). Project scheduling in AND-OR graphs: A generalization of Dijkstra's algorithm. Mathematics of Operations Research, 27 (3), 504–517.Google Scholar
Albert, R., & Othmer, H. G. (2003). The topology of the regulatory interactions predicts the expression pattern of the segment polarity genes in Drosophila melanogaster. Journal of Theoretical Biology, 223, 1–18.CrossRefGoogle ScholarPubMed
Albert, R., & Thakar, J. (2014). Boolean modeling: A logic-based dynamic approach for understanding signaling and regulatory networks and for making useful predictions. Wiley Interdisciplinary Reviews Systems Biology and Medicine, 6, 353–369.CrossRefGoogle ScholarPubMed
Balabanian, N., & Carlson, B. (2001). Digital logic design principles (pp. 39–40). New York: John Wiley. ISBN 978-0-471-29351-4.Google Scholar
Bondy, J. A., & Murty, U. S. R. (1976). Graph theory with applications (pp. 131–133). New York: Elsevier Science Publishing Co., Inc.Google Scholar
Bron, C., & Kerbosch, J. (1973). Algorithm 457: Finding all cliques of an undirected graph. Communications of the ACM, 16 (9), 575–577.Google Scholar
Buldyrev, S., Parshani, R., Paul, G., Stanley, H. E., & Havlin, S. (2010). Catastrophic cascade of failures in interdependent networks. Nature, 464, 1025–1028.CrossRefGoogle ScholarPubMed
Camarinha-Matos, L. M., & Afsarmanesh, H. (2003). Elements of a base VE infrastructure. Journal of Computers in Industry, 51 (2), 139–163.Google Scholar
Cazals, F., & Karande, C. (2008). A note on the problem of reporting maximal cliques. Theoretical Computer Science, 407 (1–3), 564–568.Google Scholar
Dinic, E. A. (1990). The fastest algorithm for PERT problem with AND- and OR-nodes. In Proceedings of Integer Programming/Combinatorial Optimization Conference (IPCO) (pp. 185–187). Waterloo: University of Waterloo Press.Google Scholar
Ford, L. R., & Fulkerson, D. R. (1956). Maximal flow through a network. Canadian Journal of Mathematics, 8, 399.Google Scholar
Goemann, B., Wingender, E., & Potapov, A. P. (2009). An approach to evaluate the topological significance of motifs and other patterns in regulatory networks. BMC Systems Biology, 3, 53.Google Scholar
Goldberg, A. V., & Tarjan, R. E. (1986). A new approach to the maximum flow problem. Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing - STOC '86 (p. 136). New York, NY, USA.Google Scholar
Hagberg, A. A., Schult, D. A., & Swart, P. J. (2008). Exploring network structure, dynamics, and function using NetworkX. In Varoquaux, G., Vaught, T., & Millman, J. (Eds.), Proceedings of the 7th Python in Science Conference (SciPy2008) (pp. 11–15). Pasadena, CA USA.Google Scholar
Kato, M., Hata, N., Banerjee, N., Futcher, B., & Zhang, M. Q. (2004). Identifying combinatorial regulation of transcription factors and binding motifs. Genome Biology, 5, R56.Google Scholar
Klamt, S., Saez-Rodriguez, J., & Gilles, E. D. (2007). Structural and functional analysis of cellular networks with CellNetAnalyzer. BMC Systems Biology, 1, 2.Google Scholar
Klamt, S., Saez-Rodriguez, J., Lindquist, J. A., Simeoni, L., & Gilles, E. D. (2006). A methodology for the structural and functional analysis of signaling and regulatory networks. BMC Bioinformatics, 7, 56.Google Scholar
Li, S., Assmann, S. M., & Albert, R. (2006). Predicting essential components of signal transduction networks: A dynamic model of guard cell abscisic acid signaling. PLoS Biology, 4, e312.Google Scholar
Lipshtat, A., Purushothaman, S. P., Iyengar, R. & Ma'ayan, A. (2008). Functions of bifans in context of multiple regulatory motifs in signaling networks. Biophysical Journal, 94, 14.Google Scholar
Ma'ayan, A., Jenkins, S. L., Neves, S., Hasseldine, A., Grace, E., Dubin-Thaler, B., . . . Iyengar, R. (2005). Formation of regulatory patterns during signal propagation in a Mammalian cellular network. Science, 309, 1078–1083.Google Scholar
Martínez-Sosa, P., & Mendoza, L. (2013). The regulatory network that controls the differentiation of T lymphocytes. Bio Systems, 8, 96–103.Google Scholar
Menger, K. (1927). Zur allgemeinen Kurventheorie. Fundamenta Mathematicae, 10, 96–115.CrossRefGoogle Scholar
Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., & Alon, U. (2002). Network motifs: Simple building blocks of complex networks. Science, 298, 824–827.Google Scholar
Miskov-Zivanov, N., Turner, M. S., Kane, L. P., Morel, P. A., & Faeder, J. R. (2013). The duration of T cell stimulation is a critical determinant of cell fate and plasticity. Science Signaling, 6, ra97.Google Scholar
Parshani, R., Buldyrev, S. V., & Havlin, S. (2011). Critical effect of dependency groups on the function of networks. PNAS USA, 108 (3), 1007–1010.Google Scholar
Rajaraman, & Radhakrishnan, (2004). Introduction To Digital Computer Design An 5Th Ed. (p. 65). New Delhi, India: PHI Learning Pvt. Ltd. ISBN 978-81-203-3409-0.Google Scholar
Remenyi, A., Scholer, H. R., & Wilmanns, M. (2004). Combinatorial control of gene expression. Nature Structural & Molecular Biology, 11 (9), 812–815.Google Scholar
Saez-Rodriguez, J., Simeoni, L., Lindquist, J. A., Hemenway, R., Bommhardt, U., Arndt, B., . . . Schraven, B. (2007). A logical model provides insights into T cell receptor signaling. PLoS Computational Biology, 3, e163.CrossRefGoogle ScholarPubMed
Samaga, R., Saez-Rodriguez, J., Alexopoulos, L. G., Sorger, P. K., & Klamt, S. (2009). The logic of EGFR/ErbB signaling: Theoretical properties and analysis of high-throughput data. PLoS Computational Biology, 5, e1000438.Google Scholar
Steinway, S. N., Zanudo, J. G., Ding, W., Rountree, C. B., Feith, D. J., Loughran, T.P. Jr., & Albert, R. (2014). Network modeling of TGFbeta signaling in hepatocellular carcinoma epithelial-to-mesenchymal transition reveals joint sonic hedgehog and Wnt pathway activation. Cancer Research, 74, 5963–5977.CrossRefGoogle ScholarPubMed
Steinway, S. N., Zanudo, J. G., Michel, P. J., Feith, D. J., Loughran, T. P., & Albert, R. (2015). Combinatorial interventions inhibit TGFβ-driven epithelial-to-mesenchymal transition and support hybrid cellular phenotypes. npj Systems Biology and Applications, 1, 15014.Google Scholar
Sun, Z., Jin, X., Albert, R., & Assmann, S. M. (2014). Multi-level modeling of light-induced stomatal opening offers new insights into its regulation by drought. PLoS Computational Biology, 10, e1003930.Google Scholar
Thakar, J., Pilione, M., Kirimanjeswara, G., Harvill, E. T., & Albert, R. (2007). Modeling systems-level regulation of host immune responses. PLoS Computational Biology, 3, e109.Google Scholar
Tomita, E., Tanaka, A., & Takahashi, H. (2006). The worst-case time complexity for generating all maximal cliques and computational experiments. Theoretical Computer Science, 363 (1), 28–42. Computing and Combinatorics, 10th Annual International Conference on Computing and Combinatorics (COCOON 2004).Google Scholar
Wang, R. S., & Albert, R. (2011). Elementary signaling modes predict the essentiality of signal transduction network components. BMC Systems Biology, 5, 44.Google Scholar
Wang, R., Sun, Z., & Albert, R. (2013). Minimal functional routes in directed graphs with dependent edges. International Transactions in Operational Research, 20, 19.CrossRefGoogle Scholar
Wunderlich, Z., & Mirny, L. A. (2006). Using the topology of metabolic networks to predict viability of mutant strains. Biophys J., 91, 2304–2311.CrossRefGoogle ScholarPubMed
Zanudo, J. G., & Albert, R. (2013). An effective network reduction approach to find the dynamical repertoire of discrete dynamic networks. Chaos, 23, 025111.Google Scholar
Zhang, R., Shah, M. V., Yang, J., Nyland, S. B., Liu, X. et al. (2008). Network model of survival signaling in large granular lymphocyte leukemia. Proceedings of the National Academy of Sciences of the United States of America, 105, 16308–16313.Google Scholar