Alla författare bidrog lika mycket till detta arbete. Författare lista beställs lexikografiskt. Molekylärbiologi är i allt högre grad beroende av stora skärmar där ett enormt antal exemplar systematiskt analyseras i sökandet efter ett visst, sällsynt utfall. Dessa skärmar inkluderar systematisk testning av små molekyler för potentiella läkemedel och testa sambandet mellan genetisk variation och en fenotyp av intresse. Medan dessa skärmar är "hypotesfria", kan de vara slösaktiga; att samla proverna och sedan testa poolerna är mer effektivt. Vi formulerar på exakt matematiska sätt den typ av strukturer som är användbar i kombinationsdesigner för att eliminera avfall, för att ge låg vikt, flexibel och modulär design. Vi visar att Reed-Solomon koder, och mer allmänt linjära koder, uppfyller alla dessa matematiska egenskaper. Vi demonstrerar ytterligare kraften i denna teknik med Reed-Solomonbaserade biologiska experiment. Vi tillhandahåller allmänna verktyg för experimentister att konstruera och utföra praktiska pooling design med rigorösa garantier för stora skärmar. multiplexade analyser  och kombinatoriska grupptester  med komprimerad avkänning, experimentella konstruktioner, linjära felkorrigeringskoder Vi tillhandahåller en matematisk formulering av biologiskt relevanta strukturer i kombinatoriska poolningskonstruktioner. Innan detta arbete hade biologerna inte på ett exakt sätt formulerat vilken typ av strukturer som var nödvändig eller användbar i poolingdesignen. Vi visar också att ReedSolomon koder, och mer allmänt linjära koder, uppfyller alla dessa matematiska egenskaper. Vi etablerar nya kopplingar mellan biologiskt relevanta och kombinatoriska egenskaper felkorrigering koder och hur man konstruerar praktiska, relevanta pooling konstruktioner med rigorösa garantier. Området molekylärbiologi bygger i allt högre grad på stora skärmar där ett överväldigande antal exemplar systematiskt analyseras i sökandet efter ett visst resultat. Dessa skärmar kan komma i olika former: systematisk testning av tiotusentals små molekyler i ett sökande efter potentiella droger; störa aktiviteten hos varje gen i genomet för att belysa organisationen av genetiska nätverk som underlydande cancerframkallande processer med RNAi; bestämma förmågan hos ett protein att binda till varje annat protein i genomet i jäst tvåhybridsystem; och testa sambandet mellan praktiskt taget varje möjlig genetisk variation i genomet och någon fenotyp av intresse såsom diabetes eller hjärtsjukdomar. En fördel med dessa skärmar är att de anses "hypotesfria", låta data avslöja nya och oväntade resultat som är svåra att härleda från aktuell biologisk kunskap. Nackdelen är att skärmarna kan vara ganska resurs- och energikrävande. I många fall skärmar "avfall" ett överväldigande antal analyser som levererar negativa och ointressanta resultat för att hitta de knappa positiva fynd. Under de senaste åren har vi och andra självständigt demonstrerat skärmar inom olika biologiska områden som är baserade på kombinatorisk poolning (se tabellen i det kompletterande materialet). Dessa experiment har två grundläggande gemensamma drag. Först, i stället för att självständigt testa var och en av proverna, börjar experimenten med att gruppera proverna i pooler med hjälp av specifika matematiska regler, och sedan testa poolerna. Detta förfarande minskar dramatiskt kostnaderna för experimenten eftersom antalet pooler är mycket mindre än antalet originalprover. För det andra, i motsats till naiv pooling där en grupp exemplar deltar i exakt en pool, deltar varje prov i kombinatorial pooling i en serie unika pooler. Således är det möjligt att tilldela ett unikt resultat till varje prov genom att jämföra mönstret av resultaten med pooling design, så länge antalet positiva resultat är relativt litet. De flesta av experimenten ovan utnyttjade icke-adaptiva grupptester eller komprimerad avkänning för att utforma poolningsmönstret. Dessa två nära relaterade matematiska domäner handlar om konstruktion av effektiva konstruktioner som minskar antalet pooler samtidigt som förmågan att tilldela unika resultat till varje objekt bevaras. Enligt dessa ramar är biologiska skärmar gjutna som ett system av (linjära) ekvationer y = M x + med n variabler, varje variabel motsvarar ett objekt i skärmen. Posterna kan komma i olika former: små molekyler i kemiska skärmar, olika hårnålar i RNAi skärmar, ett bibliotek av byten i jäst två-hybrid skärmar, eller mänskliga individer i genetiska studier. Syftet med skärmen är att avslöja x, en vektor av längd n, vars ith position betecknar den biologiska egenskapen hos objekt i. Till exempel, i en liten molekyl skärm, x kan vara antingen 1 eller 0, där 1 betecknar en aktiv förening och 0 betecknar en inaktiv förening. Experimentören observerar inte x direkt. Snarare använder hon t analyser i vilka n objekt har poolats och observerar y, en vektor av längd t vars jth position betecknar analysresultaten för jth analys. Till exempel, i en liten molekyl skärm, poster av y kan beteckna fraktionen av överlevande celler i närvaro av föreningen, eller y kan vara en vektor med poster som är antingen 0 eller 1, där 0 innebär att ingen cell överlever medan 1 fångar överlevnaden av vissa av cellerna i analysen. Slutligen kan vi uttrycka pooling design av M, en matris med t rader och n kolumner vars poster är icke-negativa tal. Posten Mij = r innebär att r-enheter (mikrogram, mikroliter, mullvadar eller något godtyckligt mått) av objekt j analyseras i ith-reaktionen. Med denna representation motsvarar triviala skärmar (ingen sammanslagning) helt enkelt n × n identitetsmatrisen; varje objekt analyseras i exakt reserverad för publikation Fotnoter Volym Utfärda nummer 1-17 en distinkt reaktion. Ljudet kan vara noll, en slumpmässig variabel eller ett godtyckligt, avgränsat värde, beroende på modell. I grupptestning beräknas produkten M x med hjälp av boolesk aritmetik: resultatet av en analys är positivt om och endast om minst ett prov i poolen är positivt. I komprimerad avkänning, posterna i matrisen M är reella tal och produkten M x beräknas med hjälp av standard real-värderad aritmetik. Tyvärr tar det teoretiska arbetet med grupptester och komprimerad avkänning inte upp många praktiska designutmaningar som biologerna står inför när de använder sådana poolningsstrategier. Betydande framsteg har gjorts i utvecklingen av pooling mönster med ett minimalt antal analyser men med liten uppmärksamhet på om dessa mönster kan genomföras i praktiken. Här kartlägger vi de nuvarande bristerna i genomförandet och föreslår en matematisk ram baserad på kodningsteori som tar itu med de flesta av dessa hinder. Vi beskriver också experimentella valideringar av ReedSolomon-kod och ger en översikt över webbaserade verktyg som vi har utvecklat för att skapa och implementera pooling designs på bänken. Med hjälp av dessa verktyg kan experimentister utan matematisk kunskap i kodningsteori och minimal utrustning utföra komplexa poolingexperiment. Funktioner i praktisk pooling design. Under de senaste åren har vi genomfört dussintals storskaliga poolade skärmar inom olika biologiska områden som belyser gemensamma egenskaper och problem i genomförandet av poolade experiment. Välbalanserad design. Vi märkte att de flesta implementationrobust mönster är välbalanserade konstruktioner, där varje objekt poolas exakt samma antal gånger och alla analyser har (nära) ett identiskt antal objekt. Dessa konstruktioner förbrukar samma mängd material från alla objekt, vilket möjliggör direkt planering av experimentet och minska risken för att en vara kommer att ta slut under poolning. Det säkerställer också att varje vara behandlas lika. Assays med identiska antal objekt är också mycket fördelaktigt. De ger mer konsekventa resultat som minskar effekten av utspädning av proverna. En annan biprodukt är att välbalanserade konstruktioner möjliggör snabb kvalitetsbedömning av poolningsförfarandet innan det dyra screeningsteget inleds. Stora avvikelser i poolvolymer eller i restmaterialet kan lätt upptäckas av ögat och fungera som en indikator på att det fanns en potentiell brist i konstruktionen av poolerna. Maximalt utnyttjande av biologiska kit. Ett stort antal biologiska satser säljs i satser med 96 analyser för att passa de vanliga mikrotiterplattorna. I många realistiska scenarier finns det minimala kostnadsskillnader mellan en design med 50 analyser eller 96 analyser, men en betydande skillnad mellan en design med 96 pooler och 97 pooler. Således är det önskvärt att hitta en pooling design med en multipel av 96 analyser. Naturligtvis kan man konstruera en slumpmässig pooling design för att uppnå detta mål, men då designen inte kommer att vara välbalanserad. föreslog Shifted Transversal Design (STD), som är välbalanserad och används i stor utsträckning i biologiska experiment. Tyvärr kan STD inte helt utnyttja en 96 brunn platta, eftersom det producerar antal pooler som är en liten multipel av ett primtal (mindre än huvudnumret). Lätt vikt. De flesta teoretiska pooling mönster tar inte hänsyn till vikten av designen, det vill säga antalet 1s i M. Vikten är en kritisk funktion för poolade experiment. Tung vikt innebär att varje prov prov tas fler gånger, vilket förbrukar mer material. I teorin, naturligtvis, kan vi ta en mindre mängd av varje prov för att lindra detta problem. Men i verkligheten, konventionella flytande hantering robotar kan inte exakt aspirera och dela ut små mängder, vilket begränsar den möjliga vikten. Dessutom är tung vikt design mer mödosamt att genomföra och har högre omkostnader, bidrar till kostnaderna för pooling förfarande (robotisk tid, tips, eller manuellt arbete). I vår erfarenhet och undersökning av litteraturen, dragbar pooling mönster sällan överstiger en kolumn vikt på 10 i många fall. Varaktighet. När antalet indataprover är stort, är ett samlingsförsök vanligen uppdelat i partier av distinkta block av prover. För varje parti börjar försöksledaren huvudsakligen från grunden för att bygga poolerna med den nya undergruppen av prover. Detta tillvägagångssätt är mer robust eftersom ett sporadiskt fel i vätskehanteringssystemet påverkar endast ett begränsat antal exemplar snarare än hela experimentet. Dessutom begränsar det mängden flytande avdunstning från poolerna genom att minimera den tid det tar att avsluta byggandet av en pool. En önskad egenskap är att varje sats kommer att ha en bra prestanda och att försöksledaren kommer att kunna samla olika partier tillsammans till en "mega-design" utan alltför stor förlust av prestanda. Detta kommer att ge maximal flexibilitet vid genomförandet av flera experiment. Experimentören kan till exempel börja med ett konservativt pilotexperiment på en sats. Baserat på resultaten, kan hon besluta om att ta en mer aggressiv strategi och poola flera partier tillsammans i en mega design eller att behålla den mer konservativa strategi. En annan fördel med modulära konstruktioner beror på att de konstruerade poolerna vanligtvis kommer att användas många gånger under olika förhållanden (t.ex. genom att använda olika betesproteiner i jäst tvåhybrid experiment), med varierande antal positiva objekt. En mega design kan vara tillräckligt i de flesta fall, men avkodning kan misslyckas när antalet positiva är ovanligt högt. Men när detta händer kan man göra om experimentet med hjälp av de underliggande underkonstruktioner, som har mer mindre pooler och därmed framgångsrikt identifiera positiva. Genomsnittligt resultat. Väsentliga delar av teorin om grupptestning behandlar det värsta tänkbara utförandet av en pooling design, som kallas matris disjunktness. Med denna egenskap är det mycket lätt att härleda minimalt antal positiva objekt som kan avkodas efter sammanslagning med ett visst antal fel. I praktiken har dock det sämsta resultatet låg nytta för försökspersonen. Vad vi verkligen behöver är en design som presterar bra i genomsnitt och att känna till den förväntade snarare än sämsta prestandan i designen. Robusthet mot buller. Mycket av den klassiska grupptestteorin behandlar fallet med perfekta mätningar; d.v.s. observerar vi y = M x. I praktiken är nästan alla mätningar utförda av experimentister bullriga. Vi behöver därför gemensamma konstruktioner och rekonstruktionsalgoritmer som ger god genomsnittlig prestanda i en bullrig miljö. Hittills har dessa två sista punkter endast behandlats genom simulering [23]. Reed-Solomon baserade pooling mönster. Vi har hittat en pooling design baserad på Reed-Solomon (RS) felkorrigering koder som dramatiskt minskar antalet pooler jämfört med pooling mönster som ofta används i biologiska experiment, samtidigt ta itu med de praktiska egenskaper som nämns ovan. I kodningsteorin är en kod en uppsättning vektorer som skiljer sig åt parvis på ett stort antal platser. RS-koder är linjära koder, baserade på polynom över ändliga fält. Konstruktioner baserade på RS-koder har använts i biologiska grupptester sedan 1960-talet, då de föreslogs av Kautz och Singleton [14]. Befintliga arbeten har dock inte tagit itu med ovannämnda utmaningar; arbetets bidrag visar hur man använder RS-konstruktioner för att tillgodose den moderna biologins praktiska behov. Nedan beskriver vi konstruktionen av en RS-design ur utövarens perspektiv; det kompletterande materialet innehåller ett mer teoretiskt förhållningssätt. Vi bygger matrisen M genom att stapla mindre submatriser, som kallas lager ovanpå varandra. Den grundläggande konstruktionen börjar med att välja tre heltal: q, antalet pooler i varje lager, m, antalet lager, och k, den maximala graden av polynom som vi konstruerar. Vi hänvisar till sådana koder som [m, k, m − k + 1]q-RS-koder. Det finns tre begränsningar på dessa parametrar, påtvingade av teorin. Först måste antalet exemplar, n, vara som mest q k ; i praktiken kommer vi att välja k att vara det minsta heltal så att detta är sant. För det andra måste q vara antingen en primär eller en primär effekt (t.ex. 7, eller 2 4 = 16). Av praktiska skäl som diskuteras senare är vi särskilt intresserade av fallet när q = 16. För det tredje måste både k och m vara mindre eller lika med q. Poolingsmatrisen M har t = qm rader (pooler), och är uppdelad i m submatriser (lager) Fotlinje Författare av lika storlek q × n. Vi kommer att numrera lagren 0, 1,..., m − 1, och vi kommer att numrera raderna inom varje lager 0, 1,.., q − 1. Pv ( Uppbyggnad av poolningsmatrisen Reed-Solomon med q = 16 och m = 6, och n = 288. Kolumnerna motsvarar prover och indexeras av polynom över F 16, och raderna grupperas i 6 lager. Vi belyser tilldelningen av exemplaret v = 275 i lager 2. Som beskrivs i texten överväger vi P 275 = U 2 + U + 3 och utvärderar P 275 (2) = 5. Därefter representerar vi varje provnummer som ett polynom av grad k−1. Vi beställer polynomet lexikografiskt. Om t.ex. k = 3, och q = 16, representeras det första exemplaret av polynomet P0(U) = 0U 2 +0U +0 = 0, representeras det andra exemplaret av polynomet P1(U) = 0U 2 + 0U + 1 = 1, det 275:e exemplaret representeras av P275(U) = U 2 +U +3, och det 276:e av P276(U) = U 2 + U + 4. Observera att denna polynom representation beror på q: om q = 7, sedan P275(U) = 5U 2 + 4U + 2. Varje prov kommer att tilldelas en pool i varje lager. För att hitta pooling tilldelning av ith prov i det jth skiktet, kommer vi att utvärdera polynomet Pi på position j, Pi(j), över det finita fältet av storlek q, betecknade Fq. Till exempel om q = 7, i = 275, och j = 2, sedan P275.2 = 5 · 2 2 + 4 · 2 + 3 mod 7 = 3. Nu är i kolumnen i j-lagret en binär vektor av längd q, vars - th position är 1 om Pi( j) = och 0 annars. Således ith provet kommer att tilldelas den th poolen i det jth lagret. Till exempel, om q = 7, i lager 2, kommer det 275: e provet att tilldelas den pool märkt 3 i det lagret. Vi noterar att när q är ett primtal, addition och multiplikation operationer för att utvärdera polynom utförs helt enkelt modulo q. Men när q är en primär kraft, är aritmetiken av det finita fältet mer involverad-till exempel, över F16, vi har 4 2 = 3. Vi har i tilläggsmaterialet inkluderat en introduktion till finita fält och aritmetiska tabeller för F16. I detta exempel, om q = 16, då vi anser P275.2 = 2 2 + 2 + 3 över F16, vilket visar sig vara 5. Således kommer det 275: e exemplaret att tilldelas pool 5 i lager 2. Processen illustreras i figur 1, med q = 16, m = 6, och n = 288. Vi kommer att återkomma till detta exempel i hela dokumentet för att illustrera våra idéer. Shifted Transversal Designs [22] är specialfall av RS-koder, när q är begränsad till en prime snarare än en prime power. Vi beskriver korrespondensen i det kompletterande materialet. Vi kommer att visa att RS-koder har alla egenskaper av STD, samtidigt som de ger mer flexibilitet: tvärtemot STD, RS-koder är instriniskt väl anpassade till typiska laboratorieautomation hårdvara. Från konstruktionerna av RS-konstruktioner ser vi omedelbart att flera av våra praktiska önskemål uppfylls. För det första, parametern utrymme är mycket rik, och i synnerhet detta gör det möjligt för konstruktioner som fullt utnyttja 96-well plattor. Som i exemplet ovan, att välja m = 6 och q = 16 ger exakt 96 brunnar. Dessutom, eftersom proverna också lagras i 96-håls plattor, är det bekvämt för pooling mönster att arbeta med n prover, där n är en multipel av 96. Återigen visar exemplet ovan (där n = 288 = 3 · 96) att detta är lätt att få fram. Ytterligare (som kan ses i figur 1 ), dessa konstruktioner har en hel del struktur, vilket resulterar i effektivare poolning samt felkontroll av poolning förfarande genom visuell inspektion. För det andra har dessa mönster utmärkt regelbundenhet och vikt. Varje prov poolas i exakt en pool i varje lager; således varje prov deltar i m pooler totalt. Det är också sant att varje pool innehåller exakt n/q prover, så länge n är en multipel av q. Figur 1, Vi ser att den resulterande designmatrisen är balanserad. I varje 16 × 16 block finns exakt en 1 i varje rad och varje kolumn. Detta innebär att a) var och en av de 288 exemplaren deltar i exakt 6 pooler, och b) varje pool innehåller exakt 288/16 = 18 prov. Dessutom innebär det att dessa egenskaper håller modulärt: den design som ges av den skuggade submatrisen har 96 exemplar, som var och en deltar i exakt 6 pooler, så att varje pool innehåller exakt 6 av dessa prover. Detta faktum innebär mycket starka regelbundenhet egenskaper: inte bara är designen lätt och välbalanserad, men dessa egenskaper håller på ett modulärt sätt. Som beskrivits ovan är det ofta användbart att kunna samla olika uppsättningar exemplar vid olika tidpunkter. Med RS mönster, så länge exemplaren är poolade i multiplar av q, har forskaren lätt och välbalanserad design i alla storlekar är lämpligt. Diskontens och tillfrisknande. Utöver den praktiska strukturen bör samlingsdesignen möjliggöra en effektiv återhämtning av mönstret för positiva exemplar, med tanke på de sammanslagna uppgifterna. För detta introducerar vi begreppet diskontitet. En pooling design är d-disjunkt om för varje uppsättning av d prover, och varje prov i inte i den uppsättningen, det finns några pool j som inkluderar i men inte innehåller någon post i ι. Det resulterande villkoret på matrisen M illustreras i figur 3. Om M har denna egenskap, då kan vi snabbt hitta rätt uppsättning av positiva från de poolade resultaten, förutsatt att denna uppsättning inte är större än d. Vi hävdar helt enkelt att en post i är positiv om alla dess pooler var positiva. Om punkten jag inte var positiv, och den sanna uppsättningen positiva var ι, då disjunktness villkor exakt anger att jag kommer att landa i någon pool som inte testa positivt. Diskontivitet diskuteras mer i detalj i det kompletterande materialet. För pooling mönster som härrör från koder, som RS mönster, är det lätt att få en gräns på disjunktness. RS-designen som definieras ovan har dikonktitet minst d = (m − 1)/k. I vårt körexempel från Figur 1 kommer detta ut till d = 2. Vi kommer att se i ett senare avsnitt (förslag 2) varför så är fallet. När det gäller antalet exemplar n, garanterar ovanstående bundna att med t pooler kan vi uppnå diskontensitet av minst t q(log q (n)-1). Denna gräns innebär en avvägning mellan återvinningsgarantier (högsta antal defekter som återvunnits, d) och budget (förutsatt att de står i proportion till antalet pooler t). Dessutom är den RS-baserade designen som beskrivs ovan inkrementell - d.v.s. en experimentist kan börja med ett litet antal Emission Date Volume Emission Number 3 lager m, vilket ger en liten poolningsmatris M med ett visst diskonteringsvärde, och gradvis öka m genom att lägga till ytterligare lager till poolningsmatrisen, vilket ökar diskontensen. Att lägga till ytterligare ett lager j uppnås enkelt genom att utvärdera polynom pi över fältet Fq vid elementet j  på Fq.  Som diskuteras i inledningen, i många tillämpningar är det praktiskt att samla prover i satser, så att dessa satser kan antingen testas självständigt, eller blandas med andra och testas gemensamt. Mer specifikt, med tanke på två grupper av c exemplar vardera, kan en poola varje grupp separat (med hjälp av två olika pooling mönster) i p pooler vardera; den resulterande designen har 2c prover poolas i 2p pooler. Alternativt kan man kombinera eller "överlappa" konstruktionerna, vilket resulterar i 2c exemplar poolade i p pooler. Den resulterande situationen för mätmatriser visas i figur 4. Det finns kompromisser mellan dessa två strategier: i den första, det finns fler tester men det finns färre prover i varje pool, potentiellt ger mer exakta analysresultat. I den andra, det finns färre tester, men en möjlighet till mindre noggrannhet. Ett praktiskt mål i pooling designs är att göra denna kompromiss så fördelaktigt som möjligt. Det vill säga, vi vill dela upp kolumnerna i poolning matris M i submatriser Mi så att varje submatris Mi har god diskontitet. Trivialt, varje Mi kommer att vara minst lika disjunkt som M själv, men vi söker mönster där passera till en submatris ger en strikt förbättring i disjunktness (och därmed en strikt bättre avvägning mellan noggrannheten och antalet pooler). Vi hänvisar till denna egenskap som modularitet i konstruktionen, och vi diskuterar de matematiska detaljerna mer i detalj i avsnittet om allmänna linjära koder. Även utan att förbättra disjunktness, de mindre konstruktioner som motsvarar submatriser Mi är lättare att avkoda eftersom d positiva kommer att spridas över dessa underdesigner, så att varje experiment kommer att behöva ta itu med (och identifiera) färre positiva. I praktiken finns det många skäl till att man skulle vilja ha den typ av flexibilitet som modularitet innebär. Till exempel, anta-som är ofta fallet-att man inte vet det verkliga antalet positiva, d. Då kan man använda moduläritet för att uppskatta d på flugan, enligt följande. Antag att pooling design ges av en modulär matris M, som bryts ner i submatriser M1, M2,. .., M b, Där varje delmatris Mi tilldelar, låt oss säga, 96 objekt till p pooler. Innan du gör några tester, kan biologen samla sina prover i b olika 96-well plattor, enligt b olika pooling mönster, var och en med mycket god diskontness. När det är dags att köra tester, kan hon välja att börja med en enda platta; om hennes resultat är mycket bra, hon kan tycka att hon har överskattat d. För sina nästa två tester, hon kan välja att kombinera den andra och tredje plattor, vilket resulterar i en design (som i figur 4 b), med sämre disjunktitet men färre pooler. Om detta fortfarande verkar alltför pessimistisk, hon kan fortsätta på detta sätt, testa fler och fler plattor i taget tills hon träffar den önskade avvägningen mellan diskontitet och antalet pooler. Som ett annat exempel har Shifted Transversal Design god modularitet, och detta har gett viktiga praktiska fördelar i ett samverkande kartläggningsförsök [25]. I detta arbete konstruerades underkonstruktioner ("mikropooler") en gång och kombinerades sedan med superposition för att erhålla mönster som var väl lämpade för olika experimentella format: parvis för 1536-well format, i sexor för 384-well format, och i tolvor för 96-well format. RS-konstruktioner (och, liksom trenden i detta arbete, konstruktioner från lämpliga linjära koder mer allmänt) har goda modulära egenskaper. Den grundläggande tanken är att varje platta av q kolumner (demarcated by the orange lines in Figur 2 ) har liknande disjunktness egenskaper. Detta följer av det faktum att de uppsättningar polynom de motsvarar ser liknande: när det gäller diskontering är det inte mycket skillnad mellan uppsättningen {U 2 + U, U 2 + U + 1,..., U 2 + U + 15} och uppsättningen konstant polynom (0, 1,.., 15}. På samma sätt, i en större skala, är det inte så stor skillnad mellan uppsättningen av alla polynom av formen U 2 + au + b och uppsättningen av alla polynom i formen 2U 2 + au + b. På grund av arten av dessa symmetrier, modulariteten förekommer naturligt för uppsättningar av kolumner av storlek q, q 2, q 3, och så vidare. Till exempel när q = 16, m = 6, och k = 3, kan vi stödja upp till n = q k = 16 3 = 4096 objekt med diskontitet 2. Dessa poster kan delas in i undergrupper av storlek 16 2 = 256 med en garanti för disjunktes 5. Som diskuterats ovan är det dock ofta lämpligt om storlekarna på delmängderna av prover är multiplar av 96. För illustration, överväga en något större version av vår kör exempel, där q, m, och k är som ovan, men där n = 576 = 6 · 96. Om vi delar upp exemplaren i sex partier av storlek 96 på det naturliga sättet: de första 96 kolumnerna, sedan de nästa 96 och så vidare, de flesta block av storlek 96 inte störa blocken i storlek 256 (eller inte överlappa 256-blocksgränserna). På så sätt fick de flesta partier av 96 exemplar på detta sätt ärva den förbättrade splittringen i blocken av storlek 256. Samma argument fungerar för varje multipel av 96. Bilda. 4........................................... Olika sätt att kombinera två pooling mönster ges av matriserna M 1 och M 2. I a poolas varje grupp av exemplar separat, vilket resulterar i 2p-pooler. I b kombineras poolingdesignen, vilket resulterar i p-pooler. En design M som består av submatriser M 1, M 2 har god modularitet om pooling matrisen (a) har strikt bättre diskontitet än matrisen (b). Oavsett om vi utnyttjar moduläriteten i RS-designen eller inte, hela designen av vårt körexempel har disjunktitet av bara två som verkar ganska dyster. Tyvärr, med bara 96 pooler och ett stort antal prover, är det inte möjligt att få mycket bättre värsta fall garantier. I praktiken är dock dessa garantier ofta alltför pessimistiska. Därför är det naturligt att fråga om prestanda av dessa mönster mot de flesta mönster av positiva. Vi söker ett uttalande av formen, "för de flesta mönster av defekter, är grupptestmatrisen effektivt d-disjunkt." I detta syfte definierar vi en svagare uppfattning om olikhet, som vi kallar den genomsnittliga olikheten, som mäter hur många defekter som på ett tillförlitligt sätt kan identifieras i en "typisk" snarare än i värsta fall situation. Vi säger att en uppsättning exemplar är dåligt om det orsakar en situation som i den högra sidan av figur 3. Det vill säga, det är dåligt om det finns något exemplar i så att det sammanfaller med minst en medlem av ι varje gång det poolas. Därför är en design d-diskonterad om alla uppsättningar av storlek d inte är dåliga. Vi slappnar av detta på ett naturligt sätt, och säger att en pooling design är (δ, d)-genomsnittlig-disjunkt, om som mest en δ-fraktion av de uppsättningar av exemplar i storlek d är dåliga. (När det inte nämns tar vi det som en lämplig liten konstant, som 0,01). Om de positiva exemplaren fördelas slumpmässigt, med sannolikhet 1−δ, är den uppsättning positiva exemplar som visas inte dålig. Således, genom samma resonemang om (sämsta-fallet) diskontness, drar vi slutsatsen att (δ, d)-genomsnitt-dijunktness tillåter effektiv identifiering av d positiva väljs enhetligt slumpmässigt med sannolikhet hos Footline Författare minst 1 − δ. Det är naturligtvis orimligt att i praktiken anta att de positiva exemplaren kommer att fördelas jämnt. Ovanstående resonemang fungerar dock för all distribution som är "nära" den enhetliga i lämplig bemärkelse; t.ex., fysiska exemplar tilldelas kolumnidentiteter slumpmässigt. En matris kan vara d-genomsnittlig disjunkt utan att vara d-disjunkt, och vi är intresserade av att kvantifiera och utnyttja denna lucka. Det gör vi både i praktiken och i teorin. I det kompletterande materialet visar vi hur man på ett effektivt sätt beräknar enkla, påvisbara gränser på värdena i (δ, d) så att RS-konstruktioner är (δ, d)-genomsnittlig disjunkt. Vi kompletterar våra teoretiska resultat med empiriska, vilket indikerar att våra gränser är ganska exakta för små d, och förlorar noggrannhet när d växer. Konstruktioner. I båda diagrammen jämförs den empiriska prestandan hos RS pooling-designen med dess teoretiska prestanda, liksom den empiriska prestandan hos två randomiserade pooling-designer. För RS-matriserna bedömdes empirisk prestanda med hjälp av 5000 slumpmässiga studier. För de slumpmässiga matriserna bedömdes empirisk prestanda från 100 studier vardera på 100 slumpmässiga matriser. De teoretiska gränserna erhölls genom en rekursiv formel beskriven i det kompletterande materialet. Det översta diagrammet spårar den empiriska och bevisbara framgångsannolikheten 1 − δ för en RS-design med m = 6 och d = 6, när antalet exemplar n växer, och jämför detta med felsannolikheten för slumpmässiga mönster med samma kolumnvikt och antal tester. Den nedre diagrammet rättar n = 576 = 6 · 96, och varierar d. För alla RS-mönster, den värsta fall disjunktness är två. Våra resultat, både teoretiska och empiriska, visas i figur 5. Vi jämförde RS pooling designs empiriska prestanda med två randomiserade konstruktioner. För den första slumpmässiga designen, valde vi n slumpmässiga kolumner från en RS-design med hela q k möjliga kolumner; denna jämförelse är avsedd att illustrera att vårt modulära kolumnval inte bara är bekvämt för praktiska överväganden, det ger också faktiskt bättre prestanda. För den andra slumpmässiga designen valde vi en slumpmässig m · q × n matris med m en per kolumn. Teoretiskt sett erbjuder slumpmässiga matriser de bästa asymptotiska garantierna, och det faktum att RS designar överträffar den för någorlunda stora värden av n är slående. Dessa resultat är mycket mer hoppfulla än de värsta fall gränserna för d = 2. För n = 576 kan t.ex. upp till 7 eller 8 positiva identifieras korrekt med rimlig sannolikhet. Vidare ser vi att RS-konstruktioner presterar mycket bättre än jämförbara slumpmässigt genererade mönster. Vi testade RS-designen med ett experiment som kombinerade 480 prover till 96 pooler (m = 6, q = 16). För detta experiment använde vi ett leksaksproblem där enskilda prover representerades av en enda brunn på 150 μl avjoniserat vatten och positiva prover av vatten spetsades med blått färgämne (100X utspädning). Syftet med försöket var att hitta de positiva (blå färg) exemplaren genom att inspektera poolerna. Pooling utfördes med en Tecan Evo robot med hjälp av en fyratip vätskehantering arm (LiHa). För att få fram data kvantifierade vi absorbansförhållandet (470nm/630nm) för varje pool med hjälp av en plåtläsare. Sedan använde vi en ut-of-the-box konventionell komprimerad avkänning dekoder (GPRR) [19] för att avkoda resultaten. Trots den molekylära enkelheten fångar vår experimentella design några av de utmaningar som pooling experiment innebär. Först testar den själva avrättningen i en laboratoriemiljö. För det andra fångar detta enkla experiment de tre största utmaningarna med sammanslagningsförsök: pipettering, utspädning och mätbuller. Pipettbuller avser försöksledarens oförmåga att aspirera och dela ut den exakta volymen av ingångsprovet på grund av mänskligt fel. Dessa brister introducerar buller till pooling matrisen som kan förvränga signalen. Baserat på våra empiriska resultat var variationskoefficienten för pipettstegen 5-10 %. Utspädningsbuller uppstår när signalen från det positiva provet minskas när poolens storlek ökar. I vårt leksaksexperiment innehöll varje pool 30 exemplar som spädde ut den blå färgsignalen med samma faktor. Mätningsbuller i detta exempel skulle vara ett resultat av absorbansskanningen för att mäta det blå färgämnet i de konstruerade poolerna. I detta fall härrör mätbullret huvudsakligen från antalet fotoner i varje skannad pool. Trots dessa ofullkomligheter kunde vi exakt avkoda de sammanslagna resultaten och identifiera de ursprungliga exemplaren när tre var positiva. Vi upprepade detta experiment med tio positiva exemplar och kunde korrekt avkoda åtta av de ursprungliga exemplaren med ett falskt positivt och ett falskt negativt. Detta är inte förvånande eftersom simuleringar som visas i figur 5 uppvisar ofullständig avkodning för liknande förhållanden. Uppmuntrade av dessa resultat, testade vi också vår pooling design för att hitta sällsynta genetiska variationer med hjälp av riktad hög genomströmning DNA sekvensering. Riktad sekvensering är en arbetsintensiv och kostsam procedur som bearbetar DNA i flera steg för att berika för specifika genomiska regioner; istället använde vi en pooling design. Vi samlade lika stora mängder 96 DNA-prover från HapMap-projektet till 25 pooler med hjälp av en RS-kod med m = 5 och q = 5 (även en Shifted Transversal Design). De 25 poolerna var streckkoder och berikas av hybrid urval med hjälp av Agilent SureSelect beten som berikas för gener som finns i Framingham Heart Study (790 kb genomic material). Poolerna komprimerades ytterligare till fem megapooler och sekvenserades på fem banor på Illumina HiSeq (2 × 80 bp) till 1000 gånger den genomsnittliga täckningen per pool. För att testa vårt tillvägagångssätt undersökte vi 75 av våra prover som också var sekvenserade som en del av 1000 Genomes Project [4]. Mer än 97 % av målområdet omfattades av minst en sekvensering. Efter att ha filtrerat positioner med data av låg kvalitet (se tilläggsmaterial) fick vi 92% av baserna i den ursprungliga designen. Därefter utnyttjade vi RS-kodens struktur för att uppskatta antalet bärare i vår design innan vi avkodade och tillskriver mutationen enskilda exemplar. Detta förfarande bygger på observationen att varje exemplar deltar i exakt en pool per lager. Genom att kontrollera antalet varianter avläser över pooler i samma lager är det möjligt att uppskatta antalet transportörer. Eftersom vår design hade fem lager, upprepade vi denna procedur fem gånger och i genomsnitt resultaten för att få mer exakta uppskattningar. Vi jämförde antalet bärare mellan vår estimator med hjälp av pooling data och en estimator med hjälp av individuella-nivå resultat av 75 exemplar i 1000 Genomes data. Figur 6 visar utmärkt konsistens (R 2 = 0.91) Våra resultat fann också goda avkodningsmöjligheter för sällsynta varianter. Vi avkodade de poolade data för varianter där vår poolade estimator indikerade fem eller färre bärare (översatt till en mindre allelfrekvens på 2%). Vi använde en serie avkodare som tog hänsyn till sekvenseringen buller vid varje position och fördelningen av avläsningar med varianten allel. Dessa dekodrar kördes på varje nukleotid separat och använde poolningsmatrisen för att hitta vilka exemplar som faktiskt bär den sällsynta allelen. Våra resultat indikerar en specificitet på > 99.99% och känslighet på ca 85% jämfört med 1000 Genomes data, i genomsnitt över alla positioner. Vi undrade om de falska negativen representerar en sann avkodningsmiss eller ett sekvenseringsfel i 1000 Genomes-projektet på grund av den låga täckningen av dessa genom. Vi vände oss till National Heart, Lung och Blood Institute (NHLBI) Exome Sequencing Project (ESP) [8], som innehåller genomiska data för mer än 5000 individer. Förväntningen är att sekvensering fel i 1000 Genomes data inte kommer att visas som variabla platser i ESP. När vi inspekterade missade positioner i våra resultat varierade bara 26 procent av dem inom ESP. Vi inspekterade också positioner där vår dekoder hittade en sällsynt variantsignal i den poolade datan. Nära 38 % av dessa positioner varierade också inom ESP. Detta tyder på att en del av den ofullständiga känsligheten kan tillskrivas sekvenseringsfel i referensuppgifterna snarare än ett problem med dekodern. Vi skapade ett gratis webbverktyg för att designa och leda experiment (http://pooling.teamerlich.org). En användare laddar upp ett urval karta kalkylblad och anger antalet prover och volym begränsningar. Sedan kan hon välja sin önskade pooling design (för fullständighet och utbildning kan vårt verktyg generera flera pooling mönster som beskrivs i grupptest litteratur utöver standard RS-kod design (q = 16, m = 6). På grundval av användarinmatningen kontrollerar verktyget att provexemplaren har tillräcklig volym för att poolas och att samlingsplattan kan hålla den ackumulerade volymen från det ingående materialet utan spillover. Därefter genererar verktyget en designspecifik matris och pooling instruktioner. Poolningsinstruktionerna är kompatibla med en robot för vätskehantering eller manuell hårdvara som iPipet [26]. Den senare är ett semiautomated open-source verktyg som vi utvecklat för att konvertera en vanlig iPad (och de flesta surfplattor) till en prov-tracking enhet. Användarna lägger helt enkelt provplattan och poolningsplattan på tabletten, och iPipet lyser upp de brunnar som ska sugas upp eller delas ut. Baserat på våra tester kan en utbildad försöksperson genomföra ett RS-kodbaserat poolningsförsök med 500 indataprover inom några timmar med iPipet. Med detta verktyg och den teori som beskrivs i detta dokument hoppas vi kunna minska de tekniska hindren för försöksutövare att genomföra sammanslagna experiment och ge vägledning baserad på noggrann teoretisk analys. Författarna vill tacka Institutet för Matematik och dess tillämpningar för att underlätta vårt inledande samarbete. J.E. har en karriär
Prestandan av Kautz-Singleton-konstruktionen i den slumpmässiga modellen har studerats empiriskt REF, men vi är inte medvetna om någon teoretisk analys av den utöver vad som följer omedelbart från avståndet av Reed-Solomon koder.