Revealing the canalizing structure of Boolean functions: Algorithms and applications
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2021
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910700123717632 |
|---|---|
| author | Dimitrova, Elena Stigler, Brandilyn Kadelka, Claus Murrugarra, David |
| author_facet | Dimitrova, Elena Stigler, Brandilyn Kadelka, Claus Murrugarra, David |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2106_06580 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Revealing the canalizing structure of Boolean functions: Algorithms and applications Dimitrova, Elena Stigler, Brandilyn Kadelka, Claus Murrugarra, David Computational Complexity Quantitative Methods 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. |
| title | Revealing the canalizing structure of Boolean functions: Algorithms and applications |
| topic | Computational Complexity Quantitative Methods |
| url | https://arxiv.org/abs/2106.06580 |