<figure><img src="image_1.png" /></figure>

HAL
open science

# From multivalued to Boolean functions: preservation of soft nested canalization

Élisabeth Remy, Paul Ruet

<figure><img src="image_2.png" /></figure>

## To cite this version:

Élisabeth Remy, Paul Ruet. From multivalued to Boolean functions: preservation of soft nested canalization. 2023. hal-04104379

HAL Id: hal-04104379

https://hal.science/hal-04104379

Preprint submitted on 24 May 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# From multivalued to Boolean functions: preservation of soft nested canalization

Élisabeth Remy<sup>a</sup>, Paul Ruet<sup>b</sup>

<sup>a</sup>Aix Marseille Univ, CNRS, I2M, Marseille, France

<sup>b</sup>CNRS, Université Paris Cité, Paris, France

## Abstract

Nested canalization (NC) is a property of Boolean functions which has been recently extended to multivalued functions. We study the effect of the Van Ham mapping (from multivalued to Boolean functions) on this property. We introduce the class of softly nested canalizing (SNC) multivalued functions, and prove that the Van Ham mapping sends SNC multivalued functions to NC Boolean functions. Since NC multivalued functions are SNC, this preservation property holds for NC multivalued functions as well. We also study the relevance of SNC functions in the context of gene regulatory network modelling.

**Keywords:** nested canalizing functions, Boolean functions, multivalued functions, regulatory network modelling

## 1. Introduction

Dynamical properties of biological systems, such as stability and robustness, are often associated with the canalyzing property. This notion is at the basis of the work of Waddington in embryology, which describes, in the 1940s, epigenetic landscapes representing embryogenesis by canalizing configurations [26]. In the 1990's, S. Kauffman introduced the class of canalizing Boolean functions [4, 5] to formalize the canalizing behaviour observed in gene regulatory networks. In short, canalizing Boolean functions are functions $f: (\mathbb{Z}/2\mathbb{Z})^n \to \mathbb{Z}/2\mathbb{Z}$ (or $\mathbb{R}$) such that at least one input variable, say

Email addresses: elisabeth.remy@univ-amu.fr (Élisabeth Remy), ruet@irif.fr (Paul Ruet)

URL: https://mabios.math.cnrs.fr/ (Élisabeth Remy), https://www.irif.fr/~ruet/ (Paul Ruet)
$x_i$ ($1 \le i \le n$), has a value $a = 0$ or $1$ which determines the value of $f(x)$. Nested canalizing (NC) functions provide a “recursive” version of canalizing functions: an NC function $f$ is canalizing and, moreover, its restriction $f|_{\{x_i \ne a\}}$ is itself NC. NC functions are particularly interesting because of their “low complexity”: in particular, their average sensitivity (a measure of complexity related to spectral concentration, learning properties, decision tree complexity [13] and stability properties [4, 6]) is bounded above by a constant [8, 7].

A natural question is the extension of this canalizing property to multi-valued functions, involving more than two expression levels, which are often needed in the modeling of biological systems to circumvent the too restrictive Boolean representation [23]. The present paper investigates the property of nested canalization for multivalued functions $f : (\mathbb{Z}/k\mathbb{Z})^n \to \mathbb{Z}/k\mathbb{Z}$ or $\mathbb{R}$ for some $k \ge 2$. A definition of nested canalizing (NC) multivalued function has been proposed in [10, 11]. In [16], we introduced a more general class of multivalued functions, which we called weakly nested canalizing (WNC), for which we proved that the average sensitivity is bounded above by a constant.

Multivalued modelling allows to distinguish different thresholds of action of a gene on its targets, and is of course more complex to analyse than the Boolean case. Boolean mappings have been proposed, associating one Boolean variable to each threshold. This gives access to a large number of theoretical works and numerical tools specific to the analysis of Boolean models. Thus we are interested in the relationship between the notions of canalization for multivalued and Boolean functions. Clearly an NC Boolean function is NC multivalued, but what can we say about the other direction? More precisely, a mapping $\beta$ from multivalued functions to Boolean functions have been defined by Van Ham in [25], and it have been proved in [2, 24] to be in some sense unique (it is the only injective such mapping preserving neighbours in the state space, and for which the regulatory graphs are unchanged).

We prove here that $\beta$ maps NC multivalued functions to NC Boolean functions. To this end, we introduce in Section 2 the notion of softly nested canalizing (SNC) multivalued functions, and prove that $NC \Rightarrow SNC \Rightarrow WNC$ (Proposition 2 and Section 2.3). Then we actually prove in Theorem 3 that SNC functions are mapped by $\beta$ to NC Boolean functions. On the other hand, we show that Theorem 3 does not extend to WNC functions: we shall see in Section 3.5 an example of a WNC function which is mapped by $\beta$ to a non NC Boolean function.

NC functions appear as appropriate rules in Boolean models of gene regulatory networks. Indeed, Boolean networks have been proposed as models
for gene regulatory networks [22], with different nodes corresponding to different genes. The activity of a gene is regulated by the activity of other genes to which it is connected through a Boolean function. These networks are built from biological data and knowledge from the literature, and their associated Boolean functions are far from random. It turns out that NC functions are predominant in the large databases of Boolean gene networks [21]. In Section 4 we extract the multivalued genes from this database, and we study the canalizing properties of their multivalued functions and their corresponding Boolean functions.

## 2. Nested canalizing multivalued functions

The concept of nested canalization, originally considered for Boolean functions [4], has been extended to multivalued functions in [10, 11, 3]. We first recall here this definition, before introducing soft nested canalization in Section 2.1.

Let $k, n$ be positive integers, $k \ge 2$. $\mathbb{Z}/k\mathbb{Z}$ is the ring of integers modulo $k$. A function $f: (\mathbb{Z}/k\mathbb{Z})^n \to \mathbb{Z}/k\mathbb{Z}$ is said to be *canalizing with respect to coordinate $i$ and $(a, b) \in \mathbb{Z}/k\mathbb{Z} \times \mathbb{Z}/k\mathbb{Z}$ if there exists a function $g: (\mathbb{Z}/k\mathbb{Z})^n \to \mathbb{Z}/k\mathbb{Z}$ different from the constant $b$ such that*

$$f(x) = \begin{cases} b & \text{if } x_i = a \\ g(x) & \text{if } x_i \neq a. \end{cases}$$

We shall simply say that $f$ is *canalizing* if it is canalizing with respect to some $i, a, b$.

A *segment* is a subset of $\mathbb{Z}/k\mathbb{Z}$ of the form $\{0, \dots, i\}$ or $\{i, \dots, k-1\}$. Let $\sigma \in \mathfrak{S}_n$ be a permutation, $A_1, \dots, A_n$ be segments, and $c_1, \dots, c_{n+1} \in \mathbb{Z}/k\mathbb{Z}$ be such that $c_n \neq c_{n+1}$. Then $f$ is said to be *nested canalizing (NC) with respect to $\sigma$, $A_1, \dots, A_n, c_1, \dots, c_{n+1}$ if*

$$f(x) = \begin{cases} c_1 & \text{if } x_{\sigma(1)} \in A_1 \\ c_2 & \text{if } x_{\sigma(1)} \notin A_1, x_{\sigma(2)} \in A_2 \\ \vdots & \vdots \\ c_n & \text{if } x_{\sigma(1)} \notin A_1, \dots, x_{\sigma(n-1)} \notin A_{n-1}, x_{\sigma(n)} \in A_n \\ c_{n+1} & \text{if } x_{\sigma(1)} \notin A_1, \dots, x_{\sigma(n-1)} \notin A_{n-1}, x_{\sigma(n)} \notin A_n. \end{cases}$$

We shall simply say that $f$ is *NC* if it is *NC* with respect to some $\sigma$, $A_1, \dots, A_n, c_1, \dots, c_{n+1}$.
Note that the segment $A_i$ plays the role of a threshold for the variable $x_{\sigma(i)}$. For an NC multivalued function $f$ as defined in [10, 11, 3], each variable $x_{\sigma(i)}$ is used exactly once in the process of canalization (and the value of $f$ if determined by the threshold corresponding to $A_i$). It is possible to relax the definition by allowing canalization along successive thresholds for a same variable. This is essentially what we shall do in defining softly nested canalizing functions below. In doing so, we shall also remove the condition $c_n \neq c_{n+1}$.

## 2.1. Softly nested canalizing multivalued functions

