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

HAL
open science

# Optimal resource allocation enables mathematical exploration of microbial metabolic configurations

Laurent Tournier, Anne Goelzer, Vincent Fromion

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

## To cite this version:

Laurent Tournier, Anne Goelzer, Vincent Fromion. Optimal resource allocation enables mathematical exploration of microbial metabolic configurations. Journal of Mathematical Biology, 2017, 75 (6), 10.1007/s00285-017-1118-5. [hal-01606441](https://hal.science/hal-01606441v1)

HAL Id: hal-01606441

https://hal.science/hal-01606441v1

Submitted on 4 Sep 2025

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published 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
# Optimal resource allocation enables mathematical exploration of microbial metabolic configurations

Laurent Tournier · Anne Goelzer · Vincent Fromion

Received: date / Accepted: date

**Abstract** Central to the functioning of any living cell, the metabolic network is a complex network of biochemical reactions. It may also be viewed as an elaborate production system, integrating a diversity of internal and external signals in order to efficiently produce the energy and the biochemical precursors to ensure all cellular functions. Even in simple organisms like bacteria, it shows a striking level of coordination, adapting to very different growth media. Constraint-based models constitute an efficient mathematical framework to compute optimal metabolic configurations, at the scale of a whole genome. Combining the constraint-based approach "Resource Balance Analysis" with combinatorial optimization techniques, we propose a general method to explore these configurations, based on the inference of logical rules governing the activation of metabolic fluxes in response to diverse extracellular media. Using the concept of partial Boolean functions, we notably introduce a novel tractable algorithm to infer monotone Boolean functions on a minimal support. Monotonicity seems particularly relevant in this context, since the orderliness exhibited by the metabolic network's dynamical behavior is expected to give rise to relatively simple rules. First results are promising, as the application of the method on *B. subtilis* central carbon metabolism allows to recover known regulations as well as to investigate lesser known parts of the global regulatory network.

**Keywords** Bacterial metabolic network · Systems biology · Partial Boolean function · Monotone Boolean function · Resource Balance Analysis · Central carbon metabolism

**Mathematics Subject Classification (2000)** 90C27 (Combinatorial optimization) · 92B05 (General biology and biomathematics) · 92-08 (Computational methods) · 94C10 (Switching theory, application of Boolean algebra, Boolean functions)

<footnote>This work was partly supported by Lidex IMSV (Institut de Modélisation des Systèmes vivants), Idex Paris-Saclay.</footnote>
# 1 Introduction

The behavior of a living cell can be decomposed in various elementary processes, interacting in a strikingly coordinated way to perform all tasks necessary to its survival and growth (Hartwell et al 1999). Among those processes, metabolism is absolutely central as it provides the energy (catabolism) and all the biochemical precursors (anabolism) that are vital to every cellular function. Structurally, the metabolic network can be viewed as a complex network of biochemical reactions, catalyzed by enzymes. As a system, its main functions are to sense the availability of different nutritive sources, and adjust accordingly the fluxes through each reaction to (i) produce enough energy and precursors to sustain the whole system and (ii) in the case of a bacterial cell, grow as fast as possible given available resources.

Driven by these two goals, the dynamical behavior of bacterial metabolism shows a striking level of coordination, allowing the system to adapt to very different growth media. For example, the availability of a specific amino acid in the medium will trigger the production of adequate transporter enzymes, while in its absence the production will stop, as the enzyme becomes useless and resources can be allocated elsewhere. Beyond this simple instance, more complex strategies exist such as diauxic growth, first observed by Monod (1958). When a bacterial population grows on two distinct carbon sources (e.g. glucose and sorbitol) a two-phase growth is observed, where the most efficient source (glucose in the example) is initially favored until its exhaustion. This phenomenon is widely spread (it has been observed in Gram negative bacteria such as *Escherichia coli* as well as in Gram positive bacteria such as *Bacillus subtilis*) and from a systemic point of view, it reveals a level of sophistication in the adjustment of the network's dynamics to environmental cues.

From a biological point of view, a lot has been done to elucidate how this type of behaviors are effectively implemented in the cell, leading to the landmark discovery of gene regulations in the 1960s. Among key actors, transcription factors have been identified that are able to sense diverse signals and to respond by impairing (or on the contrary enhancing) the transcription of target genes and thus stopping (or stimulating) the production of corresponding enzymes. Today the concept of gene regulation is well established, and a lot of gene regulatory networks have been investigated, in many different contexts. As an example, the regulatory network underlying diauxie, called catabolite repression, is reviewed by Fujita (2009) in the case of *B. subtilis*. For such a model organism, a lot of regulations have been identified: the whole metabolic network has been reconstructed by Goelzer et al (2008), including all known regulations. This reconstruction points out several remarkable properties in the global design of the network. Notably, the latter is composed of elementary functional modules, locally controlled by a genetic regulation sensing the internal state of each module. These modules are further coordinated by so-called global regulations, adapting the response to the availability of nutritive sources. Given the overall dimension and complexity of the network, the regulations (expressed as Boolean functions) have remarkably simple expressions: they usually involve only few variables and they often verify structural properties such as monotonicity.

In parallel, a lot of efforts have been devoted to the analysis of the metabolic network's global dynamics. Among different modeling frameworks, constraint-based
models have proven particularly efficient, notably Flux Balance Analysis (FBA),
which studies metabolites' flows under a steady-state assumption (Orth et al 2010).
Mathematically, it takes the form of a constrained optimization problem, where the
state variables are the fluxes through each reaction and the objective function rep-
resents, typically, a flux of biomass production. An appealing feature of this type
of approaches lies in suitable mathematical properties (e.g. in FBA, the linearity of
constraints and objective), making the resolution possible even in genome-scale di-
mensions. Gene regulation is absent in this type of framework: it is replaced with
structural constraints and optimization arguments. The underlying idea is that opti-
mality in the adjustment of the fluxes is sufficient (at least in a first approximation) to
explain the emergence of the network's design, whatever the actual implementation
by the cell. Overall, FBA leads to quantitative predictions that are in good accor-
dance with observations. However, it sometimes fails to recover complex strategies
like catabolite repression unless genetic regulations are added in some way, for in-
stance by Covert et al (2001).

A new constraint-based approach has been proposed by Goelzer et al (2009, 2011), where the optimization problem is amended to take into account protein production (through the translation apparatus) and to introduce a notion of enzyme cost. The ensuing optimization method, called Resource Balance Analysis (RBA), retains good mathematical properties (it is quasi-convex) making it still tractable in genome-scale dimensions. With respect to previous methods, one hallmark is that it captures complex strategies like catabolite repression without the addition of gene regulations, thus reproducing observed metabolic configurations with simple cost-benefit arguments. The method has been biologically validated and calibrated for *B. subtilis*, using a dedicated large-scale data set in few typical growth media (Goelzer et al 2015).

In the present paper, we propose to use this calibrated system as a predictor of
the real metabolic network of *B. subtilis*. Thanks to this *in silico* metabolic network,
we are able to rapidly compute the whole metabolic configuration of a cell in re-
sponse to any extracellular medium. Combined with a general "reverse engineering"
approach, it provides us with a powerful tool to unravel the organization of the net-
work's design, at the scale of an entire cell. To cope with unavoidable combinatorial
explosion, a Boolean formalism is chosen, aiming at the inference of logical rules.
These rules describe how each metabolic pathway turns on or off in response to nu-
trient availability. Boolean rules are often used in systems biology, as they provide
an efficient qualitative tool to deal with intertwined biological interactions (see e.g.
Steinway et al 2015, for a recent study). Here, emphasis is put on the inference of
monotonic effects which, given the orderliness exhibited by metabolism in general,
are expected to arise quite naturally. By generalizing previous results about Boolean
inference, we propose a new tractable algorithmic method to infer such monotone (or
unate) rules, in a general context. Combined with an efficient implementation, it is
able to take into account several tenth of variables, providing a relevant framework to
address the complexity of metabolic networks. Overall, it recovers remarkably simple
rules, reproducing most behaviors of bacterial metabolism as it is known today.

The paper is organized as follows. Part 2 gives a brief description of the RBA
method, showing how it can be used to generate Boolean training data sets, further
used to infer rules for metabolic fluxes. Parts 3 introduces the concept of Partial
Boolean Functions (PBF), used throughout this paper to infer logical rules. In particular, 3.4 revisits the search for minimal supports, emphasizing its equivalence with the well-known problem of Boolean (positive) dualization. The inference of monotonicities is further developed in Part 4 where a new, tractable algorithm is proposed for the identification of unate rules on a minimal support. Finally, Part 5 presents the first results of our method applied to central carbon metabolism of *B. subtilis*, showing how Boolean inference can be efficiently combined with constraint-based models to unravel the striking coordination exhibited by bacterial metabolic networks.

## 2 Biological motivation: towards the inference of metabolic regulations

As a motivation to our method, we first propose an introduction of the “Resource Balance Analysis” (RBA) optimization procedure, that will be used here as a black box process. After a brief summary of its main principles, we notably explain how it can be applied to generate Boolean learning data sets, subsequently used to infer logical rules governing metabolic pathways.

### 2.1 Computation of optimal metabolic configurations

For the sake of clarity, we give a simplified description of the RBA procedure, focusing on the notions that will be necessary in the rest of the paper. A more detailed description of the optimization problem as well as its resolution can be found elsewhere (Goelzer et al 2011, 2015).

Consider an exponentially growing bacterial population, in which the metabolic network has reached an equilibrium regime. The growth rate of the population is denoted by $\mu$. The flow through a metabolic reaction, catalyzed by enzyme $E_i$:

$$ \text{Substrates} \xrightarrow{E_i} \text{Products,} $$

is also called the flux of the reaction and is defined by $v_i = k_i E_i$ (or $|v_i| = k_i E_i$ in the case of a reversible reaction), where $E_i$ designates the concentration of enzyme $E_i$ and $k_i$ is a positive parameter, the apparent catalytic rate, representing the enzyme's efficiency. The flux $v_i$ is nonnegative if $E_i$ is irreversible and can have any sign if it is reversible. In general, $k_i$ depends on the concentration of substrates (for instance through a Michaelis-Menten term). Here however, at given growth rate the equilibrium assumption means the $k_i$ are supposed constant. This assumption is at the core of constraint-based models: stationary regime is expressed in function of equilibrium fluxes through each reaction. Let $N$ denote the number of enzymes and $N_p$ the number of metabolites (the current version of RBA for *B. subtilis* involves $N = 614$ enzymes and $N_p = 555$ metabolites). At steady state, total mass conservation translates to

$$ Sv = 0, \qquad (1) $$

where $S \in \mathbb{R}^{N_p \times N}$ is the stoichiometry matrix of the network and $v \in \mathbb{R}^N$ is the vector of fluxes. This flux balance constraint is at the basis of the FBA method, reviewed
by Orth et al (2010). In RBA, enzyme production is added through the translation apparatus of the cell. Beyond the vector of enzyme concentrations $E \in \mathbb{R}_+^N$, it involves a variable $R \in \mathbb{R}_+$, representing the concentration of ribosomes (the model also involves the concentration of proteins that are not enzymes, represented here by $P \in \mathbb{R}_+$). This yields three additional structural constraints, summarized thereafter. The first one represents the *metabolic network's capacity*. It formulates the fact that enough metabolic precursors<fnref n="1" /> need to be produced in order to sustain an exponential growth with rate $\mu$. Mathematically it is expressed as:

$$S'v \geq \mu (C_E E + C_R R + C_P P), \quad (2)$$

where $C_E \in \mathbb{R}_+^{N_q \times N}$ and $C_R, C_P \in \mathbb{R}_+^{N_q \times 1}$ are nonnegative parameters, $N_q (\leq N_p)$ is the number of precursors and $S' \in \mathbb{R}_+^{N_q \times N}$ is the submatrix of $S$ taken over the precursors. The second constraint represents the *translation's capacity*. It imposes that the concentration of ribosomes must be sufficient to produce all needed proteins:

$$k_R R \geq \mu (c'_E E + c'_R R + c'_P P), \quad (3)$$

where $c'_E \in \mathbb{R}_+^{1 \times N}$ and $c'_R, c'_P \in \mathbb{R}_+$; $k_R \geq 0$ represents ribosomal efficiency. The third constraint is a global *density* constraint, expressing the fact that intracellular density must be limited to ensure proper diffusion:

$$d_E E + d_R R + d_P P \leq \text{constant}, \quad (4)$$

where $d_E \in \mathbb{R}_+^{1 \times N}$ and $d_R, d_P \in \mathbb{R}_+$. The decision variables as well as the constraints are summarized in Figure 1. The external medium, represented as a vector of concentrations $X^{ext}$ is considered constant. It is used to compute the efficiency of transport enzymes (Goelzer et al 2011). The reconstruction of the constraints at the scale of a whole genome and their calibration with experimental data is a demanding task. In the case of *B. subtilis*, the validation has been made with a dedicated large-scale data set, consisting in genome-wide absolute protein quantification in five different growth media (Goelzer et al 2015).

Once the constraints have been reconstructed and biologically validated, the RBA optimization problem can be straightforwardly expressed as:

$$ \begin{array}{ll} \text{maximize:} & \mu \\ \text{such that} & \mu, R \geq 0, v \in \mathbb{R}^N, E \in \mathbb{R}_+^N \text{ satisfy: } (1), (2), (3), (4). \end{array} $$

In total, the problem involves around a thousand decision variables. The feasibility of a growth rate $\mu$ can be expressed as a Linear Programming (LP) problem, making general resolution efficiently achievable through an iteration of LP (Goelzer et al 2011). In the present paper, this whole procedure will be taken as a black box process: the input is the vector $X^{ext}$ representing the composition of the external medium and the output is the optimal metabolic configuration $(\mu^*, v^*, E^*, R^*)$ computed by RBA.

<footnote n="1">¹ Metabolic precursors are the subset of metabolites used to produce other components of the network.</footnote>
<figure><img src="image_4.png" /><figcaption>**Fig. 1** Schematic overview of the RBA optimization procedure. In the present paper, it will be taken as a black-box process: its inputs are the concentrations of external nutrients and its outputs are the maximal growth rate achievable, together with optimal fluxes configuration, enzyme and ribosome concentrations.</figcaption></figure>

## 2.2 From optimal metabolic configurations to learning Boolean data sets

As evoked previously, gene regulations are not explicitly included in the RBA formulation. Thus, if the medium is composed of glucose and sorbitol for instance, the mechanism of catabolite repression will be indirectly represented by $v_{ptsG}^* > 0$ and $v_{gutP}^* = 0$, where PtsG and GutP are respectively the transporters of glucose and sorbitol. In other words, transport of glucose is on and transport of sorbitol is off, which is exactly the effect of catabolite repression, favoring glucose's entry over sorbitol's. By construction, recall that the availability of external nutrients is a constant input of RBA. In other words, the procedure computes the optimal, “steady state” configuration under fixed external conditions. Therefore, in order to observe the dynamical process of diauxic growth for example, the optimization is applied to different scenarios (i.e. medium compositions), given in the following table.

<table><thead><tr><th>external glucose</th><th>external sorbitol</th><th>$v_{ptsG}^*$</th><th>$v_{gutP}^*$</th></tr></thead><tbody><tr><td>absent</td><td>absent</td><td>= 0</td><td>= 0</td></tr><tr><td>absent</td><td>present</td><td>= 0</td><td>&gt; 0</td></tr><tr><td>present</td><td>absent</td><td>&gt; 0</td><td>= 0</td></tr><tr><td>present</td><td>present</td><td>&gt; 0</td><td>= 0</td></tr></tbody></table>

This table qualitatively reproduces the diauxic curve initially observed by Monod (1958) and can be summarized by the following simple logical rules: glucose transporter is on when glucose is present; and sorbitol transporter is on when sorbitol is present and glucose is absent (e.g. when it has been completely consumed). Thus, glucose transport only depends on glucose availability while sorbitol transport depends on the availability of both sugars. Strikingly, this phenomenon was obtained without including the complex regulatory network of catabolite repression, centered on the master regulator CcpA (Fujita 2009), but only with an optimal allocation of enzymes throughout the network. In other words, from a systemic point of view RBA uses a
parsimony principle to capture the *realization* of the network's dynamics, independently from its actual *implementation* by the cell (through intertwined genetic and allosteric regulations). As such it provides an efficient framework to explore metabolic responses to different extracellular media at the scale of a whole genome.

Nevertheless, if the previous example can be easily generalized in theory, in practice the number of external sources rapidly generates a combinatorial explosion that needs to be handled with care. Thus, in order to infer previous rules with respect to *n* sources, 2ⁿ scenarios must be generated. This number grows very rapidly, already exceeding one million scenarios whenever *n* ≥ 20. In its present version, the RBA procedure includes 86 nutritive sources, divided into five groups: 28 carbohydrates, 20 amino acids, 16 nucleotides, 7 vitamins and 15 diverse other sources (such as oxygen, nitrogen, metal ions *etc.*). A complete exploration being completely out of reach, it is still possible to isolate a subset of them, the other ones being arbitrarily “absent” (or “present” in the case of several essential sources in the fifth group), thus reducing the analysis to specific sources of interest.

**Remark 1** In practice, we used an arbitrary value of 10 mmol.L⁻¹ to represent the presence of a nutrient in the extracellular medium. A natural extension of this work would be to consider multi-level discrete variables instead of a purely Boolean, all-or-none approach, enabling a refined representation of extracellular media by introducing intermediate levels. While relatively straightforward on a theoretical level, in practice this kind of refinement implies an increase in space dimensions (Chaves et al 2010). Given the already rapid combinatorial explosion, here we will consider exclusively Boolean variables.

Once a subset of *n* sources of interest is selected, one can generate a set *S* ⊂ {0, 1}ⁿ of scenarios, where each source can be either absent or present. This set may be exhaustive (|S| = 2ⁿ) or only partial (|S| < 2ⁿ) if *n* is too high. For each scenario, the RBA procedure computes the optimal configuration of fluxes *v**, which can then be discretized as follows: for *i* = 1, ..., *N*,

$$ \phi_i := \begin{cases} 0 & \text{if } v_i^* = 0, \\ 1 & \text{if } v_i^* > 0. \end{cases} $$

For reversible fluxes (taking nonnegative and nonpositive values), one can use two parallel discretizations:

$$ \phi_i^+ := \begin{cases} 0 & \text{if } v_i^* \le 0, \\ 1 & \text{if } v_i^* > 0, \end{cases} \quad \text{and} \quad \phi_i^- := \begin{cases} 0 & \text{if } v_i^* \ge 0, \\ 1 & \text{if } v_i^* < 0. \end{cases} $$

**Remark 2** From a numerical point of view, accurate detection of zeros is known to be a difficult task in general. It is worth noting that RBA uses Cplex Optimizer<fnref n="2" />, which is highly accurate and ensures the correct detection of zero fluxes in most cases (notably for data sets in 5.1 and 5.2). In high dimensional data sets (5.3), small flux values appeared but were limited to very few fluxes in the central carbon metabolism. To settle those cases, we considered values below 10⁻⁸ to be zeros.

<footnote n="2">² http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/</footnote>
By applying the previous steps, a Boolean data set ($\mathcal{S}$, $\phi$) is obtained, representing the activation or repression of metabolic fluxes in function of the availability of n external nutrients. These Boolean functions may be completely ($|\mathcal{S}| = 2^n$) or partially defined ($|\mathcal{S}| < 2^n$). In the following, we use the notion of Partial Boolean Function (PBF) to analyze these Boolean data sets (Boros et al 2003; Crama and Hammer 2011, chap. 12). Notably, we revisit the notion of minimal supports (Part 3.4), to efficiently uncover which sources are relevant to each flux (in the example above, GutP depends on glucose and sorbitol while PtsG only depends on glucose). Then, we propose a new algorithm to infer monotone rules over a minimal support (Part 4). The identification of monotone effects generates strikingly simple rules, even when the dimension increases. In Part 5, we show that monotonicity seems to emerge quite naturally in metabolic data sets, suggesting it is a key mathematical property to tackle the complexity of bacterial metabolic networks.

# 3 The concept of partial Boolean functions

## 3.1 Preliminaries about Boolean functions

We start with a brief summary of definitions and results about Boolean functions, together with notation that will be used throughout this paper. A more exhaustive overview of the subject can be found for instance in the textbook by Crama and Hammer (2011) and references therein. In the following, $\mathcal{B}$ designates the set $\{0, 1\}$. Classical Boolean operators will be denoted by $\lor$ (disjunction), $\land$ (conjunction) and $\lnot$ (negation). For any positive integer $n \in \mathbb{N} \setminus \{0\}$, previous operators straightforwardly generalize to the set $\mathcal{B}^n$ of n-dimensional Boolean vectors, thus forming a finite complemented distributive lattice, also called Boolean algebra. The partial order over $\mathcal{B}^n$ is defined as follows: for $x, y \in \mathcal{B}^n$, $x \le y$ if $x_i \le y_i$ for all $1 \le i \le n$. There is a one-to-one correspondence between the set $\mathcal{B}^n$ of n-dimensional Boolean vectors and the set $\mathfrak{P}_n$ of subsets of $\{1, \dots, n\}$. This correspondence takes the form of a lattice isomorphism $\Phi: (\mathfrak{P}_n, \subseteq) \to (\mathcal{B}^n, \leq)$, justifying the identification that will be made between n-dimensional Boolean vectors and subsets of $\{1, \dots, n\}$: if $S$ designates a subset of $\{1, \dots, n\}$, vector $s = \Phi(S)$ is defined by $s_i = 1$ if $i \in S$ and $s_i = 0$ if $i \notin S$. For any subset $X \subseteq \mathcal{B}^n$, $\min X$ denotes the set of minimal elements of $X$ i.e.,

$$x \in \min X \iff [x \in X \text{ and } \forall y \in X, (y \le x \Rightarrow y = x)]. \qquad (5)$$

The set of maximal elements, denoted by $\max X$, is defined in a symmetrical way. Thanks to the lattice isomorphism $\Phi$, $\min X$ and $\max X$ are straightforwardly defined for any subset $X \subseteq \mathfrak{P}_n$. Finally, for $S = \{i_1, \dots, i_p\} \subseteq \{1, \dots, n\}$ and $x \in \mathcal{B}^n$, $x[S]$ designates the subvector $(x_{i_1}, \dots, x_{i_p}) \in \mathcal{B}^p$. Similarly, for $X \subseteq \mathcal{B}^n$, $X[S]$ designates the set $\{x[S], x \in X\} \subseteq \mathcal{B}^p$. In the rest of the paper, $n$ designates a positive integer.

**Definition 1** A Boolean function of $n$ variables is a function from $\mathcal{B}^n$ to $\mathcal{B}$. The set of all such functions is denoted by $\mathcal{F}_n$, its cardinality is $2^{2^n}$. Given $f \in \mathcal{F}_n$, a point $x \in \mathcal{B}^n$ such that $f(x) = 1$ (respectively, $f(x) = 0$) is called a true point (respectively a false point) of $f$. The set of true points and false points of a function $f$ are respectively denoted by $T_f$ and $F_f$.
For any Boolean function $f \in \mathcal{F}_n$, $T_f \cap F_f = \emptyset$ and $T_f \cup F_f = \mathcal{B}^n$. Furthermore, any couple $(T, F)$ where $T, F \subseteq \mathcal{B}^n$ verify those properties determines a unique function $f \in \mathcal{F}_n$ such that $T = T_f$ and $F = F_f$. In other words, any Boolean function is entirely determined by the set of its true points or, equivalently, by the set of its false points (since $F_f = \mathcal{B}^n \setminus T_f$). The set $\mathcal{F}_n$ is partially ordered: for $f, g \in \mathcal{F}_n$, $f \le g$ iff $T_f \subseteq T_g$ (or equivalently, iff $F_f \supseteq F_g$). In the following, if $f \le g$ then $[f, g]$ will designate the set $\{h \in \mathcal{F}_n, f \le h \le g\} \subseteq \mathcal{F}_n$.

Let $f \in \mathcal{F}_n$. Given $i \in \{1, \dots, n\}$, denote by $f_{|x_i=0}$ and $f_{|x_i=1}$ the two functions in $\mathcal{F}_{n-1}$ defined, for every $(x_1, \dots, x_{i-1}, x_{i+1}, \dots, x_n) \in \mathcal{B}^{n-1}$, by

$$ \left\{ \begin{array}{l} f_{|x_i=0}(x_1, \dots, x_{i-1}, x_{i+1}, \dots, x_n) = f(x_1, \dots, x_{i-1}, 0, x_{i+1}, \dots, x_n), \\ f_{|x_i=1}(x_1, \dots, x_{i-1}, x_{i+1}, \dots, x_n) = f(x_1, \dots, x_{i-1}, 1, x_{i+1}, \dots, x_n). \end{array} \right. \qquad (6) $$

These functions are called restrictions of $f$ on $x_i = 0$ (respectively, on $x_i = 1$). Note that even if Definition 1 does not formally introduce functions with no argument, when $n = 1$ we will conveniently consider that the restrictions are simply the constants $f(0)$ and $f(1)$. Thus, the restrictions of $f(x_1) = x_1$ for instance are $f_{|x_1=0} = 0$ and $f_{|x_1=1} = 1$. Restrictions prove useful in the following definitions 2 and 3.

**Definition 2** Let $f \in \mathcal{F}_n$ and $i \in \{1, \dots, n\}$. The variable $x_i$ is said inessential for $f$ if $f_{|x_i=0} = f_{|x_i=1}$, otherwise it is said essential. The set of $i \in \{1, \dots, n\}$ such that $x_i$ is essential is called the *support* of $f$ and is denoted by $S(f)$.

**Remark 3** Observe that a function $f \in \mathcal{F}_n$ admitting inessential variables can also be viewed as a function of $p$ variables, where $p = |S(f)| < n$. For $x \in \mathcal{B}^n$, we will abusively write $f(x) = f(x[S(f)])$, thus using the same symbol $f$ to designate the function as an element of $\mathcal{F}_n$ and as an element of $\mathcal{F}_p$. Moreover, note that $p = 0$ arises if and only if $f$ is one of the constant functions $f = 0$ or $f = 1$.

**Definition 3** Let $f \in \mathcal{F}_n$ and $i \in \{1, \dots, n\}$. If $f_{|x_i=0} \le f_{|x_i=1}$ (respectively $f_{|x_i=0} \ge f_{|x_i=1}$), then $f$ is increasing (respectively decreasing) in $x_i$. In either case, $f$ is said *monotone* (or *unate*) in $x_i$. It is simply said *monotone* (or *unate*) if it is monotone in all $x_i$. In particular, if it is increasing in all $x_i$ then it is said *positive*. The sets of unate and positive functions of $n$ variables will be denoted respectively by $\mathcal{F}_n^+$ and $\mathcal{F}_n^-$.

The classes of unate and positive Boolean functions have attracted much interest in different communities as they share some notable properties. Interested reader will find in the book by Crama and Hammer (2011) and references therein a list of such properties. Positive functions are also extensively reviewed by Korshunov (2003) (as often in the realm of Boolean functions, the terminology is not completely standardized and the term *monotone* in that article actually corresponds to the notion of *positive* function as defined in the present paper).

According to Definition 3, determining whether a function is unate implies to analyze the sign of each variable $x_i$ independently. The following theorem actually gives more global characterizations, in the special case of positive functions. It is a classical result, for completeness a proof can be found in Appendix A.

**Theorem 1** For any $f \in \mathcal{F}_n$, the following assertions are equivalent:
(i) $f \in \mathcal{F}_n^+$,

(ii) $\forall x, y \in \mathcal{B}^n, x \le y \Rightarrow f(x) \le f(y),$

(iii) $\{(x, y) \in T_f \times F_f : x \le y\} = \emptyset,$

(iv) $\{(x, y) \in \min T_f \times \max F_f : x \le y\} = \emptyset.$

## 3.2 The concept of partial Boolean functions

Historically, the concept of Partial Boolean Functions (PBF, sometimes called partially defined Boolean functions) has been developed in the context of switching circuits, notably in view to design circuits with prescribed behaviors in certain Boolean conditions and with arbitrary behaviors in other conditions (“don’t care” values). In a machine learning context, PBF can be used to represent a data set consisting of examples of an unknown phenomenon, or output. The latter is supposed on/off, i.e. it can take the values 0 or 1. Each example takes the form of a *n*-dimensional Boolean vector, containing the values of *n* Boolean variables (or binary attributes). For each given example, one knows the value taken by the output, and the general goal is to infer a Boolean rule describing the output, in function of the *n* variables, that is consistent with the data. An *extension* of the PBF is thus defined as any Boolean function in $\mathcal{F}_n$ accurately reproducing the behavior of all known examples. The following definition summarizes these notions in a mathematical framework (see also Crama et al 1988; Boros et al 2003; Crama and Hammer 2011, chap. 12).

**Definition 4** A *partial Boolean function* (PBF) of dimension $n > 0$ is a couple $(T, F)$, where $T, F$ are two subsets of $\mathcal{B}^n$. The *size* of the PBF is the integer $p = |T| + |F|$. Any Boolean function $f \in \mathcal{F}_n$ such that $T \subseteq T_f$ and $F \subseteq F_f$ is called an *extension* of $(T, F)$. The set of extensions of $(T, F)$ is denoted by $\mathcal{E}(T, F)$.

Following machine learning terminology, points in $T$ are called *positive* examples and points in $F$ are called *negative* examples. If $U$ designates the set $\mathcal{B}^n \setminus (T \cup F)$, points in $U$ are examples for which the value of the phenomenon under study is *unknown*. In many applications, including ours, this term is preferable to “don’t care” values, emphasizing the fact that although they are unknown, those values may still be relevant to the phenomenon’s description (and they can still be obtained at the cost of additional observations).

One fundamental question when dealing with a PBF is to ask whether or not an extension exists and, in the affirmative, whether the set of extensions has a notable structure. This is in fact answered by the following theorem. For the sake of completeness, a proof is given in Appendix B.

**Theorem 2** (Crama and Hammer 2011, p. 515) A *n*-dimensional PBF $(T, F)$ admits an extension in $\mathcal{F}_n$ if and only if $T \cap F = \emptyset$, which can be tested in polynomial time. In this case, the PBF is said *non-degenerate* and $\mathcal{E}(T, F) = [f_{min}, f_{max}]$, where $f_{min}$ and $f_{max}$ are respectively the smallest and largest extensions of $(T, F)$. This set is isomorphic to a Boolean algebra of cardinal $2^q$, where $q = 2^n - |T \cup F|$.

According to Theorem 2, the existence of extensions is a tractable problem (as well as the problem of deciding if a function is an extension). More precisely, it belongs
to class P i.e., it can be answered by an algorithm that is polynomial in the size of the instance (note that in this case, the instance is composed of the two sets *T* and *F*). It also shows that the number of extensions grows exponentially when the size *p* of the PBF becomes small with respect to $2^n$ (the total number of possible examples). In practice this implies that, as the number *n* of variables grows, the number of extensions may become huge, thus necessitating further criteria distinguishing subsets of “good candidates” among them. In general terms, it consists in identifying extensions that verify additional constraints, or that belong to a specific subset of $\mathcal{F}_n$. Among possible candidates are the class of unate or positive functions, $\mathcal{F}_n^+$ and $\mathcal{F}_n^-$ . The case of unate extensions is actually hard, and will be treated in Section 4. The case of positive extensions is tractable, as shown by Theorem 3 below, a proof of which can be found in Appendix B (see also Zuev 1978).

**Theorem 3** (Crama and Hammer 2011, p. 531) A *n*-dimensional PBF (*T*,*F*) admits a positive extension if and only if *J* := {*(*x*,*y*) ∈ *T* × *F*, *x* ≤ *y*} = ∅, which can be tested in polynomial time. The set of positive extensions is of the form E⁺(*T*,*F*) = [*f*⁺<sub>min</sub>, *f*⁺<sub>max</sub>] ∩ $\mathcal{F}$⁺<sub>*n*</sub>, where *f*⁺<sub>min</sub> and *f*⁺<sub>max</sub> are respectively the smallest and largest positive extensions of (*T*,*F*).

Even though no formula exists for the number of positive extensions, it is expected to
be far less than the total number of extensions. This is a good thing from a learning
point of view, as the number of candidate functions for the phenomenon under study
may decrease drastically. In this respect, it is to be noted that to this day no closed
formula is known for the total number of positive functions |$\mathcal{F}_n^+$|, also called the
Dedekind number $D_n$ (the last known value $D_8$ was obtained by Wiedemann (1991)).
Even though $D_n$ grows slower than |$\mathcal{F}_n$| = $2^{2^n}$, it is still exponential. The review by
Korshunov (2003) notably includes bounds for $D_n$.

Besides Theorems 2 and 3 giving general results on the set of extensions, the concept of PBF provides a practical framework to analyze an unknown Boolean phenomenon. One particular interest lies in the identification of a PBF’s minimal supports, that generalize the notion of support for a Boolean function.

3.3 Minimal supports of a PBF

A first step in the inference of a PBF’s extensions is the identification of variables that
are relevant to the phenomenon under consideration, from those that are independent
from it and therefore irrelevant. While rather intuitive, the notion of variable *rele-
vance* in a machine learning context actually gives rise to several possible definitions,
either deterministic or probabilistic (John et al 1994). In the present paper, we adopt
a deterministic approach by generalizing the notion of essential variable of a Boolean
function. Importantly, the concept of a relevant variable for a PBF is not unequivocal,
as shown by the following example (Crama and Hammer 2011, p. 513).
**Example 1** Consider the 8-dimensional PBF $(T, F)$ given by

$$T = \begin{pmatrix} 0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \end{pmatrix}, \quad F = \begin{pmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \end{pmatrix}.$$

Note that we use matrices to represent the sets $T$ and $F$ with the convention that their elements are denoted by rows and columns correspond to variables. One can verify that $(\bar{x}_5 \wedge \bar{x}_8) \vee (x_5 \wedge x_8)$ is an extension, implying that $x_5$ and $x_8$ are sufficient to reconstruct the phenomenon described by $(T, F)$, the other variables being redundant. Generalizing Definition 2, the set $\{5, 8\}$ is then called a *support* of the PBF. Likewise, observe that $(\bar{x}_6 \wedge \bar{x}_7) \vee (x_6 \wedge x_7)$ is also an extension, indicating the couple $\{6, 7\}$ is also a support of the PBF.

Example 1 shows that contrary to a function, supports of a partial function are not unique. To properly formalize this notion, we follow Crama and Hammer (2011) and Boros et al (2003) and propose the following definition, directly inspired by Theorem 2.

**Definition 5** Let $(T, F)$ be a $n$-dimensional non-degenerate PBF such that $T, F \neq \emptyset$. A non-empty set $S \subseteq \{1, \dots, n\}$ is called a *support* of $(T, F)$ if $T[S] \cap F[S] = \emptyset$.

**Remark 4** For convenience, the case of the empty set has been ruled out. By convention, we will say that $\emptyset$ is a support of $(T, F)$ iff $T = \emptyset$ or $F = \emptyset$: this is the only case where constant functions (with empty supports) are extensions. Trivially, if $T = \emptyset$ the simplest extension is the constant $f = 0$ while if $F = \emptyset$ the simplest extension is the constant function $f = 1$.

Thanks to Theorem 2, it is easy to see that if $f \in \mathcal{F}_n$ is an extension of $(T, F)$ then $S(f)$ (the support of $f$ according to Definition 2) is a support of $(T, F)$. The converse, however, is not always true, as shown by the following example.

**Example 2** Consider the bidimensional PBF $(T, F)$ with $T = \{10, 11\}, F = \{00, 01\}$. The supports of $(T, F)$ are the sets $\{1\}$ and $\{1, 2\}$. Nevertheless, even though $\{1, 2\}$ is a support, one can easily see that $(T, F)$ admits a unique extension $f(x_1, x_2) = x_1$, of support $S(f) = \{1\}$ (variable $x_2$ is inessential).

Example 2 shows that in general, a support of a PBF is not necessarily the support of an extension. To avoid this technical detail, next we introduce the notion of *minimal* support of a PBF.

**Definition 6** Let $(T, F)$ be a $n$-dimensional non-degenerate PBF and $S \subseteq \{1, \dots, n\}$. $S$ is a *minimal* support of $(T, F)$ if $S$ is a support of $(T, F)$ and if there is no support $S' \subsetneq S$. The set of minimal supports of $(T, F)$ will be denoted by $\text{Supp}(T, F)$.

Like supports, minimal supports are not unique as shown by Example 1 ($\{5, 8\}$ and $\{6, 7\}$ are both minimal supports). Nevertheless, they are suitably linked with the supports of extensions, as emphasized by the proposition below, a proof of which is given in Appendix C.
**Proposition 1** Let $(T, F)$ be a $n$-dimensional non-degenerate PBF. The set of minimal supports verifies $\text{Supp}(T, F) = \min\{S(f), f \in \mathcal{E}(T, F)\}$. In other words, the minimal supports of a PBF are the minimal supports of its extensions.

*Remark 5* Note that Definition 5 is directly based on Theorem 2. With a very similar development, it is possible to define (minimal) *positive* supports of a PBF in the same spirit by adapting Definition 5 to the set $\mathcal{I}$ defined in Theorem 3 (Crama et al 1988; Crama and Hammer 2011).

The following part is devoted to the algorithmic computation of minimal supports. While this problem is not new from a theoretical point of view, emphasis is put on the tractability of the problem (both theoretical and practical) as it will be a key to the identification of monotonic rules addressed in Part 4.

## 3.4 Computation of a PBF's minimal supports

Consider a $n$-dimensional PBF $(T, F)$ and assume $T \cap F = \emptyset$, thus ensuring the existence of extensions. Without loss of generality, suppose $T$ and $F$ non-empty so that the supports of $(T, F)$ are not empty (see Remark 4 above). To list all relevant variables, one needs to compute the set of minimal supports $\text{Supp}(T, F)$. A customary way is to cast the problem as an Integer Linear Programming (ILP) problem, as done for instance by Crama et al (1988) or by Boros et al (2003). More precisely, those papers propose a formulation under the form of a set-covering problem (more exactly of a hitting set problem, its dual form) which belongs to the class of ILP problems, known to be NP-hard in general (Nemhauser and Wolsey 1989). Nevertheless, this set-cover version takes the form of a minimization problem, thus searching for minimal supports that contain the fewest variables (also called *minimum supports*). In the following, we are interested in the enumeration of all minimal supports, not limiting the search to only minimum supports. The problem can be stated as follows.

### Problem 1 (MIN-SUPPORT)

*Instance:* A non-degenerate, $n$-dimensional PBF $(T, F)$ of size $p$.

*Output:* The set $\text{Supp}(T, F)$ of all minimal supports of $(T, F)$.

Rather than relying on ILP formalism, the computation of minimal supports reduces to a classical enumeration problem, known as *positive (Boolean) dualization* (Crama and Hammer 2011, p. 517 and chap. 4). This problem can be expressed as follows:

### Problem 2 (POS-DUAL)

*Instance:* The set $\max_{f \in \mathcal{F}_n^+} F_f$ of maximal false points of a positive function $f \in \mathcal{F}_n^+$.

*Output:* The set $\min_{f \in \mathcal{F}_n^+} T_f$ of minimal true points of $f$.

Another common way to express positive dualization is based on normal Boolean expressions, namely disjunctive normal forms (DNF) and conjunctive normal forms (CNF). Any positive function $f \in \mathcal{F}_n^+$ admits a unique minimal DNF and a unique minimal CNF and the dualization<fnref n="3" /> of $f$ consists in computing one from the other

<footnote n="3">³ In this context, the term “dualization” comes from the notion of dual functions defined as follows: for $f \in \mathcal{F}_n$, the dual of $f$ is $f^d \in \mathcal{F}_n$ such that $f^d(x) = f(\bar{x})$, $x \in \mathbb{R}^n$.</footnote>
(Crama and Hammer 2011, chap. 4). As a combinatorial enumeration problem, positive dualization is actually related to many problems arising in different fields of Computer Science and Graph Theory, as reviewed by Eiter et al (2008). In particular, it is equivalent to computing minimal transversals of a finite hypergraph, thus giving one of the first algorithmic solutions by Berge (1989).

For the sake of completeness, in the following we summarize the main steps showing the equivalence of MIN-SUPPORT and POS-DUAL. The proofs of Propositions 2 and 3 can be found in Appendix C. Recall that for any subset $S \subseteq \{1, \dots, n\}$, the lower-case symbol $s$ designates the Boolean representation of $S$ ($s \in \mathcal{B}^n$, $s_i = 1$ iff $i \in S$). Let $(T, F)$ be a $n$-dimensional, non-degenerate PBF; define the Boolean function $\Sigma \in \mathcal{F}_n$ as follows: $\Sigma(s) = 1$ if $S$ is a support of $(T, F)$ and $\Sigma(s) = 0$ otherwise.

**Proposition 2** *The Boolean function Σ is positive. Furthermore, the minimal true points of Σ are exactly the minimal supports of (T, F).*

Now introduce the set $\mathcal{A} := \{\overline{x} \oplus y, (x,y) \in T \times F\}$, where $\oplus$ denotes the “exclusive or” operator: $x \oplus y = (x \land \overline{y}) \lor (\overline{x} \land y)$. In other words, for $x,y \in \mathcal{B}^n$, Boolean vector $a = \overline{x} \oplus y$ verifies $a_i = 1$ iff $x_i = y_i$, for any $i \in \{1, \dots, n\}$.

**Proposition 3** *The maximal false points of Σ are the maximal elements of A, in other words $\max F_Σ = \max A$. The computation of $\max F_Σ$ is polynomial in the size of the instance (T, F).*

The polynomial equivalence of MIN-SUPPORT and POS-DUAL naturally follows Propositions 2 and 3. Even though the dualization problem has been investigated for many years, its precise tractability status is still an open question, as noted by Eiter et al (2008). In the nineties, the landmark paper by Fredman and Khachiyan (1996) provided a quasi-polynomial time algorithm to solve a decision version of the problem, leading to subsequent quasi-polynomial total time algorithms by Gurvich and Khachiyan (1999) (i.e. with a quasi-polynomial time in the combined size of the input and the output). If, from a theoretical point of view, the existence of a polynomial total time algorithm is still open, in practice efficient algorithmic solutions have been investigated, leading to efficient implementations solving relatively large instances (e.g. with tens of variables and tens of thousands examples, see Part 5) in reasonable time, for example the one by Murakami and Uno (2014). This is important, as the computation of minimal supports is a critical step to identify variables that are relevant to the phenomenon modeled by a PBF. It is all the more crucial in the next part, where a method is proposed to enumerate unate rules on a minimal support, thus allowing to efficiently identify monotonic effects in large datasets.

# 4 Inference of unate rules on a minimal support

## 4.1 About positive extensions

From a theoretical point of view, Theorem 3 gives a polynomial algorithm to analyze the existence of positive extensions for any given PBF. From a practical point of view, one can extend the efficiency of this algorithm by remarking the following rather immediate corollary (a proof is given in Appendix B).
**Corollary 1** Let $(T, F)$ be a $n$-dimensional PBF. $(T, F)$ admits positive extensions if and only if $(\min T, \max F)$ admits positive extensions. Furthermore, $\mathcal{E}^+(T, F) = \mathcal{E}^+(\min T, \max F)$ and

(i) $\min T_{f_{min}^+} = \min T$,

(ii) $\max F_{f_{max}^+} = \max F$,

with $f_{min}^+$, $f_{max}^+$ being respectively the smallest and largest positive extensions of $(T, F)$.

It is worth noting that this result do not affect the theoretical complexity of Theorem 3. In practice though, computing $\min T$ and $\max F$ as a pre-processing step may allow a drastic reduction of the PBF's size$^4$. However, a perhaps greater advantage of this corollary lies in the fact that (i) (respectively (ii)) automatically gives the minimal DNF of the smallest positive extension (respectively, the minimal CNF of the largest positive extension) of $(T, F)$. This is a direct consequence of one-to-one correspondences, for positive functions, between minimal true points and minimal DNF and between maximal false points and minimal CNF (Crama and Hammer 2011, p. 39).

Although the existence of extensions in $\mathcal{F}_n$ and in $\mathcal{F}_n^+$ are tractable problems (they belong to class P according to Theorems 2 and 3), it is not the case for the existence of unate extensions $(\mathcal{F}_n^u)$, which is in fact NP-complete. To understand this striking contrast, consider a unate function $f \in \mathcal{F}_n^u$. According to Definition 3, $f$ is either increasing, decreasing or constant in each variable $x_i$, $i \in \{1, \dots, n\}$. Define $\varepsilon \in \{-1, 0, 1\}^n$ as follows: $\varepsilon_i = -1$ if $f$ is decreasing in $x_i$, $\varepsilon_i = 1$ if $f$ is increasing in $x_i$ and $\varepsilon_i = 0$ if $x_i$ is inessential for $f$. The vector $\varepsilon$ is called the sign profile of $f$. Then, define the change of variables $y = \varphi_\varepsilon(x)$ by $y_i = x_i$ if $\varepsilon_i \in \{0, 1\}$ and $y_i = \bar{x}_i$ if $\varepsilon_i = -1$. It is clear that $g = f \circ \varphi_\varepsilon$ is positive. Now consider a $n$-dimensional PBF $(T, F)$: the same change of variable can be applied to construct $(T_{\varphi_\varepsilon}, F_{\varphi_\varepsilon})$, with

$$ \begin{cases} T_{\varphi_{\varepsilon}} = \{\varphi_{\varepsilon}(x), x \in T\}, \\ F_{\varphi_{\varepsilon}} = \{\varphi_{\varepsilon}(x), x \in F\}. \end{cases} \qquad (7) $$

One immediately sees that $g$ is a positive extension of $(T_{\varphi_\varepsilon}, F_{\varphi_\varepsilon})$ if and only if $f = g \circ \varphi_\varepsilon$ is a unate extension of $(T, F)$, with sign profile $\varepsilon$. Therefore, the search of unate extensions with a fixed sign profile is polynomially equivalent to the search of positive extensions. However, when the sign profile is unknown (which is the case in the major part of applications) an exponential number of sign profiles have to be checked, making the general search of unate extensions significantly harder. While previous reasoning does not prove in itself the NP-completeness of the existence of unate extensions (see Crama and Hammer 2011, p. 533 for a formal proof), it is at the basis of the method proposed in the following. The core of the method consists first in the computation (in polynomial time) of sign profiles that are compatible with a PBF (part 4.2). This information, combined with the computation of minimal supports described in 3.4 will provide an overall tractable algorithm identifying unate extensions of a PBF on a minimal support (part 4.3). While this problem is slightly less general (one needs to compute minimal supports as a preliminary step), its interest lies in its

<footnote>$^4$ Given a set $X$, the computation of $\min X$ (or $\max X$) is at worst quadratic in $|X|$ (consider a case where no couples of elements of $X$ are comparable). Nevertheless, it can be much more efficient in practice with suitable data structures (a more precise analysis of the complexity is beyond the scope of this paper).</footnote>
tractability. Overall, the proposed method provides an efficient way to detect mono-
tonicity in a Boolean unknown phenomenon, which will prove particularly useful in
the context of the inference of metabolic regulations.

4.2 Computing sign profiles compatible with a PBF

Let $i \in \{1, \dots, n\}$. For any set $X \subseteq \mathcal{B}^n$, introduce the projections of $X$ defined by:

$$
\left\{
\begin{array}{l}
X_{|x_i=0} = \{(x_1 \dots x_{i-1}, x_{i+1} \dots x_n) \in \mathcal{B}^{n-1}, (x_1, \dots, 0, \dots, x_n) \in X\}, \\
X_{|x_i=1} = \{(x_1 \dots x_{i-1}, x_{i+1} \dots x_n) \in \mathcal{B}^{n-1}, (x_1, \dots, 1, \dots, x_n) \in X\}.
\end{array}
\right.
$$

For any $i \in \{1, \dots, n\}$, one has $X_{|x_i=0} \cup X_{|x_i=1} = X[\bar{i}]$, where $\bar{i}$ designates the set $\{1, \dots, n\} \setminus \{i\}$. Furthermore, it is well known that any Boolean function $f \in \mathcal{F}_n$ can be uniquely decomposed along variable $x_i$:

$$
f = (x_i \wedge f_{|x_i=1}) \vee (\bar{x}_i \wedge f_{|x_i=0}) = x_i f_{|x_i=1} \vee \bar{x}_i f_{|x_i=0},
$$

where $f_{|x_i=0}, f_{|x_i=1} \in \mathcal{F}_{n-1}$ are the restrictions of $f$ defined by (6). This decomposition is known as Shannon’s expansion. Proposition 4 below actually gives a generalization in the framework of partial Boolean functions.

**Proposition 4** Let (T, F) be a *n*-dimensional PBF.

(i) If (T, F) admits an extension f, then restrictions f|_{x_i=0} and f|_{x_i=1} belong respec-
tively to ℰ(T|x_i=0, F|x_i=0) and ℰ(T|x_i=1, F|x_i=1).

(ii) Reciprocally, if (T|_{x_i=0}, F|_{x_i=0}) and (T|_{x_i=1}, F|_{x_i=1}) admit respective extensions f_0 and f_1, then the function x_i f_1 \lor \bar{x}_i f_0 is an extension of (T, F).

Proof (i) Let $f \in \mathcal{E}(T,F)$. For any $x = (x_1, \dots, x_{i-1}, x_{i+1}, \dots, x_n) \in T_{|x_i=0}$, we have $f_{|x_i=0}(x) = f(x_1, \dots, 0, \dots, x_n) = 1$. In the same way, for any $x \in F_{|x_i=0}$ we have $f_{|x_i=0}(x) = 0$. Therefore, $f_{|x_i=0}$ is an extension of $(T_{|x_i=0}, F_{|x_i=0})$. The fact that $f_{|x_i=1} \in \mathcal{E}(T_{|x_i=1}, F_{|x_i=1})$ is proved with symmetrical arguments.

(ii) Let $f_0 \in \mathcal{E}(T|_{x_i=0}, F|_{x_i=0})$, $f_1 \in \mathcal{E}(T|_{x_i=1}, F|_{x_i=1})$ and define $f := x_i f_1 \lor \bar{x}_i f_0$. Consider any $x \in T$. There are two possible cases, according to the value of $x_i$. If $x_i = 0$, then $x[\bar{i}] \in T|_{x_i=0}$ and $f(x) = f_0(x[\bar{i}]) = 1$; if $x_i = 1$, then $x[\bar{i}] \in T|_{x_i=1}$ and $f(x) = f_1(x[\bar{i}]) = 1$. So in both cases, $f(x) = 1$ and in a similar way, one proves that any $x \in F$ verifies $f(x) = 0$, thus implying $f$ is an extension of $(T, F)$. $\square$

The ensuing theorem gives a new tractable method to detect if a PBF admits exten-
sions which are monotone with respect to $x_i$.

**Theorem 4** Let (T, F) be a *n*-dimensional PBF and suppose $T \cap F = \emptyset$, so that it is non-degenerate. Then for all $i \in \{1, \dots, n\}$,

(i) (T, F) admits an extension increasing in $x_i$ iff $T_{|x_i=0} \cap F_{|x_i=1} = \emptyset$.

(ii) (T, F) admits an extension decreasing in $x_i$ iff $T_{|x_i=1} \cap F_{|x_i=0} = \emptyset$.

In both cases, the condition can be checked in polynomial time.
*Proof* Assertions (i) and (ii) are completely symmetrical and can be proved in a similar way. We only prove (i).

*Necessity:* Let $f$ be an extension of $(T, F)$, increasing in $x_i$. Let $f_0, f_1$ denote respectively $f|_{\{x_i=0\}}, f|_{\{x_i=1\}}$. Proposition 4 implies $f_0 \in \mathscr{E}(T|_{\{x_i=0\}}, F|_{\{x_i=0\}})$, $f_1 \in \mathscr{E}(T|_{\{x_i=1\}}, F|_{\{x_i=1\}})$, and $f$ increasing in $x_i$ implies $f_0 \le f_1$ (see Definition 3). Suppose a vector $x = (x_1, \dots, x_{i-1}, x_{i+1}, \dots, x_n)$ belongs to $T|_{\{x_i=0\}} \cap F|_{\{x_i=1\}}$, then by definition $f_0(x) = 1 > 0 = f_1(x)$ which contradicts the fact that $f$ is increasing in $x_i$. Hence, $T|_{\{x_j=0\}} \cap F|_{\{x_j=1\}} = \emptyset$.

*Sufficiency:* Now suppose $T|_{\{x_i=0\}} \cap F|_{\{x_i=1\}} = \emptyset$. $(T, F)$ being non-degenerate, Proposition 4 ensures $(T|_{\{x_i=0\}}, F|_{\{x_i=0\}})$ and $(T|_{\{x_i=1\}}, F|_{\{x_i=1\}})$ admit extensions. Among them, choose $f_0$ to be the smallest extension of $(T|_{\{x_i=0\}}, F|_{\{x_i=0\}})$ and $f_1$ to be the largest extension of $(T|_{\{x_i=1\}}, F|_{\{x_i=1\}})$. According to the proof of Theorem 2, it means that $T_{f_0} = T|_{\{x_i=0\}}$ and $F_{f_1} = F|_{\{x_i=1\}}$. The initial hypothesis induces $T_{f_0} \cap F_{f_1} = \emptyset$, i.e. $T_{f_0} \subseteq \overline{F_{f_1}} = T_{f_1}$, in other words: $f_0 \le f_1$. With Proposition 4, $f = x_i f_1 \lor \tilde{x}_i f_0$ is an extension of $(T, F)$ and since $f_0 \le f_1$, it is increasing in $x_i$ which concludes the proof.

Finally, note that the computation of $T|_{\{x_i=0\}}$ and $T|_{\{x_i=1\}}$ is in $O(|T|)$, and the computation of $F|_{\{x_i=0\}}$ and $F|_{\{x_i=1\}}$ is in $O(|F|)$. Therefore, checking conditions (i) and (ii) is, in the worst case, quadratic in the size of the PBF $(T, F)$. $\square$

The method to compute sign profiles compatible with a $n$-dimensional PBF $(T, F)$ is described in Algorithm 1. It consists in analyzing the variations of $(T, F)$ extensions with respect to each variable $x_i$ separately. As opposed to Boolean functions where the sign profile is defined exactly (a function is either increasing, decreasing or non-monotonic in $x_i$), the notion of sign profile is defined more loosely for a PBF. Thus, we will say that $(T, F)$ is positive (respectively negative) in $x_i$ if there exists an extension $f \in \mathscr{E}(T, F)$ that is increasing (respectively decreasing) in $x_i$. The definition of the sign profile $\sigma$ of $(T, F)$ comes as a natural consequence; $\sigma \in \{+, -, *, 0\}^n$ is defined as follows: for each $i \in \{1, \dots, n\}$,

- $\sigma_i = +$ if there exists an extension increasing in $x_i$, and there is no extension decreasing in $x_i$,

- $\sigma_i = -$ if there exists an extension decreasing in $x_i$, and there is no extension increasing in $x_i$,

- $\sigma_i = *$ if there is no extension monotone in $x_i$,

- $\sigma_i = 0$ if there exist both an extension increasing in $x_i$ and an extension decreasing in $x_i$ (the sign is thus undetermined).

*Remark 6* Since the sign of each variable is analyzed separately, the definition of $\sigma$ must be handled with care. Indeed, $\sigma_i = \sigma_j = +$ for instance does not necessarily imply there exists an extension $f \in \mathscr{E}(T, F)$ that is increasing in both $x_i$ and $x_j$ simultaneously.

Algorithm 1 is an important step towards the existence of unate extensions, for the two following reasons. First, if for any $i \in \{1, \dots, n\}$, $\sigma_i = *, $ then $(T, F)$ cannot have unate extensions, whatever the other signs. Second, if $\sigma_i \neq *$ for all $i$, then let $n_0 := |\{i, \sigma_i = 0\}|$ denote the number of undetermined signs. Then only $2^{n_0}$ sign profiles must be checked, instead of $2^n$, which could reduce drastically the exploration in some cases. This argument is pushed further in the next part, where it is
<caption>**Algorithm 1** Computing sign profiles compatible with a partial Boolean function</caption>

**Input:** (T, F): a *n*-dimensional PBF.
**Output:** $\sigma \in \{+, -, 0, *\}^n$: the sign profile of (T, F) if extensions exist and $\emptyset$ otherwise.
1: Initialize $\sigma$ as a *n*-dimensional vector
2: **for** i = 1 to *n* **do**
3:     $T_0 := T_{|x_i|=0}$; $T_1 := T_{|x_i|=1}$; $F_0 := F_{|x_i|=0}$; $F_1 := F_{|x_i|=1}$
4:     **if** $T_0 \cap F_0 \neq \emptyset$ OR $T_1 \cap F_1 \neq \emptyset$ **then**
5:         **return**($\emptyset$) ▷ extensions do not exist: terminate
6:     **else**
7:         **if** $T_0 \cap F_1 \neq \emptyset$ AND $T_1 \cap F_0 \neq \emptyset$ **then**
8:             $\sigma(i) := *$ ▷ non-monotonicity in $x_i$
9:             **else if** $T_0 \cap F_1 = \emptyset$ AND $T_1 \cap F_0 \neq \emptyset$ **then**
10:         $\sigma(i) := +$ ▷ increase in $x_i$
11:     **else if** $T_0 \cap F_1 \neq \emptyset$ AND $T_1 \cap F_0 = \emptyset$ **then**
12:         $\sigma(i) := -$ ▷ decrease in $x_i$
13:     **else**
14:         $\sigma(i) := 0$ ▷ sign of $x_i$ undetermined
15:     **end if**
16: **end if**
17: **end for**
18: **return**($\sigma$)

combined with the notion of minimal support to completely eliminate undetermined
signs. Finally, note that Algorithm 1 is polynomial in the size of its input. Indeed, if
$p = |T| + |F|$ is the size of the PBF, then the computation of the different intersections
at lines 4, 7, 9 and 11 can be performed in $O(np^2)$ in worst case (considering bitwise
comparisons), so that the main loop runs in $O(n^2p^2)$.

4.3 Inferring unate rules on a minimal support

Given any *n*-dimensional PBF (*T*, *F*), Algorithm 1 provides a tractable way to analyze monotonicity of extensions. More precisely, values $\sigma_i$ in {+,-,*} indicate possible signs of any unate extensions; however, undetermined signs ($\sigma_i$ = 0) do not give any indication. Unfortunately, in many applications the number of undetermined signs can be high, even reach the number *n* of variables (it is particularly true when the size *p* of the PBF becomes negligible with respect to the total space size 2*^n*). The following result allows to circumvent this difficulty, and comes as a direct consequence of Theorem 4.

**Corollary 2** *Under the hypotheses of Theorem 4, the existence of an extension increasing in $x_i$ and of an extension decreasing in $x_i$ implies the existence of an extension for which variable $x_i$ is inessential.*
*Proof* It suffices to remark (recall that $\bar{i} := \{1, \dots, n\} \setminus \{i\}$):

$$ 
\begin{aligned}
T[\bar{i}] \cap F[\bar{i}] &= (T_{|x_i=0} \cup T_{|x_i=1}) \cap (F_{|x_i=0} \cup F_{|x_i=1}), \\
&= \underbrace{(T_{|x_i=0} \cap F_{|x_i=0})}_{A} \cup \underbrace{(T_{|x_i=0} \cap F_{|x_i=1})}_{B} \cup \\
&\qquad \underbrace{(T_{|x_i=1} \cap F_{|x_i=0})}_{C} \cup \underbrace{(T_{|x_i=1} \cap F_{|x_i=1})}_{D}.
\end{aligned}
$$

$(T, F)$ being non-degenerate, Proposition 4 ensures $A = D = \emptyset$. According to Theorem 4, the existence of an extension increasing in $x_i$ leads to $B = \emptyset$, and the existence of an extension decreasing in $x_i$ leads to $C = \emptyset$. Hence, $T[\bar{i}] \cap F[\bar{i}] = \emptyset$ which, according to Definition 5 means there exists an extension for which $x_i$ is inessential. $\square$

We can now describe a general algorithmic method to search for unate extensions on a minimal support. Let $(T, F)$ be a (non-degenerate) PBF and let $S$ be a minimal support. Without loss of generality, set $T := T[S]$, $F := F[S]$ and suppose $S = \{1, \dots, n\}$ (this step is just a projection on $S$, therefore polynomial). The application of Algorithm 1 to $(T, F)$ provides compatible sign profile $\sigma \in \{+, -, 0, *\}^n$. Thanks to Corollary 2, this vector $\sigma$ is fully determined, i.e. $\sigma \in \{+, -, *\}^n$. Indeed, $\sigma_i = 0$ for some $i$ would imply that $S \setminus \{i\}$ is a support and contradict the fact that $S$ is a minimal support. From there it is easy to conclude:

1. If $\sigma_i = *$ for any $i$, then no unate extension exists on $S$.

2. Otherwise, construct $\varepsilon \in \{-1, 1\}^n$ as follows: $\varepsilon_i = 1$ iff $\sigma_i = +$ and $\varepsilon_i = -1$ iff $\sigma_i = -$. Then the search for unate extensions on minimal support $S$ becomes equivalent to the search for positive extensions of $(T_{\phi_e}, F_{\phi_e})$, defined in (7).

Basically, step 1 gives an immediate, negative answer to the question of existence of unate extensions. Nevertheless, the algorithm provides additional information that can possibly give further insight on the phenomenon modeled by $(T, F)$. Indeed, if variable $x_i$ has an undetermined sign ($\sigma_i = *$), then the sets $B = T_{|x_i=0} \cap F_{|x_i=1}$ and $C = T_{|x_i=1} \cap F_{|x_i=0}$, computed in Algorithm 1, allow to reconstruct the examples in $T$ and $F$ that impede, respectively, increase and decrease with respect to $x_i$. Further examination of these examples may give useful information, by pointing out sources of non-monotonicity with respect to certain variables. Another possibility, when the number of such variables is small, is to use projections of the PBF in order to reconstruct the whole rule. A practical example of this approach is given in Part 5 below.

Step 2 needs further computations, since a fully determined sign profile $\sigma$ is not sufficient for the existence of a unate extension (see Remark 6). However, by construction if $(T, F)$ admits a unate extension $f \in \mathcal{F}_n^u$ then the sign profile of $f$ is necessarily $\varepsilon$. Furthermore, it is straightforward to see that $f$ is a unate extension of $(T, F)$ with profile $\varepsilon$ if and only if $g = f \circ \phi_e$ is a positive extension of $(T_{\phi_e}, F_{\phi_e})$. Therefore, the identification of unate extensions on a minimal support is brought back to the identification of positive extensions, which is polynomial according to Theorem 3. More precisely, one starts by applying change of variable (7) to $(T, F)$ to obtain the new PBF $(T_{\phi_e}, F_{\phi_e})$, which can be done polynomially. Then, following Corollary 1,
the PBF (min $T_{\phi_e}$, max $F_{\phi_e}$) is computed, which is also polynomial. The last step consists in the computation of the set $\mathcal{I} = \{(x,y) \in \min T_{\phi_e} \times \max F_{\phi_e}, x \le y\}$. Thanks to Theorem 3 and Corollary 1, if $\mathcal{I} \ne \emptyset$ then no unate extension exist on minimal support $S$. Otherwise, we directly obtain the minimal DNF of the smallest (respectively the minimal CNF of the largest) unate extension.

# 5 Application: analysis of *B. subtilis* central carbon metabolism

We propose in this part a series of computational experiments illustrating our method. Algorithms were implemented in Matlab (as evoked in Remark 2, the RBA procedure also involves Cplex routines), and the dualization (for the computation of minimal supports) was made with SHD<fnref n="5" /> (Murakami and Uno 2014). All experiments use the RBA procedure validated by Goelzer et al (2015).

The first step consists in the generation of Boolean datasets described in 2.2: after choosing a subset of $n$ specific nutrients, a set of Boolean scenarios $\mathcal{S} \subseteq \{0,1\}^n$ is generated, where each source can be absent or present. In our experiments, we focused primarily on carbohydrates and amino acids, imposing other nutrients to zero except for specific essential sources such as oxygen (to privilege respiration over fermentation), nitrogen (under the form of ammonia) as well as different types of ions. The set of scenarios may be exhaustive (for small $n$) or partial, in which case the scenarios are chosen at random. For each scenario, the RBA procedure is then launched to compute optimal flux configurations $v^* \in \mathbb{R}^{614}$, which are then discretized as described in 2.2. Among the 614 enzymes, we focused on 90 enzymes located in *B. subtilis* central carbon metabolism. Thus, for each irreversible flux (respectively reversible flux) the set $\mathcal{S}$ can be decomposed into one PBF (respectively two PBF) describing the Boolean behavior of the corresponding flux. The second step is the analysis of all obtained PBF with the tools described in Parts 3 and 4: first the minimal supports are computed, then the algorithmic method detailed in 4.3 is applied to detect monotonicities. If a unate extension exists, we obtain rules for the extremal unate extensions (as minimal DNF or minimal CNF, which can be translated from one another with the cost of a dualization). This allows us to test the equality between extremal extensions, and in turn test the uniqueness of a unate extension.

In order to test the validity and practicality of our method, we first generated small and exhaustive datasets (Sections 5.1 and 5.2), specifically designed to recover known rules of catabolite repression. These experiments were successful, further validating the RBA calibration on a qualitative level. Furthermore, a striking majority of the analyzed PBF have unate extensions, which seems to confirm that monotonicity is a critical mathematical property to help capture the order exhibited by bacterial metabolic networks. Encouraged by those results, we then generated large-scale, partial data sets to explore the effects of other sources (Section 5.3).

<footnote n="5">⁵ http://research.nii.ac.jp/~uno/dualization.html</footnote>
## 5.1 Deciphering catabolite repression: towards a hierarchy of carbon sources

In his seminal work, Monod (1958) highlighted the concept of diauxic growth, showing that even a simple organism like *B. subtilis* was able to elaborate strategies with regards to the assimilation of carbon sources. As evoked previously, he notably showed that in the presence of two sources like glucose and sorbitol, the bacterium was able to favor the most efficient one (glucose), turning to the least efficient one (sorbitol) only when the first one has been entirely assimilated. He extended this result to other carbohydrates as well, classifying them into two groups according to their order of preference. Since then, the mechanism of catabolite repression underlying those strategies has been extensively studied, as illustrated for instance by Fujita (2009) or Sonenshein (2007). Nevertheless, to our knowledge Monod (1958) remains quite unique in its systematic analysis of the combinatorics between carbon sources. To test our method, we generated a Boolean data set centered on the 9 sources that are in common between the RBA procedure and Monod's experiments: glucose, fructose, mannose, sucrose<fnref n="6" />, mannitol, maltose, sorbitol, inositol and arabinose. Given the reasonable dimension, we generated an exhaustive data set of $2^9 = 512$ scenarios.

*Remark 7* Since those nine carbohydrates were the only sources of carbon, scenario (0, ..., 0) led to a null solution, where the bacterium was unable to grow. This scenario was artificially added to our data set by imposing all fluxes to zero.

The data set being exhaustive, “partial” functions are in fact completely determined, which means all minimal supports are unique. More surprisingly, all identified rules are unate. In particular, the rules of the nine transporters are summarized in Table 1. These rules clearly indicate a hierarchy in the assimilation of the nine carbohydrates. Among them, glucose and fructose are always favored (RBA does not induce any order between the two, at least on a qualitative level) and the seven other sources can be ordered according to the rule of their transporter: mannitol > mannose > sucrose > maltose > sorbitol > arabinose > inositol (see Fig. 2). Interestingly, the first four all participate to a common entry mechanism, the phosphotransferase system (PTS), allowing the sugar to enter the cell directly in a phosphorylated form. This hierarchy is consistent with Monod’s experimental observations with the exception of sucrose, which seems to be more efficient than predicted by our method. However, a careful examination of the experimental protocol of Monod (1958) indicates that strains were initially cultured in a minimal medium supplemented with sucrose. The apparent discrepancy might then be explained by the fact that sucrose transporter was initially at a high level, favoring its initial assimilation in experimental curves.

Since the RBA procedure is genome-scale, our method also generated logical rules for all internal enzymes. The identification of these rules brings precious information about the internal logic of the metabolic network, as encoded by RBA. For the sake of conciseness, we do not reproduce these results in their entirety, as our primary goal was to focus on catabolite repression. As a single example, we mention that all glycolytic enzymes share the same rule, illustrated by central glycolytic

<footnote n="6">⁶ The sugar “sucrose” is sometimes called “saccharose”.</footnote>
<table><caption>**Table 1** Logical rules of the nine carbon transporters of Monod's experiments. The first column is the transported carbohydrate, the second column is the name of the transporter (as given in RBA) and the third column is the Boolean rule obtained by our method (the conjunctions (∧) are omitted).</caption><thead><tr><th>Source</th><th>Transp.</th><th>Rule</th></tr></thead><tbody><tr><td>glucose</td><td>PtsG</td><td>glucose</td></tr><tr><td>fructose</td><td>Fru<sub>lev</sub></td><td>fructose</td></tr><tr><td>mannitol</td><td>MtlA</td><td>glucose fructose mannitol</td></tr><tr><td>mannose</td><td>ManP</td><td>glucose fructose mannose mannitol</td></tr><tr><td>sucrose</td><td>SacP</td><td>glucose fructose mannose sucrose mannitol</td></tr><tr><td>maltose</td><td>MalP</td><td>glucose fructose mannose sucrose mannitol maltose</td></tr><tr><td>sorbitol</td><td>GutP</td><td>glucose fructose mannose sucrose mannitol maltose sorbitol</td></tr><tr><td>arabinose</td><td>AraE</td><td>glucose fructose mannose sucrose mannitol maltose sorbitol arabinose</td></tr><tr><td>inositol</td><td>IolF</td><td>glucose fructose mannose sucrose mannitol maltose sorbitol inositol arabinose</td></tr></tbody></table>

enzyme GapA:

$$ \text{GapA} = \text{arabinose} \lor \text{inositol} \lor \text{sorbitol} \lor \text{maltose} \lor \text{mannitol} \lor \text{sucrose} \lor \text{mannose} \lor \text{fructose} \lor \text{glucose}. $$

This rule simply means that the presence of either source is sufficient to switch glycolysis on, which was expected since all chosen carbohydrates are glycolytic sources. According to Remark 7 above, it also means that in this configuration glycolysis is necessary and sufficient for bacterial growth. Again, this result is not surprising from a biological viewpoint as every potential source of energy (other than the nine carbohydrates) is absent from the medium.

## 5.2 An efficient tool to tackle the complexity of bacterial carbon management

To test our method further, we explored lesser known parts of *B. subtilis* carbon metabolism, in particular regarding the generalization of catabolite repression to gluconogenic sources such as malate. Malate is one of the primary carbon products in a large group of plants and as such is relatively commonly available in *B. subtilis* natural habitats (Jones 1998). An intermediate of the tricarboxylic acid (TCA) cycle, malate is known to be a preferred carbon source for this organism, as illustrated by rapid adaptations to nutritional shifts (Buescher et al 2012). However, its precise role in the catabolite repression regulatory network is still largely unknown (Meyer et al 2011). To investigate the effects of malate introduction to the general carbon hierarchy, we generated a new data set by adding malate to the nine carbohydrates previously cited. As before, we added the scenario (0, ..., 0) by imposing zero fluxes, leading to an exhaustive data set of $2^{10} = 1024$ scenarios. Again, the logical rules for the ten transporters are all unate; they are presented in Table 2.

Observe that the rule of malate's transport depends only on malate availability, placing it at the top of the hierarchy along with glucose and fructose. This confirms its status of preferred source hinted by Buescher et al (2012). Our results also indicate malate interferes with the previously obtained hierarchy in several specific ways. Regarding PTS sugars, sucrose and maltose enter directly after glucose in the presence of malate, separating the PTS into two groups: mannose and mannitol on the one
<table><caption>**Table 2** Logical rules of transporters in the second data set (9 carbohydrates of Table 1 + malate).</caption><thead><tr><th>Source</th><th>Transp.</th><th>Rule</th></tr></thead><tbody><tr><td>glucose</td><td>PtsG</td><td>glucose</td></tr><tr><td>fructose</td><td>Fru<sub>lev</sub></td><td>fructose</td></tr><tr><td>mannitol</td><td>MtlA</td><td>glucose fructose mannitol</td></tr><tr><td>mannose</td><td>ManP</td><td>glucose fructose mannose mannitol</td></tr><tr><td>sucrose</td><td>SacP</td><td>glucose fructose sucrose (maltose malate ∨ mannose mannitol)</td></tr><tr><td>maltose</td><td>MalP</td><td>glucose fructose maltose (malate ∨ mannose sucrose mannitol)</td></tr><tr><td>sorbitol</td><td>GutP</td><td>glucose fructose sucrose maltose sorbitol (malate ∨ mannose mannitol)</td></tr><tr><td>arabinose</td><td>AraE</td><td>glucose fructose mannose sucrose mannitol maltose sorbitol arabinose</td></tr><tr><td>inositol</td><td>IoIF</td><td>glucose fructose mannose sucrose mannitol maltose sorbitol inositol arabinose</td></tr><tr><td>malate</td><td>CimH2</td><td>malate</td></tr></tbody></table>

hand and sucrose and maltose on the other (see Fig. 2). Interestingly, this separation corresponds to a structural difference: the first group consists of monosaccharides whereas the second one consists of disaccharides. Slight differences between the as- simulation of these groups may thus explain the separation. Moreover, while in the absence of malate sucrose was preferred to maltose, it is the inverse in the presence of malate. Finally, the bottom of the hierarchy is mainly unchanged, except for the fact that sorbitol’s entry no longer depends on mannose and mannitol. Figure 2 de- picts the two hierarchies, in absence and presence of malate, derived from Tables 1 and 2. At this point, it is important to emphasize that these observations naturally result from several modeling hypotheses at the basis of the RBA method. To bear any significance on a biological level, they would need to be confirmed with the help of biological experiments. Nevertheless, even if not confirmed they would still provide insightful information as they would point out an ill-parametrized region of the net- work. On a practical point of view, the ability to detect such weak spots in the sizable and complex metabolic network is one of the main interest of the proposed method.

<figure><img src="image_5.png" /><figcaption>**Fig. 2** Hierarchy in the utilization by *B. subtilis* of the nine carbohydrates in (Monod 1958). On the left: in the absence of malate, on the right: in the presence of malate. Arrows indicate order of preference, interpreted from inferred logical rules (Table 1 and 2).</figcaption></figure>
The observation of other fluxes sheds some light on internal adjustments to malate intake. Most of the inferred rules are monotone, notably GapA. Furthermore, the presence of malate now induces the possibility of gluconeogenesis. In B. *subtilis*, the switch between glycolysis and gluconeogenesis is directly linked with the activity of GapA and its counterpart GapB. It is well captured by the two obtained rules:

$$ \text{GapA} = \text{arabinose} \lor \text{inositol} \lor \text{sorbitol} \lor \text{maltose} \lor \text{mannitol} \lor \text{sucrose} \lor \text{mannose} \lor \text{fructose} \lor \text{glucose}, $$

$$ \text{GapB} = \text{glucose} \text{ fructose} \text{ mannose} \text{ sucrose} \text{ mannitol} \text{ maltose} \text{ sorbitol} \text{ inositol} \text{ arabinose} \text{ malate}. $$

Contrary to the previous case, the presence of malate also induces the existence of several non monotone PBF. It concerns a minority of enzymes: only six are in the central carbon metabolism. Two are in the glycolysis pathway, phosphoglucose isomerase (pgi) and pyruvate kinase (pyk), one in the pentose phosphate pathway, ribulose epimerase (rpe) and three in the TCA cycle, oxoglutarate dehydrogenase (odh), succinyl-coA synthetase (suc) and succinate dehydrogenase (sdh). As an example, consider the case of pyruvate kinase pyk. This enzyme is the last step of glycolysis and interestingly, it is known to undergo complex regulations, still only partially known today (Muñoz and Ponce 2003). When applying Algorithm 1, we obtain the following compatible sign profile:

$$ \begin{array}{c|ccccccc} \sigma & \text{gluc.} & \text{fruc.} & \text{mann.} & \text{sucr.} & \text{mannitol} & \text{malt.} & \text{sorb.} & \text{inos.} & \text{ara.} & \text{malate} \\ \hline + & + & * & + & * & + & + & + & + & - \end{array} $$

Since $\sigma_3 = \sigma_5 = *$, there cannot exist monotone extensions, thus preventing the direct identification of a rule by our method. Still, we show how our results may be used to circumvent this difficulty. First, divide the PBF into four 8-dimensional PBF, by projecting it onto $x_3$ and $x_5$ (mannose and mannitol):

$$ \left\{ \begin{array}{l} (T_{x_3,x_5=00}, F_{x_3,x_5=00}), \\ (T_{x_3,x_5=01}, F_{x_3,x_5=01}), \\ (T_{x_3,x_5=10}, F_{x_3,x_5=10}), \\ (T_{x_3,x_5=11}, F_{x_3,x_5=11}). \end{array} \right. $$

Then, apply the method to these projected PBF. This step results in unate rules:

$$ \left\{ \begin{array}{l} f_{00} = \text{glucose} \lor \text{fructose} \lor \text{sucrose} \lor \text{maltose} \lor \text{sorbitol} \lor \text{arabinose} \lor \text{inositol} \text{ malate}, \\ f_{01} = f_{10} = f_{11} = \text{glucose} \lor \text{fructose} \lor \text{malate}. \end{array} \right. $$

Thus, with a straightforward application of Proposition 4 we are able to reconstruct the (non unate) pyk rule in its entirety:

$$ \begin{align*} \text{pyk} &= \overline{\text{mannose}} \overline{\text{mannitol}} f_{00} \lor (\text{mannose} \lor \text{mannitol}) f_{11}, \\ &= \text{glucose} \lor \text{fructose} \lor \overline{\text{malate}} (\text{mannose} \lor \text{mannitol} \lor \text{inositol}) \lor \overline{\text{mannose}} \overline{\text{mannitol}} (\text{sucrose} \lor \text{maltose} \lor \text{sorbitol} \lor \text{arabinose}). \end{align*} $$

This Boolean function is slightly more complicated than those obtained previously, which may mirror more complex regulations of the pyruvate kinase enzyme. Since the precise regulatory network is still largely unknown, it is difficult to compare this function to actual biological knowledge. Nevertheless, it may provide new insights about the regulation of this enzyme and more generally, this example constitutes another illustration of the exploratory nature of the proposed method.
## 5.3 Exploration of large-scale data sets

Previous experiments illustrated the interest of our method in the case of small exhaustive data sets. Encouraged by these results, we generated higher dimensional data sets to test the method's tractability and explore the effects of other sources on the adjustment of the metabolic network. With growing dimensions, it rapidly becomes impractical (or even impossible) to generate exhaustive data sets, leading to the generation of partial sets of scenarios. We generated two data sets (denoted by I and II in the following) including respectively $n = 32$ and $n = 43$ sources and $p = 17122$ and $p = 27563$ scenarios. To build these sets, we drew random groups of scenarios involving the presence of $i$ sources, $i$ varying from 0 to $n$, in order to mix the presence of sources while ensuring the presence of scenarios with few nutritive sources corresponding to poor extracellular media (note that Boros et al (2003) proposes a theoretical approach on the analysis of random PBF).

Table 3 and Figure 3 summarize our main results. Given the high dimension ($n$) and small coverage ($p/2^n$) of the data sets (Table 3), we imposed an arbitrary threshold of 100000 to the number of computed minimal supports. For the PBF above this threshold, we searched for the largest $k$ such that the subset $\{S \in \text{Supp}(T, F), |S| \le k\}$ had less than 100000 elements. Interestingly, such “non-exhaustive” PBF are in minority, in each data set (see Table 3). Our results also indicate that even with very small learning ratio $p/2^n$, a high proportion of PBF have a unique minimal support, further confirming the generated data sets were mixed enough to capture relevant dependencies.

<table><caption>**Table 3** Description of the two large-scale data sets I and II. Symbols $n$ and $p$ denote respectively the dimension (number of variables) and the size (number of scenarios) of the PBFs and $N$ denotes the total number of PBF in the core carbon metabolism (note that according to the set of scenarios, this number may vary as certain fluxes may or may not be reversible).</caption><thead><tr><th></th><th>n</th><th>p</th><th>p/2<sup>n</sup></th><th>N</th><th>exhaustive min. supp.</th><th>unique min. supp.</th></tr></thead><tbody><tr><td>I</td><td>32</td><td>17122</td><td>4.0 10<sup>-6</sup></td><td>102</td><td>100 (98%)</td><td>39 (38%)</td></tr><tr><td>II</td><td>43</td><td>27563</td><td>3.1 10<sup>-9</sup></td><td>105</td><td>80 (76%)</td><td>12 (11%)</td></tr></tbody></table>

Concerning the detection of monotonicities (Figure 3), in order to limit computational costs we analyzed in each case up to $m = 500$ minimal supports, prioritizing the supports with the fewest variables. Consequently, a PBF may be “undetermined” in case it has more than $m$ supports and none of the $m$ smallest supports is unate. While the number of undetermined PBF is small in data set I (less than 10%), it grows in data set II to almost 40%. This is linked with the general increase of the number of minimal supports, and it means the threshold $m$ should be increased in the future.

In spite of this, our results point out a relatively large proportion of PBF still manageable and explainable with unate rules, even in such high dimensions. This fact is striking, and again confirms that unateness is a good mathematical property to tackle the high complexity arising in metabolic configurations. As before, our method allows to exhibit actual Boolean rules in the unate case or compatible sign profiles in the non-unate case. The investigation of these results, as well as the comparison
<figure><img src="image_6.png" /><figcaption>**Fig. 3** Detection of monotonicities in large-scale data sets I and II. In white: proportion of PBF for which there exists a unate minimal support; in grey: proportion of PBF with no unate minimal support (in both cases, hatched regions indicate uniqueness of the minimal support). In black: proportion of undetermined PBF (i.e. with more than 500 minimal supports and none of the 500 smallest is unate).</figcaption></figure>

to actual biological knowledge on bacterial metabolic networks is under way. One
observation that can be made about the obtained rules is that a lot of them seem to
have partial similarities, either in their expressions or their sign profiles. This does
not come as a surprise as it is well known that part of the behavior of metabolic net-
works is regulated by so-called global regulators, sensing different high-level signals
(such as carbon or nitrogen starvation for example). The identification of such global
variables, in a systematic way, would undeniably help to break the combinatorial ex-
plosion linked with the dimension increase. It constitutes an interesting investigation
field for the future.

Overall, if a general hierarchy in carbon sources is still perceptible in those di-
mensions, the combination of inefficient carbohydrates and energy-degradable amino
acids seems to generate non-unateness in the rules of several enzymes in the core car-
bon metabolism. Again, this kind of phenomena might as well be explained by the
high sophistication of some metabolic regulations (when bacteria are subject to a vast
diversity of external conditions), or by the accumulation of parameter uncertainties
during the reconstruction of the network at the scale of a whole genome. In both
cases, the proposed method provides a mathematical and computational framework
to guide future experiments as well as tackle the challenging complexity in the anal-
ysis of metabolic network’s dynamics and regulation.

**6 Conclusion**

We proposed a general methodology to analyze the regulation of metabolic pathways
in function of the availability in external nutritive sources. The proposed method
combines genome-scale, constraint-based method "Resource Balance Analysis" with
combinatorial optimization concepts. It aims at the inference, on a qualitative level,
of logical rules governing the adjustment of metabolic fluxes in response to any ex-
tracellular medium.

In particular, a novel algorithm is presented to efficiently identify monotone par-
tial Boolean functions on a minimal support. Monotone Boolean functions share re-
markable properties and from a machine learning point of view, they are good can-
didates when one wants to reverse-engineer a complex, high-dimensional black box
system. While this algorithm may be used in very different contexts, its application
to the metabolic network of *Bacillus subtilis* brings promising results in the realm of
metabolic engineering. First, it allows to recover local regulations and to analyze their
effects onto the global dynamical behavior of the network. Second, it provides an ef-
ficient mathematical framework to explore lesser known parts of the network, and
possibly propose new experiments. Finally, the combination of combinatorial opti-
mization concepts and efficient implementations helps to manage the unavoidable
combinatorial explosion arising when analyzing such a complex, high-dimensional
system. As such, hopefully the proposed method will contribute to improve our gen-
eral understanding of metabolism, at the scale of a whole cell.

References

Berge C (1989) Hypergraphs: combinatorics of finite sets, North-Holland Mathematical Library, vol 45. Elsevier

Boros E, Horiyama T, Ibaraki T, Makino K, Yagiura M (2003) Finding essential attributes from binary data. *Annals of Mathematics and Artificial Intelligence* 39:223–257

Buescher J, Liebermeister W, Jules M, Uhr M, Muntel J, Botella E, Hessling B, Kleijn R, Le Chat L. Lecointe F, et al (2012) Global network reorganization during dynamic adaptations of bacillus subtilis metabolism. *Science* 335(6072):1099–1103

Chaves M, Tournier L, Gouzé JL (2010) Comparing Boolean and piecewise affine differential models for genetic networks. *Acta Biotheoretica* 58:217–232

Covert M, Schilling C, Palsson B (2001) Regulation of gene expression in flux balance models of metabolism. *Journal of Theoretical Biology* 213(1):73–88

Crama Y, Hammer P (2011) Boolean functions, theory, algorithms and applications. Cambridge University Press, NY, USA

Crama Y, Hammer P, Ibaraki T (1988) Cause-effect relationships and partially defined Boolean functions. *Annals of Operations Research* 16:299–326

Eiter T, Makino K, Gottlob G (2008) Computational aspects of monotone dualization: a brief survey. *Discrete Applied Mathematics* 156:2035–2049

Fredman M, Khachiyan L (1996) On the complexity of dualization of monotone disjunctive normal forms. *Journal of Algorithms* 21:618–628

Fujita Y (2009) Carbon catabolite control of the metabolic network in *Bacillus subtilis*. *Bioscience, Biotechnology, and Biochemistry* 73(2):245–259

Goelzer A, Bekkal Brikci F, Martin-Verstraete I, Noirot P, Bessières P, Aymerich S, Fromion V (2008) Re-construction and analysis of the genetic and metabolic regulatory networks of the central metabolism of *Bacillus subtilis*. *BMC Systems Biology* 2:20

Goelzer A, Fromion V, Scorletti G (2009) Cell design in bacteria as a convex optimization problem. In: *Proceedings of the 48th IEEE Conference on Decision and Control (CDC'09)*, pp 4517–4522

Goelzer A, Fromion V, Scorletti G (2011) Cell design in bacteria as a convex optimization problem. *Automatica* 47(6):1210–1218

Goelzer A, Muntel J, Chubukov V, Jules M, Prestel E, Nolker R, Mariadassou M, Aymerich S, Hecker M, Noirot P, Becher D, Fromion V (2015) Quantitative prediction of genome-wide resource allocation in bacteria. *Metabolic Engineering* 32:232–243

Gurvich V, Khachiyan L (1999) On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions. *Discrete Applied Mathematics* 96:363–373

Hartwell L, Hopfield J, Leibler S, Murray A (1999) From molecular to modular cell biology. *Nature* 402:C47–C52

John G, Kohavi R, Pfleger K (1994) Irrelevant features and the subset selection problem. In: *Machine Learning: Proceedings of the Eleventh International Conference*, pp 121–129

Jones D (1998) Organic acids in the rhizosphere – a critical review. *Plant and soil* 205(1):25–44

Korshunov A (2003) Monotone Boolean functions. *Russian Mathematical Surveys* 58(5):929–1001

Meyer F, Jules M, Mehne F, Le Coq D, Landmann J, Görke B, Aymerich S, Stülke J (2011) Malate-mediated carbon catabolite repression in bacillus subtilis involves the hprk/ccpa pathway. *Journal of Bacteriology* 193(24):6939–6949

Monod J (1958) Recherches sur la croissance des cultures bactériennes, 2nd edn. Hermann, Paris

Muñoz M, Ponce E (2003) Pyruvate kinase: current status of regulatory and functional properties. Comparative Biochemistry and Physiology Part B 135(2):197–218
Murakami K, Uno T (2014) Efficient algorithms for dualizing large-scale hypergraphs. Discrete Applied Mathematics 170:83–94

Nemhauser G, Wolsey L (1989) Integer programming. In: Nemhauser G, Rinooy Kan A, Todd M (eds) Optimization, Handbooks in Operations Research and Management Science, vol 1, Elsevier (North-Holland), pp 447–527

Orth J, Thiele I, Palsson B (2010) What is flux balance analysis? Nature Biotechnology 28(3):245–248

Sonenshein A (2007) Control of key metabolic intersections in bacillus subtilis. Nature Reviews Microbiology 5(12):917–927

Steinway S, Biggs M, Loughran Jr T, Papin J, Albert R (2015) Inference of network dynamics and metabolic interactions in the gut microbiome. PLoS Comput Biol 11(6):e1004,338

Wiedemann D (1991) A computation of the eighth Dedekind number. Order 8:5–6

Zuev Y (1978) Approximation of a partial Boolean function by a monotonic Boolean function. USSR Computational Mathematics and Mathematical Physics 18(6):212–218

## A Proof of Theorem 1

We start with the following technical lemma.

**Lemma 1** Let $X \subseteq \mathcal{B}^n$. For all $x \in X$, either $x \in \min X$ or there exists $y \in \min X$ such that $y < x$.

*Proof* Consider $x \in X \setminus \min X$. Negating (5), one obtains $x_1 \in X$ such that $x_1 < x$. If $x_1 \in \min X$ then define $y = x_1$ and the proof is over, otherwise the same process is iterated to obtain $x_2 \in X$ such that $x_2 < x_1$. $X$ being finite, this iterative process eventually leads to $y = x_k < x_{k-1} < \cdots < x_1 < x$, with $y \in \min X$. □

*Proof (Theorem 1)* The equivalence between assertions (i) and (ii) is classical (Crama and Hammer 2011, p. 35). The equivalence between (ii) and (iii) is easier to see using negations:

$$ 
\begin{align*}
\neg(\text{ii}) &\iff \exists x, y \in \mathcal{B}^n, (x \le y) \land \neg(f(x) \le f(y)), \\
&\iff \exists x, y \in \mathcal{B}^n, (x \le y) \land (f(x) = 1) \land (f(y) = 0), \\
&\iff \exists x \in T_f, \exists y \in F_f, x \le y, \\
&\iff \neg(\text{iii}).
\end{align*}
$$

Finally, let us prove the implication (iii) ⇒ (iv) (the converse being trivial). Suppose there exists $(x, y) \in T_f \times F_f$ such that $x \le y$. Lemma 1 ensures there exists $\xi \in \min T_f$ such that $\xi \le x$. A symmetrical reasoning gives a $\chi \in \max F_f$ such that $y \le \chi$. Therefore, we found $(\xi, \chi) \in \min T_f \times \max F_f$ such that $\xi \le x \le y \le \chi$, completing the proof. □

## B Proofs of Theorems 2, 3 and Corollary 1

*Proof (Theorem 2)* Suppose $T \cap F \ne \emptyset$, then an extension $f$ cannot exist otherwise it would verify $f(x) = 0$ and $f(x) = 1$ for any $x \in T \cap F$.

Suppose now $T \cap F = \emptyset$ and define the function $f_{min} \in \mathcal{F}_n$ by $T_{f_{min}} = T$, then since $T \cap F = \emptyset$, $F_{f_{min}} = \mathcal{B}^n \setminus T \supseteq F$, therefore $f_{min}$ is an extension of $(T, F)$. With a similar argument, the function $f_{max}$ defined by $F_{f_{max}} = F$ is also an extension of $(T, F)$. To prove the last part of the theorem, it suffices to remark that the set of extensions is in fact the segment $[f_{min}, f_{max}]$:

$$ 
\begin{align*}
f \in \mathcal{E}(T, F) &\iff T \subseteq T_f \text{ and } F \subseteq F_f, \\
&\iff T_{f_{min}} \subseteq T_f \text{ and } F_{f_{max}} \subseteq F_f, \\
&\iff f_{min} \le f \le f_{max}.
\end{align*}
$$

In other words, choosing an extension of $(T, F)$ consists in choosing arbitrary Boolean values on the set $U = \mathcal{B}^n \setminus (T \cup F)$ of unknown examples. This means one has $|U| = 2^n - |T| - |F| = q$ degrees of freedom. From a computational point of view, note that the existence of an extension is simply solved by the computation of the intersection $T \cap F$. In the worst case it will involve $|T| \times |F|$ comparisons, which is polynomial in $p$ the size of the PBF. □
*Proof (Theorem 3)* Suppose $\mathcal{I} \neq \emptyset$, then there are $x \in T$ and $y \in F$ such that $x \le y$. If a positive extension $f$ existed, it would imply $f(x) = 1 > 0 = f(y)$ which is absurd.

Suppose now $\mathcal{I} = \emptyset$. Define $f_{min}^{+} \in \mathcal{F}_n$ by $T_{f_{min}^{+}} := \{x \in \mathcal{B}^n, \exists a \in T, a \le x\}$, then $f_{min}^{+}$ verifies three properties:

(i) $f_{min}^{+}$ is an extension of $(T, F)$,

(ii) $f_{min}^{+}$ is positive, and

(iii) any positive extension $f$ of $(T, F)$ verifies $f_{min}^{+} \le f$.

(i): By construction, $T \subseteq T_{f_{min}^{+}}$. Let $y \in F$ and suppose $y \in T_{f_{min}^{+}}$. Then there is $a \in T$ such that $a \le y$, implying $(a, y)$ belongs to $\mathcal{I}$ which contradicts the assumption $\mathcal{I} = \emptyset$. So $F \subseteq F_{f_{min}^{+}}$ and $f$ is an extension of $(T, F)$.

(ii): Let $x, y \in \mathcal{B}^n$ such that $x \le y$, and suppose $x \in T_{f_{min}^{+}}$. Then there is $a \in T$ such that $a \le x$. Since $x \le y$, it implies that $y$ necessarily belongs to $T_{f_{min}^{+}}$ as well, thus proving $f_{min}^{+}$ is positive.

(iii): Let $f \in \mathcal{E}^{+}(T, F)$ and $x \in T_{f_{min}^{+}}$. There is $a \in T$ such that $a \le x$; $f$ being positive, $f(a) = 1 \le f(x)$, thus proving that $T_{f_{min}^{+}} \subseteq T_f$, i.e. $f_{min}^{+} \le f$.

Now define $f_{max}^{+} \in \mathcal{F}_n$ by $F_{f_{max}^{+}} := \{x \in \mathcal{B}^n, \exists b \in F, x \le b\}$. With completely symmetrical arguments, it can be shown that $f_{max}^{+}$ is also a positive extension of $(T, F)$, and that any positive extension $f$ verifies $f \le f_{max}^{+}$.

To conclude the proof, consider any positive function $f$ verifying $f_{min}^{+} \le f \le f_{max}^{+}$. Then, $T \subseteq T_{f_{min}^{+}} \subseteq T_f$ and $F \subseteq F_{f_{max}^{+}} \subseteq F_f$, ensuring $f \in \mathcal{E}^{+}(T, F)$. Therefore, the set of positive extension is in fact $\mathcal{E}^{+}(T, F) = [f_{min}^{+}, f_{max}^{+}] \cap \mathcal{F}_{n}^{+}$, which is a sublattice of $\mathcal{F}_{n}^{+}$. As for Theorem 2, from a computational point of view deciding whether a positive extension exists is solved by the computation of the set $\mathcal{I}$, which amounts to $|T| \times |F|$ comparisons in the worst case. $\square$

*Proof (Corollary 1)* Let $f$ be a positive extension of $(T, F)$, then $\min T \subseteq T \subseteq T_f$ and $\max F \subseteq F \subseteq F_f$, so $f$ is a positive extension of $(\min T, \max F)$. Reciprocally, suppose $f$ is a positive extension of $(\min T, \max F)$. Let $x \in T$, then there is $y \in \min T$ such that $y \le x$ and the positivity of $f$ implies $f(x) \ge f(y) = 1$, so $T \subseteq T_f$. With a similar reasoning, $F \subseteq F_f$, and $f$ is a positive extension of $(T, F)$.

To prove the second part, recall the smallest positive extension $f_{min}^{+}$ of $(T, F)$ is defined by $T_{f_{min}^{+}} = \{x \in \mathcal{B}^n, \exists a \in T, a \le x\}$. This definition immediately yields $T \subseteq T_{f_{min}^{+}}$. Assertion (i) is proved in two steps.

First, let $x \in \min T_{f_{min}^{+}}$, i.e. (1) $x \in T_{f_{min}^{+}}$ and (2) $(\forall y \in T_{f_{min}^{+}}, y \le x \Rightarrow y = x)$. By definition, (1) implies there exists $a \in T$ such that $a \le x$. Since $T \subseteq T_{f_{min}^{+}}$, $a \in T_{f_{min}^{+}}$ so (2) leads to $a = x$ and $x \in T$. Now let $y \in T$ such that $y \le x$, $y \in T \subseteq T_{f_{min}^{+}}$ so (2) implies $y = x$. In conclusion, $\min T_{f_{min}^{+}} \subseteq \min T$.

Second, let $x \in \min T$, i.e. (1') $x \in T$ and (2') $(\forall y \in T, y \le x \Rightarrow y = x)$. Then clearly $x \in T_{f_{min}^{+}}$. Now let $y \in T_{f_{min}^{+}}$ such that $y \le x$. By definition there is $a \in T$ such that $a \le y$ and (2') leads to $x = y = a$. Therefore, $\min T_{f_{min}^{+}} = \min T$. Equality (ii) is proved by symmetrical arguments. $\square$

## C Proofs of Propositions 1, 2 and 3

*Proof (Proposition 1)* Let $S \in \text{Supp}(T, F)$. Since $T[S] \cap F[S] = \emptyset$, a direct application of Theorem 2 implies the existence of an extension $f$ whose essential variables are in $S$. In other words, $S(f) \subseteq S$. By construction, $S(f)$ is a support of $(T, F)$ and since $S$ is minimal, $S = S(f)$. Furthermore, there cannot be an extension $g$ with $S(g) \subseteq S$ as it would contradict the fact that $S$ is minimal.

Conversely, if $S \in \min\{S(f), f \in \mathcal{E}(T, F)\}$ then there is an extension $f$ such that $S = S(f)$, implying $S$ is a support of $(T, F)$. Furthermore, it is minimal otherwise it would imply the existence of an extension with a support strictly included in $S$, which would lead to a contradiction. $\square$

*Proof (Proposition 2)* The positivity of $\Sigma$ is straightforward: it is a direct application of Theorem 1 and of the fact that any superset of a support is itself a support (which is a natural consequence of Definition 5). The second part is simply a translation of Definition 6.

To prove Proposition 3 we will use the following technical lemma.
**Lemma 2** For all $s \in \mathcal{B}^n$, the following equivalence is verified:

$$ \Sigma(s) = 0 \iff \exists a \in \mathcal{A}, s \le a. $$

*Proof* Let $s \in \mathcal{B}^n$ such that $\Sigma(s) = 0$. By definition, $S$ is not a support of $(T, F)$, i.e. $T[S] \cap F[S] \neq \emptyset$. Let $z \in T[S] \cap F[S]$; there exist $x \in T$ and $y \in F$ such that $x[S] = y[S] = z$. Define $a = \bar{x} \oplus \bar{y}$, $a$ belongs to $\mathcal{A}$ and $x[S] = y[S]$ implies $a_i = 1$ for all $i \in S$, yielding $s \le a$.

Conversely, let $s \in \mathcal{B}^n$ and suppose there exists $a \in \mathcal{A}$ such that $s \le a$. By definition, $a = \bar{x} \oplus \bar{y}$ for some $(x, y) \in T \times F$. Using the usual convention, let $\mathcal{A}$ denote the set $\{i, a_i = 1\} \subseteq \{1, \dots, n\}$. From $a = \bar{x} \oplus \bar{y}$ we deduce that $x[A] = y[A]$, which implies $T[A] \cap F[A] \neq \emptyset$, i.e. $\Sigma(a) = 0$. By positivity of $\Sigma$, $\Sigma(s) = 0$. $\square$

*Proof* (Proposition 3) Let $s \in \max_{\mathcal{A}}$, i.e.: (i) $s \in \mathcal{A}$ and (ii) $(\forall s' \in \mathcal{A}, s' \ge s \Rightarrow s' = s)$. Since $s \in \mathcal{A}$, $s$ belongs to $F_{\Sigma}$. To show it is a maximal element of $F_{\Sigma}$, let $s' \in F_{\Sigma}$ such that $s' \ge s$. Using Lemma 2, $s' \le a$ for some $a \in \mathcal{A}$. So $s \le s' \le a$ and from (ii) we deduce that $s = a$, hence $s = s'$. Therefore, $\max_{\mathcal{A}} \subseteq \max F_{\Sigma}$. Now let $s \in \max F_{\Sigma}$, i.e.: (i') $s \in F_{\Sigma}$ and (ii') $(\forall s' \in F_{\Sigma}, s' \ge s \Rightarrow s' = s)$. Since $s \in F_{\Sigma}$, Lemma 2 implies that $s \le a$ for some $a \in \mathcal{A} \subseteq F_{\Sigma}$. With (ii') we deduce that $s = a$, so $s \in \mathcal{A}$. Now let $s' \in \mathcal{A}$ such that $s' \ge s$. Similarly, $s' \in F_{\Sigma}$ so (ii') yields $s = s'$, which concludes the proof.

Let $p$ designate the size of $(T, F)$. The computation of $\mathcal{A}$ involves $O(p^2n)$ bitwise operations. For a set $X \subseteq \mathcal{B}^n$, the enumeration of its maximal elements is in $O(n|X|^2)$ in the worst case, ensuring that the complexity of the computation of $\max F_{\Sigma}$ is indeed polynomial in the size of the instance. $\square$