Kraken: ultrafast metagenomisk sekvensklassifisering ved hjelp av eksakte justeringer

Sekvensklassifiseringsalgoritme

for å klassifisere EN DNA-sekvens s samler vi alle k-mere innenfor den sekvensen i et sett, betegnet Som K (S). Vi kartlegger deretter hver k-mer I K (S), ved hjelp av algoritmen beskrevet nedenfor, TIL LCA-taxonet av alle genomene som inneholder den k-mer. DISSE LCA taxa og deres forfedre i taksonomitreet danner det vi kaller klassifiseringstreet, et beskåret subtre som brukes Til å klassifisere S. Hver node i klassifiseringstreet er vektet med antall k-mers I K (S) som kartlagt til taxon forbundet med den noden. DERETTER blir hver ROT-til-blad-bane (RTL) i klassifiseringstreet scoret ved å beregne summen av alle nodevekter langs banen. Maksimal scoring RTL-bane i klassifikasjonstreet er klassifikasjonsbanen, Og S er tildelt etiketten som svarer til bladet (hvis det er flere maksimalt scoring-baner, er LCA av alle disse banenes blader valgt). Denne algoritmen, illustrert I Figur 1, tillater Kraken å vurdere hver k-mer i en sekvens som et eget bevis, og deretter forsøke å løse eventuelle motstridende bevis om nødvendig. Merk at for et passende valg av k, de fleste k-mers vil kartlegge unikt til en enkelt art, i stor grad forenkle klassifiseringsprosessen. Sekvenser som ingen av k-mers i K (S) er funnet i noen genom er igjen uklassifisert av denne algoritmen.

BRUK AV RTL – baneskår i klassifikasjonstreet er nødvendig i lys av de uunngåelige forskjellene mellom sekvensene som skal klassifiseres og sekvensene som er tilstede i et hvilket som helst bibliotek av genomer. Slike forskjeller kan, selv for store verdier av k, resultere i en k-mer som er til stede i biblioteket, men forbundet med en art fjernt fra den sanne kilde arter. Ved å score DE FORSKJELLIGE RTL-banene i klassifikasjonstreet, kan vi kompensere for disse forskjellene og korrekt klassifisere sekvenser selv når et lite mindretall av k-mers i en sekvens indikerer at sekvensen skal tilordnes en feil taksonomisk etikett.

Database creation

Effektiv implementering Av Kraken klassifisering algoritme krever at kartlegging av k-mers til taxa utføres ved å spørre en pre-beregnet database. Kraken skaper denne databasen gjennom en flertrinnsprosess, som begynner med valg av et bibliotek med genomiske sekvenser. Kraken inneholder et standardbibliotek, basert på fullførte mikrobielle genomer I National Center For Biotechnology Information (NCBI) RefSeq database, men biblioteket kan tilpasses etter behov av individuelle brukere .

når biblioteket er valgt, bruker vi Maneter multithreaded k-mer counter for å lage en database som inneholder hver distinkt 31-mer i biblioteket. Når databasen er fullført, er 4-byte mellomrom Maneter brukes til å lagre k-mer teller i databasefilen i stedet brukes Av Kraken å lagre taksonomiske ID-numre av k-mers ‘ lca verdier. Etter at databasen er opprettet Av Maneter, behandles de genomiske sekvensene i biblioteket en om gangen. For hver sekvens brukes taxonet som er knyttet til det, til å angi de lagrede lca-verdiene for alle k-mere i sekvensen. Når sekvenser behandles, hvis en k-mer fra en sekvens har hatt SIN LCA-verdi tidligere angitt, beregnes LCA av den lagrede verdien og den nåværende sekvensens taxon, OG AT LCA er lagret for k-mer. Taxon informasjon er hentet fra NCBI taksonomi database.

Databasestruktur og søkealgoritme

