Stratification and enumeration of Boolean functions by canalizing depth

• The kk-canalizing functions generalize both canalizing and nested canalizing functions.
• Every Boolean function has a unique extended monomial form and core polynomial.
• We enumerate the nn-variable Boolean functions with canalizing depth kk.

Boolean network models have gained popularity in computational systems biology over the last dozen years. Many of these networks use canalizing Boolean functions, which has led to increased interest in the study of these functions. The canalizing depth of a function describes how many canalizing variables can be recursively “picked off”, until a non-canalizing function remains. In this paper, we show how every Boolean function has a unique algebraic form involving extended monomial layers and a well-defined core polynomial. This generalizes recent work on the algebraic structure of nested canalizing functions, and it yields a stratification of all   Boolean functions by their canalizing depth. As a result, we obtain closed formulas for the number of nn-variable Boolean functions with depth kk, which simultaneously generalizes enumeration formulas for canalizing, and nested canalizing functions.