Was ist ein gepoolter CRISPR-Screen?
CRISPR ist eine Methode, mit der einzelne Gene gezielt ausgeschaltet werden können.
In einem gepoolten Screen werden viele Gene gleichzeitig untersucht: Anstatt
jedes Gen einzeln auszuschalten, mischt man Tausende von Anleitung-RNAs (guide RNAs)
in einem einzigen Experiment – und unterscheidet später anhand molekularer
Barcodes, welche Kombination in welcher Zelle aktiv war.
Dabei stellt sich eine präzise kombinatorische Frage: Wie viele Experimente sind nötig,
damit jede mögliche Kombination aus drei Genen mindestens einmal untersucht wird?
What is a pooled CRISPR screen?
CRISPR is a method for selectively knocking out individual genes.
In a pooled screen, many genes are studied simultaneously: instead of knocking out
each gene individually, thousands of guide RNAs are mixed in a single experiment,
and molecular barcodes later identify which combination was active in which cell.
This raises a precise combinatorial question: how many experiments are needed so that
every possible three-gene combination is tested at least once?
Die mathematische Struktur.
Mit N = 20 Zielgenen und allen möglichen 3er-Kombinationen gibt es
C(20,3) = 1.140 Triplets zu erfassen.
Ein naiver Ansatz benötigt genau 1.140 separate Experimente.
Durch „Pooling“ — jeder Ansatz enthält M = 10 Gene gleichzeitig —
lässt sich diese Zahl drastisch reduzieren.
Die entscheidende Frage lautet: Existiert überhaupt eine so kleine Bibliothek?
Und wie groß muss sie mindestens sein?
The mathematical structure.
With N = 20 target genes and all possible 3-gene combinations,
there are C(20,3) = 1,140 triplets to cover.
A naive approach requires exactly 1,140 separate experiments.
Through “pooling” — each assay simultaneously contains M = 10 genes
— this number can be drastically reduced.
The critical question: does such a small library exist at all?
Erdős’ probabilistische Methode als Existenzbeweis.
Man definiert einen Wahrscheinlichkeitsraum: Jeder Pool wählt zufällig M Gene aus N aus.
Die Wahrscheinlichkeit, dass ein zufälliger 10-Pool ein bestimmtes Triplet überdeckt, beträgt
p = C(17,7)/C(20,10) = 24.310/184.756 ≈ 10,53 %.
Mit L zufälligen Pools gilt:
P(irgendein Triplet nicht abgedeckt) ≤ C(20,3) · (1−p)^L.
Für diese Schranke < 1 folgt:
Eine Bibliothek der Größe L ≥ 126 überdeckt alle 1.140 Triplets
mit Wahrscheinlichkeit > 99,9 %.
Also existiert sie — auch ohne eine einzige explizite Konstruktion angegeben zu haben.
Erdős’ probabilistic method as an existence proof.
We define a probability space: each pool randomly selects M genes from N.
The probability that a random 10-pool covers a specific triplet is
p = C(17,7)/C(20,10) = 24,310/184,756 ≈ 10.53 %.
With L random pools: P(some triplet uncovered) ≤ C(20,3) · (1−p)^L.
Setting this bound < 1: a library of size L ≥ 126 covers all 1,140 triplets
with probability > 99.9 %.
Therefore it exists — without exhibiting a single explicit construction.
Gen-Triplets C(20,3)
1.140
zu erfassende Kombinationen
Erdős-Existenzschranke
L ≤ 126
Pools à 10 Gene · ε = 0,1 %
Greedy-Konstruktion
24 Pools
5,25× besser als Schranke
Coverage-Verifikation
1.140 / 1.140
✓ vollständig · Ø = 2,53×
LLL-Bedingung p·e·(d+1)
0,0038
< 1 ✓ — Lovász-LLL erfüllt
RIP(3)-Konstante δ₃
1,34
Covering ≠ Sparse Recovery
Befund: Greedy schlägt den Existenzbeweis um Faktor 5.
Der probabilistische Beweis garantiert L = 126 Pools als ausreichend —
der explizite Greedy-Algorithmus findet eine vollständige Bibliothek mit nur 24 Pools.
Diese Lücke ist kein Zufall: Die probabilistische Methode ist bewusst konservativ,
denn ihr Union-Bound-Argument muss für das „schlechteste“ zufällige Objekt gelten.
Explizite Konstruktionen nützen die Struktur des Problems aus und kommen daher mit weit weniger aus.
Ehrlicher Befund zur RIP-Analyse:
Die 24×20-Messmatrix erfüllt die Restricted Isometry Property (RIP) nicht
(δ₃ = 1,34 > 0,41). Das ist kein Fehler, sondern ein inhaltliches Ergebnis:
Covering-Design (jedes Triplet mindestens einmal präsent) und
Compressed Sensing (eindeutige Signalrekonstruktion aus wenigen Messungen)
sind mathematisch verschiedene Anforderungen.
Finding: Greedy outperforms the existence bound by a factor of 5.
The probabilistic proof guarantees L = 126 pools as sufficient —
the explicit greedy algorithm finds a complete library with only 24 pools.
This gap is not accidental: the probabilistic method is deliberately conservative,
since its union-bound argument must hold for the “worst” random object.
Explicit constructions exploit problem structure and therefore need far fewer experiments.
Honest RIP finding:
The 24×20 measurement matrix does not satisfy the Restricted Isometry Property
(δ₃ = 1.34 > 0.41). This is not an error but a substantive result:
covering design (every triplet present at least once) and
compressed sensing (unique signal reconstruction from few measurements)
are mathematically different requirements.
Visualisierung · 6-Panel-Atlas
Visualization · 6-Panel Atlas
Links: Erdős-Existenzbeweis · Greedy-Fortschritt · Coverage-Verteilung
|
Rechts: Messmatrix · RIP-Analyse · Ergebniszusammenfassung
Left: Erdős existence proof · Greedy progress · Coverage distribution
|
Right: Measurement matrix · RIP analysis · Summary
Lean 4 · Formalisierter Existenzsatz
Lean 4 · Formalized Existence Theorem
Der numerische Kern des Existenzbeweises lässt sich als Lean-4-Satz formulieren
und von norm_num automatisch verifizieren:
The numerical core of the existence proof can be stated
as a Lean 4 theorem and automatically verified by norm_num:
theorem existence_N20_K3_M10 :
(1140 : ℝ) * (1 - (24310 : ℝ) / 184756) ^ 64 < 10⁻³ := by
norm_num
-- Ergebnis: 1140 · 0.8947^64 ≈ 8.4 × 10⁻⁴ < 10⁻³ ✓
Werkzeuge: numpy · scipy · matplotlib · itertools (Standard-Python, keine externen Abhängigkeiten) ·
Skript: /Volumes/CLAUDE-DATA/Projekte/C5_CRISPR_Covering/crispr_covering.py