Fordi Kraken ofte bruker en k-mer som en databasespørring umiddelbart etter spørring av en tilstøtende k-mer, og fordi tilstøtende k-mere deler en betydelig mengde sekvens, bruker vi minimizer-konseptet til å gruppere lignende k-mere sammen. For å forklare vår anvendelse av dette konseptet, vi her definerer den kanoniske representasjon AV EN DNA-sekvens S som leksikografisk mindre Av S og omvendt komplement Av S. For å bestemme en k-mers minimizer av lengde M, vurderer vi den kanoniske representasjonen av alle M-mers i k-mer, og velger den leksikografiske minste av Disse M-mers som k-mers minimizer. I praksis vil tilstøtende k-mers ofte ha samme minimizer.

I Krakens database lagres alle k-mere med samme minimizer fortløpende, og sorteres i leksikografisk rekkefølge av deres kanoniske representasjoner. En spørring for en k-mer R kan deretter behandles ved å slå opp i en indeks posisjonene i databasen der k-mers med R minimizer vil bli lagret, og deretter utføre et binært søk i den regionen (Figur 5). Fordi tilstøtende k-mere ofte har samme minimizer, er søkeområdet ofte det samme mellom to påfølgende spørringer, og søket i den første spørringen kan ofte bringe data inn I CPU-hurtigbufferen som skal brukes i den andre spørringen. Ved å tillate minnetilgang i etterfølgende spørringer for å få tilgang til data i CPU-bufferen i stedet FOR RAM, gjør denne strategien etterfølgende spørringer mye raskere enn de ellers ville være. Indeksen som inneholder forskyvningene til hver gruppe k-mere i databasen krever 8 × 4m byte. Som standard Kraken bruker 15-bp minimizers, men brukeren kan endre denne verdien; for eksempel, i å lage MiniKraken, vi brukte 13-bp minimizers for å sikre den totale databasestørrelsen bodde under 4 GB.

Kraken database struktur. Hver k-mer som skal spørres mot databasen har en bestemt substring som er dens minimizer. For å søke etter en k-mer i databasen, undersøkes posisjonene i databasen som inneholder k-mers med samme minimizer. Disse posisjonene er raskt funnet ved å undersøke minimizer offset array for startposisjoner poster med k-mer minimizer (oransje) og neste mulige minimizer (blå). Innenfor en rekke poster knyttet til en gitt minimizer, er postene sortert etter leksikografisk bestilling av deres k-mers, slik at en spørring kan fullføres ved å bruke et binært søk over dette området.

ved implementering Av Kraken gjorde vi ytterligere optimaliseringer til strukturen og søkealgoritmen beskrevet ovenfor. Først, som nevnt Av Roberts et al. , en enkel leksikografisk bestilling Av M-mers kan resultere i en skjev fordeling av minimizers som over-representerer lav kompleksitet M-mers. I Kraken ville en slik bias skape mange store søkeområder, noe som ville kreve mer tid til å søke. For å skape en jevnere fordeling av minimisatorer (og dermed øke søkene), bruker vi den eksklusive-eller (XOR) operasjonen for å bytte halvparten av bitene til Hver M-mers kanoniske representasjon før vi sammenligner M-mers med hverandre ved hjelp av leksikografisk bestilling. DETTE xor operasjonen effektivt forvrenger standard bestilling, og hindrer den store skjevhet mot lav kompleksitet minimizers.

vi utnytter også det faktum at søkeområdet ofte er det samme mellom spørringer for å gjøre Krakens spørringer raskere. I stedet for å beregne minimisatoren hver gang vi utfører en spørring, søker vi først i forrige område. Hvis vår spørres k-mer er funnet i dette området, kan spørringen returnere umiddelbart. Hvis k-mer ikke er funnet, da minimizer beregnes; hvis k-mer minimizer er den samme som den siste spørres k-mer, så spørringen mislykkes, som minimizer søk plass har vist seg ikke å ha k-mer. Bare hvis minimizer har endret Seg, Må Kraken justere søkeområdet og søke igjen for k-mer.

Konstruere simulerte metagenomer

