Tænkeboks: Hvordan bruger man færrest mulig virustests?

Bagsidens opgave har fået fornyet aktualitet. FDA har netop godkendt 'pooled testing' for at øge kapaciteten. Dog med kun 4 prøver per analyse.

Jeg overvejede hvordan det idealiserede regnestykke ville se ud hvis prøverne blev arrangeret i et kvadrat, hvor hver række og søjle blev analyseret. Eller i en terning, hvor man startede med at undersøge hvert lag i de tre dimensioner.

Nå, skulle bare regne lidt mere. p(n)=1-f=(1/n)^(1/n)=exp(-1/xln(x)) p'=p/n^2(ln(n)-1)=0 for min p og max f ln(n)=1 n=e≈2,72 p(e)≈0,692 f(e)≈0,308

Jojo, men hvordan finder man frem til x=e?

Øh? Jeg får det fint til =0.3078? exp skal opfattes som invers ln

Jeg svarer kun på dit spørgsmål, jeg har ikke gået løsningen igennem.

Fra bagsiden: "...1/N - (1-f)^N < 0, hvilket kan opfyldes for et passende N, hvis f < 1 - exp(-1/e) =~ 0,308." Hvordan finder man 1-exp(-1/e)? Nogen der kan forklare det? Tak :)

Hej Søren Du har helt ret i at Dorfman umiddelbart er hurtigere at gennemføre, fordi man kan lave alle tests i kun to kørsler (hvis man har kapacitet nok), mens man med Sterretts metode må igennem adskillige test-kørsler, fordi man er nødt til at lave mange af dem serielt. Hvis man skal teste rigtig mange individer, altså langt flere end der kan klares i en enkelt kørsel, og man alligevel skal køre mange testkørsler, betyder det dog at Sterretts metode i nogle tilfælde også vil være hurtigst at gennemføre.

Som du kan se af mit svar til Morten, satte jeg mig ind i emnet på opfordring. Efter at have sat mig ind i hvad der fandtes af viden på området, slog det mig at det meste af den slags metoder blev udviklet i perioden omkring 1940-1965. Jeg tror faktisk det skyldes både at de rent matematiske metoder blev afdækket der og at vi derefter begyndte af få computere, der så småt kunne begynde at lave modelberegninger og simuleringer. Der ud over, var det også dengang et spørgsmål om at en (eller flere) laboranter skulle udføre disse tests og tidsforbruget var mere afhængigt af hvor mange tests der skulle laves, hvor det i dag er ligegyldigt om man skal lave 10 eller 3.000 tests, fordi maskinen er 3 timer om at gennemføre testen uanset om du fylder den helt eller halvt.

Det beregningerne IKKE tager højde for, er tiden der bruges på at blande prøver og holde styr på hvilke samples der skal testes igen. Hvis man går rigtigt til den, kan man sandsynligvis reducere antallet af nødvendige prøver yderligere ved at teste de samme samples i forskellige gruppe-kombinationer og på den måde indentificere de få positive i en stor gruppe. Det kan imidlertid godt betyde at logistikken kommer til at tage længere tid og koste flere penge end bare at teste noget mere med en mindre effektiv metode.

Tak, Morten Ja, det er Dorfmans metode du har genopfundet og jeg genkendte den med det samme, fordi jeg netop sammen med en matematiker havde beskrevet den og Sterrets metode, samt en modificeret version af Sterrets metode, hvor man også verificerer at den sidste i en gruppe TESTES positiv, i stedet for blot at antage det. Beskrivelsen udarbejdede jeg fordi jeg blev opfordret til det af en gruppe, der forsøgte at hjælpe sundhedsstyrelsen omkring udfordringerne med (på det tidspunkt) meget begrænset testkapacitet.

Da vi ikke havde tal for for sikker en Corona test er, valgte vi i første omgang ikke at forholde os til effekterne af reduceret følsomhed i pool'ede tests og risikoen for falske positiver/negativer, men det ville være et meget spændende næste step.

