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.
|State||Published - Dec 2022|
Bibliographical noteFunding 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.
© 2022 Elsevier Ltd
- Boolean functions
- Canalizing layers
- Disjunctive normal forms
- Reverse engineering
ASJC Scopus subject areas
- Control and Systems Engineering
- Electrical and Electronic Engineering