HiSeq og MiSeq metagenomer ble bygget ved hjelp av 20 sett med bakterielle helgenom hagle leser. Disse leser ble funnet enten som en del AV GAGE-b prosjektet eller I NCBI Sekvens Lese Arkivet. Hver metagenome inneholder sekvenser fra ti genomer (Tilleggsfil 1: Tabell S1). For både 10.000 og 10 millioner leste prøver av hver av disse metagenomene ble 10% av deres sekvenser valgt fra hvert av de ti komponentgenomdatasettene (dvs.hvert genom hadde lik sekvensoverflod). Alle sekvenser ble trimmet for å fjerne lav kvalitet baser og adapter sekvenser.

sammensetningen av disse to metagenomene utgjør visse utfordringer for våre klassifikatorer. For Eksempel Kan Pelosinus fermentans, funnet i Vår HiSeq metagenome, ikke bli riktig identifisert på slektsnivå Av Kraken (eller noen av de andre tidligere beskrevne klassifiseringene), fordi Det ikke finnes Noen Pelosinus genomer i RefSeq complete genomes database; det er imidlertid syv slike genomer i kraken-GBS database, inkludert seks stammer Av p. fermentans. På samme måte, I Vårt MiSeq metagenome, Blir Proteus vulgaris ofte klassifisert feil på slektsnivå fordi Det eneste Proteus-genomet i Krakens database er et Enkelt Proteus mirabilis-genom. Fem Proteus-genomer er til stede i kraken-GBS database, slik At Kraken-GB kan klassifisere leser bedre fra det slaget. I Tillegg Inneholder MiSeq metagenomet fem genomer Fra Familien Enterobacteriaceae (Citrobacter, Enterobacter, Klebsiella, Proteus Og Salmonella). Den høye sekvens likheten mellom slægten i denne familien kan gjøre skille mellom slægter vanskelig for enhver klassifikator.

simBA-5 metagenomet ble opprettet ved å simulere leser fra settet av komplette bakterielle og archaeal genomer I RefSeq. Replikoner fra disse genomene ble brukt hvis de var assosiert med et taxon som hadde en oppføring knyttet til slektsrangen, noe som resulterte i et sett med replikoner fra 607 slekter. Vi brukte Mason les simulator Med Sin Illumina modell for å produsere 10 millioner 100-bp leser fra disse genomene. Først opprettet vi simulerte genomer for hver art, ved hjelp AV EN SNP-hastighet på 0,1% og en indel-hastighet på 0,1% (begge standardparametrene), hvorfra vi genererte lesene. For de simulerte lesingene multipliserte vi standard mismatch og indel-ratene med fem, noe som resulterte i en gjennomsnittlig mismatchrate på 2% (fra 1% i begynnelsen av leser til 6% i endene) og en indelrate på 1% (0,5% innsettingssannsynlighet og 0,5% slettingssannsynlighet). For simBA – 5 metagenome ble 10.000 lesesett generert fra et tilfeldig utvalg av 10 millioner lesesett.

Evaluering av nøyaktighet og hastighet

vi valgte å måle nøyaktighet primært på slektsnivå, som var det laveste nivået som vi enkelt kunne bestemme taksonomiinformasjonen for PhymmBL og NBCS spådommer på en automatisert måte. (Dette skyldes måten PhymmBL og NBC rapporterer sine resultater på). Fordi noen genomer ikke har taksonomiske oppføringer i alle syv ledd (arter, slekt, familie, orden, klasse, rekke og rike), definerte vi slektsnivåfølsomhet som A/B, Hvor A er antall leser med en tildelt slekt som ble riktig klassifisert på den rangen, og B er det totale antall leser med noen tildelt slekt. Vi definerte følsomhet på samme måte for andre taksonomiske ranger.