Ideen til metoden jeg beskrev til sidst kom faktisk af din opgave. Jeg talte med matematikeren (Bjarke Ebert) og vi vendte forskellige muligheder for at se hvor langt vi kunne komme ned ved evt. at pool'e restgrupper i Sterrets metode. Da jeg ikke er helt så skarp i statistik som Bjarke, forsøgte jeg med en mere simpel to-trins metode, hvor jeg kunne bruge formelsættet fra Sterrets metode og lave en indledende screening først. Det er klart den metode kun er rigtig interessant ved meget lave frekvenser.

Hvis der bliver behov for at arbejde videre med effekter af reduceret følsomhed og falske positiver/negativer, kunne det være spændende hvis du ville deltage i dette? Jeg kan ikke vedhæfte min beskrivelse her, men hvis du sender en mail til mig på innovation@egenfeldt.com, vil jeg meget gerne sende dig beskrivelsen.

Tak, Svend, det er fremragende kommentarer!

Tak, Svend, det er fremragende kommentarer! Jeg kendte ikke til de to artikler, men kan nu påstå, at jeg har genopdaget Dorfmans metode. :-) Jeg var godt klar over, at man kunne optimere metoden, men spørgsmål og svar skulle egne sig til Ingeniørens bagside, så af denne og andre grunde valgte jeg at holde det simpelt. Metoden, du beskriver i din sidste kommentar, er meget elegant og effektiv. Igen kunne det være interessant at modellere effekten af falske positive/negative, eventuelt med reduceret følsomhed af testene ved store grupper osv.

Det må matematikere bestemme. Jeg ved det ikke, men synes at det ser mærkeligt ud. 30,6 er jo højst 30,65, så det passer ikke med 30,66. Det gør 30,7=30,65-30,75... Derfor er det sidste tal en bedre beskrivelse af værdien... i min verden. :)

Jo lavere frekvensen er, jo større grupper er det optimalt at bruge og jo større besparelse kan opnås, fordi besparelsen opnås ved at spare N-1 tests hver gang en gruppe på N testes negativ. Den øvre grænse for N opnås, når der fås så høj en frekvens af positiv-grupper, der umiddelbart kræver N+1 tests at disse æder besparelsen. For store populationer med en lille frekvens, kan man starte med at høste de lave frugter og teste i relativt store grupper og smide alle positiv grupper til gentest i mindre grupper og derved opnå en yderligere besparelse.

Hvis man f.eks. ønsker at teste en population på 1.000 individer og en frekvens f=0,01, ville man med den i opgaven beskrevne metode (Dorfmans metode) finde frem til 19,6%=196tests ved grupper af 11. Sterrett ville med sin metode i gennemsnit skulle bruge 14%=140tests startende med grupper af 16.

Starter man i stedet med grupper på 25, skal der indledningsvis laves 40 tests. her forventes f'=(1-f)^N at teste negativ, hvilket med f=1% giver at knap 78% af grupperne testes negative. Derved kan vi pille ikke færre end 778 invivider ud som negative allerede efter 40 tests. da vi nu har pillet 77,8% af individerne ud som negative, har vi 222 individer tilbage, som nu må antages at have en højere frekvens, da alle positiverne er tilbage blandt de reterende. Frekvensen blandt de resterende må så være: f=f/(1-f') og altså her 4,5%.

Anvendes Sterretts metode på de resterende 222 individer med en frekvens på 4,5%, fås at dette kan gøres med 73 tests startende med grupper på 7-8 individer. Derved kan antallet af test altså reduceres fra Sterretts 140 tests til 40+73=113 tests eller 11,3%.

Ved optimering findes det at man ved at starte med grupper på 32 kan forvente at finde 725 negativer efter 31,25 tests i snit og stå tilbage med 275 individer med en frevens på 3,6%. Ved brug af Sterretts metode startende med grupper af 8-9 individer, kan disse klassificeres efter gennemsnitligt 80,57 tests og hele populationen altså klassificeret efter kun 31,25+80,57=111,82 tests eller 11,2% test/person, hvilket er en reduktion på 20% i forhold til Sterretts metode og en reduktion på 43% i forhold til Dorfmans metode, som opgaven tog udgangspunkt i.

