Djupsekvensering har gjort det möjligt att undersöka ett brett spektrum av mikrobiella ekosystem i miljön, men de höga kraven på minne för de novo-montering av kortlästa hagelgevärssekvensdata från dessa komplexa populationer är en allt större praktisk barriär. Här introducerar vi en minneseffektiv grafrepresentation med vilken vi kan analysera k-mer-anslutningen av metagenomiska prover. Grafrepresentationen är baserad på en probabilistisk datastruktur, ett Bloom-filter, som gör att vi effektivt kan lagra monteringsgrafer i så lite som 4 bitar per k-mer, om än inexakt. Vi visar att denna datastruktur exakt representerar DNA-samlingsgrafer i lågt minne. Vi tillämpar denna datastruktur på problemet med att dela upp monteringsgrafer i komponenter som en inledning till montering, och visar att detta minskar de övergripande minneskraven för de novo montering av metagenomer. På en jordmetagenomsamling uppnår detta tillvägagångssätt en nästan 40-faldig minskning av de maximala minneskraven för montering. Denna probabilistiska graf representation är ett betydande teoretiskt framsteg i att lagra monteringsgrafer och ger också omedelbar hävstångseffekt på metagenomic montering. metagenomics. de novo construction. de Bruijn grafer. k-mers De novo montering av hagelgevär sekvensering avläser i längre sammanhängande sekvenser spelar en viktig roll i praktiskt taget all genomisk forskning [1]. Befintliga beräkningsmetoder för sekvensmontering är emellertid inte så omfattande att de nu är lätt tillgängliga från nästa generations sekvenseringsmaskiner [1, 2]. Särskilt den djupa sekvensering som krävs för att provta komplexa mikrobiella miljöer resulterar lätt i datamängder som överträffar arbetsminnet hos tillgängliga datorer [3, 4]. Djupsekvensering och sammanställning av korta avläsningar är särskilt viktigt för sekvensering och analys av komplexa mikrobiella ekosystem, som kan innehålla miljoner olika mikrobiella arter [5, 6]. Dessa ekosystem medlar viktiga biogeokemiska processer men är fortfarande dåligt förstådda på molekylär nivå, till stor del eftersom de består av många mikrober som inte kan odlas eller studeras individuellt i laboratoriet [5, 7]. Ensemble sequencing ("metagenomics") av dessa komplexa miljöer är ett av få sätt att göra dem tillgängliga, och har resulterat i betydande tidiga framsteg i att förstå den mikrobiella sammansättningen och funktionen av havet, människans tarm, koromen och permafrost jord [3, 4, 8, 9]. Men i takt med att sekvenskapaciteten ökar har sammansättningen av sekvenser från dessa komplexa prover blivit allt svårare att beräkna. Befintliga metoder för kortläsande sammansättning bygger på inexakt dataminskning där avläsningar från lågöverflödiga organismer förkastas, partiska analyser mot högöverflödande organismer [3, 4, 9]. Den dominerande sammansättning formalism tillämpas på kortlästa sekvensering datamängder är en de Bruijn diagram [10, 11, 12]. I en de Bruijn graf metod, sekvensering av avläsningar bryts ned i fast längd ord, eller k-mers, och används för att bygga en konnektivitet graf. Denna graf korsas sedan för att bestämma sammanhängande sekvenser [12]. Eftersom de Bruijn-grafer endast lagrar k-mers, skalor minnesanvändning med antalet unika k-mers i datamängden snarare än antalet läsningar [13, 12]. Människans genom kan således samlas i mindre än 512 GB systemminne [14]. För mer komplexa prover såsom jordmetagenomer, som kan ha miljontals eller fler arter, terabyte av minne skulle krävas för att lagra grafen. Dessutom begränsar den stora variationen i artrikedomen nyttan av standardmetoder för minnesminskning, såsom överflödsbaserad felkorrigering [15]. I detta arbete beskriver vi en enkel probabilistisk representation för lagring av de Bruijn grafer i minne, baserad på Bloom filter [16]. Bloom filter är fasta-minne probabilistiska datastrukturer för lagring sparse uppsättningar; i huvudsak hash tabeller utan kollision upptäckt, ställa medlemskap frågor Bloom filter kan ge falska positiva men inte falska negativa. Bloom filter har tidigare använts i bioinformatiska mjukvaruverktyg, men de har inte använts för att lagra grafer [17, 18, 19, 20]. Vi visar att denna probabilistiska graf representation mer effektivt lagrar de Bruijn grafer än någon möjlig exakt representation, för ett brett spektrum av användbara parametrar. Vi visar också att det kan användas för att lagra och passera faktiska DNA de Bruijn grafer med en 20 till 40-faldig minskning av minnesanvändning över två vanliga de Bruijn graf-baserade montörer, Velvet och ABySS [21, 22]. Vi relaterar förändringar i lokala och globala grafanslutning till den falska positiva frekvensen av de underliggande Bloom filter, och visar att grafens globala struktur är korrekt för falska positiva frekvenser på 15% eller lägre, vilket motsvarar en lägre minnesgräns på cirka 4 bitar per graf nod. Vi tillämpar denna graf representation för att minska det minne som behövs för att montera ett jordmetagenom prov, genom användning av läsa partitionering. Partitionering separerar en de Bruijn-graf upp till frånkopplade grafkomponenter. Dessa komponenter kan användas för att dela upp sekvensavläsningar i frånkopplade undergrupper som kan monteras separat. Detta utnyttjar en bekväm biologisk egenskap hos metagenomiska prover: de innehåller många mikrober som inte bör samlas tillsammans. Diagramdelning har använts för att förbättra kvaliteten på metagenom- och transkriptomenheter genom att anpassa monteringsparametrarna till den lokala täckningen av grafen [23, 24, 25]. Men vad vi vet har partitionering inte tillämpats på skalning av metagenomet. Genom att tillämpa den probabilistiska de Bruijn graf representation på problemet med partitionering, uppnår vi en dramatisk minskning med nästan 40-faldigt i minnet som krävs för montering av en jordmetagenom. Bloom filter kan lagra de Bruijn grafer. Med tanke på en uppsättning korta DNA-sekvenser, eller avläsningar, bryter vi först ner varje avläsning till en uppsättning överlappande k-mers. Vi lagrar sedan varje k-mer i ett Bloom-filter, en probabilistisk datastruktur för lagring av element från glesa datamängder (se Metoder för genomförandedetaljer). Varje k-mer fungerar som en vertex i en graf, med en kant mellan två hörn N1 och N2 om och endast om N1 och N2 delar en (k-1)-mer som är ett prefix av N1 och ett postfix av N2, eller vice versa. Denna kant lagras inte explicit, vilket kan leda till falska anslutningar när två läser abut men inte överlappar; dessa falska anslutningar manifesteras som falska positiva, diskuteras i detalj nedan. Således varje k-mer har upp till 8 kanter som ansluter till 8 angränsande k-mers, som kan bestämmas genom att helt enkelt bygga alla möjliga 1-bas förlängningar och testa för sin närvaro i Bloom-filtret. På så sätt behandlar vi grafen implicit som en enkel graf i motsats till en multigraf, vilket innebär att det inte kan finnas några självslingor eller parallella kanter mellan hörn/kmers. Genom att förlita sig på Bloom filter, är storleken på datastrukturen fast: inget extra minne används som ytterligare data läggs till. Denna graf struktur är effektivt komprimeras eftersom man kan välja en större eller mindre storlek för de underliggande Bloom filter; för ett fast antal poster, ett större Bloom filter har lägre beläggning och producerar motsvarande färre falska positiva, medan ett mindre Bloom filter har högre beläggning och producerar fler falska positiva. I utbyte mot minne, kan vi lagra k-mer noder mer eller mindre exakt: till exempel, för en falsk positiv hastighet på 15%, där 1 av 6 slumpmässiga k-mers testade skulle felaktigt anses närvarande, varje verklig k-mer kan lagras i under 4 bitar av minne (se tabell 1 ). Även om det finns många falska k-mers, de bara spelar roll om de ansluter till en riktig k-mer. Den falska positiva hastighet som ingår i Bloom filter väcker därför en oro för graflagring: i motsats till en exakt graf lagring, finns det en chans att en k-mer kommer att vara i anslutning till en falsk positiv k-mer. Det vill säga, en k-mer kan ansluta till en annan k-mer som faktiskt inte existerar i den ursprungliga datauppsättningen men ändå registrerar som närvarande, på grund av den probabilistiska karaktären hos Bloom-filtret. Då minnet per verklig k-mer minskar, vinner man falska positiva hörn och kanter, så att komprimera grafen resulterar i en mer sammanflätad graf. Om den falska positiva frekvensen är för hög, kommer grafstrukturen att domineras av falsk konnektivitet - men vilken hastighet är "för hög"? Vi studerar denna nyckelfråga i detalj nedan. Falska positiva faktorer orsakar lokal utveckling av grafstrukturen. Errona grannar skapade av falska positiva kan ändra grafstrukturen. För att bättre förstå denna effekt, genererade vi en slumpmässig 1,031bp cirkulär sekvens och visualiserade effekten av olika falska positiva hastigheter. Efter att ha lagrat denna enda sekvens i komprimerade grafer med k = 31 med fyra olika falska positiva hastigheter (p f = 0,01, 0,05, 0.10 och 0,15), utforskade vi grafen med hjälp av bredd-första sökningen som börjar vid den första 31-mer. Graferna i figur 2 illustrerar hur de falskt positiva k-mers kopplade till de ursprungliga k-mers (från 1,031bp-sekvensen) utvecklar den falska positiva hastigheten medan den totala cirkulära grafstrukturen förblir, utan några felaktiga genvägar mellan k-mers som finns i den ursprungliga sekvensen. Det är visuellt uppenbart att även en hög falsk positiv frekvens på 15 procent inte systematiskt och felaktigt förbinder avlägsna k-mers. Falsk långdistansanslutning är en icke-linjär funktion av den falska positiva hastigheten. För att utforska den punkt där vår datastruktur systematiskt skapar falska långdistansanslutningar, infogade vi slumpmässiga k-mers i Bloom filter med ökande falska positiva hastigheter. Dessa k-mers ansluter till andra k-mers för att bilda grafkomponenter som ökar i storlek med den falska positiva hastigheten. Vi beräknade sedan den genomsnittliga komponentstorleken i grafen för varje falsk positiv frekvens (n = 10000) och använde percentil bootstrap för att erhålla uppskattningar inom ett 95% konfidensintervall. Figur 3 visar att den genomsnittliga komponentstorleken snabbt ökar när ett visst tröskelvärde närmar sig, vilket verkar ha en falsk positiv hastighet nära 0,18 för k=31. Utöver 0,18 börjar komponenterna sammanfogas till större komponenter. När den falska positiva takten ökar, observerar vi en plötslig övergång från många små komponenter till färre, större komponenter som skapas av felaktiga kopplingar mellan de "sanna" komponenterna (figur 3). I motsats till den linjära ökningen i den lokala kvartersstrukturen när den falska positiva hastigheten ökar linjärt, är förändringen i den globala grafstrukturen abrupt då tidigare bortkopplade komponenter går samman. Denna snabba förändring liknar en geometrisk fasövergång, som för grafer kan diskuteras i termer av perkolationsteori [26]. Vi kan kartlägga vårt problem till webbplatsen percolation genom att överväga en sannolikhet p att en viss k-mer är närvarande, eller "på". (Detta är i motsats till obligationsperkolering där p representerar sannolikheten för att en viss kant finns.) Så länge den falska positiva andelen ligger under perkoleringströskeln p  på (d.v.s. I den subkritiska fasen skulle vi förutsäga att grafen inte är starkt kopplad till falska positiva. Perkoleringströsklar för finita grafer kan uppskattas genom att man finner var komponentstorleksfördelningen övergår från linjär till kvadratisk i form [27]. Med hjälp av den beräkningsmetod som beskrivs i Metoder, fann vi platsen percolation tröskel för DNA de Bruijn grafer att vara p  och = 0,183 ± 0,001 för k mellan 5 och 12. Även om vi bara testade inom detta begränsade område av k, verkar perkoleringströskeln vara oberoende av olika k (se figur S1 ). Så länge den falska positiva frekvensen är lägre än 0,183, förutspår vi alltså att verkligt bortkopplade komponenter i grafen sannolikt inte kommer att ansluta till varandra felaktigt, dvs. på grund av fel som införts av den probabilistiska representationen. Storskalig grafstruktur bibehålls upp till perkoleringströskeln. Resultaten från analysen av komponentstorlek och uppskattningen av perkoleringströskeln tyder på att grafens globala konnektivitet sannolikt inte kommer att förändras under en falsk positiv frekvens på 18 %. Ser vi denna variation i den globala konnektiviteten i andra grafåtgärder? För att bedöma den globala konnektiviteten använde vi diametern metrisk i grafteorin, längden på den "längst kortaste" vägen mellan två hörn [28]. Om kortare vägar mellan verkliga k-mers systematiskt skapades på grund av falska positiva, skulle vi förvänta oss att diametern på komponenter minskar när den falska positiva hastigheten ökade. Vi genererade slumpmässigt 58bp långa cirkulära kromosomer (50bp läst med den första 8-mer bifogade till slutet av strängen) för att konstruera komponenter som innehåller 50 8-mers och beräknade diametern vid olika falska positiva hastigheter. Vi höll k lågt eftersom vi behövde kunna utforska grafen på ett uttömmande sätt även bortom perkoleringströskeln, vilket är beräkningsmässigt oöverkomligt att göra vid högre k-värden. Dessutom skulle större cirkulära kromosomer vara mer benägna att felaktigt ansluta på en fast 2 www.pnas.org -- Footline Författare k, men på grund av det relativt låga antalet möjliga 8-mers, var vi tvungna att hålla kromosomerna små. Vi övervägde bara vägar mellan två riktiga k-mers i datasetet. Vid varje falsk positiv hastighet körde vi simuleringen 500 gånger och uppskattade medelvärdet inom ett 95% konfidensintervall med percentil bootstrap. Som figur 4 visar är felaktiga kopplingar mellan par av riktiga k-mers sällsynta under en falsk positiv frekvens på 20%. För falska positiva värden över detta tröskelvärde skapas falska kopplingar mellan verkliga k-mers, vilket sänker diametern. Således, den större skalan graf struktur behålls upp genom p = 0,183, som föreslås av komponentstorlek analys och perkolering resultat. Detta visar att så länge k-mer utrymmet bara är glest ockuperat av falska positiva, långa "broar" mellan avlägsna k-mers inte visas spontant. Erronösa k-mers från sekvenserande förmörkelsediagram falskt positiva. Det är viktigt att jämföra felen från falska positiva i de Bruijn graf representation med fel från verkliga data. I synnerhet, verkliga data från massivt parallella sequencers kommer att innehålla bas anropsfel. I de Bruijn grafbaserade montörer, dessa sekvenseringsfel lägga till grafens komplexitet och göra det svårare att hitta högkvalitativa vägar för att generera långa, exakta contigs. Eftersom vårt tillvägagångssätt också genererar falska positiva, ville vi jämföra felfrekvensen från Bloom filter grafen med experimentella fel som genereras av sekvensering (Tabell 2). Vi använde E. coli K-12 MG1665 genomet för att jämföra olika grafinvarianter mellan en Illumina datauppsättning som genereras från samma stam (se Metoder), en exakt representation av genomet, och inexakta representationer med olika falska positiva hastigheter. För dessa jämförelser använde vi ett k-värde på 17, för vilket vi kan lagra grafer exakt, dvs. Vi har inga falska positiva eftersom vi kan lagra 4 17 poster just i 2 GB systemminne. Detta motsvarar ett Bloom filter med en hashtabell och en 0% falsk positiv frekvens. Vi hittade totalt 50,605 17-mers i den exakta representationen som inte ingick i en enkel linje, dvs.. hade mer än två grannar (grad > 2). När den falska positiva takten ökade, ökade antalet av dessa 17-mers på förväntat linjärt sätt. Dessutom utgör antalet verkliga 17-meters, de som inte är falska positiva, majoriteten av grafen. (Som ovan räknade vi bara falska positiva k-mers som är transitivt anslutna till minst en riktig k-mer.) Däremot, när vi undersökte en exakt representation av en Illumina dataset, bara 9,9% av k-mers i grafen verkligen existerar i referensgenomet. Antalet 17-mers med mer än 2 grannar i sekvens avläsningen är högre än för den exakta representationen av genomet, vilket visar att sekvensering fel ökar komplexiteten i grafen. Sammantaget, de fel som visas av sequencers dvärg fel orsakade av inexakt graf representation med en rimlig falsk positiv hastighet. När vi monterar denna datauppsättning med Velvet och ABySS-monteringarna på k=31, kräver Velvet 3,7GB för att montera datamängden, medan ABySS kräver 1,6GB; denna minnesanvändning domineras av graflagringen [29]. Således Bloom filter approach lagrar grafer 30 eller fler gånger effektivare än något av programmen, även med en låg falsk positiv frekvens på 1%. Även om denna direkta jämförelse inte kan göras rättvist monterar grafen liksom k-mer överflöd och annan information -det tyder på att det finns möjligheter att minska minnesanvändning med den probabilistiska graf representation. Sekvenser kan noggrant partitioneras med grafanslutning. Kan vi använda denna låga minnesgraf representation för att hitta och separera komponenter i de Bruijn grafer? Den primära oron är att falska positiva noder eller kanter skulle ansluta komponenter, men diametern resultaten tyder på att komponenter är osannolikt att ansluta under en 20% falskt positiv hastighet. För att verifiera detta analyserade vi en simulerad datauppsättning på 1000 slumpmässigt genererade sekvenser av längd 10 000 bp. Med hjälp av k = 31, delade vi upp data över många olika falska positiva frekvenser, med hjälp av det förfarande som beskrivs i Metoder. Som förväntat varierade det resulterande antalet partitioner inte mellan de falska positiva frekvenserna medan fp ≤ 0,15 (figur S2). Vi tillämpade sedan partitionering till en betydligt större bulkjordmetagenom ("MSB2") som innehåller 35 miljoner 75 bp långa avläsningar som genereras från en Illuminate GAII-sekvenser. Vi beräknade antalet unika 31-meters som finns i datamängden till 1,35 miljarder. Sedan, för var och en av flera falska positiva hastigheter (se tabell 3 ) laddade vi läsarna i en graf, eliminerade komponenter som innehåller mindre än 200 unika k-mers, och partitionerade läsarna i separata filer baserat på grafanslutning. När vi fått partitionen uppsättningar, vi individuellt monterat varje uppsättning partitioner med ABySS, liksom hela (odelad) datauppsättning, behålla contigs längre än 500 bp. De resulterande sammansättningarna var alla identiska, innehåller 1 444 contigs med en total sammansatt sekvens av 1,07 megabaser. Den odelade datamängden krävde 33 GB för att monteras med ABySS, medan datamängden kunde partitioneras i under 1 GB med en 30-faldig minskning av maximal minnesanvändning (tabell 3). Dessutom, trots denna dramatiska minskning av det minne som krävs för att montera datamängden, är monteringsresultaten identiska. Bloom filter kan användas för att effektivt lagra de Bruijn grafer. Användningen av Bloom filter för att lagra en de Bruijn graf är enkel och minne effektiv. Den förväntade falska positiva hastigheten kan justeras baserat på önskad minnesanvändning, vilket ger ett brett spektrum av möjliga lagringseffektivitet (Tabell 1). Eftersom minnesanvändningen är k oberoende i Bloom-filter, är den effektivare än den teoretiska lägre gränsen för en förlustfri exakt representation när antalet k-mers som infogas i grafen är glest befolkat, vilket är beroende av k (figur 5; se [13] för detaljer om lägre bunden minnesanvändning för en exakt representation). Även för låga falska positiva frekvenser som 1%, är detta fortfarande en effektiv graf representation, med betydande förbättringar i både teoretisk minnesanvändning (figur 5 ) och faktisk minnesanvändning jämfört med två befintliga monteringsföretag, Velvet och ABySS (tabell 2). Vi kan lagra k-mers i denna datastruktur med en mycket mindre uppsättning "erronous" k-mers än de som genereras av sekvensering fel, och Bloom filter falska positiva hastigheter har mindre effekt på grenning graf struktur än gör sekvensering fel. Dessutom är de falska positiva som genereras av Bloom filter okorrelerade med den ursprungliga sekvensen, till skillnad från en bas sekvenseringsfel som liknar den verkliga sekvensen. Med hjälp av en probabilistisk graf representation med falska positiva noder och kanter höjer spöket av systematiska graf artefakter som härrör från falska positiva. För partitionering, var vår främsta oro att falska positiva skulle felaktigt ansluta komponenter, vilket gör partitionering ineffektiv. Resultaten från perkoleringsanalysen, beräkningar av diametern och partitionering av simulerade och verkliga data visar att det inte finns någon signifikant falsk konnektivitet under den beräknade perkoleringströskeln. Så länge den falska positiva frekvensen är lägre än 18,3% skapas inte spontant långa falska stigar och de storskaliga grafegenskaperna ändras inte. Ovanför denna takt bryts den globala grafstrukturen långsamt ned. Partitionering fungerar på verkliga datamängder. Våra partitioneringsresultat på en verklig jordmetagenom, MSB2-datauppsättningen, visar nyttan av partitionering för att minska minnesanvändning. För denna specifika datamängd, fick vi identiska resultat med en 20-40x minskning i minne (Tabell 3). Detta är konsonant med våra resultat från lagring av E. coli genomet, där vi uppnådde en 30-faldig minskning av minnesanvändning över den exakta representationen med en falsk positiv hastighet på 1%. Även om ökad täckning och variation i datamängd komplexitet kommer att påverka den faktiska minnesanvändning för andra datamängder, dessa resultat visar att betydande skalning i minnet som krävs för montering kan uppnås i ett verkligt fall. Minneskraven för partitioneringsprocessen på MSB2-datamängden domineras av det minne som krävs för att lagra och utforska grafen; den högre minnesanvändning som observerats för partitionering med en falsk positiv hastighet på 15% beror på ökningen av komponentstorleken från lokala falska positiva. Oavsett, minneskraven för nedströmsmontering av partitioner drivs av storleken på den största partitionen, som här är mycket liten (345,000 avläsningar; tabell 3 ) på grund av den stora mångfalden av jorden och konkordatet låg täckning. Den dominerande partitionsstorleken är anmärkningsvärt eldfast mot grafens falska positiva frekvens, som ökar med mycket mindre än 1% för en 15-faldig ökning av falska positiva; detta visar att våra teoretiska och simulerade resultat för komponentstorlek och diameter gäller även för MSB2-datamängden. När komponenterna är partitionerade kan de monteras med parametrar som valts för täckningen och sekvensens heterogenitet i varje partition. Dessutom kan datamängder som är partitionerade på en låg k0 vara exakt monterade med vilken k ≥ k0, eftersom överlappningar av k0 - 1 baser inkluderar alla överlappningar av större längd. Eftersom partitionerna i allmänhet kommer att vara mycket mindre än den totala datamängden (se tabell 3 ), kan de snabbt monteras ihop med många olika parametrar. Denna förmåga att snabbt utforska många parametrar kan resultera i betydande förbättringar i undersökande metagenome montering, där de "bästa" monteringsparametrarna inte är kända och måste bestämmas empiriskt baserat på många olika sammansättningar. Kombinerat med skalegenskaperna hos graf representation, partitionering med denna probabilistic de Bruijn graf representation erbjuder ett sätt att effektivt tillämpa en partitioneringsstrategi på vissa monteringsproblem. Medan detta arbete fokuserar på de teoretiska egenskaperna hos graf representation och analyserar endast en verklig datauppsättning, resultaten är lovande; nästa steg är att utvärdera metoden på många fler verkliga datamängder. Avslutande tankar. Att utveckla effektiva och korrekta metoder för de novo-montering fortsätter att vara en av bioinformatikernas "stora utmaningar" [2]. Förbättrade metoder för sammansättning av metagenom är särskilt viktiga för undersökningen av mikrobiellt liv på jorden, av vilka en stor del inte har undersökts [30, 7]. Samtidigt som vår uppskattning av den roll som mikrober spelar i biogeokemiska processer bara växer, blir vi alltmer begränsade av vår förmåga att analysera data. Till exempel genererar Earth Microbiome Project petabyte av sekvensdata från komplexa mikrobiella samhällen, av vilka många innehåller helt nya ensembler av mikrober; skalning de novo-montering är ett kritiskt krav i denna undersökning [31]. Den probabilistiska de Bruijn graf representation presenteras här har ett antal praktiska funktioner för att lagra och analysera stora montering grafer. För det första är det effektivt och komprimerat: för en given datamängd kan ett brett spektrum av falska positiva värden väljas utan att den globala strukturen påverkas, vilket gör det möjligt att lagra grafen i så lite som 4 bitar per k-mer. Eftersom en högre falsk positiv hastighet ger en mer detaljerad lokal struktur, kan minnet handlas för traversal tid i t.ex. partitionerar. För det andra är det en fast minnesdatastruktur, med förutsägbar nedbrytning av både lokal och global struktur i takt med att fler data infogas. För datamängder där antalet unika k-mers inte är känt i förväg, kan beläggningen av Bloom-filtret övervakas eftersom data infogas och direkt omvandlas till en förväntad falsk positiv hastighet. För det tredje, minnesanvändningen är oberoende av den k-mer storlek som valts, vilket gör denna representation bekväm för att utforska egenskaper på många olika parametrar. Det tillåter också lagring och traversal av de Bruijn grafer på flera kmer storlekar inom en enda struktur, även om vi ännu inte har utforskat dessa egenskaper. Och för det fjärde, det stöder minneseffektiv partitionering, ett tillvägagångssätt som utnyttjar underliggande biologiska funktioner i data för att dela upp datauppsättningen i frånkopplade undergrupper. Vår ursprungliga motivation för att utveckla denna användning av Bloom filter var att utforska partitionering som ett sätt att skala metagenome montering, men det finns många ytterligare användningsområden bortom metagenomik. Här beskriver vi exakt partitionering av grafen i komponenter, men inexakt partitionering har framgångsrikt tillämpats på mRNAseq montering [25]. Inexakt partitionering, som görs av Chrysalis-komponenten i treenighetsledningen, använder heuristik för att dela upp grafen för senare sammansättning; den datastruktur som beskrivs i detta arbete kan också användas för detta ändamål. Mer allmänt öppnar en mer minneseffektiv de Bruijn graf representation upp många ytterligare möjligheter. Medan de Bruijn graf metoder för närvarande används främst för montering, de är en allmänt användbar formalism för sekvensanalys. I synnerhet har de utvidgats till effektiv multisekvensjustering, upprepad upptäckt och upptäckt av lokala och strukturella sekvensvariationer [29, 32, 33, 34]. Vi undersöker vidare användningen av probabilistic de Bruijn-grafer för grafbaserad felkorrigering, grafbaserad homologisökning och grafbaserad artefaktdetektering i stora sekvensdatauppsättningar. Den metod som används vid partitionering, där vi använder egenskaper mätt i de Bruijn grafen för att välja och extrahera enskilda avläsningar baserat på t.ex.. lokal graf konnektivitet eller sekvens identiy, kan generalisera till en mängd olika problem. Genom- och sekvensdata. Vi använde E. coli K-12 MG1655 genomet (GenBank: U00096.2) och två MG1655 Illumina dataset (Kort Read Archive Anslutningar SRX000429 och SRX000430) för E. coli analyser. Markdatauppsättningen för MSB2 finns som SRA-anslutning SRA050710.1. Genomförande av datastruktur. Vi implementerade en variation på Bloom-filtrets datastruktur för att lagra k-mers i minnet. I ett klassiskt Bloom filter, flera hash funktioner karta bitar i en enda hash tabell för att lägga till ett objekt eller test för närvaron av ett objekt i uppsättningen. I vår variant, använder vi flera prime-numerary-sized hash tabeller, var och en med en annan hash funktion som motsvarar modulen av DNA bitstring representation med hash tabellen storlek; detta är ett beräkningsmässigt bekvämt sätt att konstruera hash funktioner för DNA-strängar. Egenskaperna hos denna implementation är identiska med ett klassiskt Bloom-filter [35]. Uppskattning av falskt positivt värde för erronous Connectivity. Vi körde en simulering för att hitta när komponenter i grafen felaktigt börjar ansluta till varandra. För att beräkna den falska positiva hastigheten p vid vilken denna avvikande konnektivitet inträffar, lade vi till slumpmässiga k-mers, provtagna från en enhetlig GC-fördelning, till datastrukturen och beräknade sedan beläggningen och storleken på den största komponenten.  där RSSi är restsumman av kvadrater för modell i, pi är antalet parametrar för modell i, och n är antalet datapunkter. För att hantera provtagningsfelet i ändlig storlek sopades uppgifterna in med hjälp av metoden med tröskelbinning [36]. Det kritiska värdet för när avvikande konnektivitet uppstod fastställdes genom att bestämma den lokala maximan för F-värdena [37]. Grafpartitionering med hjälp av ett Bloom Filter. Vi använde Bloom filterdatastrukturen som innehåller k-mers från en datauppsättning för att upptäcka komponenter i grafen, dvs.. för att partitionera grafen. Här är en komponent en uppsättning k-mers vars ursprung läser överlappa transitivt med minst k - 1 baspar. Läser som endast hör till små komponenter kan upptäckas och elimineras i fast minne med hjälp av en enkel traversal algoritm som trunkerar efter att ha upptäckt mer än ett givet antal nya k-mers. För att upptäcka stora komponenter märker vi grafen med en minimal densitet genom att använda den underliggande avläsningen som en guide. Vi utforskar sedan utförligt grafen runt dessa taggar för att ansluta taggade k-mers baserat på grafanslutning. De underliggande avläsningarna i varje komponent kan sedan separeras baserat på deras partition. Vi använde ABySS v1.3.1 och Velvet v1.1.07 för att utföra monteringar. AByss-kommandot var: mpirun -np 8 ABYSS-P -k31 -o contigs.fa reads.fa. Velvets kommandon var: sammetslent assem 31 -fasta -kort reads.fa & & & sammetg assem. Vi använde inte Velvet för partitioneringsanalysen eftersom Velvets felkorrigeringsalgoritm är stokastisk och resulterar i olika sammansättningar för olika läsordningar. Tillgång till programvara och programvara. Vi har implementerat denna komprimerade graf representation och tillhörande partitionering algoritm i ett programpaket som heter khmer. Den är skriven i C++ och Python 2.6 och finns tillgänglig under BSD open source-licensen på https://github.com/ged-lab/khmer. Programvaran grafviz paket användes för grafvisualiseringar. Manusen för att generera siffrorna i det här pappret finns i khmerarkivet. Vi tackar Chris Adami, Qingpeng Zhang och Tracy Teal för genomtänkta kommentarer och Jim Cole och Jordan Fish för diskussioner om framtida tillämpningar. Dessutom tackar vi tre anonyma granskare för deras kommentarer, som avsevärt förbättrade dokumentet.
Pell m.fl. REF presenterade en ny datapartitioneringsmetod, där huvuddatastrukturen - en probabilistisk modell som kallas blomfilter - användes för att få en kompakt representation för grafer.