Fordi Kraken kan klassifisere en lesning på nivåer over arten, må måling av presisjonen kreve at vi definerer effekten på presisjonen av å tildele riktig slekt (for eksempel) mens vi ikke tilordner en art i det hele tatt. Av denne grunn definerte vi rangnivåpresisjon Som C/(D + E), Hvor C er antall leser merket på eller under riktig takson ved den målte rang, D er antall leser merket på eller under den målte rang, Og E er antall leser feil merket over den målte rang. For eksempel, gitt en les R som skal merkes Som Escherichia coli, vil en merking Av R Som E. coli, e. fergusonii eller Escherichia forbedre genusnivå presisjon. En etikett Av Enterobacteriaceae (riktig familie) eller Proteobacteria (riktig rekke) ville ikke ha noen effekt på genusnivå presisjon. En etikett For R Av Bacillus (feil slekt) eller Firmicutes (feil rekke) vil redusere genusnivå presisjon.

når Vi evaluerte Phymmbls nøyaktighet , fulgte utviklerens råd, valgte vi en genus confidence terskel for våre sammenligninger. Vi valgte 3,333 leser fra datasettet simulated medium complexity (simMC), som dekker 31 forskjellige slekter. For å simulere korte leser fra Sanger-sekvensdataene i simMC-settet valgte vi de siste 100 bp fra hver av lesene. Vi kjørte PhymmBL mot de 100-bp leser, og evaluerte genus-nivå følsomhet Og presisjon Av PhymmBL spådommer med slekt tillit terskler fra 0 til 1, i trinn på 0.05. Vi fant at en terskel på 0,65 ga den høyeste f-poengsummen (det harmoniske gjennomsnittet av følsomhet og presisjon), med 0,60 og 0,70 som Også har F-score innen 0.5 prosentpoeng av maksimum (Tilleggsfil 1: Tabell S2). Vi brukte derfor 0.65 genus confidence terskel i våre sammenligninger. Selv om valget av en terskel avhenger av brukerens individuelle behov, og det er til en viss grad vilkårlig, gir en terskel valgt på denne måten en mer riktig sammenligning med en selektiv klassifiserer som Kraken enn ingen terskel i det hele tatt.

tids-og nøyaktighetsresultatene ved Bruk Av Megablast som klassifikator ble oppnådd fra loggdataene produsert Av PhymmBL, da PhymmBL bruker Megablast for justeringstrinnet. Ved tildeling av en taksonomisk etikett til en les med Megablast, brukte vi taxonet knyttet til den første rapporterte justeringen. Megablast ble kjørt med standardalternativer.

Hastigheten ble evaluert ved hjelp av enkelttrådet drift av hvert program (unntatt NBC). PhymmBL ble endret slik at kallet til blastn-programmet brukte en tråd i stedet for to. NBC ble kjørt med 36 samtidige prosesser som opererer på disjoint sett av genomer i sin genomisk bibliotek, og den totale tiden for klassifikatoren ble bestemt ved å summere dekompresjon og scoring ganger for hvert genom. Veggur ganger ble registrert for alle klassifiserere. Ved å sammenligne Kraken med de andre klassifiseringene brukte VI BLAST + 2.2.27, PhymmBL 4.0, NBC 1.1 og MetaPhlAn 1.7.6. Klassifikatorer ble alle kjørt på samme datamaskin, med 48 AMD Opteron 6172 2.1 GHz Cpuer og 252 GB RAM, som kjører Red Hat Enterprise Linux 5. Datasettene som ble brukt til hastighetsevaluering hadde 10.000 leser hver for alle andre programmer enn Kraken (og dens varianter) og MetaPhlAn, som brukte 10.000.000 lese datasett. Høyere lesetall ble brukt med disse raskere programmene for å minimere effekten av de første og endelige operasjonene som finner sted under programmets utførelse.

Selv Om Kraken er den eneste av programmene vi undersøkte som eksplisitt utfører operasjoner for å sikre at dataene er i fysisk minne før klassifisering, ønsket Vi å være sikre på at alle programmer ble evaluert på en lignende måte. Når vi vurderer hastighet, leser vi for hvert program alle databasefiler (f. eks. Imm filer OG BLAST databaser For PhymmBL, k-mer frekvenslister FOR NBC og Bowtie index For MetaPhlAn) i minnet tre ganger før du kjører programmet, for å plassere databaseinnholdet i operativsystemet cache (som er lagret i fysisk minne).

