# Seed Inference in Interacting Microbial Communities Using Combinatorial Optimization

Chabname Ghassemi Nedjad, Sebastián Nelson Mendoza, Clémence Frioux, Loïc Paulevé

► To cite this version:

Chabname Ghassemi Nedjad, Sebastián Nelson Mendoza, Clémence Frioux, Loïc Paulevé. Seed Inference in Interacting Microbial Communities Using Combinatorial Optimization. CMSB 2025 - 23rd International Conference on Computational Methods in Systems Biology, François Fages, Inria Saclay, co-PC chair; Sabine Peres, Univ. Lyon, co-PC chair, Sep 2025, Villeurbanne - Lyon, France. pp.370-387, 10.1007/978-3-032-01436-8_20. http://hal-05230510

HAL Id: hal-05230510

https://inria.hal.science/hal-05230510v1

Submitted on 29 Aug 2025

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
Seed inference in interacting microbial
communities using combinatorial optimization

Chabname Ghassemi Nedjad<sup>1,2[0000-0001-7856-1180]</sup>, Sebastián Nelson
Mendoza<sup>3[0000-0002-2192-5569]</sup>, Clémence Frioux<sup>2[0000-0003-2114-0697]</sup>, and Loïc
Paulevé<sup>1[0000-0002-7219-2027]</sup>

¹ Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, F-33400 Talence,
France

² Inria, Univ. Bordeaux, INRAE, F-33400 Talence, France

³ CMM, Universidad de Chile, CP 837 0456 Santiago, Chile

**Abstract.** The behaviour of microorganisms and microbial communities can be abstracted by models combining a description of their metabolic capabilities as metabolic networks, and suitable computational or mathematical paradigms that further integrate simulation conditions. A major component of the latter is the composition of the environment or growth medium that can be referred to as seeds. Predicting the seeds from the metabolic network and an expected behaviour is an inverse problem that can be addressed with linear programming or logic paradigms such as Answer Set Programming (ASP). Here, we formalise seed prediction for microbial communities, taking into account that their members may interact positively through metabolite transfers, which may reduce the need for external seed metabolites. We address the problem with ASP and add a hybrid component ensuring the satisfiability of linear constraints. We explore the subset-minimality solving heuristic of the Clingo solver and develop two heuristics supporting priority of seeds over transfers. We present a proof of concept of seed inference in small-scale communities, and assess the scalability of the three heuristics at genome-scale. Overall, our work introduces a hybrid logic-linear model for seed inference in interacting microbial communities, and new heuristics for the exploration of the solution space with subset minimality optimisations.

**Keywords:** Answer Set Programming · Metabolic networks · Microbial communities · Solving heuristics · Flux Balance Analysis.

# 1 Introduction

Building predictive models of cellular biochemical behaviour from metabolic networks has a wide range of applications, from the investigation of genetic perturbations to chemical production or human disease comprehension [21, 9, 5, 8]. A metabolic network describes a collection of biochemical reactions transforming input molecules, or metabolites, referred to as reactants, into products. In most cases, these transformations are mediated by enzymes identified through gene-protein-reaction relationships. Considering a full genome, the entire set of
genes can be used to construct genome-scale metabolic networks (GSMNs), often consisting of a few thousands metabolic reactions and metabolites [21].

Metabolic modelling consists in applying a mathematical or computational paradigm to the network in order to derive predictions related to simulated conditions such as a description of the environment. *Constraint-based modelling* and in particular Flux Balance Analysis (FBA) [28] is commonly used. It assumes the quasi steady-state of the system and enables a quantitative prediction of fluxes in reactions. FBA solves an optimisation problem maximising (or minimising) the flux in an objective reaction taking into account bounded flux values for reactions. Alternatively, discrete models relying on a Boolean abstraction of metabolic producibility can be applied to metabolic networks. *Network expansion* (NE) [13, 31] computes the set of reachable metabolites from a collection of *seeds* describing available environmental compounds. Such reachable, or producible, metabolites form the *scope* of the metabolic network from defined seeds.

The *inverse scope problem* aims at predicting seeds satisfying the reachability of targetted metabolites. This problem has been investigated in the past [33, 27] and several algorithms have been developed [10, 22]. Prediction of growth media with metabolic modelling was also explored with constraint-based modelling resulting in tools or algorithms relying on mixed-integer linear programming or linear programming [39, 14, 1, 32, 12]. We introduced in [20] *Seed2LP*, a tool combining FBA and NE to predict sets of seed metabolites associated with an objective metabolic function. This hybrid approach relies on *Answer Set Programming (ASP)* [2] and linear programming to tackle the combinatorics of seed selection with NE while ensuring numerical accuracy with FBA.

Most metabolic models can be applied to a single population or a community of organisms [6], with the latter posing scalability challenges. Here, we focus on the inverse scope problem of seed prediction for communities of microorganisms, regardless of their abundances. Our objective in this work is to extend the prediction of seed metabolites to several populations, each represented by a GSMN, that are likely to interact. Among interactions, mutualistic interactions [23] enable the production of new metabolites by an organism thanks to precursor metabolites released by other populations. Such interactions, that we can refer to as metabolic exchanges, can limit the need for seeds by the division of labour within the community [37].

Following on our work on seed prediction for individual populations [20] and on previous work employing ASP to characterise the metabolism of microbial communities [17, 3], we use this logic paradigm to tackle the combinatorics of seed prediction in an interacting community. Our model distinguishes two components: the set of external seeds, and the set of metabolite transfers across populations that must be enabled so that the targetted metabolites can be produced by the community. Typically, we consider target metabolites that ensure growth of each individual species, i.e. biomass components. The combinatorics of such a problem is then much higher than for the independent inference of seeds for each species: for a fixed set of candidate seeds, one needs to search if additional transfers are required for ensuring the production of target metabolites. Among
possible solutions, one may want to consider in priority those requiring the fewest external seeds as possible, and then those requiring the fewest transfers as possible. In general, however, not all seeds nor transfers are biologically meaningful. Thus, beyond finding the minimal possible number of seeds, it is often required to browse alternative solutions. With this perspective, we are typically interested in subset-minimal solutions: identifying sets of seeds such that no other strict subset is a solution. Subset-minimal solutions include cardinal-minimal solutions, and give access to a much wider range of alternatives, which can be substantially different in terms of combinations of metabolites and transfers.

In this paper, we provide two main contributions, illustrated in Fig. 1. First, we formally extend the seed inference problem from individual metabolic networks to communities of metabolic networks. Then, we study several combinatorial optimisation algorithms based on the ASP solver Clingo [19] for exploring the combinatorial space of subset-minimal solutions. Notably, we show the tractability of this logic-programming approach on communities of GSMNs.

# 2 Background

## 2.1 Metabolic Networks and associated stoichiometric matrices

A metabolic network is a collection $\mathbf{R}$ of biochemical reactions of the form