I artiklen "On the detection of defective members of large populations" af Andrew Sterrett (Dec. 1957), The Annals of Mathematical Statistics 28(4):1033-1036, udvider Sterret grupperingen og ud fra antagelsen om der ved lille frekvens og relativt små grupper sjældent vil være mere end een positiv i en positiv-gruppe, foreslår han at man tester individer i grupper, der har testet positiv, individuelt indtil en positiv er fundet. Derefter testes de resterende i gruppen igen som en ny, mindre gruppe. Hvis en gruppe på to testes positiv og test af det ene individ viser negativ, konkluderes det uden yderligere test at det andet individ i gruppen så må have været den positive

Han når i artiklen frem til et udtryk, jeg ikke evner at skrive uden en formel-editor og jeg kan ikke finde ud af at poste et billede her, men artiklen kan ses via nedenstående link. [https://projecteuclid.org/download/pdf_1/euclid.aoms/1177706807

Af artiklen fremgår det at man på denne måde dels kan reducere antallet af nødvendige tests og dels kan anvende metoden ved lidt højere frekvenser end Dorfmans metode og opnå en (teoretisk) besparelse: f=1% -> N=16 ->14% (mod 19,6% Dorfman) f=10% -> N=5 -> 51% (mod59% Dorfman) f=30% -> N=2 ->90% (mod 99% Dorfman) og en øvre grænse på f=38%.

Som opgaven er beskrevet med efterfølgende test af alle individder i grupper, der tester positivt, er løsningen beskrevet af Robert Dorfman i artiklen "The Detection of Defective Members of large Populations", dec. 1943, The Annals of Mathematical Statistics 14(4):436-440

Her angives antallet af nødvendige tests til: E(T)=N/n+n(N/n)p', hvor N er antallet af invididder i populationen, n er antaller af individder i en gruppe (pool-størrelse) og p'=1-(1-p)^n

Dette giver så en "cost" (gennemsnitligt antal tests pr. person) på: C=T/N=((n+1)/n)-(1-p)^n, altså samme løsnming som bl.a. Kim Bygum og Svend Ferdinansen når frem til. Af artiklen fremgår det også at man ved anvendelsen af disse udtryk kan nå frem til de optimale løsninger: f=1% -> N=11-> 20% test/person (det rigtige resultat er 19,6%, men jeg tror Dorfman mente at 20% var tæt nok med regnestok..) f=10% -> N=4 -> 59% f=30% -> N=3 -> 99%

Ved 50% får man at man, jo mindre grupperne er, jo større bliver antallet af gennemsnitligt antalts test/person og forsøger man f.eks. med en population på 100 individder i grupper af 25, skal man regne med ialt 104 tests, hvilket vil sige at man i bedste fald kun laver 4 værdiløse gruppetests først. Så ved en frekvens på lige over 30% kan det ikke længere teoretisk betale sig at teste i grupper.

Hej Robin

God metode, men det går ikke at runde op, når det drejer sig om en maksimalværdi! En mere præcis angivelse er: 30,664 %, Så jeg fastholder 30,6 % , hvis vi skal bruge 3 betydende cifre.

Sprog: Nej, undersøg nu først før du påtaler sprog!

Holder disse overslag, ville man altså - rent hypotetisk - i to trin og med færre end 4000 ideelle analyser kunne udpege samtlige 55 smittede i en befolkning på 5.5 mill.

Ja ... vi har så desværre en lidt større f i den nuværende praktiske situation, så tallet bliver noget større

Jeg valgte dog af flere årsager at holde det simpelt.

Hvis man i 1. trin inddeler i grupper med 200 i hver, vil der være 27500 grupper og sandsynligheden for at en gruppe er smittet er ca. 0.002. N1 sættes til 23 og de ca. 55 smittede grupper kan så findes med ~2434 analyser.

De udpegne ca. 55 * 200 ~= 11000 kandidater testes så i det andet trin. f er her ca. 0.005 og N2 sættes til 15. De smittede kan så findes med ~1531 analyser.

Holder disse overslag, ville man altså - rent hypotetisk - i to trin og med færre end 4000 ideelle analyser kunne udpege samtlige 55 smittede i en befolkning på 5.5 mill.

Jeg anvendte den kumulative geometriske sandsynlighedsfordeling til beregning af antal tests anvendt.

Antal tests/person = ( (N+1) geocdf(f,N) + (1 - geocdf.(f,N) ) / N

For N=4 med f=0.1. Giver det:

Antal tests/person = ( (4+1) geocdf(,1,4) + (1 - geocdf.(,1,4) ) / 4 = 0,5939

Har ikke forsøgt at gennemskue om den øverste formel egentlig er lig den generelle formel som mange er nået frem til.

Jeg valgte dog af flere årsager at holde det simpelt.

En optimering af p med hensyn til n giver -ln(1-f)(1-f)^nn^2=1 Der rækkeudvikles f*(1-nf)n^2=1 Negligeres parentesens 2. led som værende lille, har vi tilnærmelsen n=f^(-1/2). Denne benyttes i parentesens 2. led: f(1-f^(1/2))n^2=1 dvs. n=1/[f(1-f^(1/2))]^(1/2)=1/f^(1/2)(1+1/2*f^(1/2)) Sidstnævnte formel benytter at(1-x)^(-1/2)=1+x/2 når x er lille. Så er det bare at gange ud: n=f^(-1/2)+1/2.

PS.: I min artikel skrev jeg indledningsvis 0.03066 i stedet for 0.3066.

Ja, man kan lave denne variation, og som matematisk opgave kunne man lave variationer ved at gå i mange retninger, eksempelvis tage højde for falske positive/negativ., større usikkerhed ved flere i samme test osv. Jeg valgte dog af flere årsager at holde det simpelt.

I Tyskland bruges det til at screene plejepersonale og plejehjem løbende.

SST og SSI har hele vejen igennem været et ekstremt dyrt bekendtskab og vi har nu tre måneder inde i epedimien intet overblik

Det er stadigt på trods og ikke i kraft af SST og SSI at der er nogen grad af kontrol, men hvor er det dog forfærdeligt, hvor dyrt det har været at vi ikke har haft kompetencerne på centrale poster i det beredskab som det viste sig at vi faktisk ikke havde.

I forlængelse kunne man overveje hvad de optimale gruppestørrelser N1, N2,.. ville være hvis man øgede antallet af trin. Svend var vist inde på det samme. Hvis eksempelvis f var af størrelsesordenen 1e-5 og man i en inddæmningsfase ville teste samtlige borgere. Måske det ikke er urealistisk at konstatere en enkelt smittet selv i en blanding fra en større gruppe. Jvf. rapporterne om at man har kunnet finde virussen i spildevand i ramte byer. Uden at jeg i øvrigt kan kloge mig på sagen.

Sprogpolitiet har ikke styr på paragrafferne: test hører til blandt de ord, hvor flertal er valgfrit mellem entalsform og -s. Og herefter er det en smagssag, om man foretrækker tests eller test. :-) Se ordnet.dk og dsn.dk.

Jeg er nysgerrig efter var den der halve komme fra... Empirisk eller har du været lidt mere præcis end mig? :) n=f^(-1/2)+1/2.

Selv med en meget lav frekvens bliver bundtningen ikke særlig stor, så det kan nok ikke svare sig, med mindre man tager større bundter end det optimale. Jeg tænkte på at et positivt bundt blev delt i to, hvor sandsynligheden for at den ene halvdel var negativ blev stor nok , så man straks kunne afskrive den halvdel. Omvendt, hvis den ene halvdel er positiv, slipper man ikke for at teste den anden halvdel også.

Hej Kim

Sprog: Nej, undersøg nu først før du påtaler sprog!

Stor ros for den spændende opgave. Forholdet mellem antal test og antal deltagere er: p=[(1-f)^n+(1-(1-f)^n)*(n+1)]/n Tilfældet n=2 er ikke interessant, da et højere n giver et lavere p for samme værdi af f. For n=3 har vi p=1 ved (1-f)^3=1/3, dvs. f=1-3^(-1/3)=0.03066. For alle n gælder, at en større værdi af f giver p>1 og derfor ikke mulighed for at benytte testmetoden. Hvis man lader p have samme værdi for n=3 og n=4 fås f=0.1239. Hvis man gør det samme for n=4 og n=5 fås f= 0.0656. Det er altså optimalt med 4 testpersoner for f i dette interval. Ved tilsvarende beregninger for andre små n, får vi tabellen f: 0.3066 0.1239 0.0656 0.0411 0.0283 0.0207 0.0158 0.0124 n: 3 4 5 6 7 8 9 For små værdier af f gælder tilnærmelsesformlen n=f^(-1/2)+1/2.

Man kan godt minimere selve virustesten, og det var jo en begrænsende faktor, men man kommer til at genere folk flere gange med at udtage prøver. Mængden af prøver bliver sikkert P+P(1-(1-f)^N), hvor P er populationen.

. Pokkers. Da jeg levede regnestykket forestillede jeg mig hele befolkningen skulle testes. Men det er jo ikke hvad opgaven går ud på. Er nød til at kigge på den igen.

. T(N)=1 P/N (1-f)^N + N P/N (1-(1-f)^N)) P er populationens størrelse, f er frekvensen og N antal personer i poolen (0< N <= P). T(N)=(P/N -P)(1-f)^N + P T(1)=P

