Collectively canalizing Boolean functions. (English) Zbl 1533.94092
Summary: This paper studies the mathematical properties of collectively canalizing Boolean functions, a class of functions that has arisen from applications in systems biology. Boolean networks are an increasingly popular modeling framework for regulatory networks, and the class of functions studied here captures a key feature of biological network dynamics, namely that a subset of one or more variables, under certain conditions, can dominate the value of a Boolean function, to the exclusion of all others. These functions have rich mathematical properties to be explored. The paper shows how the number and type of such sets influence a function’s behavior and define a new measure for the canalizing strength of any Boolean function. We further connect the concept of collective canalization with the well-studied concept of the average sensitivity of a Boolean function. The relationship between Boolean functions and the dynamics of the networks they form is important in a wide range of applications beyond biology, such as computer science, and has been studied with statistical and simulation-based methods. But the rich relationship between structure and dynamics remains largely unexplored, and this paper is intended as a contribution to its mathematical foundation.
MSC:
| 94D10 | Boolean functions |
Software:
BooleanCanalizationReferences:
| [1] | Bassler, Kevin E.; Lee, Choongseop; Lee, Yong, Evolution of developmental canalization in networks of competing Boolean nodes, Phys. Rev. Lett., 93, 3, Article 038101 pp. (2004) |
| [2] | Boppana, Ravi B., The average sensitivity of bounded-depth circuits, Inf. Process. Lett., 63, 5, 257-261 (1997) · Zbl 1337.68124 |
| [3] | Cook, Stephen; Dwork, Cynthia; Reischuk, Rüdiger, Upper and lower time bounds for parallel random access machines without simultaneous writes, SIAM J. Comput., 15, 1, 87-97 (1986) · Zbl 0591.68049 |
| [4] | Daniels, Bryan C.; Kim, Hyunju; Moore, Douglas; Zhou, Siyu; Smith, Harrison B.; Karas, Bradley; Kauffman, Stuart A.; Walker, Sara I., Criticality distinguishes the ensemble of biological regulatory networks, Phys. Rev. Lett., 121, 13, Article 138102 pp. (2018) |
| [5] | Dimitrova, Elena; Stigler, Brandilyn; Kadelka, Claus; Murrugarra, David, Revealing the canalizing structure of Boolean functions: algorithms and applications, Automatica, 146, Article 110630 pp. (2022) · Zbl 1533.94090 |
| [6] | Harris, Stephen E.; Sawhill, Bruce K.; Wuensche, Andrew; Kauffman, Stuart, A model of transcriptional regulatory networks based on biases in the observed regulation rules, Complexity, 7, 4, 23-40 (2002) |
| [7] | He, Qijun; Macauley, Matthew, Stratification and enumeration of Boolean functions by canalizing depth, Phys. D: Nonlinear Phenom., 314, 1-8 (2016) · Zbl 1364.94800 |
| [8] | Huang, Hao, Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture, Ann. Math., 190, 3, 949-955 (2019) · Zbl 1427.05116 |
| [9] | Just, Winfried; Shmulevich, Ilya; Konvalina, John, The number and probability of canalizing functions, Phys. D: Nonlinear Phenom., 197, 3-4, 211-221 (2004) · Zbl 1076.94045 |
| [10] | Kadelka, Claus; Kuipers, Jack; Laubenbacher, Reinhard, The influence of canalization on the robustness of Boolean networks, Phys. D: Nonlinear Phenom., 353, 39-47 (2017) · Zbl 1378.94086 |
| [11] | Kadelka, Claus; Li, Yuan; Kuipers, Jack; Adeyeye, John O.; Laubenbacher, Reinhard, Multistate nested canalizing functions and their networks, Theor. Comput. Sci., 675, 1-14 (2017) · Zbl 1370.92049 |
| [12] | Kadelka, Claus; Butrie, Taras-Michael; Hilton, Evan; Kinseth, Jack; Serdarevic, Haris, A meta-analysis of Boolean network models reveals design principles of gene regulatory networks (2020), arXiv preprint |
| [13] | Karlsson, Fredrik; Hörnquist, Michael, Order or chaos in Boolean gene networks depends on the mean fraction of canalizing functions, Phys. A, Stat. Mech. Appl., 384, 2, 747-757 (2007) |
| [14] | Kauffman, Stuart A., Metabolic stability and epigenesis in randomly constructed genetic nets, J. Theor. Biol., 22, 3, 437-467 (1969) |
| [15] | Kauffman, Stuart, The large scale structure and dynamics of gene control circuits: an ensemble approach, J. Theor. Biol., 44, 1, 167-190 (1974) |
| [16] | Kauffman, Stuart; Peterson, Carsten; Samuelsson, Björn; Troein, Carl, Random Boolean network models and the yeast transcriptional network, Proc. Natl. Acad. Sci., 100, 25, 14796-14799 (2003) |
| [17] | Kauffman, Stuart; Peterson, Carsten; Samuelsson, Björn; Troein, Carl, Genetic networks with canalyzing Boolean rules are always stable, Proc. Natl. Acad. Sci., 101, 49, 17102-17107 (2004) |
| [18] | Laubenbacher, Reinhard; Stigler, Brandilyn, A computational algebra approach to the reverse engineering of gene regulatory networks, J. Theor. Biol., 229, 4, 523-537 (2004) · Zbl 1440.92032 |
| [19] | Layne, Lori; Dimitrova, Elena; Macauley, Matthew, Nested canalyzing depth and network stability, Bull. Math. Biol., 74, 2, 422-433 (2012) · Zbl 1237.92027 |
| [20] | Li, Yuan; Adeyeye, John O.; Murrugarra, David; Aguilar, Boris; Laubenbacher, Reinhard, Boolean nested canalizing functions: a comprehensive analysis, Theor. Comput. Sci., 481, 24-36 (2013) · Zbl 1291.92068 |
| [21] | Murrugarra, David; Laubenbacher, Reinhard, The number of multistate nested canalyzing functions, Phys. D: Nonlinear Phenom., 241, 10, 929-938 (2012) · Zbl 1300.92036 |
| [22] | Nisan, Noam, CREW PRAMs and decision trees, SIAM J. Comput., 20, 6, 999-1007 (1991) · Zbl 0737.68028 |
| [23] | Olson Reichhardt, C. J.; Bassler, Kevin E., Canalization and symmetry in Boolean models for genetic regulatory networks, J. Phys. A, Math. Theor., 40, 16, 4339 (2007) · Zbl 1109.92032 |
| [24] | Paul, Elijah; Pogudin, Gleb; Qin, William; Laubenbacher, Reinhard, The dynamics of canalizing Boolean networks, Complexity (2020) · Zbl 1432.92039 |
| [25] | Peixoto, Tiago P., The phase diagram of random Boolean networks with nested canalizing functions, Eur. Phys. J. B, 78, 2, 187-192 (2010) |
| [26] | Shmulevich, Ilya; Kauffman, Stuart A., Activities and sensitivities in Boolean network models, Phys. Rev. Lett., 93, 4, Article 048701 pp. (2004) |
| [27] | Stearns, Richard E.; Ravi, S. S.; Marathe, Madhav V.; Rosenkrantz, Daniel J., Symmetry properties of nested canalyzing functions, Discret. Math. Theor. Comput. Sci., 21 (2019) · Zbl 1445.05113 |
| [28] | Waddington, Conrad H., Canalization of development and the inheritance of acquired characters, Nature, 150, 3811, 563-565 (1942) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