$$ \alpha_1 M_1 + \dots + \alpha_a M_a \leftrightarrow \beta_i M_i + \dots + \beta_n M_n $$

where $M_1, \dots, M_n$ are metabolites from a collection $\mathbf{M}$, and $\alpha_1, \dots, \alpha_a$ and $\beta_i, \dots, \beta_n$ are stoichiometric coefficients. In particular, $\{M_1..M_a\}$ are referred to as reactants and $\{M_i..M_n\}$ as products. The network can be represented as a hypergraph with metabolites as nodes and hyperedges denoting reactions.

Alternatively, the contents of the network can be described as a stoichiometric matrix $\mathcal{X} \in \mathbb{R}^{\mathbf{M} \times \mathbb{R}}$, where rows are the metabolites $\mathbf{M}$, and columns the reactions $\mathbf{R}$. Given a metabolite $m_i \in \mathbf{M}$ and a reaction $r_j \in \mathbf{R}$, the matrix stoichiometric coefficient $\mathcal{X}_{i,j}$ indicates the net gain in metabolite $m_i$ whenever applying reaction $r_j$ positively. Therefore, negative coefficients denote consumption (reactants) of metabolites and positive coefficients production (products). However, such a representation does not fully capture the metabolites that are both reactants and products of a reaction.

## 2.2 Flux Balance Analysis, a numerical model of metabolic activity

Flux Balance Analysis (FBA) is a mathematical model that aims at predicting the activity, or flux distribution, in reactions under a quasi steady state assumption for intracellular metabolites [28]. FBA uses the stoichiometric matrix $\mathcal{X}$ and additional constraints related to thermodynamics that bound the flux values of reactions. As such, a lower bound and an upper flux bound $\nu_{min,r}, \nu_{max,r} \in \mathbb{R}$ are associated with each reaction $r$. Whenever one of the bounds is null, the reaction is said irreversible.
<figure><img src="image_2.png" /><figcaption>**Fig. 1: Overview of the problem and the contributions.** We address the problem of predicting growth media for interacting microbial communities, taking into account positive "cooperative-like" mutualistic interactions that may lead to metabolite exchanges (transfers) among species (top-left panel). Top-right panel illustrates two toy metabolic networks as bipartite graphs (metabolites as ellipses, reactions as squares). In order to reduce the combinatorics associated with the search space, we aim at selecting subset-minimal sets of seeds and transfers satisfying a defined metabolic objective (reachability of $R_1$ and $R_4$ in the figure) with network expansion. The metabolism of each population is abstracted as a GSMN that forms the knowledge base of the problem. Any metabolite within the networks can be chosen as seed, and any shared metabolite across two networks can be transferred, unless specified otherwise. The knowledge base and a collection of rules and constraints describing the problem of seed and transfer inference are provided to Clingo ASP solver (bottom-right panel). Default subset-minimality implemented in Clingo considers both seeds and transfers as a unique set. To ensure subset-minimality of both sets, we developed two algorithms. The satisfiability of FBA constraints can be checked afterwards or during the solving process (hybrid inference) with COBRApy, resulting in seed and transfer solutions that satisfy both NE and FBA (bottom-left panel).</figcaption></figure>
FBA solves a linear optimisation problem that maximises (or minimises) the flux in an objective reaction $r_O \in \mathbf{R}$, usually the biomass reaction that models growth. It can be formulated as follows, with $\nu \in \mathbb{R}^{|\mathbf{R}|}$ a vector of the reaction fluxes:

$$ \text{maximise } \nu_{r_O} \qquad (1a) $$

$$ \text{subject to} \qquad \mathcal{X}.\nu = 0 \qquad (1b) $$

$$ \nu_{min} \leq \nu \leq \nu_{max} \qquad (1c) $$

## 2.3 Network Expansion, a Boolean abstraction of metabolic activity

The activity of reactions in a metabolic network can be discretized using a Boolean approximation implemented in the network expansion (NE) algorithm [13]. Starting from a subset of metabolites $\mathbf{S} \subseteq \mathbf{M}$, called *seeds* representing compounds that are available in the environment (e.g. growth medium), NE determines the *scope* of the metabolic network by propagating the activation of reactions from the availability of all of their reactants, either from seeds or as products of other, previously reached, reactions.

More formally, the scope of a metabolic network $\mathbf{N} = (\mathbf{M}, \mathbf{R})$ from a set of seeds $\mathbf{S}$ can be computed iteratively until it reaches a fixed point (Eq. (2)). To ease notations, we consider that reactions are irreversible (reversible reactions being duplicated in two irreversible ones). We denote as *reactants(r)* and *products(r)* the reactants and products of a reaction *r* respectively.

$$ \begin{gathered} \text{Scope}(\mathbf{N}, \mathbf{S}) = \bigcup_{i} \mathbf{A}_{i} \quad \text{where} \quad \mathbf{A}_{0} = \mathbf{S} \quad \text{and} \\ \mathbf{A}_{i+1} = \mathbf{A}_{i} \quad \bigcup_{r \in \mathbf{R}: \text{reactants}(r) \subseteq \mathbf{A}_{i}} \text{products}(r) \end{gathered} \qquad (2) $$

## 2.4 Answer Set Programming

Answer Set Programming (ASP) pertains to the field of knowledge representation and reasoning [2]. This logic paradigm solves combinatorial problems on Boolean variables subject to logical constraints. An ASP program consists in a set of atoms, forming the knowledge base, and rules expressing deductions, choices, and constraints. In this work we use the Clingo solver [19] on which we and others relied for previous applications to metabolic modelling [33, 17, 35]. Clingo can be hybridised with linear programming solvers, enabling to verify linear constraints such as those from FBA [18].

Concretely, an ASP program is a set of logical rules of the form:

<footnote n="1">1 $a_0 :- a_1, ..., a_n, \text{ not } a_{n+1}, ..., \text{ not } a_{n+k}.$</footnote>
where $a_i$ are (variable-free) atoms, i.e., elements of the Herbrand base, which is built from all the possible predicates of the logic program (LP). The Herbrand base is built by instantiating the LP predicates with the LP terms (constants or elements of the Herbrand universe).

Essentially, such a logical rule states that when all $a_1, \dots, a_n$ are true and none of $a_{n+1}, \dots, a_{n+k}$ can be proven to be true, then $a_0$ has to be true as well. Whenever $a_0$ is $\perp$ (false), the rule, also called *integrity constraint*, becomes:

1. $\neg a_1, \dots, a_n, \text{ not } a_{n+1}, \dots, \text{ not } a_{n+k}.$

Such a rule is satisfied only if the right-hand side of the rule is false (at least one of $a_1, \dots, a_n$ is false or at least one of $a_{n+1}, \dots, a_{n+k}$ is true). On the other hand, $a_0 \vdash \neg (a_0 \text{ is always true})$ is abbreviated as $a_0$. A solution (answer set) is a *stable* Herbrand model, that is, a minimal set of true atoms where all the logical rules are satisfied. For instance, consider the following program:

1. a.

2. b: $\neg a$.

3. d: $\neg a, c$.

It has for unique solution $\{a, b\}$: indeed, whereas $\{a, b, d\}$ does not contradict the rules, d is not a fact and cannot be derived from a rule; so it is not stable.

ASP allows using variables (starting with an upper-case) instead of terms/predicticates: these *template* declarations will be *grounded* before the solving. We also use the notation $a(X): b(X)$ which is satisfied whenever for each $b(X)$ true, $a(X)$ is true. If any term follows such a condition, it is separated with ;.

Clingo supports combinatorial optimisation with costs functions. Alternatively, the solving process can be customised with heuristics that outputs subset-minimal solutions. A solution is subset-minimal provided no subset of this solution is itself a solution.

# 3 Contributing methods

## 3.1 Problem description

We address the problem of inferring seed metabolites and transfers of metabolites in a community of $n$ metabolic networks $N_1 = (M_1, R_1), \dots, N_n = (M_n, R_n)$ that are each associated to an objective reaction $O_i \in R_i$, for $i \in \{1..n\}$. For convenience, we denote by $MO_i$ the reactants of the objective reaction $O_i$. We generalize NE to capture the reachability of metabolites accounting for possible transfers, and consider linear constraints (FBA) to validate numerically the relevance of inferred solutions. We detail below the characteristics of the problem and the algorithms and heuristics developed for its solving using ASP.

*Merged metabolic networks:* In order to account for the redundancy of metabolic reactions and molecules within GSMNs, each of their components is labelled with the identifier of the community member. This ensures that each population relies on its own enzymatic capabilities to transform molecules, and that both transfers and seed metabolites are specifically applied to a network. Using such labelling
permits considering the collection of metabolic networks as a unique metabolic network, and guarantees explainability of the inference through the association of seeds and transfers to each individual network.

The labelling function $\sigma_i$ for network $i$ is defined as $\sigma_i(M) = (i, M)$ for each $M \in \mathbf{M}_i$. Then, we denote by $\mathbf{N}_{1..n} = (\mathbf{M}_{1..n}, \mathbf{R}_{1..n})$ the merge of the $n$ metabolic networks, with $\mathbf{M}_{1..n}$ being the union of relabelled sets of metabolites, i.e., $\mathbf{M}_{1..n} = \bigcup_{i=1}^n \{\sigma_i(M) : M \in \mathbf{M}_i\}$, and $\mathbf{R}_{1..n}$ being the union of relabelled sets of reactions.

**Network expansion from seeds and transfers:** A seed is a metabolite that is artificially made available to the corresponding network. In the following, $\mathbf{S}$ denotes a set of seeds, i.e., a subset of $\mathbf{M}_{1..n}$. A transfer models the non-reversible transportation of a metabolite $M$ from network $i$ to network $j$. We denote sets of transfers by $\mathbf{T}$, with $\mathbf{T} \subseteq \{(i, M), (j, M) \mid M \in \mathbf{M}_i \cap \mathbf{M}_j\}$.

We generalize the notion of scope of a metabolic network defined in Sect. 2.3 to compute the sets of metabolites in the merged metabolic network that are activated by a given set of seeds $\mathbf{S}$ and transfers $\mathbf{T}$ as follows:

$$ \text{Scope}(\mathbf{N}_{1..n}, \mathbf{S}, \mathbf{T}) = \bigcup_{i} \mathbf{A}_i \quad \text{where} \quad \mathbf{A}_0 = \mathbf{S} \quad \text{and} \\ \mathbf{A}_{i+1} = \mathbf{A}_i \cup \bigcup_{r \in \mathbf{R}_{1..n}: \text{reactants}(r) \subseteq \mathbf{A}_i} \text{products}(r) \quad (3) \\ \cup \{M_j \mid (M_i, M_j) \in \mathbf{T}, M_i \in \mathbf{A}_i\} $$

**Seed and transfer search in a merged metabolic network:** A collection of objective reactions, that usually correspond to biomass reactions of each community member [28], or metabolites, are identified in the merged network. In this paper, as defined in the beginning of this section, we consider objectives on sets of metabolites, for instance reactants of biomass reactions. We denote by $\text{MO}_{1..n} = \bigcup_{i=1}^n \{\sigma_i(M) : M \in \text{MO}_i\}$ the merge objective on metabolite production. The search for seeds and transfers occurs within the collection of all metabolites (including internal ones) of the merged metabolic network describing the microbial community, with the objective of ensuring the reachability of targets $\text{MO}_{1..n}$. Thus, the problem of seed identification in communities of interacting metabolic networks can be formalized as follows:

$$ \text{find } \mathbf{S} \subseteq \mathbf{M}_{1..n} \text{ and} \quad (4a) \\ \mathbf{T} \subseteq \{(i, M), (j, M) \mid M \in \mathbf{M}_i \cap \mathbf{M}_j; i, j \in \{1..n\}\} $$

$$ \text{such that } \text{MO}_{1..n} \subseteq \text{Scope}(\mathbf{N}_{1..n}, \mathbf{S}, \mathbf{T}) \quad (4b) $$

**ASP implementation:** We show in Listing 1.1 a simplified implementation in ASP of the seed and transfer search in a merged metabolic network. Inputs (L1-6) are the (labelled) contents of the merged metabolic networks and the objectives (targets). Note that the ASP implementation allows for the possibility
<caption>**Listing 1.1** Seed inference in metabolic network community</caption>

```R
1 % input: merged metabolic network defined with atoms of the form:
2 % metabolite(I,M): metabolite M of network I
3 % reaction(R): reaction R of one network (assumed to be unique for simplification purposes)
4 % reactant(R,(I,M),Q): reaction R consumes Q metabolites (I,M), assuming Q>0
5 % product(R,(I,M),Q): reaction R produces Q metabolites (I,M), assuming Q>0
6 % target(I,M): metabolite M of network I must be produced
7
8 % select seeds
9 { seed(I,M) : metabolite(I,M), not target(I,M) }.
10
11 % scope with seeds
12 scope(I,M) :- seed(I,M).
13 scope(R) :- reaction(R); scope(I,M) : reactant(R,(I,M),_).
14 scope(I,M) :- scope(R); product(R,(I,M),_).
15
16 % select transfers
17 { transfer(I,J,M) : scope(I,M), metabolite(J,M), I != J }.
18
19 % scope with transfers
20 scope(J,M) :- transfer(I,J,M), scope(I,M).
21
22 % each target must be in the scope
23 :- target(I,M), not scope(I,M).
```

