Revealing the canalizing structure of Boolean functions: Algorithms and applications
arXiv:2106.06580 · doi:10.1016/j.automatica.2022.110630
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. Other canonical representation is based on the polynomial representation of Boolean functions where they can be written as a nested product of canalizing layers and a polynomial that contains the noncanalizing variables. In this paper we study the problem of identifying the canalizing layers format of Boolean functions. First, we show that the problem of finding the canalizing layers is NP-hard. Second, we present several algorithms for finding the canalizing layers of a Boolean function, discuss their complexities, and compare their performances. Third, we show applications where the computation of canalizing layers can be used for finding a disjunctive normal form of a nested canalizing function. Another application deals with the reverse engineering of Boolean networks with a prescribed layering format. Finally, implementations of our algorithms in Python and in the computer algebra system Macaulay2 are available at https://github.com/ckadelka/BooleanCanalization.
arXiv comment17 pages, 2 figures
References in corpus (11)
- Genetic networks with canalyzing Boolean rules are always stable
- Cell fate reprogramming by control of intracellular network dynamics
- Logic and connectivity jointly determine criticality in biological gene regulatory networks
- Boolean nested canalizing functions: a comprehensive analysis
- Canalization and control in automata networks: body segmentation in Drosophila melanogaster
- Regulatory patterns in molecular interaction networks
- Molecular Network Control Through Boolean Canalization
- The Influence of Canalization on the Robustness of Boolean Networks
- The Number of Multistate Nested Canalyzing Functions
- Quantifying the Total Effect of Edge Interventions in Discrete Multistate Networks
- Collectively canalizing Boolean functions