Let $n$ be a positive integer. For each $i \in \{1, \dots, n\}$, let $k_i > 0$, $\Omega_i$ be a set of $k_i$ integers, $\Omega = \prod_i \Omega_i$, and $f: \Omega \to \mathbb{R}$. Note that we do not require $k_i \ge 2$ for all $i$. If $k_j = 1$ for some $j$, $f$ could be viewed as a function with one less variable, i.e. as a function on $\prod_{i \neq j} \Omega_i$, but we still consider it as a function defined on $\prod_i \Omega_i$.

We shall say that $f$ is *softly canalizing with respect to coordinate $i$ and $(a, b) \in \Omega_i \times \mathbb{R}$ if $f(x) = b$ whenever $x_i = a$, and simply that it is *softly canalizing* if it is softly canalizing with respect to some $i, a, b$.

Note that this definition differs slightly from the usual definition by the absence of condition on the values of $f$ for $x_i \neq a$: we do not require the existence of some $x$ such that $x_i \neq a$ and $f(x) \neq b$. In particular, constant functions are softly canalizing, though not canalizing.

If $f$ is canalizing with respect to $i, a, b$ and $k_i \ge 2$, we shall consider

$$f|_{x_i \neq a}: \Omega \cap \{x | x_i \neq a\} \to \mathbb{R},$$

the restriction of $f$ to the set of $x \in \Omega$ such that $x_i \neq a$.

The class of softly nested canalizing on $\Omega = \prod_i \Omega_i$ is then defined by induction on the cardinality $|\Omega| = \prod_i k_i$ of $\Omega$. If $|\Omega| = 1$, i.e. $k_i = 1$ for all $i$, any $f: \Omega \to \mathbb{R}$ is *softly nested canalizing (SNC) on $\Omega$*. If $|\Omega| > 1$, $f: \Omega \to \mathbb{R}$ is *SNC on $\Omega$* if there exist $i, a, b$ such that

* $k_i \ge 2$,

* $a$ is either the min or the max of $\Omega_i$,

* $f$ is softly canalizing with respect to $i, a, b$,

* $f|_{x_i \neq a}$ is SNC on $\Omega \cap \{x | x_i \neq a\}$, a strict subset of $\Omega$.

Intuitively, a function $f: \Omega \to \mathbb{R}$ is SNC if its domain $\Omega$ can be “peeled” by successively removing coordinate hyperplanes (defined by equations of the form $x_i = a$ with $a$ minimal or maximal) whose points are mapped by $f$ to the same value, whence the following characterization:
**Proposition 1.** Letting $K = \sum_i k_i - n$, $f$ is SNC if and only if there exist a function $v: \{1, \dots, K\} \to \{1, \dots, n\}$, numbers $a_i \in \Omega_{v(i)}$ and $b_i \in \mathbb{R}$ for each $i \in \{1, \dots, K\}$ such that:

$$f(x) = \begin{cases} b_1 & \text{if } x_{v(1)} = a_1 \\ b_2 & \text{if } x_{v(1)} \neq a_1, x_{v(2)} = a_2 \\ \vdots & \vdots \\ b_K & \text{if } x_{v(1)} \neq a_1, \dots, x_{v(K-1)} \neq a_{K-1}, x_{v(K)} = a_K \end{cases}$$

and for each $i \in \{1, \dots, K\}$, $\Omega'_{v(i)} = \Omega_{v(i)} \setminus \{a_j \mid j < i, v(i) = v(j)\}$ is not a singleton and $a_i$ is either the min or the max of $\Omega'_{v(i)}$.

In decomposing an NC function $f: (\mathbb{Z}/k\mathbb{Z})^n \to \mathbb{Z}/k\mathbb{Z}$, each coordinate $i \in \{1, \dots, n\}$ is considered exactly once (in some order prescribed by a permutation $\sigma$) and the value of $f$ is fixed for $x_{\sigma(i)}$ in some segment $A_i$. This can be realized by successively fixing the value of $f$ for each $\alpha \in A_i$, and therefore, the class of SNC functions contains the class of NC functions, as stated in the following Proposition:

**Proposition 2.** If $f: (\mathbb{Z}/k\mathbb{Z})^n \to \mathbb{Z}/k\mathbb{Z}$ is NC, then it is SNC.

*Proof.* Assume $f$ is NC with respect to $\sigma$, $A_1, \dots, A_n$, $c_1, \dots, c_{n+1}$. For each $i \in \{1, \dots, n\}$, let

$$A_i = \{\alpha_i^1, \dots, \alpha_i^{|A_i|}\} \\ (\mathbb{Z}/k\mathbb{Z}) \setminus A_i = \{\alpha_i^{1+|A_i|}, \dots, \alpha_i^{k-1}\}.$$

More precisely, the $K = n(k-1)$ numbers $\alpha_i^j \in \mathbb{Z}/k\mathbb{Z}$ are defined according to the following ordering which depends on the nature of the segment $A_i$:

* either $0 \in A_i$, and then we choose the numbers $\alpha_i^j$ so that $0 = \alpha_i^1 < \dots < \alpha_i^{|A_i|}$ and $k-1 = \alpha_i^{1+|A_i|} > \dots > \alpha_i^{k-1}$;

* or $k-1 \in A_i$, and we choose the $\alpha_i^j$ so that $k-1 = \alpha_i^1 > \dots > \alpha_i^{|A_i|}$ and $0 = \alpha_i^{1+|A_i|} < \dots < \alpha_i^{k-1}$.

If both $0$ and $k-1 \in A_i$, i.e. if $A_i = \mathbb{Z}/k\mathbb{Z}$, we choose any of the two orders. Now, for each $i \in \{1, \dots, n\}$ and $j \in \{1, \dots, k-1\}$, let

$$\beta_i^j = \begin{cases} c_i & \text{if } j \le |A_i| \\ c_{n+1} & \text{otherwise.} \end{cases}$$
To comply with the characterization of SNC functions (Proposition 1), we relabel the numbers $\alpha_i^j, \beta_i^j$ by identifying the list

$$ \alpha_1^1, \dots, \alpha_1^{|A_1|}, \dots, \alpha_n^1, \dots, \alpha_n^{|A_i|}, \alpha_1^{1+|A_1|}, \dots, \alpha_1^k, \dots, \alpha_n^{1+|A_n|}, \dots, \alpha_n^{k-1} $$

as the list $a_1, \dots, a_K$, and by identifying similarly the list

$$ \beta_1^1, \dots, \beta_1^{|A_1|}, \dots, \beta_n^1, \dots, \beta_n^{|A_n|}, \beta_1^{1+|A_1|}, \dots, \beta_1^k, \dots, \beta_n^{1+|A_n|}, \dots, \beta_n^{k-1} $$

as the list $b_1, \dots, b_K$. Call $\varphi$ this relabelling, which maps $r \in \{1, \dots, K\}$ to the pair $\varphi(r) = (i, j)$ such that $a_r = \alpha_i^j$ and $b_r = \beta_i^j$. For instance, $\varphi(1) = (1, 1)$ and $\varphi(K) = (n, k-1)$. Then finally, a function $v: \{1, \dots, K\} \to \{1, \dots, n\}$ is defined by $v(r) = \sigma(i)$ if $\varphi(r) = (i, j)$. Then $f$ clearly enjoys the characterization of SNC functions, with the choice of function $v$ and numbers $a_r, b_r$. $\square$

## 2.2. Some examples

* We have already noticed that constant functions from $(\mathbb{Z}/k\mathbb{Z})^n$ to $\mathbb{Z}/k\mathbb{Z}$ are SNC but not NC.

* An easy induction on $k$ shows that the functions $\min$ and $\max$: $(\mathbb{Z}/k\mathbb{Z})^2 \to \mathbb{Z}/k\mathbb{Z}$ are SNC. For instance, $\min = \min_k: \{0, \dots, k-1\}^2 \to \{0, \dots, k-1\}$ is softly canalizing with respect to $1, 0, 0$, then $\min_k|_{x_1 \neq 0}$ is softly canalizing with respect to $2, 0, 0$, and $\min_k|_{x_1 \neq 0, x_2 \neq 0}$ is identical to the function $\min_{k-1}: \{1, \dots, k-1\}^2 \to \{1, \dots, k-1\}$, which is SNC.

However, they are not NC [3]. Intuitively, there is more freedom in the construction of SNC functions, which can be built by successively “peeling” coordinate hyperplanes defined on some coordinate $i$ (i.e. by some equation $x_i = a$), then a coordinate hyperplane defined on some other coordinate $j$, and later a coordinate hyperplane defined on $i$ again.

* For the same reason, the identity from $(\mathbb{Z}/k\mathbb{Z})^n$ to $(\mathbb{Z}/k\mathbb{Z})^n$ is SNC but not NC. As we shall see in Section 4, this applies to the functions governing the regulation of genes such as **Raf**, **Dsor**, **Drk**, **Stat92E**.

