The Number of Multistate Nested Canalyzing Functions
arXiv:1108.0206 · doi:10.1016/j.physd.2012.02.011
Abstract
Identifying features of molecular regulatory networks is an important problem in systems biology. It has been shown that the combinatorial logic of such networks can be captured in many cases by special functions called nested canalyzing in the context of discrete dynamic network models. It was also shown that the dynamics of networks constructed from such functions has very special properties that are consistent with what is known about molecular networks, and that simplify analysis. It is important to know how restrictive this class of functions is, for instance for the purpose of network reverse-engineering. This paper contains a formula for the number of such functions and a comparison to the class of all functions. In particular, it is shown that, as the number of variables becomes large, the ratio of the number of nested canalyzing functions to the number of all functions converges to zero. This shows that the class of nested canalyzing functions is indeed very restrictive, indicating that molecular networks have very special properties. The principal tool used for this investigation is a description of these functions as polynomials and a parameterization of the class of all such polynomials in terms of relations on their coefficients.
18 pages, 2 tables
References in corpus (5)
- Random Boolean Network Models and the Yeast Transcriptional Network
- Genetic networks with canalyzing Boolean rules are always stable
- A Mathematical Framework for Agent Based Models of Complex Biological Networks
- The number and probability of canalizing functions
- Regulatory patterns in molecular interaction networks
Cited by in corpus (8)
- Identification of control targets in Boolean molecular network models via computational algebra
- Boolean nested canalizing functions: a comprehensive analysis
- Molecular Network Control Through Boolean Canalization
- Revealing the canalizing structure of Boolean functions: Algorithms and applications
- Quantifying the Total Effect of Edge Interventions in Discrete Multistate Networks
- On Analysis and Generation of some Biologically Important Boolean Functions
- Stratification and enumeration of Boolean functions by canalizing depth
- Dimension Reduction of Large AND-NOT Network Models