Når dT(N)/dN=0 er -1 + (N-N^2)ln(1-f)=0 Det ses at optimum eksisterer uafhængigt af P's størrelse. For f=0.01 er N=ca.10.49 f=0.1 er N=ca. 3.6 f=0.3 er N=ca. 2.25 f=0.5 er N=ca. 1.80 f=0.9 er N=ca. 1.33

For lille f og stor N (fN<<1) kan man finde at N=1/√f. Det giver N=10 for f=0,01. Så ved man cirka hvor man skal kigge...

Min løsning: Det forventede antal test pr person for gruppe med N personer er: E(N) = [(1-f)^N x 1 + (1-(1-f)^N) x (N+1)] / N Ved differentiation findes et transcendent udtryk til bestemmelse af optimal N: N^2 x (1-f)^N x log(1-f) + 1 = 0 For f = 0.1 fås numerisk løsning N = ca. 3.8

Grænsen kan findes ved at regne grænsen(test pp=1) ud for bestemte N=2,3,4,... 1/N+1-p^N=1 p=1-f=(1/N)^(1/N) N=2 og 4 giver p=√0,5~0,707 N=3 giver p=(1/3)^(1/3)~0,693 N>4 giver større værdier for p. Mao f maks=1-0,693=30,7%

Sprog: Nej, undersøg nu først før du påtaler sprog!

