ResearchMetabolic networksGSI-R-0014 · Note · Measurement
We enumerate minimal cut sets of the 95-reaction E. coli core network up to size 4, 87–215 times faster than our mixed-integer baseline in single runs.
A minimal cut set of e_coli_core [1] is an inclusion-minimal set of non-biomass reactions whose deletion leaves no flux v with Sv=0 (stoichiometric matrix S), directions respected, biomass flux positive. The model has 17, 128, 351 and 747 of size at most 1, 2, 3 and 4; we list them 98, 215, 133 and 87 times faster than our baseline.
- Before this work
- Tobalina et al. (2016) [2], with the code of [3], enumerated this network's minimal cut sets for biomass, without medium or ATP-maintenance constraints: 18, 111, 223 and 396 of size 1 to 4 (read 16 November 2026). Ours: 17 at size 1, 18 with biomass.
- Evidence
- Internal. Our method and baseline returned the same sets at every size; they share the model-construction code, the HiGHS solver and the set-verifying routine. A third program of ours, written separately, reproduced sizes 1 to 3 with the same definition and solver. Sizes 2 to 4 also equal published counts [2]. No review outside the lab.
- What you can check
- Counts only. Run mcs_count.py with K = 3 on e_coli_core.json from BiGG: 52 to 122 s on an Apple M4; size 4 was not run. Times and ratios cannot be checked: neither our method nor the baseline code is released.
- Not established
- That the ratios say anything about published tools or other networks: one network, one run per size, our own baseline, no published tool run on the same machine.
- Method
- Not published.
What was known
Klamt and Gilles (2004) [4] introduced minimal cut sets; Ballerstein et al. (2012) [5] showed that they are elementary modes (support-minimal steady-state fluxes) of a dual network derived with the Farkas lemma. MCSEnumerator (von Kamp and Klamt, 2014) [3] solves a mixed-integer linear programme (MILP) on that dual and listed all 2,486 cut sets of size 1 to 5 of the genome-scale model iAF1260 in about 430 hours on 12 threads. On this network, [2] listed 240,186 cut sets up to size 10 in 270 s with it. MCS2 (Miraskarshahi et al., 2019) [6] uses a nullspace-based dual; a MILP on it was on average 2.5 times faster than on the Farkas-based dual (Klamt, Mahadevan and von Kamp, 2020) [7]. The review [8] adds lazy-constraint MILPs excluding the supersets of each cut set found. We claim no priority for the method.
The result
| K | Sets of size K | Sets up to K | Baseline (s) | Ratio | Load, method / baseline |
|---|---|---|---|---|---|
| 1 | 17 | 17 | 2.13 | 98 | 21.3 / 21.8 |
| 2 | 111 | 128 | 96.3 | 215 | 21.6 / 30.4 |
| 3 | 223 | 351 | 608 | 133 | 21.7 / 30.1 |
| 4 | 396 | 747 | 2,848 | 87 | 21.9 / 29.1 |
Only each reaction’s direction is kept: the model’s flux bounds, including glucose uptake 10 and the ATP-maintenance lower bound 8.39, become 0 or ±104, with biomass flux at least 1 as normalisation. The directions fix the medium: only glucose, O₂, NH₄⁺, phosphate, CO₂, H₂O and H⁺ can be taken up.
The baseline, written by us after [3], is a Farkas-dual MILP: one dual variable per metabolite, bounded by 103; one binary per deletable reaction j, with big-M constant Mj = 103Σi|Sij| + 1; the number of deletions is minimised. Each cut set is one solve, followed by a constraint excluding it and its supersets, until the optimum exceeds K or the programme is infeasible. The solver is HiGHS 1.15.1 [9].
Baseline version 1 (dual bound 102) returned 343 of the 351 sets of size at most 3. Version 2 (bound 103, looser feasibility tolerances) returned a set failing an LP test at each K = 2, 3, 4. Version 3 (bound 103, tolerances 10-9) returned our method’s sets at every size and is the baseline of the table.
How to check it
"""Minimal cut sets of the BiGG model e_coli_core as a flux cone, by exhaustive level-wise enumeration.
Usage: python3 mcs_count.py e_coli_core.json K (needs numpy and scipy)"""
import hashlib, json, sys
import numpy as np
from scipy.optimize import linprog
path, K = sys.argv[1], int(sys.argv[2])
model = json.load(open(path))
row = {m["id"]: i for i, m in enumerate(model["metabolites"])}
R = model["reactions"]
S = np.zeros((len(row), len(R)))
for j, r in enumerate(R):
for met, coef in r["metabolites"].items():
S[row[met], j] = coef
bio = [j for j, r in enumerate(R) if r["id"].startswith("BIOMASS")][0]
lo = [0 if r["lower_bound"] >= 0 else -1e4 for r in R] # directions only: the model's own bounds become 0 or +-1e4
hi = [0 if r["upper_bound"] <= 0 else 1e4 for r in R]
lo[bio] = 1 # target: biomass flux positive, normalised to >= 1
knock = [j for j in range(len(R)) if j != bio] # the 94 reactions that may be deleted
def growth_survives(C): # LP: steady-state flux with biomass >= 1 and C deleted
b = [(lo[j], hi[j]) for j in range(len(R))]
for i in C:
b[knock[i]] = (0, 0)
res = linprog(np.zeros(len(R)), A_eq=S, b_eq=np.zeros(len(S)), bounds=b, method="highs")
assert res.status in (0, 2) # 0 feasible, 2 infeasible
return res.status == 0
live, mcs = {()}, [] # live: sets of the previous size that contain no cut set
for k in range(1, K + 1):
nxt, tested = set(), 0
for N in live:
for i in range(N[-1] + 1 if N else 0, len(knock)):
C = N + (i,)
if all(C[:t] + C[t + 1:] in live for t in range(k)): # all (k-1)-subsets keep growth
tested += 1
if growth_survives(C):
nxt.add(C)
else:
mcs.append(C) # blocks, and no proper subset does: minimal
live = nxt
masks = sorted(sum(1 << i for i in C) for C in mcs) # fingerprint: bit i is the i-th deletable reaction
digest = hashlib.sha1(",".join(map(str, masks)).encode()).hexdigest()[:12]
print(f"size {k}: {sum(len(C) == k for C in mcs)} minimal cut sets, {len(mcs)} up to size {k}, "
f"{tested} LPs, fingerprint {digest}", flush=True)
python3 mcs_count.py e_coli_core.json 3
size 1: 17 minimal cut sets, 17 up to size 1, 94 LPs, fingerprint 33c5bdbd0d36
size 2: 111 minimal cut sets, 128 up to size 2, 2926 LPs, fingerprint aaa0dc16c582
size 3: 223 minimal cut sets, 351 up to size 3, 65692 LPs, fingerprint fbd3cb101a52Baseline version 3 (baseline_runs.tsv) and our method give these fingerprints at sizes 1 to 3 and 0f5a148e1537 at size 4, for which the script was not run: it should print 396 sets of size 4, 747 in all. With the same input file, a different count or fingerprint refutes the counts in the table.
Limits
- Scope of the ratios. One network, one run per size, our own baseline, no published tool, CPLEX or Gurobi run on this machine. The baseline restarts a MILP per cut set, which the lazy-constraint MILPs of [8] avoid, so the ratios do not estimate the gain over published tools. A same-machine run of the code of [3] would close it.
- Load. The machine was shared at load average 21 to 30, the baseline at the higher load for sizes 2 to 4. A repeat of the baseline at sizes 1 to 3, at load 38, took 3.18, 95.4 and 584 s against 2.13, 96.3 and 608 s. Repeats on an idle machine would close it.
- Definition and arithmetic. The bound 104 was not varied. Each decision is a floating-point LP, and tolerance changed the sets of baseline version 2. Exact-arithmetic certificates for every decision would close it.
Files
- mcs_count.pythe script printed under How to check it; needs Python 3, NumPy and SciPy
- baseline_runs.tsvthe 13 recorded baseline runs: version, size, sets found, set fingerprint as in mcs_count.py, seconds, 1-minute load average, LP test of the returned sets, start time; includes the repeat at load 38
References
- [1]BiGG Models, model e_coli_core: 95 reactions, 72 metabolites, 137 genes. J. D. Orth, R. M. T. Fleming, B. Ø. Palsson, Reconstruction and use of microbial metabolic networks: the core Escherichia coli metabolic model as an educational guide, EcoSal Plus 4(1) (2010), doi:10.1128/ecosalplus.10.2.1; Z. A. King et al., BiGG Models: a platform for integrating, standardizing and sharing genome-scale models, Nucleic Acids Research 44, D515–D522 (2016). Page read 15 November 2026. Link
- [2]L. Tobalina, J. Pey, F. J. Planes, Direct calculation of minimal cut sets involving a specific reaction knock-out, Bioinformatics 32(13), 2001–2007 (2016). Link
- [3]A. von Kamp, S. Klamt, Enumeration of smallest intervention strategies in genome-scale metabolic networks, PLoS Computational Biology 10(1), e1003378 (2014). Link
- [4]S. Klamt, E. D. Gilles, Minimal cut sets in biochemical reaction networks, Bioinformatics 20(2), 226–234 (2004). Link
- [5]K. Ballerstein, A. von Kamp, S. Klamt, U.-U. Haus, Minimal cut sets in a metabolic network are elementary modes in a dual network, Bioinformatics 28(3), 381–387 (2012). Link
- [6]R. Miraskarshahi, H. Zabeti, T. Stephen, L. Chindelevitch, MCS2: minimal coordinated supports for fast enumeration of minimal cut sets in metabolic networks, Bioinformatics 35(14), i615–i623 (2019). Link
- [7]S. Klamt, R. Mahadevan, A. von Kamp, Speeding up the core algorithm for the dual calculation of minimal cut sets in large metabolic networks, BMC Bioinformatics 21, 510 (2020). Link
- [8]S. Klamt, J. Zanghellini, A. von Kamp, Minimal cut sets in metabolic networks: from conceptual foundations to applications in metabolic engineering and biomedicine, Briefings in Bioinformatics 26(2), bbaf188 (2025). Link
- [9]Q. Huangfu, J. A. J. Hall, Parallelizing the dual revised simplex method, Mathematical Programming Computation 10(1), 119–142 (2018): the reference of the HiGHS solver. Link