Reduserte databasestørrelser

for å generere 4 GB-databasen for Våre MiniKraken-resultater fjernet vi de første 18 av hver blokk med 19 poster i Standard Kraken-databasen. En krympende faktor på 19 ble valgt som det var den minste heltallsfaktoren som ville redusere størrelsen til mindre enn 4 GB, en størrelse som lett kan passe inn i minnet til mange vanlige personlige datamaskiner. For brukere som har MER RAM tilgjengelig, Tillater Kraken en mindre krympende faktor som skal brukes, noe som vil gi økt følsomhet.

Bruk av utkastgenomer

ved konstruksjon Av Kraken-GB-databasen la vi merke til at det var flere kontigs med kjente adaptersekvenser i enden. I etterfølgende tester fant vi også at noen sekvenser i prøver med store mengder menneskelig sekvens ble konsekvent feilklassifisert av denne databasen, noe som førte oss til å konkludere med at forurensning sannsynligvis var tilstede i utkastet til genomene. I et forsøk på å motvirke denne forurensningen fjernet vi fra databasen de k-mers fra kjente adaptersekvenser, samt de første og siste 20 k-mers fra hver av utkastskontigs. Selv om dette gjorde bedre klassifisering, det gjorde ikke eliminere feilklassifisering problemet. Av denne grunn tror vi at hvis utkast til genomer brukes i En Kraken-database, bør det brukes svært strenge tiltak for å fjerne forurensningssekvenser fra genombiblioteket.

clade exclusion experiments

når re-analysere simBA-5 datasett for våre clade exclusion experiments, noen leser ble ikke brukt for visse par av målte og ekskluderte rekkene. Hvis en leses opprinnelse manglet en taksonomisk oppføring på en av de målte eller ekskluderte rekkene, ble den ikke brukt til det aktuelle eksperimentet.

i tillegg ble en lesning ikke brukt i et eksperiment med mindre minst to andre taxa representert i vår database (bortsett fra den ekskluderte kladen) ved den ekskluderte rangen delte opprinnelseskladens takson ved den målte rangen. For eksempel ville en lese fra slekt G ikke bli brukt i et eksperiment som måler nøyaktighet ved klasserangeringen og unntatt slektsklassen, med mindre Gs hjemmeklasse hadde minst to andre slekter med genomer i Kraken ‘ s genomiske bibliotek. Uten dette filtreringstrinnet, ble en slekt ekskludert da Den var den eneste slekten i sin klasse, Kunne Kraken ikke muligens nevne den riktige klassen, da alle oppføringer i databasen fra den klassen også ville bli utelukket. Dette er den samme tilnærmingen tatt i lignende eksperimenter som ble brukt til å evaluere PhymmBL .

human microbiome data classification

Vi klassifiserte Human Microbiome Project data ved Hjelp Av En Kraken database laget av komplette RefSeq bakterielle, archaeal og virale genomer, sammen Med GRCh37 human genome. Vi hentet sekvensene av tre tiltredelser (SRS019120, SRS014468 og SRS015055) fra NCBI Sequence Read Archive, og hver tiltredelse hadde to løp sendt inn. Alle leser ble trimmet for å fjerne lav kvalitet baser og adapter sekvenser. Krona ble brukt til a generere alle taksonomiske distribusjonsplott.

fordi sekvensene var alle sammenkoblede leser, kom vi sammen med lesene sammen ved å sammenkoble kameratene med en sekvens AV ‘NNNNN’ mellom dem. Kraken ignorerer k-mers med tvetydige nukleotider, så k-mers som spenner over Disse ‘ N ‘ tegnene, påvirker ikke klassifiseringen. Denne operasjonen tillot Kraken å klassifisere et par leser som en enkelt enhet i stedet for å klassifisere kameratene separat.

Programvare og datatilgjengelighet