Jeg får samme løsning. Antal test er generelt 1/N + (1 - (1-f)^N) for N>1. Måtte bruge et regneark for at finde minimum. Differentialet er ikke lettere at løse, og det nytter ikke at finde et f der giver minimum for et fast N. frekvens N pr person 0,01 11 0,19 0,03 6 0,33 0,1 4 0,59 0,2 3 0,82 0,3 3 0,99 0,5 uendelig >1 Med frekvens over 0,2 er der ikke nogen gevinst, og grupperne skal være forbavsende små. I øvrigt kan man få næsten samme resultat ved at bruge Poisson-fordelingen.

P.S. Sprogpolitiet påtaler at opgavestilleren sætter et engelsk flertals s på test. Vi har sikkert fået ordet udefra men det er blevet fordansket med alle de besynderligheder det medfører.

Hej Kim Spændende aktuel – og måske endda relevant – opgave! Jeg er enig i din løsning. Det kan diskuteres, om det er rimeligt at sidestille ’samletesten’ med normale tests f.eks. i en økonomisk optimering, men det er vel ikke helt ved siden af at antage, at det er selve testen, der er den begrænsende faktor, og ikke de anvendte laboranttimer. I hvert fald så længe vi er afhængige af svært tilgængelige reagenser. (hvad blev der af Seruminstituttets forsøg med at koagulere blodet ved høje temperaturer?) Det fremgår af udtrykket at (1-f)^N > 1/N for at metoden kan betale sig. Numerisk har jeg fundet, at dette kun er muligt, hvis f < 30,6%.

f=50% kan ikke betale sig. Til gengæld kan 11 test kombineres for f=1%, med 19,6% test pr. person.

f=10%: 4 test kombineres, 59,4% test pr. person. f=30%: 3 test kombineres, 99% test pr. person.

Antal test er generelt 1/N + (1 - (1-f)^N) for N>1. Jeg har ikke et analytisk udtryk for hvilket N der giver min. (man kan differentiere og løse for nul, den er ikke triviel og man skal stadig prøve begge nabopunkterne)