of a metabolite being both consumed and produced in a reaction, such as in transport reactions. Seeds are selected among all metabolites except targets (L9). The NE scope is computed from these seeds and the metabolic network contents (L11-14), considering that all reactants of a reaction must be in the scope for its products to be reached (L13-14). Transfers are triplets of a donor, a receiver and a metabolite. The donor's labelled version of the metabolite must be reachable and the donor must be distinct from the receiver (L17). The receiver's labelled version of the metabolite is added to the scope (L20). Finally, there cannot be targets that are not reached (L23). This simplified code does not describe additional features of the search such as forbidding when possible the accumulation of metabolites and limiting the combinatorics of seed search by accounting for microbial compartments that are already introduced in [20].

## 3.2 Solving heuristics for seed and transfer inference

The inference problem has typically numerous solutions. Notably, remark that if $(S, T)$ is a solution, then any superset of seeds $S' \supseteq S$ and transfers $T' \supseteq T$ form a solution $(S', T')$. This motivates the focus on identifying only *subset-minimal* solutions. Leveraging on our logic ASP implementation, one can directly use the heuristics capabilities of solvers such as Clingo to obtain solutions $(S, T)$ so that $S \cup T$ is subset-minimal. We refer to this strategy as *Global subset minimal (G)*:

Limiting the number of transfers can be relevant for applications in biology as they imply complex transportation processes. Nevertheless, the number of seeds required to ensure the growth of a community is naturally a prime objective. Unfortunately, subset-minimal heuristics in ASP does not support priorities.
**Algorithm 1** *G* subset-minimal

1: **for all** solutions (S, T) to Eq. (4) s.t. S ∪ T is subset-minimal **do**

2: **output** (S, T)

3: **end for**

This led us to consider alternative search algorithms. The first one, *Bisteps subset-minimal* (*B*), consists in identifying first solutions that are subset-minimal only for the seeds, and then, having set the set of seed, search for associated subset-minimal transfers:

**Algorithm 2** *B* subset-minimal

1: **for all** solution (S, T) to Eq. (4) s.t. S is subset-minimal **do**

2: **first output** (S*)

3: Set S* and find T

4: **for all** solution (S*, T) to Eq. (4) s.t. T is subset-minimal **do**

5: **final output** (S*, T)

6: **end for**

7: **end for**

We propose an alternative to *B*, *Delete seed supersets* (*D*), with the main objective of iterating on the seed search while reducing the space of solution. The seed searching is similar to the *G* method, by finding a subset minimal of both seeds and transfers atoms, but at each iteration, the supersets and the current set of seeds are forbidden for the next iterations. Therefore, fewer set of seeds are authorized at each iteration. However, this approach still optimises on both seeds and transfers globally: a set of seeds selected after some iterations could be a subset of one of the previously found solutions. We implemented a validation step that tests each newly inferred set of seeds: if it is a subset of a previous set of seeds, the latter is discarded.

**Algorithm 3** *D* subset-minimal

1: **for all** solution (S, T) to (4a) s.t. S ∪ T is subset-minimal **do**

2: **output** (S, T)

3: erase outputed solutions being a strict superset of S

4: add constraint for excluding further solutions being a strict superset of S

5: **end for**

From an algorithmic point of view, the post-erasing of solutions that are discovered to be non-minimal can be computationally substantial. Nevertheless, one can expect such an algorithm to be of interest when solving large instances as it avoids the optimisation over seed sets.
<table><caption>Table 1: Results of solving algorithms on the selection (checkmarks) of solutions in a complete toy solution space of seeds and transfers described in the first column. Tested algorithms are the one native to Clingo (G) and the two ones developed in this work (Bistep subset-minimal B and Delete supersets D)</caption><thead><tr><th>{Seeds} + {Transfers}</th><th>Clingo G</th><th>Bistep B</th><th>Delete seed supersets D</th></tr></thead><tbody><tr><td>1: {A,B,C,Z} + {E}</td><td>✓</td><td></td><td></td></tr><tr><td>2: {A,B,C,Z} + {F}</td><td>✓</td><td></td><td></td></tr><tr><td>3: {A,B,C} + {K,L}</td><td>✓</td><td>✓</td><td>✓</td></tr><tr><td>4: {A,B,C} + {M,N}</td><td>✓</td><td>✓</td><td>✓</td></tr><tr><td>5: {A,B,C,D} + {E,F}</td><td></td><td></td><td></td></tr><tr><td>6: {A,B,C} + {E,F}</td><td>✓</td><td>✓</td><td>✓</td></tr><tr><td>7: {A,B,C,D} + {G,H}</td><td>✓</td><td></td><td></td></tr><tr><td>8: {A,B,C} + {E,F,G}</td><td></td><td></td><td></td></tr><tr><td>9: {A,B,C} + {I}</td><td>✓</td><td>✓</td><td>✓</td></tr><tr><td>10: {A,B,E} + {I}</td><td>✓</td><td>✓</td><td>✓</td></tr></tbody></table>

Notice that after completion, B and D strategies capture the exact same set of solutions: those being subset-minimal for seeds and subset-minimal for seeds and transfers. Thus, they capture a subset of solutions of G subset-minimal. We show in Table 1 the impact of each heuristic on a simple example. From a given set of 10 (non-optimised) solutions presented in the first column of the table, the presence of the solution with each solving heuristic is presented. For instance, Solution 5 is not G subset-minimal because of the existence of Solution 6; and Solutions 1 and 2 are not subset-minimal on seeds (B, D) because of Solution 3.

### 3.3 FBA validation

In the previous sections, the satisfiability of the objective $O_{1..n}$ is related to NE (Eq. (4b)), but can also include linear constraints in the hybrid context where FBA is considered. We generalised the verification of FBA-related constraints to communities of metabolic networks by considering the merged metabolic network $N_{1..n}$ in which we include the inferred seeds and transfers:

- for each seed $(i, M) \in S$, we add an import reaction $\emptyset \rightarrow (i, M)$;

- for each transfer $((i, M), (j, M)) \in T$, we add a transport reaction $(i, M) \rightarrow (j, M)$.

FBA relies on an objective function that can be dealt with in several ways when considering a community of organisms that each have their own objective function. We detail below two methods we implemented to perform community FBA ensuring the growth of all members.

*Minimal flux* A basic objective is that each target reaction $O_i$ has a strictly positive flux. This is achieved by using the objective function over the sum of
fluxes in target reactions, i.e., $\sum_{i=1}^{n} \nu_{r_{O_i}}$ and by adding constraints

$$ \nu_{r_{O_i}} > 0 \quad \forall i \in \{1..n\} \qquad (5) $$

to the system of equations in Eq. (1).

*Equality of fluxes* Proposed by [7, 24] for community-scale constraint-based models, one can impose that the fluxes of the objective reactions of each network are all equal (and strictly positive). Such a constraint results in fixed relative abundances for each community member over time, which is true at steady state. This boils down to add constraints of the form

$$ \nu_{r_{O_1}} = \nu_{r_{O_i}} \quad \forall i \in \{2..n\} \qquad (6) $$

to the system of equations in Eq. (1) and using $\nu_{r_{O_1}}$ as objective function.

# 4 Experiments

