Bevölkerungsscreenings sind ein wichtiges Element im Kampf zur Eindämmung der Ausbreitung des Coronavirus. Doch wie lässt sich ein möglicher Mangel an Reagenzien und Geräten vermeiden? Indem man Mischungen von einzelnen Proben testet und sich auf die Mathematik verlässt!
Angesichts der zu erwartenden zweiten Welle von COVID-19 sind sich viele Experten darin einig, dass ein breit angelegtes Screening der Bevölkerung notwendig ist, um die Ausbreitung des Coronavirus zu stoppen. Immunologische, serologische oder antigene Tests an repräsentativen Stichproben aus der Bevölkerung könnten auch dazu beitragen, die Prävalenz der Krankheit abzuschätzen, die Herdenimmunität zu bewerten und Maßnahmen zum Pandemiemanagement anzupassen.
Die erfolgreiche Umsetzung einer Bevölkerungsscreening-Strategie erfordert aber den Zugang zu erheblichen Ressourcen in Bezug auf Personal und Ausrüstung. Mit zunehmender globaler Nachfrage zeichnet sich rasch ein Mangel an Reagenzmitteln ab, die für die Labortests benötigt werden. Dies stellt ein Problem für die Gesundheitsbehörden in Kanada und auf der ganzen Welt dar.
Können wir angesichts der Tatsache, dass die Tests größtenteils (glücklicherweise) negativ sind, mathematische Methoden einsetzten, um es besser zu machen? Ja! Dies wird ermöglicht durch Gruppentests an geeignet zusammengestellten Mischungen von Proben.
Gruppentests
Angenommen, ein Labor hat 100 einzelne Proben für diagnostische Tests erhalten. Es teilt diese nach dem Zufallsprinzip in 5 Gruppen der Größe 20 ein. Dann verwendet es, Gruppe für Gruppe, die Hälfte des Probenmaterials der 20 Proben, um eine Mischung herzustellen. Diese Mischung wird dann getestet.
Wenn ein Test einer zusammengefassten Probe negativ ausfällt, kann sofort der Schluss gezogen werden, dass niemand aus dem Pool infiziert ist. Fällt dagegen der Test positiv aus, so muss jede der 20 Proben einzeln getestet werden.
Stammen die ersten 100 Proben von gesunden Personen, so reduziert dieser Ansatz die Anzahl der durchzuführenden Tests von 100 auf 5. Ist nur eine Person infiziert, so reichen 5 + 20 = 25 Tests aus, um diese Person eindeutig zu identifizieren. Wenn zwei Personen infiziert sind, reichen ebenfalls 25 Tests aus, um sie zu identifizieren, zumindest falls sie zur gleichen Gruppe gehören. Es sind aber 5 + 20 + 20 = 45 Tests erforderlich, falls sie zu verschiedenen Gruppen gehören. Dies setzt sich so fort, falls es drei oder mehr infizierte Personen gibt.
Man erkennt, dass ein Gruppenscreening zu erheblichen Einsparungen führen kann, vorausgesetzt natürlich, dass die Sensitivität und Spezifität des Tests nicht durch die Vermischung der Proben beeinträchtigt wird. Dies wird hier angenommen, da es in der Praxis tatsächlich sehr oft der Fall ist.
Alternativ hätte das Labor die gleiche Screening-Strategie auf 10 Gruppen mit jeweils 10 Proben anwenden können. Wenn nur eine Person infiziert ist, dann sind nur 20 Tests erforderlich, um diese Person zu identifizieren. Es sind dann jedoch schon 10 Tests erforderlich, um zu dem Schluss zu kommen, dass niemand infiziert war.
Welche dieser beiden Strategien ist besser? Und gibt es weitere Strategien, die noch besser sind? Die Antwort hängt von der Prävalenz der Krankheit ab, d.h. vom Anteil der Bevölkerung, der infiziert ist.
In einer Notiz aus 1943, die in The Annals of Mathematical Statistics veröffentlicht wurde, berichtete Robert Dorfman, dass in seiner grundlegendsten Form das Gruppen-Screening bereits während des Zweiten Weltkriegs verwendet worden war, um US-Armee-Rekruten auf Syphilis zu testen. Der Ansatz wurde zum Standard, und heute gibt es viele Variationen dieser Idee, darunter Tests in ganz Nordamerika auf HIV, Grippe und den West-Nil-Virus.
Optimieren des Algorithmus
Dorfman zeigte, wie man die optimale Gruppengröße auf Grundlage der Prävalenz der Krankheit $p \in [0, 1]$ bestimmt. Bezeichnen Sie mit $n ≥ 2$ die Größe der Gruppe und gehen Sie davon aus, dass ihre Testpersonen eine repräsentative Zufallsstichprobe der Gesamtbevölkerung sind.
Wenn $X$ die unbekannte Anzahl der infizierten Personen in der Gruppe bezeichnet, dann folgt diese Variable einer Binomialverteilung 1 mit den Parametern $n$ und $p$. Daraus folgt, dass \[\text{Pr}(X=0)=(1–p)^n,\]
da jedes Individuum eine Wahrscheinlichkeit von $1-p$ hat, gesund zu sein, und
\[\text{Pr}(X>0)=1–\text{Pr}(X=0)=1–(1–p)^n.\]
Wenn $X=0$ ist, dann braucht man nur den Test $N =1$ durchzuführen. Wenn jedoch $X >0$, dann müssen $N=n+1$ Tests durchgeführt werden. Die durchschnittliche Anzahl der durchzuführenden Tests, genannt Erwartung von $N$ und von uns bezeichnet mit $E(N)$, ist gleich
\[\begin{array}{r c l}E(N) &=&1×\text{Pr}(X=0)+(n+1)×\text{Pr}(X>0) \\&=& n+1-n(1-p)^n.\end{array}\]
Diese Funktion steigt an, wenn $p$ wächst. Ist $p = 0$, so haben wir $E(N) = 1$, was offensichtlich ist, da dann niemand die Krankheit hat und daher ein einziger Test erforderlich ist, um dies zu bestätigen. Wenn $p=1$, so haben wir $E(N)=n+1$, da der erste Test notwendigerweise positiv ausfallen wird.
Für jeden Wert von $p \in [0, 1]$ können die relativen Kosten bei Anwendung des Gruppen-Screenings bestimmt werden (relativ zum Testen aller Personen), indem man das Verhalten des Quotienten
\[E(N)/n=1+1/n–(1–p)^n\]
als eine Funktion von $n$ untersucht. Je kleiner $E(N)/n$ ist, desto mehr lohnt es sich, Gruppentests zu verwenden, vorausgesetzt natürlich, dass das Verhältnis kleiner als $1$ ist. Falls $p = 0$ ist, so finden wir $E(N)/n=1/n$. Also lohnt es sich, $n$ so groß wie möglich zu wählen. Wenn $p = 1$ ist, haben wir immer
\[E(N)/n=1+1/n>1\]
weil der Gruppentest immer positiv ausfällt und somit den Aufwand nur erhöht.
Figure 1
Darstellung der Kurve $100×E(N)/n$ für verschiedene Werte von $p$: 1% (schwarz), 2% (braun), 5% (orange), 8% (rot), 10% (blau) and 15% (grün).
Für einen festen Wert von $p$ stellt die Funktion $100 \ mal E(N)/n$ den durchschnittlichen Prozentsatz der durchgeführten Tests in Abhängigkeit der Größe der Gruppe, $n$, dar. Die Abbildung zeigt das Schaubild dieser Funktion für verschiedene Werte von $p$, was einer Prävalenz von 1% (schwarz), 2% (braun), 5% (orange), 8% (rot), 10% (blau) und 15% (grün) entspricht. Wie man sehen kann, variiert die optimale Größe der Mischungen, die dem Minimum der Kurve entspricht, je nach Anteil, $p$, der infizierten Personen in der Bevölkerung. Die nachstehende Tabelle, über die Dorfman berichtet, gibt die optimale Wahl von $n$ für einige Werte von $p$ an.
| $p$ (%) | $n$ | Relatice Kosten (%) |
| 1 | 11 | 20 |
| 2 | 8 | 27 |
| 5 | 5 | 43 |
| 8 | 4 | 53 |
| 10 | 4 | 59 |
| 15 | 3 | 72 |
Verallgemeinerungen
Das oben beschriebene Testprotokoll ist ein Beispiel für einen adaptiven „Zwei-Runden-Algorithmus“. Es wird als adaptiv bezeichnet, da die Wahl (und damit die Anzahl) der in der zweiten Runde durchzuführenden Tests vom Ergebnis des in der ersten Runde durchgeführten Tests abhängt. Es gibt mehrere Möglichkeiten, solche Algorithmen zu verbessern. Insbesondere kann das Verfahren erweitert werden, indem die Anzahl der Runden erhöht wird.
Hier ist ein klassischer Algorithmus, den wir Teile-und-herrsche-Verfahren nennen werden und der bestimmte Optimalitätseigenschaften aufweist (siehe Abbildung 2).
a) Man nehme eine ganze Zahl $n$, die dargestellt werden kann als eine Zweierpotenz der Form $n = 2^s$, und führe $k$-Runden von Tests durch, wobei $k ≤ s+1$.
b) Testen Sie in der ersten Runde eine Mischung von Proben aus der gesamten Gruppe.
c) Fällt der Test positiv aus, dann wird die Gruppe in zwei Untergruppen mit Proben der Form $2^{s-1}$ aufgeteilt und eine Mischung aus beiden getestet.
d) Dies wird bis zur $k$-ten Runde fortgesetzt, in der alle Mitglieder einer Untergruppe, die in der vorherigen Runde positiv war, einzeln getestet werden. Im besonderen Fall $k=s+1$ hat diese Untergruppe nur noch zwei einzelne Proben übrig.
Figure 2
Grafische Darstellung eines adaptiven 5-Runden-Teile-und-herrsche-Verfahren, der auf eine Anfangsprobe von $n = 2^4 = 16$-Proben angewendet wird, von denen nur eine infiziert ist.
Falls die Proben nur eine einzelne infizierte Person enthalten, identifiziert der Algorithmus dieses Individuum in genau $s+1=\log_2(n)+1$ Runden. Generell gilt: je höher die Anzahl der Runden, desto größer die Einsparungen, die durch diesen Ansatz erzielt werden. Wenn es jedoch 24 bis 48 Stunden dauert, bis ein Test durchgeführt ist, kann der Ansatz auch kontraproduktiv sein. Es ist auch zu beachten, dass diese Verbesserung größere Proben (also mehr entnommenes Material) erfordert. Dies wird allerdings nicht als echtes Problem angesehen und bei allen nachfolgend vorgestellten Algorithmen als unproblematisch angenommen.
Ein nicht-adaptiver Algorithmus
Zur besseren Kontrolle der benötigten Zeit bis zum endgültigen Ergebnis, können auch nicht-adaptive Gruppen-Screeningmethoden in Betracht gezogen werden. Diese Ansätze umfassen nur einen Durchgang, so dass alle Tests zeitgleich durchgeführt werden können. Sie sind für die Problemstellung sehr effektiv, wenn eine zuverlässige Schätzung der Prävalenz der Krankheit verfügbar ist.
Lassen Sie uns das Konzept anhand des folgenden Beispiels erklären, das von einem Team ruandisch Forscher als Teil der aktuellen COVID-19-Gegenmaßnahmen entwickelt wurde. Zunächst wird eine Zufallsstichprobe der Größe $n = 3^m$ gebildet. Als nächstes wird eine Zuordnung zwischen den $3^m$ Individuen und den Punkten eines diskreten Hyperwürfels $\{0, 1, 2\}^m$ hergestellt. Siehe Abbildung 3 für eine Illustration des Falls $m = 3$.
Figure 3
Diskreter Hyperwürfel $\{0,1,2\}^3$. Jeder Punkt des Gitters entspricht einem Individuum aus einer Zufallsstichprobe der Größe $n=3^3=27$. Die $3^2=9$-Individuen in jeder der 9 Mischungen befinden sich entlang einer roten, blauen oder grünen Scheibe.
Der vorgeschlagene Ansatz besteht dann darin, gleichzeitig $3m$-Tests an Mischproben durchzuführen, die jeweils $3^{m-1}$ Individuen enthalten. Die zusammengefassten Proben werden jedoch nach sehr speziellen Modalitäten zusammengestellt, d.h. gemäß den Scheiben des Hyperwürfels. Wenn nämlich $x_1,\ldots,x_m $ die Koordinatenachsen des Hyperwürfels bezeichnen, entspricht jede der Mischungen der Individuen, die sich in der Hyperebene $x_i=t$ befinden, wobei $i\in \{1,\ldots,m\}$ und $t\in \{0,1,2\}$ eine Scheibe von $3^{m-1}$ Individuen ist.
Falls gilt $m = 3$ (wie in Abbildung 3), dann werden $3 \times 3=9$ Tests an Gruppen von jeweils $3^2 = 9$ Individuen durchgeführt. Falls $m = 4$, was dem in Ruanda verwendete Wert entspricht, so werden 12 Tests an einer Zufallsstichprobe von $n = 81$ Individuen durchgeführt. Das bedeutet, dass jede Stichprobe in vier gleiche Teile aufgeteilt wird und zu vier verschiedenen Tests beiträgt. Darüber hinaus ist jeder Test eine Mischung aus genau 27 Stichproben.
Dieser Ansatz basiert auf einer im Informationsblock beschriebenen Technik zur Fehlerkorrektur von Code-Konstruktionen. Einer ihrer großen Vorteile besteht darin, dass die Mischungen so zusammengesetzt sind, dass, wenn nur ein infiziertes Individuum in der Probe vorhanden ist, dieses mit Sicherheit identifiziert werden kann. Wenn jedoch mehr als eine Person infiziert ist, dann ist eine zweite Testrunde erforderlich.
Betrachten wir nun das ruandisch Beispiel im Fall $n = 81=3^4$. Mit dem Wissen, dass die Anzahl $X$ der infizierten Personen in der Probe einer Binomialverteilung mit Parametern $n = 81$ und $p$ gehorcht, haben wir
\[\text{Pr}(X ≤1)=(1 – p)^{81}+81p(1-p)^{80}.\]
Die verfolgte Strategie ist interessant, falls die Wahrscheinlichkeit, dass $X ≤ 1$ ist, groß ist. Aber um sicherzustellen, dass z.B. $\text{Pr}(X ≤ 1) ≥ 0,95$ gilt, muss schon $p ≤ 0,44\%$ gelten. Mit anderen Worten, die Prävalenz der Krankheit muss sehr gering sein. Schon bei einer Prävalenz von 1% haben wir $\text{Pr}(X ≤ 1) = 0,806$ und in fast 20% der Fälle werden wir auf eine zweite Testrunde zurückgreifen müssen. Bei einer Prävalenz von 1% haben wir jedoch immer noch
\[\text{Pr}(X=2)=\pmatrix{81 \\\ 2}p^2(1-p)^{79}=0.146,\]
Daher gilt $\text{Pr}(X ≤ 2) = 0.952$.
Die Kosten lassen sich nun leicht beschränken, wenn wir die zweite Runde geschickt durchführen, falls es mehr als eine infizierte Person gibt. Zum Beispiel erfüllen alle Fälle, die $X = 2$ entsprechen, die folgende Eigenschaft (siehe Abbildung 4, wo wir im Fall von $m = 3$ die Klammern mit einem positiven Test zeigen):
Für jeden Wert von $i \in \{1, \ldots, m\}$, gibt es höchstens zwei Scheiben der Form $x_i = s$ und $x_i = t$, die zu einem positiven Test führen, und es gibt mindestens einen Wert von $i$, für den es genau zwei positive Tests dieser Form gibt.
Figure 4
Der diskrete Hyperwürfel $\{0, 1, 2\}^3$ und die drei Möglichkeiten für zwei infizierte Individuen: auf der gleichen Geraden parallel zu einer Achse (links), an gegenüberliegenden Eckpunkten eines Quadrats in einer Ebene (Mitte) oder an gegenüberliegenden Eckpunkten eines Würfels (rechts). In jedem Fall werden die Schnitte, die zu einem positiven Test führen, in rot, grün oder blau mit den gleichen Farbkonventionen wie in Abbildung 3.
Wenn $k$ die Anzahl der Werte von $i \in {1,\ldots , m}$ ist, für die es zwei positive Tests der in (P) angegebenen Form gibt, so ist die Anzahl der zusätzlichen Tests, die erforderlich sind, um alle infizierten Personen zu identifizieren, in der folgenden Tabelle angegeben.
| $k$ | Anzahl der zusätzlichen Tests |
| 1 | 0 |
| 2 | 4 |
| 3 | 8 |
| 4 | 16 |
Wenn die Eigenschaft (P) nicht verifiziert ist, müssen alle Personen in den Scheiben, die positiv getestet werden, individuell getestet werden, was zu maximal 81 zusätzlichen Tests führt. Am Ende sind die relativen Gesamtkosten daher gleich 100 × 17/81 ≈ 21%.
Perspektiven
Die Suche nach Algorithmen, die an den Kampf gegen das Coronavirus angepasst sind, ist in vollem Gange. So wurde vor kurzem von einem israelischen Forschungsteam ein neuer Algorithmus entwickelt und in einem Labor implementiert. Er besteht darin, 48 Tests an einer einzigen Zufallsstichprobe der Größe 8 $ \times 48 = 384 $ durchzuführen, wobei jede einzelne Stichprobe in sechs gleiche Teile geteilt wird. Jeder der Tests basiert auf der Mischung von 48 dieser Anteile, einen pro Person. Die Stichprobe jedes Individuums ist also in sechs verschiedenen Tests vorhanden. Im Labor wurde ein Roboter programmiert, der die 48 Mischungen vorbereitet. Der Algorithmus kann bis zu vier infizierte Individuen identifizieren. Das bedeutet, dass achtmal weniger Tests erforderlich sind als bei Einzelpersonentests. Auch hier gilt: Je geringer der Prozentsatz der infizierten Personen, desto Leistungsfähiger ist der Algorithmus.
Natürlich kommen bei der Entwicklung von statistischen Testverfahrens auch andere Überlegungen ins Spiel. Der Einfachheit halber haben wir hier implizit angenommen, dass der verwendete Test unfehlbar ist. In der Praxis können selbst die besten Verfahren « falsch positive » oder « falsch negative » Ergebnisse liefern. Die Sensitivität und Spezifität der Tests sind wichtige Überlegungen bei der Empfehlung ihrer Durchführung, ebenso wie ihre Durchführbarkeit im Hinblick auf Zeit, Kosten und Komplexität der Handhabung.
Erstellung eines nicht-adaptiven Algorithmus
Wir wollen nun einen nicht-adaptiven Algorithmus entwickeln, um eine Gruppe von Menschen zu testen. Wir werden diesen Algorithmus durch eine Tabelle mit $T$-Zeilen und $n$-Spalten darstellen, oder in äquivalenter Weise durch eine Matrix der Dimension $T × n$, in der alle Einträge 0 oder 1 sind. Die $i$-te Zeile der Matrix stellt den $i$-ten Test dar. Die Einträge mit 1 in der $j$-ten Spalte repräsentieren die Tests, an denen die $j$-te Testprobe teilnimmt. Somit ist $m_{ij} = 1$, falls Person $j$ zum Test $i$ beiträgt, und $0$ andernfalls.
Konstruieren wir einen Vektor $X$ der Länge $n$, der die Gruppe repräsentiert, die wir testen wollen: seine $i$-te Koordinate, $x_i,$ ist $1$, falls das $i$-te Individuum infiziert ist, und $0$ andernfalls. Wir beschließen, $X$ als ein Wort der Länge $n$ und seine wenigen Koordinaten, die $1$ entsprechen, als Fehler in einem Anfangswort $X_0$ zu behandeln, dessen Koordinaten alle null gewesen sein sollten. Fehlerkorrigierende Code-Algorithmen werden verwendet, um die Fehler zu korrigieren, die bei der Übertragung von $X_0$ aufgetreten wären, was darauf hinausläuft, zu identifizieren, welche Koordinaten $x_i$ von $X$ gleich $1$ sind. Das ist genau das, was beabsichtigt ist. Wie im Beispiel veranschaulicht, kann ein Fehlerkorrektur-Algorithmus nur eine maximale Anzahl von Fehlern, $k$, korrigieren, die bei seiner Konstruktion vorher ausgewählt wurde.
Die Matrix $M$ ist die Matrix des Codes. Eine ausreichende Eigenschaft des Codes zur Korrektur von $k$-Fehlern ist, dass die Matrix $k$-disjunkt ist. Lassen Sie uns diesen Begriff definieren. Wir wollen nicht, dass, wenn Individuen $j_1, \ldots, j_k$ (nicht notwendigerweise eindeutig) infiziert sind, ein $j_{k+1}$-te infiziertes Individuum unbemerkt bleibt. Sich selbst die Spalte $j$ (d.h. das Individuum $j$) zu geben, ist dasselbe, wie sich selbst die Teilmenge $A_j$ von $\{1, \ldots , T\}$ ihrer Einträge gleich 1 zu geben (d.h. die Menge der Tests, zu denen dieses Individuum beiträgt). Wenn die Personen $j_1, \ldots , j_k$ infiziert sind, dann werden alle Tests, die der Untermenge $A_{j_1} \cup \cdots \cup A_{j_k}$ positiv sein. Damit das $j_{k+1}$-te infizierte Individuum nicht unbemerkt bleibt, darf $A_{j_{j_{k +1}}}$ nicht in $A_{j_1} \cup \cdots \cup A_{j_k}$ eingeschlossen werden. Die $M$-Matrix ist $k$-disjunkt, wenn dies für alle $j_1, \ldots , j_k$ und alle $j_{k+1}$, die sich von $j_1, \ldots ,j_k$ unterscheiden, der Fall ist. Die $12 \times 81$-Matrix, die dem obigen, in Ruanda verwendeten Beispiel entspricht, wäre eine 1-disjunkte Matrix.
Es gibt zwei bekannte Strategien zur Konstruktion von $k$-disjunkt Matrizen. Die erste ist basierend auf Zufälligkeit: Matrizen werden zufällig mit Einträgen von $1$ mit der Wahrscheinlichkeit $q$ und sonst mit $0$ generiert. Für gut gewählte $n$, $T$ und $k$ ist die Wahrscheinlichkeit, dass die Matrix $k$-disjunkt ist, größer als null; durch wiederholtes Ausprobieren erzeugen wir nach einiger Zeit immer eine $k$-Disjunkt Matrix.
Die zweite Methode, die algebraisch ist, stammt aus der Reed-Solomon-Theorie der fehlerkorrigierenden Codes. Sie erlaubt die Erstellung von $M$-Matrizen, bei denen alle Zeilen die gleiche Anzahl $m$ von Nicht-Null-Eingaben haben und alle Spalten die gleiche Anzahl $c$ von Nicht-Null-Eingaben haben. Auf diese Weise werden alle Tests an Untergruppen der Größe $m$ durchgeführt und jede einzelne Stichprobe wird in $c$ Teile aufgeteilt, die in $c$ separate Tests einbezogen werden.
- Dies ist eine sinnvolle Annäherung unter der Voraussetzung, dass die Gesamtpopulation sehr groß ist im Verhältnis zu den getesteten Gruppen. ↩
