Revealing the canalizing structure of Boolean functions: Algorithms and applications

Elena Dimitrova, Brandilyn Stigler, Claus Kadelka, David Murrugarra

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


Boolean functions can be represented in many ways including logical forms, truth tables, and polynomials. Additionally, Boolean functions have different canonical representations such as minimal disjunctive normal forms. Another canonical representation is based on the polynomial representation of Boolean functions and the biologically motivated concept of canalization: any Boolean function can be written as a nested product of canalizing layers and a polynomial that contains the variables that are never canalizing. In this paper we study the problem of identifying the canalizing layers of a Boolean function. First, we show that the problem of finding the canalizing layers is NP-hard. Second, we present several algorithms for finding the canalizing layers, discuss their complexities, and compare their performances. Third, we exhibit how the canalizing layers format can be used to find a disjunctive normal form for any nested canalizing function. Another application deals with the reverse engineering of Boolean networks with a prescribed layering format. Implementations of the developed algorithms in Python and in the computer algebra system Macaulay2 are available at

Original languageEnglish
Article number110630
StatePublished - Dec 2022

Bibliographical note

Publisher Copyright:
© 2022 Elsevier Ltd


  • Boolean functions
  • Canalizing layers
  • Disjunctive normal forms
  • NP-hard
  • Reverse engineering

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Electrical and Electronic Engineering


Dive into the research topics of 'Revealing the canalizing structure of Boolean functions: Algorithms and applications'. Together they form a unique fingerprint.

Cite this