We present in this section the experiments carried on a toy microbial community and the scalability tests performed using published GSMNs. We implemented in Python and ASP seed inference for communities; FBA validation relied on the COBRApy library [14]. In all experiments, the *B* and *D* algorithms do not enumerate the alternative transfer solutions for a given subset-minimal set of seeds. The possibility to enumerate all transfer solutions for a given set of seed is implemented, but we favoured here generating diverse sets of seeds rather than the enumeration of transfers. For *B* (Alg. 2), this is achieved by iterating over only one solution in the second loop (line 3). For *D* (Alg. 3), this is achieved by excluding further solutions being a superset (or equal) to the current solution.

The code is available on https://github.com/bioasp/seed2lp. Experiments have been performed on a 2.6Ghz Intel® Ivy Bridge® CPU with 50GB of RAM.

## 4.1 Toy community

Figure 2 describes a toy community composed of four small metabolic networks, each sharing at least one metabolite with any other, generating a collection of 11 possible transfers. Computation of subset-minimal sets of seeds for each individual network generates 3 solutions for member *Bact 1* ({*H*}, {*F*}, {*G*}, {*A*}, *C*, *K*), 3 for *Bact 2* ({*E*}, *I*}, *J*), {*B*}, *E*}, *J*), {*A*}, *E*}, *J*), 1 for *Bact 3* ({*M*}, *O*), *P*}) and 1 for *Bact 4* ({*Q*}, *R*}, *S*}, *T*}, *U*}).

Table 2 presents the number of solutions and the solving times of all possible combinations of toy networks, with the solving heuristics introduced in subsection 3.2: *G*, *B* and *D*. For each community composition and heuristic, we study the solving of the pure combinatorial problem ensuring the targets are reachable by network expansion (Eq. (4)), and the additional verification of FBA constraints (Eq. (1)) with minimal (Eq. (5)) or equal flux with constraints (Eq. (6)). It appeared that, in this specific case, both latter constraints give the same results, and that the *B* heuristic is consistently the fastest.
<figure><img src="image_3.png" /><figcaption>Fig. 2: Illustration of four toy metabolic networks interacting as a community. Metabolic networks are represented as hypergraphs: nodes of the networks are metabolites and arrows denote reactions. *Cytosol* is the internal compartment of the networks and *ExtraCell* is the extracellular compartment, connecting the modelled system with its boundaries. In our mathematical formalism of metabolic networks, the compartments are encoded by suffixing metabolite names with the compartment they belong to. Dotted lines across networks depict the space of possible metabolite transfers; each pair of networks being connected by a different color. *Biomass 1* (resp. 2, 3, 4) is the objective reaction of *Bact 1* (resp. 2, 3, 4).</figcaption></figure>
<table><caption>Table 2: Application of the three solving heuristics to the toy metabolic networks of Figure 2. The first column describes the community composition, with the numbers corresponding to the identifiers of members in Fig. 2. For each heuristic, we indicate the number of solutions (nb. sol.) and solving time for NE constraint only, or NE+FBA constraints (in parentheses for the latter).</caption><thead><tr><th rowspan="2">Community composition</th><th colspan="2">G<br>NE (NE+FBA)</th><th colspan="2">B<br>NE (NE+FBA)</th><th colspan="2">D<br>NE (NE+FBA)</th></tr><tr><th>nb sol.</th><th>solving time</th><th>nb sol.</th><th>solving time</th><th>nb sol.</th><th>solving time</th></tr></thead><tbody><tr><td>1+2</td><td>58 (30)</td><td>0.099 s (0.894 s)</td><td>11 (7)</td><td><b>0.005 s (0.218 s)</b></td><td>11 (7)</td><td>0.012 s (0.177 s)</td></tr><tr><td>1+3</td><td>9 (7)</td><td>0.084 s (0.145 s)</td><td>5 (4)</td><td><b>0.003 s (0.092 s)</b></td><td>5 (4)</td><td>0.008 s (0.09 s)</td></tr><tr><td>1+4</td><td>3 (2)</td><td>0.093 s (0.079 s)</td><td>3 (2)</td><td><b>0.002 s (0.063 s)</b></td><td>3 (2)</td><td>0.008 s (0.07 s)</td></tr><tr><td>2+3</td><td>5 (5)</td><td>0.084 s (0.1 s)</td><td>5 (5)</td><td><b>0.002 s (0.087 s)</b></td><td>5 (5)</td><td>0.007 s (0.093 s)</td></tr><tr><td>2+4</td><td>6 (6)</td><td>0.091 s (0.114 s)</td><td>3 (3)</td><td><b>0.002 s (0.063 s)</b></td><td>3 (3)</td><td>0.008 s (0.066 s)</td></tr><tr><td>3+4</td><td>2 (2)</td><td>0.087 s (0.059 s)</td><td>1 (1)</td><td><b>0.001 s (0.032 s)</b></td><td>1 (1)</td><td>0.005 s (0.039 s)</td></tr><tr><td>1+2+3</td><td>236 (168)</td><td>0.097 s (4.708 s)</td><td>7 (6)</td><td><b>0.005 s (0.157 s)</b></td><td>7 (6)</td><td>0.011 s (0.185 s)</td></tr><tr><td>1+2+4</td><td>87 (45)</td><td>0.088 s (1.864 s)</td><td>11 (7)</td><td><b>0.007 s (0.357 s)</b></td><td>11 (7)</td><td>0.018 s (0.277 s)</td></tr><tr><td>1+3+4</td><td>18 (14)</td><td>0.097 s (0.427 s)</td><td>5 (4)</td><td><b>0.004 s (0.124 s)</b></td><td>5 (4)</td><td>0.011 s (0.114 s)</td></tr><tr><td>2+3+4</td><td>20 (20)</td><td>0.098 s (0.482 s)</td><td>5 (5)</td><td><b>0.004 s (0.12 s)</b></td><td>5 (5)</td><td>0.011 s (0.127 s)</td></tr><tr><td>1+2+3+4</td><td>708 (504)</td><td>0.163 s (20.571 s)</td><td>7 (6)</td><td><b>0.006 s (0.229 s)</b></td><td>7 (6)</td><td>0.016 s (0.206 s)</td></tr></tbody></table>

## 4.2 Communities of genome-scale metabolic networks

Following our previous work [20] on seed inference of individual GSMNs from the BiGG database [25], we selected four of them, associated to gut bacteria. We combined them to construct communities of size 2 to 4 in order to test the scalability of community seed inference. GSMN normalisation prior seed inference removed the existing seeds, implemented in the model as exchange reactions, by blocking imports as described in [20]. We considered iAF1260 (*Escherichia coli* str. K-12 substr. MG1655 – 2 382 reactions and 1 668 metabolites), STM_v1_0 (*Salmonella enterica* subsp. enterica serovar Typhimurium str. LT2 – 2 545 react. and 1 802 met.), iSF_1195 (*Shigella flexneri* 2a substr. 301 – 2 630 react. and 1 917 met.), and iECUMN_1333 (*Escherichia coli* UMN026 – 2 740 react. and 1 935 met.). The selection criterion was the behaviour of the GSMNs for individual-based seed inference. iAF1260 and STM_v1_0 were chosen because all 1000 generated NE solutions satisfied FBA constraints. On the contrary, iSF_1195 was chosen because only 2/1000 solutions passed FBA validation while a subset of iECUMN_1333’s solutions passed FBA validation (869/1000). The number of shared metabolites within pairs of GSMNs ranged from 1602 metabolites to 1912 metabolites.