* In Section 4, we shall see other examples of SNC and non SNC functions occurring in multivalued gene regulatory networks found in the literature.
### 2.3. WNC multivalued functions and average sensitivity

It is possible to consider a slightly more general notion of multivalued canalization, by removing the condition on canalizing values in the definition of SNC functions. This is what we do in [16]: weakly nested canalizing (WNC) functions $f: (\mathbb{Z}/k\mathbb{Z})^n \to \mathbb{Z}/k\mathbb{Z}$ are defined like SNC functions, but the values $a$ used to define $f(x)$ for $x_i = a$ need not be extreme values (initially 0 or $k-1$), they can be intermediate values: $0 < a < k-1$.

By Proposition 2, NC ⇒ SNC ⇒ WNC, and we prove in [16] that WNC (hence NC and SNC) multivalued functions have “low complexity” in the sense that their average sensitivity (see [13, Chapter 8]) is bounded above by a constant (independent of $n$), while the average sensitivity of an arbitrary multivalued function is of order $O(n)$.

It is worth noticing that the above implications are strict. For instance, the function $f: \mathbb{Z}/3\mathbb{Z} \times \mathbb{Z}/3\mathbb{Z} \to \mathbb{Z}/3\mathbb{Z}$ defined by the following table:

$$f(x, y) = \begin{array}{c|ccc} x \setminus y & 0 & 1 & 2 \\ \hline 0 & 2 & 0 & 0 \\ 1 & 1 & 1 & 1 \\ 2 & 2 & 0 & 2 \end{array}$$

is WNC but not SNC: the first canalization has to take the intermediate value $x = 1$ (and determines $f(x, y) = 1$), then the second canalization takes $y = 0$ (determining $f(x, y) = 2$) or $y = 1$ (determining $f(x, y) = 0$), and finally $x = 0$ or $x = 2$.

## 3. Preservation of nested canalization under Boolean mapping

### 3.1. Mapping multivalued functions to Boolean functions

Let $n$, $\Omega_i = \mathbb{Z}/k_i\mathbb{Z}$ and $\Omega = \prod_{i=1}^n \Omega_i$ be as above.

The injective mapping $\beta: \Omega \hookrightarrow \{0, 1\}^k$, with $k = \sum_i k_i - n$, proposed by Van Ham [25] is defined as follows. For $i \in \{1, \dots, n\}$ and $1 \le a \le k_i - 1$, let $\beta_{i,a}: \Omega \to \{0, 1\}$ be defined by

$$\beta_{i,a}(x) = \begin{cases} 1 & \text{if } x_i \ge a \\ 0 & \text{otherwise,} \end{cases}$$

and

$$\beta_i(x) = (\beta_{i,1}(x), \dots, \beta_{i,k_i-1}(x)) = 1^{x_i} 0^{k_i-1-x_i},$$
where $1^\ell = (1, \dots, 1)$ is the $\ell$-tuple of 1's (and similarly for $0^\ell$), and tuples of 0's and 1's are represented by words (without commas and parentheses). The maps can be combined to define $\beta : \Omega \hookrightarrow \{0, 1\}^k$ by

$$ \begin{aligned} \beta(x) &= (\beta_{1,1}(x), \dots, \beta_{1,k_1-1}(x), \dots, \beta_{n,1}(x), \dots, \beta_{n,k_n-1}(x)) \\ &= 1^{x_1} 0^{k_1-1-x_1} \dots 1^{x_n} 0^{k_n-1-x_n}. \end{aligned} $$

The image $\beta(\Omega)$ of $\beta$ is a strict subset of $\{0, 1\}^k$ (unless $k_i = 2$ for all $i$), and a point $x \in \{0, 1\}^k$ is said *admissible* when $x \in \beta(\Omega)$. Given $F : \Omega \to \Omega$, by injectivity of $\beta$, the equality

$$ F^{\beta} \circ \beta = \beta \circ F, $$

defines $F^{\beta} : \beta(\Omega) \to \beta(\Omega)$, the Booleanization of $F$.

Clearly, if $F$ is Boolean (i.e. $k_i = 2$ for all $i$), then $\beta(\Omega) = \Omega = (\mathbb{Z}/2\mathbb{Z})^n$ and $F^{\beta} = F$.

Let us mention that other injective mappings from $\Omega$ to $\{0, 1\}^k$ may be defined but $\beta$ is the only one preserving neighbours and regulatory graphs [2, 24]:

* two neighbouring states (i.e. states $x, y \in \Omega$ whose Hamming distance equals 1) are mapped by $\beta$ to neighbouring states in $\beta(\Omega)$,

* the global regulatory graphs $G(F)$ and $G(F^{\beta})$ underlying the dynamics $F$ and $F^{\beta}$ are isomorphic. We refer to, e.g., [15, 17, 18] for the definition of $G(F)$.

The purpose of the remainder of this section is to prove that $\beta$ maps SNC multivalued functions to NC (Boolean) functions. Before doing this in Theorem 3 we need to recall the definition of nested canalization for Boolean functions.

### 3.2. Nested canalizing Boolean functions

Let $k$ be a positive integer, $\sigma \in \mathfrak{S}_k$ be a permutation, and $a_1, \dots, a_k, b_1, \dots, b_k \in \{0, 1\}$. We recall that a Boolean function $f : \{0, 1\}^k \to \{0, 1\}$ is said to be *nested canalizing (NC) with respect to $\sigma$, $a_1, \dots, a_k, b_1, \dots, b_k$* if

$$ f(x) = \begin{cases} b_1 & \text{if } x_{\sigma(1)} = a_1 \\ b_2 & \text{if } x_{\sigma(1)} \neq a_1, x_{\sigma(2)} = a_2 \\ \vdots & \vdots \\ b_k & \text{if } x_{\sigma(1)} \neq a_1, \dots, x_{\sigma(k-1)} \neq a_{k-1}, x_{\sigma(k)} = a_k. \end{cases} \quad (*) $$
Note that we slightly modify the usual definition by not requiring $f(x) = 1 - b_k$ when $x_{\sigma(1)} \neq a_1, \dots, x_{\sigma(k-1)} \neq a_{k-1}, x_{\sigma(k)} \neq a_k$.

We shall simply say that $f$ is NC if it is NC with respect to some $\sigma, a_1, \dots, a_k, b_1, \dots, b_k$, and that a function $F = (F_1, \dots, F_k) : \{0, 1\}^k \to \{0, 1\}^k$ is NC if $F_j : \{0, 1\}^k \to \{0, 1\}$ is NC for all $j$.

### 3.3. Nested canalizing partial Boolean functions

In Section 3.4, we shall consider functions $f : X \to \{0, 1\}$ defined on a subset $X \subseteq \{0, 1\}^k$. We extend the notion of nested canalization to such partial functions, by simply saying that $f : X \to \{0, 1\}$ is NC with respect to the above data if condition (*) holds for all $x \in X$.

### 3.4. Relation between $\beta$ and nested canalization

**Theorem 3.** If $F = (F_1, \dots, F_n) : \Omega \to \Omega$ is SNC, then $F^\beta : \beta(\Omega) \to \beta(\Omega)$ is NC.

*Proof.* As in the definition of $\beta$, we shall use double indices for Boolean functions, and let

$$ 
\begin{aligned}
F^{\beta} &= (F_{1,1}^{\beta}, \dots, F_{1,k_1-1}^{\beta}, \dots, F_{n,1}^{\beta}, \dots, F_{n,k_n-1}^{\beta}) \\
&= (F_1^{\beta}, \dots, F_n^{\beta}),
\end{aligned}
 $$

where $F_{j,a}^{\beta} = \beta_{j,a} \circ F : \beta(\Omega) \to \{0, 1\}$ and

$$ F_j^\beta = \beta_j \circ F = (F_{j,1}^\beta, \dots, F_{j,k_{j-1}}^\beta) : \beta(\Omega) \to \{0,1\}^{k_j-1}. $$

Therefore $F_j^\beta(\beta(x)) = 1^{F_j(x)} 0^{k_j-1-F_j(x)}$ and $F_{j,a}^\beta(\beta(x)) = 1 \Leftrightarrow F_j(x) \ge a$.

Let us fix $j \in \{1, \dots, n\}$ and $1 \le a \le k_j - 1$ and prove that $F_{j,a}^\beta$ is NC.

By assumption, $F_j : \Omega \to \Omega_j$ is SNC, hence by Proposition 1, there exist a function $v : \{1, \dots, K\} \to \{1, \dots, n\}$, with $K = \sum_i k_i - n$, and numbers $a_i \in \Omega_{v(i)}$ and $b_i \in \Omega_j$ for each $i \in \{1, \dots, K\}$ such that, for all $x \in \Omega$:

$$ F_j(x) = \begin{cases} b_1 & \text{if } x \in \Omega^{(1)} \text{ and } x_{v(1)} = a_1 \\ b_2 & \text{if } x \in \Omega^{(2)} \text{ and } x_{v(2)} = a_2 \\ \vdots & \vdots \\ b_K & \text{if } x \in \Omega^{(K)} \text{ and } x_{v(K)} = a_K, \end{cases} $$

where for all $i \in \{1, \dots, K\}$, $\Omega^{(i)} \subseteq \Omega$ is the set of $x$ such that

$$ x_{v(1)} \neq a_1, \dots, x_{v(i-1)} \neq a_{i-1}. $$
Note that $\Omega = \Omega^{(1)} \supset \Omega^{(2)} \supset \dots \supset \Omega^{(K)}$ form a decreasing sequence of subsets of $\Omega$.

Moreover, by Proposition 1, the numbers $a_i$ are assumed to satisfy the following constraint:

$$ \text{either } a_i = \min \Omega_{v(i)}^{(i)} \text{ or } a_i = \max \Omega_{v(i)}^{(i)}. $$

Let $\varepsilon_i = 0, a'_i = a_i + 1$ in the first case (min case) and $\varepsilon_i = 1, a'_i = a_i$ in the second case (max case). Letting $y = \beta(x)$, we observe that in the min case, when $x \in \Omega^{(i)}$ we have

$$ x_{v(i)} = a_i \Leftrightarrow x_{v(i)} \le a_i \Leftrightarrow y_{v(i),a_i+1} = \beta_{v(i),a_i+1}(x) = 0, $$

and that in the max case, we have

$$ x_{v(i)} = a_i \Leftrightarrow x_{v(i)} \ge a_i \Leftrightarrow y_{v(i),a_i} = \beta_{v(i),a_i}(x) = 1. $$

These two equivalences are summarized in the following property:

$$ x_{v(i)} = a_i \Leftrightarrow y_{v(i),a'_i} = \varepsilon_i \text{ whenever } x \in \Omega^{(i)}. \quad (P) $$

Let us prove by induction on $i$ that

$$ x \in \Omega^{(i)} \Leftrightarrow \left\{ \begin{array}{l} y_{v(1),a'_1} \ne \varepsilon_1 \\ \vdots \\ y_{v(i-1),a'_{i-1}} \ne \varepsilon_{i-1} \end{array} \right. \quad (Q_i) $$

$Q_1$ is trivial because $\Omega^{(1)} = \Omega$, and by property P, we have

$$ \begin{align*} x \in \Omega^{(i+1)} &\Leftrightarrow (x \in \Omega^{(i)} \text{ and } x_{v(i)} \ne a_i) \\ &\Leftrightarrow (x \in \Omega^{(i)} \text{ and } y_{v(i),a'_i} \ne \varepsilon_i), \end{align*} $$

hence $Q_i$ entails $Q_{i+1}$, and we have shown that $Q_i$ holds for any $i$. Combining properties P and $Q_i$, we then obtain:

$$ \left\{ \begin{array}{l} x \in \Omega^{(i)} \\ x_{v(i)} = a_i \end{array} \right. \Leftrightarrow \left\{ \begin{array}{l} y_{v(1),a'_1} \ne \varepsilon_1 \\ \vdots \\ y_{v(i-1),a'_{i-1}} \ne \varepsilon_{i-1} \\ y_{v(i),a'_i} = \varepsilon_i \end{array} \right. $$
On the other hand, $F_{j,a}^{\beta}(y) = 1 \Leftrightarrow F_j(x) \ge a$. Hence, letting $\chi_{b\ge a} = 1$ if $b \ge a$ and 0 otherwise, we have $F_{j,a}^{\beta}(y) = \chi_{F_j(x)\ge a}$. In particular

$$F_j(x) = b_i \Rightarrow F_{j,a}^{\beta}(y) = \chi_{b_i \ge a}.$$

Therefore, the condition that $F_j$ is SNC gives, for any $y \in \beta(\Omega)$:

$$F_{j,a}^{\beta}(y) = \begin{cases} \chi_{b_1 \ge a} & \text{if } y_{v(1),a'_1} = \varepsilon_1 \\ \chi_{b_2 \ge a} & \text{if } y_{v(1),a'_1} \neq \varepsilon_1, y_{v(2),a'_2} = \varepsilon_2 \\ \vdots & \vdots \\ \chi_{b_K \ge a} & \text{if } y_{v(1),a'_1} \neq \varepsilon_1, \dots, y_{v(K-1),a'_{K-1}} \neq \varepsilon_{K-1}, y_{v(K),a'_K} = \varepsilon_K \end{cases}$$

This means that $F_{j,a}^{\beta}$ is NC in the sense of Section 3.3. Since this holds for all $j, a$, $F^{\beta}$ is NC. $\square$

### 3.5. Counterexample for WNC functions

Let $f : \Omega = \mathbb{Z}/3\mathbb{Z} \times \mathbb{Z}/3\mathbb{Z} \to \mathbb{Z}/3\mathbb{Z}$ be the function defined in Section 2.3. It is WNC but not SNC, and $\beta(\Omega) \subseteq \{0,1\}^2 \times \{0,1\}^2$. The function $f^{\beta} : \beta(\Omega) \to \{0,1\}^2$ is given by the following table:

$$f^{\beta}(x, y) = \begin{array}{c|ccc} & 00 & 10 & 11 \\ \hline 00 & 11 & 00 & 00 \\ 10 & 10 & 10 & 10 \\ 11 & 11 & 00 & 11 \end{array}$$

where pairs in $\{0,1\}^2$ are written without commas and parentheses. This table is simply obtained from the one defining $f$ by the substitutions $0 \mapsto 00, 1 \mapsto 10, 2 \mapsto 11$.

Now, the two Boolean functions $f_1^{\beta}, f_2^{\beta} : \beta(\Omega) \to \{0,1\}$ such that $f^{\beta} = (f_1^{\beta}, f_2^{\beta})$ are therefore:

$$f_1^{\beta}(x, y) = \begin{array}{c|ccc} & 00 & 10 & 11 \\ \hline 00 & 1 & 0 & 0 \\ 10 & 1 & 1 & 1 \\ 11 & 1 & 0 & 1 \end{array}$$

$$f_2^{\beta}(x, y) = \begin{array}{c|ccc} & 00 & 10 & 11 \\ \hline 00 & 1 & 0 & 0 \\ 10 & 0 & 0 & 0 \\ 11 & 1 & 0 & 1 \end{array}$$

and it is easy to see that $f_1^{\beta}$ is NC but that $f_2^{\beta}$ is not NC. Therefore Theorem 3 does not extend to WNC functions.
## 4. Examples in the regulatory network literature

Boolean NC functions appear predominant in databases of Boolean genetic networks [21]. If this canalyzing property reflects physical characteristics of biological systems, we wonder whether this property is also present in multivalued functions that model these same systems. Thus, in order to have an insight into the characteristics of multivalued functions specified in the context of biological systems, we have selected the multivalued genes present in the logical models explored in [21] (45 genes endowed with a ternary variable) and studied the canalizing properties (NC, SNC, WNC) of their logical functions. We also applied the Boolean mapping $\beta$ and studied the canalizing property of the resulting Boolean functions. The results of the analysis are collected in Table 1, reflecting four different qualitative situations:

(a) functions $F$ which are NC (hence SNC, WNC, and with NC Booleanization $F^\beta$);

(b) functions which are not NC, but SNC (hence WNC, and with NC Booleanization);

(c) functions which are not WNC (hence neither NC nor SNC) but with NC Booleanization;

(d) functions which are not WNC and with non NC Booleanizations.

Remark that in this set of functions, all WNC functions are actually SNC.

The logical rules corresponding to these genes are collected in the Appendix. To simplify the notation in the rules, the name of the gene is written to represent its activity variable (for instance $A: 1$ stands for $x_A = 1$), and the value of $F_A$ is defined by means of the usual logical connectives (conjunction $\wedge$, disjunction $\vee$ and negation $\neg$). For example, the first and third lines of Table A.2 mean:

$$F_{Drk}(x) = \begin{cases} 1 & \text{if } x_{Der} = 1 \\ 2 & \text{if } x_{Der} = 2 \\ 0 & \text{otherwise} \end{cases}$$

$$F_{RI}(x) = \begin{cases} 1 & \text{if } x_{Dsor1} = 1 \text{ and } x_{Msk} = 1 \\ 2 & \text{if } x_{Dsor1} = 2 \text{ and } x_{Msk} = 1 \\ 0 & \text{otherwise} \end{cases}$$

This means that gene **Drk** can be activated at level 1 (resp. 2) when its (unique) regulator **Der** is at level 1 (resp. 2). Gene **RI** has two regulators, **Msk** (which is Boolean) and **Dsor1**, and it can be activated at level 1 (resp. 2) if **Msk** is present ($x_{Msk} = 1$) and **Dsor1** is at level 1 (resp. 2).
Some situations are more complex. For instance, gene **MadMed** (extracted from the model described in [9]) has three regulators: a multilevel activator **Tkv**, a Boolean activator **Sax** and a Boolean inhibitor **Dad**. The rule for **MadMed** is the following (cf Table A.5):

$$F_{\text{MadMed}}(x) = \begin{cases} 1 & \text{if } (x_{\text{Tkv}} = 1 \text{ or } x_{\text{Sax}} = 1) \text{ and } x_{\text{Dad}} = 0 \text{ and } x_{\text{Tkv}} < 2 \\ 2 & \text{if } x_{\text{Tkv}} = 2 \text{ and } x_{\text{Dad}} = 0 \\ 0 & \text{otherwise.} \end{cases}$$

Thus, in the absence of the inhibitor **Dad**, the presence of one of the two activators at level 1 (max level for **Sax** and intermediate for **Tkv**) allows **MadMed** to be activated at its level 1. **MadMed** can be activated at its maximum level as soon as its activator **Tkv** is at its maximum level 2 and the inhibitor **Dad** is absent.

The structure of multivalued logical rules varies greatly. A quite current situation is when the level of only one regulator determines the target value of the gene:

$$\begin{cases} \mathbf{A} = 1 & \text{if } \mathbf{B} \wedge \varphi \\ \mathbf{A} = 2 & \text{if } \neg \mathbf{B} \wedge \varphi \end{cases} \qquad (S)$$

with **B** a regulator of **A**, and $\varphi$ a “context” (conditions on the presence or absence of other regulators). This concerns the genes listed in Tables A.2, A.3, A.4. We can see in Table 1 that the rules satisfying this structure (S) generally have strong canalyzing properties: situations (a) or (b). In particular, their Booleanizations are all NC. Then, depending on the context, we distinguish three situations:

* if $\varphi$ depends on multivalued variables and is expressed only with $\wedge$, then the function behaves according to situation (b); this is the case of, e.g., **Stat92E**; these functions are listed in Table A.2;

* if $\varphi$ is expressed with at least one $\vee$, then the function behaves according to situation (c) (functions listed in Table A.3);

* if $\varphi$ depends on Boolean variables and is expressed only with $\wedge$, then the function behaves according to situation (a) (functions listed in Table A.4). Note that nodes **IL4RA** and **E2F3** are controlled by a multivalued gene (resp. **STAT5** and **CHEK**), but their level depends only on one threshold (to be above or below level 2).
<table><thead><tr><th>Gene</th><th>NC</th><th>SNC</th><th>WNC</th><th>Bool. NC</th><th>Struct.</th></tr></thead><tbody><tr><td>E_Spl</td><td>Yes</td><td>Yes</td><td>Yes</td><td>Yes</td><td></td></tr><tr><td>mQH2_Q</td><td>Yes</td><td>Yes</td><td>Yes</td><td>Yes</td><td>(S)</td></tr><tr><td>mdH</td><td>Yes</td><td>Yes</td><td>Yes</td><td>Yes</td><td>(S)</td></tr><tr><td>mGR</td><td>Yes</td><td>Yes</td><td>Yes</td><td>Yes</td><td></td></tr><tr><td>mGSH_GSSG</td><td>Yes</td><td>Yes</td><td>Yes</td><td>Yes</td><td>(S)</td></tr><tr><td>mTRX</td><td>Yes</td><td>Yes</td><td>Yes</td><td>Yes</td><td>(S)</td></tr><tr><td>cGSH_GSSG</td><td>Yes</td><td>Yes</td><td>Yes</td><td>Yes</td><td>(S)</td></tr><tr><td>cGR</td><td>Yes</td><td>Yes</td><td>Yes</td><td>Yes</td><td></td></tr><tr><td>E2F3</td><td>Yes</td><td>Yes</td><td>Yes</td><td>Yes</td><td>(S)</td></tr><tr><td>IL12RB1</td><td>Yes</td><td>Yes</td><td>Yes</td><td>Yes</td><td>(S)</td></tr><tr><td>IL4RA</td><td>Yes</td><td>Yes</td><td>Yes</td><td>Yes</td><td>(S)</td></tr><tr><td>Drk</td><td>No</td><td>Yes</td><td>Yes</td><td>Yes</td><td>(S)</td></tr><tr><td>Dsor1</td><td>No</td><td>Yes</td><td>Yes</td><td>Yes</td><td>(S)</td></tr><tr><td>Pnt</td><td>No</td><td>Yes</td><td>Yes</td><td>Yes</td><td>(S)</td></tr><tr><td>Stat92E</td><td>No</td><td>Yes</td><td>Yes</td><td>Yes</td><td>(S)</td></tr><tr><td>Raf</td><td>No</td><td>Yes</td><td>Yes</td><td>Yes</td><td>(S)</td></tr><tr><td>RI</td><td>No</td><td>Yes</td><td>Yes</td><td>Yes</td><td>(S)</td></tr><tr><td>Sos</td><td>No</td><td>Yes</td><td>Yes</td><td>Yes</td><td>(S)</td></tr><tr><td>Tkv</td><td>No</td><td>Yes</td><td>Yes</td><td>Yes</td><td></td></tr><tr><td>mNNT</td><td>No</td><td>Yes</td><td>Yes</td><td>Yes</td><td></td></tr><tr><td>mCa</td><td>No</td><td>Yes</td><td>Yes</td><td>Yes</td><td>(S)</td></tr><tr><td>mGPX</td><td>No</td><td>Yes</td><td>Yes</td><td>Yes</td><td>(S)</td></tr><tr><td>mTR</td><td>No</td><td>Yes</td><td>Yes</td><td>Yes</td><td></td></tr><tr><td>cGPX</td><td>No</td><td>Yes</td><td>Yes</td><td>Yes</td><td>(S)</td></tr><tr><td>cTR</td><td>No</td><td>Yes</td><td>Yes</td><td>Yes</td><td></td></tr><tr><td>cTRX</td><td>No</td><td>Yes</td><td>Yes</td><td>Yes</td><td>(S)</td></tr><tr><td>STAT5</td><td>No</td><td>Yes</td><td>Yes</td><td>Yes</td><td></td></tr></tbody></table>
<table><caption>Table 1: Multivalued genes occurring in logical models from database considered in [21]. The two rightmost columns indicate whether the Booleanized functions are nested canalizing, and which rules satisfy structure (S).</caption><thead><tr><th>Gene</th><th>NC</th><th>SNC</th><th>WNC</th><th>Bool. NC</th><th>Struct.</th></tr></thead><tbody><tr><td>Ras</td><td>No</td><td>No</td><td>No</td><td>Yes</td><td></td></tr><tr><td>MadMed</td><td>No</td><td>No</td><td>No</td><td>Yes</td><td></td></tr><tr><td>Hop</td><td>No</td><td>No</td><td>No</td><td>Yes</td><td></td></tr><tr><td>mNADPH_NADP</td><td>No</td><td>No</td><td>No</td><td>Yes</td><td></td></tr><tr><td>mNADH_NAD</td><td>No</td><td>No</td><td>No</td><td>Yes</td><td>(S)</td></tr><tr><td>cCa</td><td>No</td><td>No</td><td>No</td><td>Yes</td><td></td></tr><tr><td>KrebsCycle</td><td>No</td><td>No</td><td>No</td><td>Yes</td><td>(S)</td></tr><tr><td>VIM</td><td>No</td><td>No</td><td>No</td><td>Yes</td><td></td></tr><tr><td>CDH1</td><td>No</td><td>No</td><td>No</td><td>Yes</td><td></td></tr><tr><td>EMT</td><td>No</td><td>No</td><td>No</td><td>Yes</td><td></td></tr><tr><td>IL2R</td><td>No</td><td>No</td><td>No</td><td>Yes</td><td>(S)</td></tr><tr><td>IL4R</td><td>No</td><td>No</td><td>No</td><td>Yes</td><td>(S)</td></tr><tr><td>mROS</td><td>No</td><td>No</td><td>No</td><td>No</td><td></td></tr><tr><td>Der</td><td>No</td><td>No</td><td>No</td><td>No</td><td></td></tr><tr><td>cROS</td><td>No</td><td>No</td><td>No</td><td>No</td><td></td></tr><tr><td>cNADPH_NADP</td><td>No</td><td>No</td><td>No</td><td>No</td><td></td></tr><tr><td>E2F1</td><td>No</td><td>No</td><td>No</td><td>No</td><td></td></tr><tr><td>Spi1</td><td>No</td><td>No</td><td>No</td><td>No</td><td></td></tr></tbody></table>

The rules that do not satisfy structure (S) are collected in Tables A.5 and A.6. In particular, Table A.6 gathers all the rules in situation (d), for which even the Booleanized functions are not NC.

The study of these multivalued functions suggests a certain relevance of canalization, notably SNC, among models arising in the modelling of gene networks. But it should be noted that we have not specified the assumptions for updating the system while they play an important role in the dynamical behavior of the system and its properties. Implicitly, we here considered that the gene directly reached its target value: for instance, **Drk** can be activated at level 2 when **Der** is at level 2, and if the current state of **Drk** is 0, it will update directly to value 2. However, in such context of biological systems, it is not a realistic hypothesis, steps of 1 are more common: in the previous example, if **Der** is at level 2 and **Drk** is not active, its activity will first reach level 1. The introduction of the “steps of 1” hypothesis in the definition of the function would obviously change the canalizing properties.
Appendix A. Logical rules

<table><caption>Table A.2: Rules associated to multivalued genes from databases considered in [21], satisfying structure (S) and behaving according to situation (b).</caption><thead><tr><th>Gene <i>i</i></th><th><i>x</i><sub><i>i</i></sub></th><th>Rule</th><th>Ref</th></tr></thead><tbody><tr><td rowspan="2">Drk</td><td>1</td><td>Der : 1</td><td rowspan="2"></td></tr><tr><td>2</td><td>Der : 2</td></tr><tr><td rowspan="2">Dsor1</td><td>1</td><td>Raf : 1</td><td rowspan="2"></td></tr><tr><td>2</td><td>Raf : 2</td></tr><tr><td rowspan="2">RI</td><td>1</td><td>Dsor1 : 1 ∧ Msk</td><td rowspan="2">[9]</td></tr><tr><td>2</td><td>Dsor1 : 2 ∧ Msk</td></tr><tr><td rowspan="2">Pnt</td><td>1</td><td>RI : 1</td><td rowspan="2"></td></tr><tr><td>2</td><td>RI : 2</td></tr><tr><td rowspan="2">Sos</td><td>1</td><td>Drk : 1</td><td rowspan="2"></td></tr><tr><td>2</td><td>Drk : 2</td></tr><tr><td rowspan="2">Stat92E</td><td>1</td><td>Hop : 1 ∧ φ</td><td rowspan="2">[9]</td></tr><tr><td>2</td><td>Hop : 2 ∧ φ where φ = ¬Su<sub>var</sub> ∧ ¬Ptp61F ∧</td></tr><tr><td rowspan="2">Raf</td><td>1</td><td>Ras : 1 ∧ Cnk ∧ Src42 ∧ Ksr</td><td rowspan="2"></td></tr><tr><td>2</td><td>Ras : 2 ∧ Cnk ∧ Src42 ∧ Ksr</td></tr><tr><td rowspan="2">mCa</td><td>1</td><td>cCa : 1</td><td rowspan="2"></td></tr><tr><td>2</td><td>cCa : 2</td></tr><tr><td rowspan="2">mGPX</td><td>1</td><td>mGSH_GSSG : 1 ∧ ¬mROS</td><td rowspan="2">[19]</td></tr><tr><td>2</td><td>mGSH_GSSG : 2 ∧ ¬mROS</td></tr><tr><td rowspan="2">cTRX</td><td>1</td><td>cTR ∧ cROS : 1</td><td rowspan="2"></td></tr><tr><td>2</td><td>cTR ∧ ¬cROS</td></tr><tr><td rowspan="2">cGPX</td><td>1</td><td>cGSH_GSSG : 1 ∧ ¬cROS</td><td rowspan="2"></td></tr><tr><td>2</td><td>cGSH_GSSG : 2 ∧ ¬cROS</td></tr></tbody></table>

<table><thead><tr><th>Gene <i>i</i></th><th><i>x</i><sub><i>i</i></sub></th><th>Rule</th><th>Ref</th></tr></thead><tbody><tr><td rowspan="2">mNADH<br>_NAD</td><td>1</td><td>(KrebsCycle ∨ mPDH ∨ FAO) ∧ ETC</td><td rowspan="2"></td></tr><tr><td>2</td><td>(KrebsCycle ∨ mPDH ∨ FAO) ∧ ¬ETC</td></tr><tr><td rowspan="2">KrebsCycle</td><td>1</td><td>¬mCa ∧ ¬mNADH_NAD ∧</td><td rowspan="2">[19]</td></tr><tr><td>2</td><td>(AcetylCoA ∨ GLUTAMINOLYSIS)<br>mCa ∧ ¬mNADH_NAD ∧</td></tr><tr><td rowspan="2">IL2R</td><td>1</td><td>¬IL2RA ∧ CGC ∧ IL2RB ∧ (IL2 ∨ IL2_e)</td><td rowspan="2">[12]</td></tr><tr><td>2</td><td>IL2RA ∧ CGC ∧ IL2RB ∧ (IL2 ∨ IL2_e)</td></tr></tbody></table>
<table><caption>Table A.3: Rules associated to multivalued genes from databases considered in [21], satisfying structure (*S*) and behaving according to situation (c).</caption><thead><tr><th>Gene <i>i</i></th><th><i>x</i><sub><i>i</i></sub></th><th>Rule</th><th>(continued)</th><th>Ref</th></tr></thead><tbody><tr><td rowspan="2">IL4R</td><td>1</td><td>IL4RA : 1 ∧ CGC ∧ (IL4 ∨ IL4_e)</td><td></td><td rowspan="2">[12]</td></tr><tr><td>2</td><td>IL4RA : 2 ∧ CGC ∧ (IL4 ∨ IL4_e)</td><td></td></tr></tbody></table>

<table><caption>Table A.4: Rules associated to multivalued genes from databases considered in [21], satisfying structure (*S*) and behaving according to situation (a).</caption><thead><tr><th>Gene <i>i</i></th><th><i>x</i><sub><i>i</i></sub></th><th>Rule</th><th>Ref</th></tr></thead><tbody><tr><td rowspan="2">IL12RB1</td><td>1</td><td>¬IRF1</td><td rowspan="2">[12]</td></tr><tr><td>2</td><td>IRF1</td></tr><tr><td rowspan="2">mGSH<br>_GSSG</td><td>1</td><td>mGR ∧ mGPX</td><td rowspan="2">[19]</td></tr><tr><td>2</td><td>mGR ∧ ¬mGPX</td></tr><tr><td rowspan="2">mdH</td><td>1</td><td>ETC ∧ ATPSyn</td><td rowspan="2">[19]</td></tr><tr><td>2</td><td>ETC ∧ ¬ATPSyn</td></tr><tr><td rowspan="2">mQH2_Q</td><td>1</td><td>ETC ∧ ¬mdH</td><td rowspan="2">[19]</td></tr><tr><td>2</td><td>ETC ∧ mdH</td></tr><tr><td rowspan="2">mTRX</td><td>1</td><td>mTR ∧ mROS</td><td rowspan="2">[19]</td></tr><tr><td>2</td><td>mTR ∧ ¬mROS</td></tr><tr><td rowspan="2">cGSH<br>_GSSG</td><td>1</td><td>cGR ∧ cGPX</td><td rowspan="2">[19]</td></tr><tr><td>2</td><td>cGR ∧ ¬cGPX</td></tr><tr><td rowspan="2">IL4RA</td><td>1</td><td>¬STAT5 : 2</td><td rowspan="2">[12]</td></tr><tr><td>2</td><td>STAT5 : 2</td></tr><tr><td rowspan="2">E2F3</td><td>1</td><td>¬CHEK : 2 ∧ ¬RB1 ∧ RAS</td><td rowspan="2">[14]</td></tr><tr><td>2</td><td>CHEK : 2 ∧ ¬RB1 ∧ RAS</td></tr></tbody></table>

<table><thead><tr><th>Gene <i>i</i></th><th><i>x</i><sub><i>i</i></sub></th><th>Rule</th><th>Ref</th></tr></thead><tbody><tr><td rowspan="2">Ras</td><td>1</td><td>(Sos : 1 ∧ ¬(Sty ∧ Gap1)) ∨ (Gap1 ∧ Sty ∧ Sos : 2)</td><td rowspan="2">[9]</td></tr><tr><td>2</td><td>Sos : 2 ∧ ¬(Sty ∧ Gap1)</td></tr><tr><td rowspan="2">Tkv</td><td>1</td><td>(Dpp : 1 ∨ Scw ∨ Gbb) ∧ Punt ∧ ¬(Sog ∨ Tsg)</td><td rowspan="2">[19]</td></tr><tr><td>2</td><td>Dpp : 2 ∧ Punt ∧ ¬(Sog ∨ Tsg)</td></tr><tr><td rowspan="3">mNNT</td><td>1</td><td>mNADH_NAD : 1 ∧ mdH : 1</td><td rowspan="3">[19]</td></tr><tr><td>2</td><td>(mNADH_NAD : 2 ∧ mdH : 1) ∨</td></tr><tr><td></td><td>(mNADH_NAD : 2 ∧ mdH : 2) ∨</td></tr><tr><td></td><td></td><td>(mNADH_NAD : 1 ∧ mdH : 2)</td><td></td></tr><tr><td rowspan="2">mNADPH<br>_NADP</td><td>1</td><td>(¬mNNT ∧ mIDH2) ∨ (mNNT : 1 ∧ ¬mIDH2)</td><td rowspan="2">[19]</td></tr><tr><td>2</td><td>mNNT : 2 ∨ (mNNT : 1 ∧ mIDH2)</td></tr></tbody></table>
<table><caption>Table A.5: Rules associated to multivalued genes from databases considered in [21], not satisfying structure (S) and behaving according to situations (a), (b) or (c).</caption><thead><tr><th>Gene i</th><th>x<sub>i</sub></th><th>Rule (continued)</th><th>Ref</th></tr></thead><tbody><tr><td rowspan="2">mGR</td><td>1</td><td>(mNADPH_NADP : 1 ∨ mNADPH_NADP : 2) ∧</td><td rowspan="2"></td></tr><tr><td>2</td><td>(¬mGSH_GSSG ∨ mGSH_GSSG : 1)</td></tr><tr><td rowspan="2">mTR</td><td>1</td><td>(mNADPH_NADP : 1 ∨ mNADPH_NADP : 2) ∧</td><td rowspan="2"></td></tr><tr><td>2</td><td>mGSH_GSSG : 2</td></tr><tr><td rowspan="2">cCa</td><td>1</td><td>(IP3R ∧ ¬ORAI1 ∧ ¬TRPM2 ∧ ¬PMCA) ∨</td><td rowspan="2">[19]</td></tr><tr><td>2</td><td>(¬IP3R ∧ ¬ORAI1 ∧ TRPM2 ∧ ¬PMCA) ∨</td></tr><tr><td rowspan="2">cGR</td><td>1</td><td>(¬IP3R ∧ ORAI1 ∧ TRPM2 ∧ ¬PMCA) ∨</td><td rowspan="2"></td></tr><tr><td>2</td><td>(¬IP3R ∧ ORAI1 ∧ TRPM2 ∧ ¬PMCA) ∨</td></tr><tr><td rowspan="2">cTR</td><td>1</td><td>(IP3R ∧ ORAI1 ∧ TRPM2 ∧ ¬PMCA) ∨</td><td rowspan="2"></td></tr><tr><td>2</td><td>(IP3R ∧ ORAI1 ∧ TRPM2 ∧ ¬PMCA) ∨</td></tr><tr><td rowspan="2">Hop</td><td>1</td><td>(¬cGSH_GSSG ∨ cGSH_GSSG : 1)</td><td rowspan="2"></td></tr><tr><td>2</td><td>(cNADPH_NADP : 1 ∨ cNADPH_NADP : 2) ∧</td></tr><tr><td rowspan="2">MadMed</td><td>1</td><td>(cNADPH_NADP : 1 ∨ cNADPH_NADP : 2) ∧</td><td rowspan="2">[9]</td></tr><tr><td>2</td><td>(¬cTRX ∨ cTRX : 1)) ∨</td></tr><tr><td rowspan="2">E_Spl</td><td>1</td><td>(cNADPH_NADP : 2 ∧ (¬cTRX ∨ cTRX : 1)) ∨</td><td rowspan="2"></td></tr><tr><td>2</td><td>(cNADPH_NADP : 2 ∧ cTRX : 1)</td></tr><tr><td rowspan="2">STAT5</td><td>1</td><td>(¬ET ∧ [(Stam ∧ Hrs ∧ Socs36E) ∨</td><td rowspan="2">[12]</td></tr><tr><td>2</td><td>(¬(Stam ∧ Hrs) ∧ ¬Socs36E)]</td></tr><tr><td rowspan="2">VIM</td><td>1</td><td>(¬ET ∧ Stam ∧ Hrs ∧ Socs36E)</td><td rowspan="2"></td></tr><tr><td>2</td><td>(¬(Stam ∧ Hrs) ∧ (¬Dad : 1) ∧ (¬Tkv : 2) ∨</td></tr><tr><td rowspan="2">CDH1</td><td>1</td><td>(¬(Tkv : 1 ∨ Sax : 1) ∧ (¬Dad : 1) ∧ (¬Tkv : 2) ∨</td><td rowspan="2">[20]</td></tr><tr><td>2</td><td>(¬(Tkv : 2 ∧ Dad : 1) ∧ (¬Tkv : 2) ∨ (¬Dad : 1) ∧ (¬Tkv : 2) ∨ (¬Dad : 1))</td></tr><tr><td rowspan="2">EMT</td><td>1</td><td>(¬(Nicd ∧ Mam) ∧ (¬Nicd : 1) ∧ (¬Nicd : 2) ∧ (¬Nicd : 1) ∧ (¬Nicd : 2))</td><td rowspan="2"></td></tr><tr><td>2</td><td>(¬(Nicd : 1) ∧ (¬Nicd : 2) ∧ (¬Nicd : 1) ∧ (¬Nicd : 2))</td></tr></tbody></table>
<table><caption>Table A.6: Rules associated to multivalued genes from databases considered in [21], not satisfying structure (S) and behaving according to situation (d).</caption><thead><tr><th>Gene <i>i</i></th><th><i>x</i><sub><i>i</i></sub></th><th>Rule</th><th>Ref</th></tr></thead><tbody><tr><td rowspan="2">mROS</td><td>1</td><td>((¬<b>mPRX</b> ∧ <b>mGPX</b>) ∨ (<b>mPRX</b> ∧ ¬<b>mGPX</b>)) ∧ (<b>ETC</b> ∨ <b>mGR</b> ∨ <b>mTR</b>) ∧ ¬<b>cROS</b></td><td rowspan="2">[19]</td></tr><tr><td>2</td><td>[(<b>ETC</b> ∨ <b>mGR</b> ∨ <b>mTR</b> ∨ <b>cROS</b>) ∧ ¬(<b>mPRX</b> ∨ <b>mGPX</b>)] ∨ [<b>cROS</b> ∧ (<b>mPRX</b> ∨ <b>mGPX</b> ∨ <b>ETC</b> ∨ <b>mGR</b> ∨ <b>mTR</b>)]</td></tr><tr><td rowspan="2">cROS</td><td>1</td><td>((<b>cPRX</b> ∧ ¬<b>cGPX</b>) ∨ (¬<b>cPRX</b> ∧ <b>cGPX</b>)) ∧ (<b>NOX2</b> ∨ <b>DUOX1</b> ∨ <b>cTR</b> ∨ <b>cGR</b>) ∧ ¬<b>mROS</b></td><td rowspan="2">[19]</td></tr><tr><td>2</td><td>[¬(<b>cPRX</b> ∨ <b>cGPX</b>) ∧ (<b>NOX2</b> ∨ <b>mROS</b> ∨ <b>DUOX1</b> ∨ <b>cTR</b> ∨ <b>cGR</b>)] ∨ [<b>mROS</b> ∧ (<b>cPRX</b> ∨ <b>cGPX</b> ∨ <b>NOX2</b> ∨ <b>DUOX1</b> ∨ <b>cTR</b> ∨ <b>cGR</b>)]</td></tr><tr><td rowspan="2">cNADPH_NADP</td><td>1</td><td>(<b>mShuttle</b> ∧ ¬<b>PPP</b> ∧ ¬<b>GLUTAMINOLYSIS</b>) ∨ (¬<b>mShuttle</b> ∧ <b>PPP</b> ∧ ¬<b>GLUTAMINOLYSIS</b>) ∨ (¬<b>mShuttle</b> ∧ ¬<b>PPP</b> ∧ <b>GLUTAMINOLYSIS</b>)</td><td rowspan="2">[19]</td></tr><tr><td>2</td><td>(<b>mShuttle</b> ∧ <b>PPP</b> ∧ <b>GLUTAMINOLYSIS</b>) ∨ (¬<b>mShuttle</b> ∧ <b>PPP</b> ∧ <b>GLUTAMINOLYSIS</b>) ∨ (<b>mShuttle</b> ∧ ¬<b>PPP</b> ∧ <b>GLUTAMINOLYSIS</b>) ∨ (<b>mShuttle</b> ∧ <b>PPP</b> ∧ ¬<b>GLUTAMINOLYSIS</b>)</td></tr><tr><td rowspan="2">Der</td><td>1</td><td>[(<b>Spi</b> : 1 ∨ <b>Vein</b>) ∧ ¬<b>Aos</b> : 1 ∧ ¬<b>Kek</b> : 1 ∧ ¬<b>Cbl</b> ∧ ¬<b>Spi</b> : 2 ∧ <b>Shc</b>] ∨ [<b>Spi</b> : 2 ∧ <b>Shc</b> ∧ (<b>Kek</b> : 1 ∨ <b>Aos</b> : 1 ∨ <b>Cbl</b>)]</td><td rowspan="2">[9]</td></tr><tr><td>2</td><td><b>Spi</b> : 2 ∧ ¬<b>Kek</b> : 1 ∧ ¬<b>Aos</b> : 1 ∧ ¬<b>Cbl</b> ∧ <b>Shc</b></td></tr><tr><td rowspan="2">E2F1</td><td>1</td><td>[(¬(<b>CHEK</b> : 2 ∧ <b>ATM</b> : 2) ∧ (<b>RAS</b> ∨ <b>E2F3</b>)) ∨ (<b>CHEK</b> : 2 ∧ <b>ATM</b> : 2 ∧ ¬<b>RAS</b> ∨ <b>E2F3</b> : 1)] ∧ ¬<b>RB1</b> ∧ ¬<b>RBL2</b></td><td rowspan="2">[14]</td></tr><tr><td>2</td><td>¬<b>RB1</b> ∧ ¬<b>RBL2</b> ∧ <b>ATM</b> : 2 ∧ <b>CHEK</b> : 2 ∧ (<b>RAS</b> ∨ <b>E2F3</b> : 2)</td></tr><tr><td rowspan="2">Spi1</td><td>1</td><td>[<b>Spi1</b> ∧ <b>Runx1</b> ∧ (¬((<b>Cebpa</b> ∨ <b>Cebpb</b>) ∧ <b>Csf1r</b>) ∨ (<b>Foxo1</b> ∧ ¬<b>lkzf1</b>) ∨ ¬<b>Gfi1</b>)] ∨ (<b>Foxo1</b> ∧ <b>Ebf1</b> ∧ <b>lkzf1</b> ∧ ¬(<b>Spi1</b> ∨ <b>Runx1</b>))</td><td rowspan="2">[1]</td></tr><tr><td>2</td><td>(<b>Spi1</b> ∧ <b>Runx1</b> ∧ (<b>Cebpa</b> ∨ <b>Cebpb</b>) ∧ <b>Csf1r</b>) ∨ (<b>Spi1</b> ∧ <b>Runx1</b> ∧ ¬(<b>Gfi1</b> ∨ (<b>Foxo1</b> ∧ <b>lkzf1</b>)))</td></tr></tbody></table>

## References

[1] S. Collombet, C. van Oevelen, J. L. Sardina Ortega, W. Abou-Jaoudé, B. Di Stefano, M. Thomas-Chollier, T. Graf, and D. Thieffry. Logical
modeling of lymphoid and myeloid cell specification and transdifferentiation. *Proc. Natl. Acad. Sci.*, 114(23):5792-5799, 2017.

[2] G. Didier, É. Remy, and C. Chaouiya. Mapping multivalued onto Boolean dynamics. *J. Theoret. Biol.*, 270(1):177-184, 2011.

[3] C. Kadelka, Y. Li, J. Kuipers, J. O. Adeyeye, and R. Laubenbacher. Multistate nested canalizing functions and their networks. *Theoret. Comput. Sci.*, 675:1-14, 2017.

[4] S. A. Kauffman. *The origins of order: Self organization and selection in evolution*. Oxford University Press, 1993.

[5] S. Kauffman, C. Peterson, B. Samuelsson, and C. Troein. Random Boolean network models and the yeast transcriptional network. *Proc. Natl. Acad. Sci.*, 100(25), 2003.

[6] S. Kauffman, C. Peterson, B. Samuelsson, and C. Troein. Genetic networks with canalizing Boolean rules are always stable. *Proc. Natl. Acad. Sci.*, 101(49), 2004.

[7] J. G. Klotz, R. Heckel, and S. Schober. Bounds on the average sensitivity of nested canalizing functions. *Plos One*, 8(5), 2013.

[8] Y. Li, J. O. Adeyeye, D. Murrugarra, B. Aguilar, and R. Laubenbacher. Boolean nested canalizing functions: A comprehensive analysis. *Theoret. Comput. Sci.*, 481:24-36, 2013.

[9] A. Mbodj, G. Junion, C. Brun, E. Furlong, and D. Thieffry. Logical modelling of Drosophila signalling pathways. *Mol. Biosyst.*, 9(9):2248-2258, 2013.

[10] D. Murrugarra and R. Laubenbacher. Regulatory patterns in molecular interaction networks. *J. Theor. Biol.*, 288:66-72, 2011.

[11] D. Murrugarra and R. Laubenbacher. The number of multistate nested canalizing functions. *Physica D: Nonlinear Phenomena*, 241(10):929-938, 2012.

[12] A. Naldi, J. Carneiro, C. Chaouiya, and D. Thieffry. Diversity and plasticity of Th cell types predicted from regulatory network modelling. *PLoS Comput. Bio.*, 6(9), 2010.

[13] R. O'Donnell. *Analysis of Boolean functions*. Cambridge University Press, 2014.
[14] É. Remy, S. Rebouissou, C. Chaouiya, A. Zinovyev, F. Radvany, and L. Calzone. A modeling approach to explain mutually exclusive and co-occurring genetic alterations in bladder tumorigenesis. *Cancer Res.*, 75(19): 4042–4052, 2015.

[15] É. Remy and P. Ruet. On differentiation and homeostatic behaviours of Boolean dynamical systems. *BioConcur 2005*, in *Transactions on Computational Systems Biology VIII*, Springer LNCS 4780: 92–101, 2007.

[16] É. Remy and P. Ruet. Average sensitivity of nested canalizing multi-valued functions. *arXiv:2211.14649*, 2022.

[17] É. Remy, P. Ruet, and D. Thieffry. Graphic requirements for multistability and attractive cycles in a Boolean dynamical framework. *Adv. Appl. Math.*, 41(3):335–350, 2008.

[18] P. Ruet. Local cycles and dynamical properties of Boolean networks. *Math. Struct. Comput. Sci.*, 26(4):702–718, 2016.

[19] J.A. Sánchez-Villanueva, O. Rodríguez-Jorge, O. Ramírez-Pliego, G.R. Salgado, W. Abou-Jaoudé, C. Hernandez, A. Naldi, D. Thieffry, and M.A. Santana. Contribution of ROS and metabolic status to neonatal and adult CD8+ T cell activation. *PLoS ONE* 14(12): e0226388, 2019.

[20] D.A. Silveira, and J.C. Mombach. Dynamics of the feedback loops required for the phenotypic stabilization in the epithelial-mesenchymal transition. *FEBS J.*, 287(3):578–588, 2020.

[21] A. Subbaroyan, O. C. Martin, and A. Samal. Minimum complexity drives regulatory logic in Boolean models of living systems. *PNAS Nexus*, 1:1–12, 2022.

[22] R. Thomas. Boolean formalization of genetic control circuits. *J. Theor. Biol.*, 42:563–585, 1973.

[23] R. Thomas. Regulatory networks seen as asynchronous automata: a logical description. *J. Theor. Biol.*, 153:1–23, 1991.

[24] E. Tonello. On the conversion of multivalued gene regulatory networks to Boolean dynamics. *Discrete Appl. Math.*, 259(C):193–204, 2019.

[25] P. Van Ham. How to deal with variables with more than two levels. In *Kinetic logic: a Boolean approach to the analysis of complex regulatory systems*. Springer, 326–343, 1979.
[26] C.H. Waddington. Canalization of development and the inheritance of acquired characters. *Nature*, 150:563-565, 1942.