Stratification and enumeration of Boolean functions by canalizing depth

Abstract

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 n-variable Boolean functions with depth k, which simultaneously generalizes enumeration formulas for canalizing, and nested canalizing functions.

References in corpus (8)

• The Yeast Cell-Cycle Network Is Robustly Designed
• Random Boolean Network Models and the Yeast Transcriptional Network
• Genetic networks with canalyzing Boolean rules are always stable
• Canalizing Kauffman networks: non-ergodicity and its effect on their critical behavior
• Boolean nested canalizing functions: a comprehensive analysis
• The number and probability of canalizing functions
• The Number of Multistate Nested Canalyzing Functions
• On Analysis and Generation of some Biologically Important Boolean Functions

Cited by in corpus (1)

• Certificate complexity and symmetry of nested canalizing functions