Table 3 summarizes the seed and transfer inferences on two to four-member communities using the three solving heuristics (*G*, *B* and *D*). Two experimental conditions were tested: time to compute the first solutions validating NE and FBA, and obtaining the most solutions satisfying NE under a 15 minute timeout. For the latter, satisfiability of FBA constraints (Eq. (1) with constraints of flux equality (6)) was tested a posteriori, and is not accounted for in the time limit.

For all communities, the *G* heuristic raised much more solutions than *B* which itself raised also more solutions than *D*. However, finding the first solution was
<table><caption>Table 3: Results of seed and transfer inference in communities composed of curated GSMN from the BiGG database with the three solving heuristics. We performed two experiments: one until obtaining a solution satisfying both NE+FBA constraints ($1^{st}$ NE+FBA) and one with the enumeration of NE solutions in 15 min. In each experiment, we report the number of solutions satisfying NE and the number of solutions satisfying both NE+FBA. For $1^{st}$ NE+FBA, we indicate the total time for solving NE and checking FBA; TO indicates the absence of solution after 2h of computation.</caption><thead><tr><th rowspan="2">Community</th><th rowspan="2">Conditions</th><th colspan="3">Solving heuristic<br>Nb. sol. validating flux / Nb. sol. raised</th></tr><tr><th>G</th><th>B</th><th>D</th></tr></thead><tbody><tr><td rowspan="2">iAF + iSF</td><td>1<sup>st</sup> NE+FBA</td><td>1/1 (1m 18s)</td><td>1/1 (17s)</td><td>1/1 (1m 41s)</td></tr><tr><td>15min limit</td><td>35 756 / 116 082</td><td>289 / 18 139</td><td>170 / 214</td></tr><tr><td rowspan="2">iAF + STM</td><td>1<sup>st</sup> NE+FBA</td><td>1/1 (1m 44s)</td><td>1/1 (1m 48s)</td><td>1/1 (1m 28s)</td></tr><tr><td>15min limit</td><td>119 200 / 141 733</td><td>18 952 / 19 385</td><td>219 / 229</td></tr><tr><td rowspan="2">STM +<br>iECUMN</td><td>1<sup>st</sup> NE+FBA</td><td>1/157 (32m 32s)</td><td>1/50 (10m 1s)</td><td>0/280 (TO)</td></tr><tr><td>15min limit</td><td>90 892 / 123 939</td><td>407 / 16 807</td><td>0 / 165</td></tr><tr><td rowspan="2">iAF + iECUMN + STM + iSF</td><td>1<sup>st</sup> NE+FBA</td><td>0/300 (TO)</td><td>0/298 (TO)</td><td>1/4 (8m 19)</td></tr><tr><td>15min limit</td><td>5 168 / 57 013</td><td>1 436 / 2 625</td><td>25 / 140</td></tr></tbody></table>

consistently faster with one of the two developed heuristics *B* and *D*. The second community in Table 3 is composed of the two GSMNs for which all of independently computed solution validated FBA constraints in [20]; their community raises the most solutions validating FBA as well. This suggests that the topological structure of these networks that facilitate reconciliation of NE and FBA formalisms also hold at the community level. Overall, the proportion of solutions validating FBA constraints varies with the community and the solving heuristics. Globally, at least one heuristic can generate several hundreds of FBA-validated solutions within 15 minutes for every community.

A notable observation regarding the use of *D* heuristics is that unless all solutions are found by the solver, there is no guaranty of subset minimality, only partial subset-minimality with respect to the sets of computed solutions. On the other hand, *B* mode ensures subset minimality.

# 5 Discussion

The problem of predicting environmental, nutritional inputs to metabolic networks is an inverse problem that has been mostly addressed at the level of individual populations [10, 39, 32, 4]. With the growing interest in understanding microbial communities [15, 34, 16], and the observation that division of labour among their members have many biotechnological applications [36], methods
addressing this problem ought to scale up to communities. Considering a micro-
bial community raises new challenges due to the numerous interactions between
their members [23, 11]. In this work, we addressed the problem of seed infer-
ence in microbial communities taking into account mutualistic, i.e. cooperative
interactions, meaning that one member may provide metabolic resources to an-
other, thereby bypassing nutritional environment limitations. Such behaviour is
expected to occur frequently in microbial ecology [29] and fosters the search
of metabolic interactions, or transfers of molecules, in addition to seeds. It has
to be noted that this work only considers mutualistic interactions but others,
such as competition for limited resources, may impact the growth of a microbial
community. They would require further developments to be taken into account.

Given the redundancy of functions and metabolites in metabolic networks,
the search for seeds and transfers is a highly combinatorial problem. Reasoning-
based approaches have been previously used to tackle such problems [30, 17],
motivating a similar strategy for seed and transfer inference. Previous works ad-
dressing the question of medium prediction for community rather used (mixed-
integer) linear programming algorithms [26, 38], relying on the widely used FBA
modelling framework. Our first contribution was to formally describe the com-
binatorial problem of seed and transfer search in a community of GSMNs con-
sidering the satisfiability of NE constraints and the satisfiability of both NE
and FBA constraints in a hybrid framework. Because subset-minimality of seeds
and transfers is an interesting solving heuristic to provide biologically relevant
solutions, we focused on it as a means to reduce the solution space. Our sec-
ond contribution is to address the limitation of Clingo ASP solver that does not
permit priority over atoms (first seeds, then transfers) in subset-minimality, by
developing two heuristics for this purpose. We studied in depth the behaviour of
Clingo's default subset-minimality (*Global* subsetmin *G*) and the new heuristics,
namely *Bistep* subsetmin *B* and *Delete seed supersets* subsetmin *D*. We illus-
trated their differences and performances on toy minimal communities and on
realistic size communities using curated GSMNs.

The newly developed heuristics are the fastest in providing a first solution
satisfying NE, and NE+FBA constraints. However, *G* heuristic with satisfiabil-
ity of NE raises the most solutions within a time limit, with a good proportion
of them validating FBA constraints, although they do not ensure subset mini-
mality of seeds nor transfers. If the subset minimality is required, the *B* solving
heuristic seems to be a good trade-off between the number of solution raised
and their proportion satisfying FBA. Overall, no configuration nor heuristic
tends to outperform all others, which advocates for the test of several of them
in a iterative manner when studying a new community composition. Much of
the combinatorics rises from the inference of transfers, which makes the problem
more difficult compared to the study of individual populations that we previously
performed [20]. A way to limit this combinatorics is to constrain the number of
transfers with an upper bound during solving.

