Revealing the canalizing structure of Boolean functions: Algorithms and applications

Elena Dimitrova, Brandilyn Stigler, Claus Kadelka, David Murrugarra

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

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 https://github.com/ckadelka/BooleanCanalization.

Original languageEnglish
Article number110630
JournalAutomatica
Volume146
DOIs
StatePublished - Dec 2022

Bibliographical note

Funding Information:
D.M. was partially supported by a Collaboration grant ( 850896 ) from the Simons Foundation . C.K. was partially supported by a Collaboration grant ( 712537 ) from the Simons Foundation . E.D. was partially supported by NSF Award DMS-1419038 . B.S. was supported by the National Science Foundation Award #1720335 . The material in this paper was not presented at any conference. This paper was recommended for publication in revised form by Associate Editor Jun Liu under the direction of Editor Sophie Tarbouriech.

Publisher Copyright:
© 2022 Elsevier Ltd

Keywords

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

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Electrical and Electronic Engineering

Fingerprint

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

Cite this