17. Combinatorial explosion — double perturbations and the wall of 2ⁿ · Dr. Seok's Cancer-Cell Digital Twin, First Steps

In lesson 15 we saw a case where you have to switch two off together for anything to happen. So double perturbations need enumerating too. How much does that cost?

Two things grow at once.

	Single	Double
Combinations to test	2n	4 × n(n−1)/2 = 2n(n−1)
Cells rolled per combination	2ⁿ (the same either way)
Total work	2n · 2ⁿ	2n(n−1) · 2ⁿ

In an eight-gene toy this is no trouble at all. In a realistic hundred-gene model both are impossible.

Even with doubles in the mix, the top of the table is held by single targets — the less you touch, the better.

Python Runs in your browser

import bn

net = bn.twin()
n = len(net.druggable())
print(f"{n} candidate targets")
print(f"  single perturbations : {2*n}")
print(f"  double perturbations : {4 * n * (n-1) // 2}")
print()

rows = net.screen(doubles=True, quiet=True)
print(f"combinations actually computed: {len(rows)} (including untreated)")
print()
bn.print_screen(rows, top=8)

Synergy is by definition invisible to a single-target screen. That is why the expensive double search is worth it.

Python Runs in your browser

import bn

net = bn.twin()
base = net.landscape()
rows = net.screen(doubles=True, quiet=True)

# Pick out pairs that do nothing alone but work together (= genuine synergy)
single = {r["treatment"]: r for r in rows if len(r["perturb"]) == 1}
print("pairs that are each useless alone but effective together")
print("-" * 64)
found = 0
for r in rows:
    if len(r["perturb"]) != 2:
        continue
    parts = [f"{g}{'-KO' if v == 0 else '+OE'}" for g, v in sorted(r["perturb"].items())]
    if all(single[p]["reversion"] == 0 and single[p]["dormant"] == 0 for p in parts):
        if r["reversion"] > 0 or r["dormant"] > 0:
            print(f"  {r['treatment']:<30} reversion {r['reversion']:>3.0f}%  dormant {r['dormant']:>3.0f}%")
            found += 1
print(f"\nsynergistic pairs found: {found}")
print("None of these would ever have been found by single-target screening alone.")

This table is the last piece of humility in the course. What we did was the smallest possible case.

Python Runs in your browser

import bn

# Big numbers in exponential notation, so the digits do not run off the screen
def big(x):
    return f"{x:,}" if x < 10 ** 9 else f"{x:.2e}"

print(bn.pad("genes", 12) + bn.pad("state space", 16)
      + bn.pad("double combos", 16) + "total cell simulations")
print("-" * 66)
for n in [4, 8, 12, 20, 30, 50, 100]:
    states = 2 ** n
    doubles = 4 * n * (n - 1) // 2
    print(bn.pad(f"{n}", 12) + bn.pad(big(states), 16)
          + bn.pad(big(doubles), 16) + big(doubles * states))

print()
print("At 30 genes the age of the universe is already not enough.")
print("So real platforms give up on exhaustive enumeration and take other roads -")
print("solving only for fixed points algebraically, sampling, network reduction,")
print("and feedback-loop analysis.")

🎮 Combination calculator

Change the gene count and the number of simultaneous perturbations and watch the work required.

Push the slider to the right and the numbers run off the screen.

Loading…

🤔 Check yourself

With n genes, how many double-perturbation combinations are there?

🤔 Check yourself

Why can a 'synergistic pair' not be found by single-target screening?

🤔 Check yourself

As the gene count rises, what is the main reason the work becomes unmanageable?