Here, we limited ourselves to the analysis of a four-member community at
most. Future work testing the scalability of the approaches to larger communities
would be relevant: in biotechnological applications, consortia size is of a similar order of magnitude but real microbiomes rather host hundreds, or even thousands of distinct populations. Additionally, further development work could consider other types of interactions, such as competition, in the search for seeds and transfers.

**Availability of code and data.** Seed2LP is available at https://github.com/bioasp/seed2lp. Datasets, raw results and analysis scripts are available at https://doi.org/10.57745/Y6KDJC for reproducibility purposes.

**Acknowledgments** CF and LP were supported by French National Research Agency (ANR) in the scope of the project REBON (ANR-23-CE45-0008). CF was also supported by ANR France 2030 PEPR Systemes Alimentaires, Microbiome et Santé CULTISSIMO ANR-24-PESA-0002 and ANR France 2030 PEPR Agroécologie et Numérique MISTIC ANR-22-PEAE-0011. Experiments presented in this paper were carried out using the PlaFRIM experimental testbed (https://www.plafrim.fr), supported by Inria, CNRS (LaBRI and IMB), Université de Bordeaux, Bordeaux INP and Conseil Régional de la Nouvelle Aquitaine.

**Conflict of interest** The authors have no competing interests to declare that are relevant to the content of this article.

**Authors contributions.** Conceptualisation: CF, CGN, LP - Supervision: CF, LP - Investigation: CGN - Formal Analysis: CGN - Software: CGN, LP - Methodology: CF, CGN, LP, SNM - Validation: CGN - Visualisation: CF, CGN - Writing, Original Draft Preparation: CF, CGN, LP - Writing, Review & Editing: all - Funding acquisition: CF, LP.

**References**

1. Andrade, R., Wannagat, M., Klein, C.C., Acuña, V., Marchetti-Spaccamela, A., Milreu, P.V., Stougie, L., Sagot, M.F.: Enumeration of minimal stoichiometric precursor sets in metabolic networks. Algorithms for Molecular Biology **11**(1), 25 (2016). https://doi.org/10.1186/s13015-016-0087-3

2. Baral, C.: Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge University Press, New York, NY, USA (2003)

3. Belcour, A., Frioux, C., Aite, M., Bretaigne, A., Hildebrand, F., Siegel, A.: Metage2Metabo, microbiota-scale metabolic complementarity for the identification of key species. *eLife* **9**, e61968 (2020). https://doi.org/10.7554/elife.61968

4. Carr, R., Borenstein, E.: NetSeed: a network-based reverse-ecology tool for calculating the metabolic interface of an organism with its environment. *Bioinformatics* **28**(5), 734–735 (2012). https://doi.org/10.1093/bioinformatics/btr721

5. Carter, E.L., Constantinidou, C., Alam, M.T.: Applications of genome-scale metabolic models to investigate microbial metabolic adaptations in response to genetic or environmental perturbations. *Briefings in Bioinformatics* **25**(1), bbad439 (2023). https://doi.org/10.1093/bib/bbad439
6. Cerk, K., Ugalde-Salas, P., Nedjad, C.G., Lecomte, M., Muller, C., Sherman, D.J., Hildebrand, F., Labarthe, S., Frioux, C.: Community-scale models of microbiomes: Articulating metabolic modelling and metagenome sequencing. Microbial Biotechnology 17(1), e14396 (2024). https://doi.org/10.1111/1751-7915.14396

7. Chan, S.H.J., Simons, M.N., Maranas, C.D.: SteadyCom: Predicting microbial abundances while ensuring community stability. PLOS Computational Biology 13(5), e1005539 (2017). https://doi.org/10.1371/journal.pcbi.1005539

8. Chowdhury, S., Fong, S.S.: Leveraging genome-scale metabolic models for human health applications. Current Opinion in Biotechnology 66, 267-276 (2020). https://doi.org/10.1016/j.copbio.2020.08.017

9. Cortese, N., Procopio, A., Merola, A., Zaffino, P., Cosentino, C.: Applications of genome-scale metabolic models to the study of human diseases: A systematic review. Computer Methods and Programs in Biomedicine p. 108397 (2024). https://doi.org/10.1016/j.cmpb.2024.108397

10. Cottret, L., Milreu, P.V., Acuña, V., Marchetti-Spaccamela, A., Martinez, F.V., Sagot, M.F., Stougie, L.: Enumerating Precursor Sets of Target Metabolites in a Metabolic Network. In: Algorithms in Bioinformatics. WABI 2008. Lecture Notes in Computer Science. vol. 5251, pp. 233-244 (2008). https://doi.org/10.1007/978-3-540-87361-7_20

11. Coyte, K.Z., Rakoff-Nahoum, S.: Understanding Competition and Cooperation within the Mammalian Gut Microbiome. Current Biology 29(11), R538-R544 (2019). https://doi.org/10.1016/j.cub.2019.04.017

12. Crisci, E., Mahout, M., Peres, S.: Computing thermodynamically consistent elementary flux modes with answer set programming. In: Gori, R., Milazzo, P., Tribastone, M. (eds.) Computational Methods in Systems Biology. pp. 80-88. Springer Nature Switzerland, Cham (2024)

13. Ebenhöh, O., Handorf, T., Heinrich, R.: Structural analysis of expanding metabolic networks. Genome informatics. International Conference on Genome Informatics 15(1), 35-45 (2004)

14. Ebrahim, A., Lerman, J.A., Palsson, B.O., Hyduke, D.R.: COBRApy: Constraints-Based Reconstruction and Analysis for Python. BMC Systems Biology 7(1), 74 (2013). https://doi.org/10.1186/1752-0509-7-74

15. Fierer, N.: Embracing the unknown: disentangling the complexities of the soil microbiome. Nature Reviews Microbiology 15(10), 579-590 (2017). https://doi.org/10.1038/nrmicro.2017.87

16. Tara Oceans Foundation, Abreu, A., Bourgois, E., Gristwood, A., Troublé, R., Oceans, T., Acinas, S.G., Bork, P., Boss, E., Bowler, C., Budinich, M., Chafron, S., Vargas, C.d., Delmont, T.O., Eveillard, D., Guidi, L., Iudicone, D., Kandels, S., Morlon, H., Lombard, F., Pepperkok, R., Karlusich, J.J.P., Piganeau, G., Régimbeau, A., Sommeria-Klein, G., Stemmann, L., Sullivan, M.B., Sunagawa, S., Wincker, P., Zablocki, O., (EMBL), E.M.B.L., Arendt, D., Bilic, J., Finn, R., Heard, E., Rouse, B., Vamathevan, J., (EMBRC-ERIC), E.M.B.R.C.E.R.I.C., Casotti, R., Cancio, I., Cunliffe, M., Kervella, A.E., Kooistra, W.H.C.F., Obst, M., Pade, N., Power, D.M., Santi, I., Tsagaraki, T.M., Vanaverbeke, J.: Priorities for ocean microbiome research. Nature Microbiology 7(7), 937-947 (2022). https://doi.org/10.1038/s41564-022-01145-5

17. Frioux, C., Fremy, E., Trottier, C., Siegel, A.: Scalable and exhaustive screening of metabolic functions carried out by microbial consortia. Bioinformatics 34(17), i934-i943 (2018). https://doi.org/10.1093/bioinformatics/bty588
18. Frioux, C., Schaub, T., Schellhorn, S., Siegel, A., Wanko, P.: Hybrid metabolic network completion. Theory and Practice of Logic Programming **19**(1), 83–108 (2019). https://doi.org/10.1017/s1471068418000455

19. Gebser, M., Kaminski, R., Kaufmann, B., Schaub, T.: Multi-shot ASP solving with clingo. Theory and Practice of Logic Programming **19**(1), 27–82 (2019). https://doi.org/10.1017/s1471068418000054

20. Ghassemi-Nedjad, C., Bolteau, M., Bourneuf, L., Paulevé, L., Frioux, C.: Seed2LP: seed inference in metabolic networks for reverse ecology applications. Bioinformatics p. btaf140 (2025). https://doi.org/10.1093/bioinformatics/btaf140

21. Gu, C., Kim, G.B., Kim, W.J., Kim, H.U., Lee, S.Y.: Current status and applications of genome-scale metabolic models. Genome Biology **20**(1), 121 (2019). https://doi.org/10.1186/s13059-019-1730-3

22. Handorf, T., Christian, N., Ebenhöh, O., Kahn, D.: An environmental perspective on metabolism. Journal of Theoretical Biology **252**(3), 530–537 (2008). https://doi.org/10.1016/j.jtbi.2007.10.036

23. Hug, L.A., Co, R.: It Takes a Village: Microbial Communities Thrive through Interactions and Metabolic Handoffs. mSystems **3**(2), e00152-17 (2018). https://doi.org/10.1128/msystems.00152-17

24. Jiménez, N.E., Acuña, V., Cortés, M.P., Eveillard, D., Maass, A.E.: Unveiling abundance-dependent metabolic phenotypes of microbial communities. mSystems pp. e00492-23 (2023). https://doi.org/10.1128/msystems.00492-23

25. King, Z.A., Lu, J., Dräger, A., Miller, P., Federowicz, S., Lerman, J.A., Ebrahim, A., Palsson, B.O., Lewis, N.E.: BiGG Models: A platform for integrating, standardizing and sharing genome-scale models. Nucleic Acids Research **44**(D1), D515-D522 (2016). https://doi.org/10.1093/nar/gkv1049

26. Klitgord, N., Segrè, D.: Environments that Induce Synthetic Microbial Ecosystems. PLoS Computational Biology **6**(11), e1001002 (2010). https://doi.org/10.1371/journal.pcbi.1001002

27. Nikoloski, Z., Grimbs, S., Selbig, J., Ebenhöh, O.: Hardness and Approximability of the Inverse Scope Problem. In: Algorithms in Bioinformatics. WABI 2008. Lecture Notes in Computer Science. vol. 5251, pp. 99–112 (2008). https://doi.org/10.1007/978-3-540-87361-7_9

28. Orth, J.D., Thiele, I., Palsson, B.Ø.: What is flux balance analysis? Nature Biotechnology **28**(3), 245–248 (2010). https://doi.org/10.1038/nbt.1614

29. Pacheco, A.R., Moel, M., Segrè, D.: Costless metabolic secretions as drivers of interspecies interactions in microbial ecosystems. Nature Communications **10**(1), 103 (2019). https://doi.org/10.1038/s41467-018-07946-9

30. Prigent, S., Frioux, C., Dittami, S.M., Thiele, S., Larhlimi, A., Collet, G., Gutknecht, F., Got, J., Eveillard, D., Bourdon, J., Plewniak, F., Tonon, T., Siegel, A.: Meneco, a Topology-Based Gap-Filling Tool Applicable to Degraded Genome-Wide Metabolic Networks. PLOS Computational Biology **13**(1), e1005276 (2017). https://doi.org/10.1371/journal.pcbi.1005276

31. Romero, P.R., Karp, P.: Nutrient-related analysis of pathway/genome databases. Pacific Symposium on Biocomputing. Pacific Symposium on Biocomputing pp. 471–82 (2001)

32. Santos, F.B.d., Olivier, B.G., Boele, J., Smessaert, V., Rop, P.D., Krumpochova, P., Klau, G.W., Giera, M., Dehottay, P., Teusink, B., Goffin, P.: Probing the Genome-Scale Metabolic Landscape of Bordetella pertussis, the Causative Agent of Whooping Cough. Applied and Environmental Microbiology **83**(21), e01528-17 (2017). https://doi.org/10.1128/aem.01528-17
33. Schaub, T., Thiele, S.: Metabolic network expansion with answer set programming. In: Logic Programming. pp. 312–326. Springer Berlin Heidelberg, Berlin, Heidelberg (2009)

34. Schmidt, T.S., Raes, J., Bork, P.: The Human Gut Microbiome: From Association to Modulation. Cell **172**(6), 1198–1215 (2018). https://doi.org/10.1016/j.cell.2018.02.044

35. Thuillier, K., Baroukh, C., Bockmayr, A., Cottret, L., Paulevé, L., Siegel, A.: Learning Boolean Controls in Regulated Metabolic Networks: A Case-Study. In: Computational Methods in Systems Biology, 19th International Conference, CMSB 2021, Bordeaux, France, September 22–24, 2021. pp. 159–180. Lecture Notes in Computer Science (2021). https://doi.org/10.1007/978-3-030-85633-5\_10

36. Tsoi, R., Wu, F., Zhang, C., Bewick, S., Karig, D., You, L.: Metabolic division of labor in microbial systems. Proceedings of the National Academy of Sciences **115**(10), 201716888 (2018). https://doi.org/10.1073/pnas.1716888115

37. West, S.A., Cooper, G.A.: Division of labour in microorganisms: an evolutionary perspective. Nature Reviews Microbiology **14**(11), 716–723 (2016). https://doi.org/10.1038/nrmicro.2016.111

38. Weston, B.R., Thiele, I.: A nutrition algorithm to optimize feed and medium composition using genome-scale metabolic models. Metabolic Engineering (2023). https://doi.org/10.1016/j.ymben.2023.01.010

39. Zarecki, R., Oberhardt, M.A., Reshef, L., Gophna, U., Ruppin, E.: A Novel Nutritional Predictor Links Microbial Fastidiousness with Lowered Ubiquity, Growth Rate, and Cooperativeness. PLoS Computational Biology **10**(7), e1003726 (2014). https://doi.org/10.1371/journal.pcbi.1003726