The number of multistate nested canalyzing functions

David Murrugarra, Reinhard Laubenbacher

Research output: Contribution to journalArticlepeer-review

16 Scopus citations


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. The principal tool used for this investigation is a description of these functions as polynomials and a parametrization of the class of all such polynomials in terms of relations on their coefficients. This parametrization can also be used for the purpose of network reverse-engineering using only nested canalyzing functions.

Original languageEnglish
Pages (from-to)929-938
Number of pages10
JournalPhysica D: Nonlinear Phenomena
Issue number10
StatePublished - May 15 2012

Bibliographical note

Funding Information:
The authors were partially supported by grants NSF CMMI-0908201 and ARO 56757-MA . They thank Alan Veliz-Cuba, Abdul Jarrah, and Henderson Wallace for helpful discussions during the research phase. And thanks are due to the anonymous reviewers for many suggestions that improved the article.


  • Formula
  • Multistate
  • Nested canalyzing functions
  • Regulatory logic

ASJC Scopus subject areas

  • Statistical and Nonlinear Physics
  • Mathematical Physics
  • Condensed Matter Physics
  • Applied Mathematics


Dive into the research topics of 'The number of multistate nested canalyzing functions'. Together they form a unique fingerprint.

Cite this