BWA (Biological Sequence Alignment)

BWA
Sorts bioinformatik
Författare Heng Lee , Richard Durbin
Skrivet i C++
Operativ system UNIX , Linux
senaste versionen 0.7.17 (r1140) [1] (07.11.2017)
Licens GNU GPL , MIT-licens
Hemsida bio-bwa.sourceforge.net

BWA  ( Burrows-Wheeler A ligner )  är ett mjukvarupaket för kartläggning av korta läsningar till stora referensgenom (som till exempel det mänskliga genomet [2] ), skrivet av den kinesiske bioinformatikern Heng Li och engelsmannen Richard Durbin . Det är en av de allmänt använda anpassningsalgoritmerna [3] [4] [5] och rekommenderas även för dataanalys av Illumina [6] . BWA består av tre huvudalgoritmer: BWA-BackTrack, BWA-SW och BWA-MEM. BWA-algoritmerna är baserade på Burrows-Wheeler-transformen , suffixarrayer och Smith-Waterman-justeringsalgoritmen . Mjukvarupaketet kan arbeta med långa sekvenser en storleksordning snabbare än MAQ ( Mapping and Assembly with Qualities ) samtidigt som det uppnår en liknande inriktningsnoggrannhet [7] . 

För prover från Illumina-SOLEXA-plattformar , 454 Life Sciences , jon-halvledarsekvensering eller Sanger-sekvensering med en längd av avläsningar ("reads" från engelska  reading  - "reading, reading"; individuella DNA-fragment erhållna som ett resultat av sekvenseraren ) är större än eller lika med 70 baspar (hädanefter - b.p.), är BWA-MEM vanligtvis att föredra. BWA-MEM och BWA-SW har liknande funktioner som stöd för långa läsningar. BWA-MEM har bättre prestanda än BWA-BackTrack för 70-100 bp läsningar. från Illumina-SOLEXA-plattformen.

Oavsett den valda algoritmen måste BWA-mjukvarupaketet först bygga ett FM-index för referensgenomet. Följande kommando används för att skapa ett index: bwa index [-p prefix] [-a algoType] <in.db.fasta>. Vidare appliceras inriktningsalgoritmer på mottagna data, som anropas av olika underkommandon: aln/samse/sampeför BWA-BackTrack, bwaswför BWA-SW och memför BWA-MEM [8] .

Historik

Heng Lee, en forskare vid Cambridge Broad Institute [9] , började skriva den första delen av koden den 24 maj 2008 och fick den initiala stabila versionen redan den 2 juni samma år. Under samma period samarbetade Prof. Tak-Wah Lam, den första författaren till BWT-SW-artikeln [10] , med Beijing Genomic Institute om SOAP2, efterföljaren till SOAP (kortsekvensoligonukleotidanalyspaket). SOAP2 släpptes i november 2008.

BWA-SW-algoritmen är en ny komponent i BWA. Det skapades i november 2008 och implementerades tio månader senare. Från och med 2015 ansågs BWA-MEM (0.7.10) vara mer att föredra att använda för snipsökning än bowtie (2-2.2.25) eller Novoalign (3.02.12) [11] .

Användning

BWA-mjukvarupaketet kan användas inom områden som genotypning för att söka efter singelnukleotidpolymorfismer (snip) [12] . Genotypning möjliggör individuell jämförelse av olika människors genotyper, den kan användas för att förutsäga människors anlag för olika sjukdomar, som till exempel cancer, diabetes och många andra. Paketet kommer också att vara användbart i transkriptomik [13] .

Från och med version 0.6.x kan alla algoritmer arbeta med genom vars totala längd överstiger 4 GB [8] . Storleken på en enskild kromosom får dock inte överstiga 2 GB. Varje algoritm anropas av ett separat kommando, som accepterar en indatafil via standardinmatning ("stdin") och returnerar resultatet via standardutgång ("stdout").

BWA-BackTrack

Först byggs en suffixarray och sedan genereras en BWT. Odefinierade nukleotider (betecknade med bokstaven "N") i referensgenomet omvandlas till slumpmässiga nukleotider och behandlas som felparningar i läsningarna. Detta kan leda till områden med falska matchningar ("träffar") med tvetydiga baser. Men sannolikheten att detta kan hända är mycket liten, med tanke på de relativt långa läsningarna [14] .

BWA-SW

BWA-SW bygger FM-index för både referenssekvensen och avläsningarna. Det är implicit en referenssekvens i form av ett prefixträd och en läsning som en deterministisk acyklisk tillståndsmaskin , som är sammansatt av ett prefixträd för läsning med dynamisk programmering . Till skillnad från BLAT och SSAHA2 hittar BWA-SW frön (från engelska  seed  - "seed"; en exakt matchning av flera läsbaspar [4] ) i referensgenomet med hjälp av konstruktionen av FM-index. Inriktningen expanderar när fröet har flera förekomster i referenssekvensen. Hastighet uppnås genom att minska onödig expansion för mycket repetitiva sekvenser. Jämfört med standard Smith-Waterman-utjämningen, som har en tidskomplexitet på , har BWA-SW bättre tidskomplexitet eftersom den är minst lika snabb som BWT-SW, som har en komplexitet på [10] . I BWA-SW anses två anpassningar vara olika om längden på begäranden överlappande zonen är mindre än halva längden av det kortare begäransegmentet.

BWA-SW-implementeringen tar ett BWA-index och en FASTA-fråga eller FASTQ-fil som indata och matar ut justeringen i SAM-format. Indatafilen innehåller som regel många sekvenser ("reads"). Varje sekvens bearbetas i sin tur med flera trådar (om möjligt). Minnesanvändningen när man arbetar med denna algoritm är cirka 5 GB för att indexera kompletta sekvenser av det mänskliga genomet [8] . Korta läsningar kräver cirka 3,2 GB med kommando alnoch 5,4 GB med sampe. Mängden minne som krävs för varje fråga är ungefär proportionell mot sekvensens längd. Dessutom kan BWA-SW upptäcka en chimär som potentiellt kan orsakas av strukturella förändringar eller läsa referensfel som kan utgöra ett hot mot BLAT och SSAHA2. BWA-SW skiljer sig från BWT-SW på flera sätt [15] : BWT-SW garanterar att hitta alla lokala matchningar, medan BWA-SW är en heuristisk algoritm som kan missa sanna matchningar men är mycket snabbare.

BWA-MEM

BWA-MEM är den senaste implementerade algoritmen för BWA-paketet. Den använder en strategi där läsjusteringsalgoritmen väljs automatiskt från fall till fall: lokal eller global anpassning. Pair-end-läsningar och chimära läsjusteringar stöds. Algoritmen är resistent mot sekvenseringsfel och är tillämpbar på ett brett spektrum av sekvenslängder från 70 bp till 70 bp. upp till flera megabaser. Och för kartläggning av sekvenser 100 bp långa. BWA-MEM visar bättre prestanda än vissa avancerade läsjusteringsalgoritmer [16] .

Kvalitetsindikatorer

För varje anpassning beräknar BWA-mjukvarupaketet ett kartläggningskvalitetspoäng - Phred, den skalade sannolikheten för att anpassningen är felaktig [8] ( Phred  quality score​ – en bedömning av kvaliteten på den lästa DNA-nukleotiden). Behovet av en statistisk bedömning av kartläggning uppstår av att avläsningarna är små (40–100 bp), medan genomerna är ganska stora, så det kan finnas flera anpassningar. Det är dock nödvändigt att förstå vilken som är mest informativ. Och i huvudsak är Phred-poängen sannolikheten att läsningen är felinriktad. Den beräknas med formeln , där q är läskvaliteten på avläsningen [17] . Algoritmen liknar utvärderingen för MAQ , förutom att BWA antar att en sann matchning alltid kan hittas. Denna ändring gjordes eftersom MAQ-formeln överskattar sannolikheten för att missa en sann matchning, vilket resulterar i underskattad kartkvalitet. Modellering visar att BWA kan överskatta kvaliteten på kartläggningen på grund av denna modifiering, men avvikelsen är relativt liten.

Exempel

Ett exempelscenario för att använda mjukvarupaketet BWA från Dutch Computing Center är följande [18] :

Steg 1 - genomindexering (~3 CPU-timmar för det mänskliga genomet) bwa index -a bwtsw ref.fa

, där ref.fa är namnet på referensgenomfilen.

Steg 2a - generering av anpassning i suffixarraykoordinater bwa aln ref.fa read1.fq.gz > read1.sai bwa aln ref.fa read2.fq.gz > read2.sai

, där read1.fq.gz är en fil med direkta läsningar, är read2.fq.gz en omvänd läsning. Använd alternativet -q15 om kvaliteten är lägre vid 3'-ändarna av läsningarna.

Steg 3a - generering av justering i SAM-format för parade läsningar bwa sampe ref.fa read1.sai read2.fq.gz > aln.sam Steg 4a - Generera SAM-justering för udda läsningar bwa samse ref.fa read1.sai read1.fq.gz Steg 2b - BWA-SW för långa läsningar bwa bwasw ref.fa long-read.fq.gz > aln-long.sam

, där long-read.fq.gz är en fil med långa läsningar.

För ytterligare kompatibilitet av den resulterande anpassningen med standardprogram för att analysera NGS-data, som till exempel Pikard Tools eller GATK, när du anropar programmet, bör du ange den så kallade läsgruppen ( engelsk  läsgrupp - en uppsättning data som erhålls använda ett läge för sequencern) genom att lägga till flagga -r[19] . Själva läsgruppen för ett prov från Illumina-SOLEXA-plattformen ser ut ungefär så här: -r ‘@RG\tID:1\tSM:S000336\tPL:ILLUMINA\tLB:L00000336\t PU:C3A7NACXX:1’[19] , där ID är en unik identifierare för detta prov, SM är provnamnen, Pl är sekvenseringsplattformen, LB är namnet på bibliotek, och PU är systemidentifieraren [20] .

Praktiskt värde

I praktiken är BWA det huvudsakliga verktyget för att förenkla korta avläsningar [21] [22] [23] [24] . BWA tillämpas för närvarande i följande studier:

De främsta fördelarna med att använda BWA-programvarupaketet är följande fördelar [7] [25] :

Dessutom är BWA en del av de mest använda biologiska pipelines, inte bara inom vetenskaplig verksamhet utan också inom klinisk:

Anteckningar

  1. ↑ Heng Li. BWA Releases  (engelska)  (nedlänk) . GitHub. Hämtad 5 april 2017. Arkiverad från originalet 5 april 2017.
  2. ↑ Goltsov A.Yu., Andreeva T.V., Reshetov D.A., Tyazhelova T.V., Gavrik O.A., Rogaev E.I. Sök efter mutationer i mitokondriella DNA-gener associerade med utvecklingen av Alzheimers sjukdom med hjälp av parallell sekvenseringsteknologi  // Modern problem of science and education: journal. - M . : Russian Academy of Natural Sciences, 2012. - Nr 6 . - S. 23 . — ISSN 1817-6321 . Arkiverad från originalet den 5 april 2017.
  3. ↑ Ivan Borozan, Stuart N. Watt, Vincent Ferretti. Utvärdering av anpassningsalgoritmer för upptäckt och identifiering av patogener med RNA-Seq  // PLoS One: Journal. - 2013. - T. 8 , nr. 10 . — PMID 24204709 .
  4. ↑ 1 2 Li Heng, Homer Nils. En undersökning av sekvensanpassningsalgoritmer för nästa generations sekvensering  // Brief Bioinformatics: journal. - 2010. - September ( vol. 11 , nummer 5 ). - S. 473-483 . - doi : 10.1093/bib/bbq015 . — PMID 20460430 . Arkiverad från originalet den 15 april 2017.
  5. ↑ Jing Shang, Fei Zhu, Wanwipa Vongsangnak, Yifei Tang, Wenyu Zhang, Bairong Shen. Utvärdering och jämförelse av multipla aligners för nästa generations sekvenseringsdataanalys  // Brief Bioinformatics: Journal. - 2010. - September ( vol. 11 , nummer 5 ). - S. 1754-1760 . — PMID 24779008 .
  6. ↑ Stor helgenomsekvensering  . Illumina. Arkiverad från originalet den 30 januari 2016.
  7. ↑ 1 2 Li Heng, Durbin Richard. Snabb och exakt långläst anpassning med Burrows-Wheeler transform  //  Bioinformatics : journal. - Oxford University Press, 2010. - 1 mars ( vol. 26 , iss. 5 ). - S. 589-595 . — ISSN 1367-4803 . - doi : 10.1093/bioinformatics/btp698 . — PMID 20080505 . Arkiverad från originalet den 5 april 2017.
  8. ↑ 1 2 3 4 Manual Reference Pages - bwa  (engelska)  (länk ej tillgänglig) . Souce Forge. Hämtad 5 april 2017. Arkiverad från originalet 5 april 2017.
  9. ↑ Heng Lis hemsida  (engelska)  (länk ej tillgänglig) . sourceforge. Hämtad 6 april 2017. Arkiverad från originalet 6 april 2017.
  10. ↑ 1 2 Lam TW, Sung WK, Tam SL, Wong CK, Yiu SM. Komprimerad indexering och lokal anpassning av DNA  (engelska)  // Bioinformatics : journal. - Oxford University Press, 2008. - 15 mars ( vol. 24 , iss. 6 ). - s. 791-797 . — ISSN 1367-4803 . - doi : 10.1093/bioinformatics/btn032 . — PMID 18227115 . Arkiverad från originalet den 5 april 2017.
  11. ↑ Sohyun Hwang, Eiru Kim, Insuk Lee, Edward M. Marcotteb. Systematisk jämförelse av pipelines för variantanrop med hjälp av personliga exomvarianter i guldstandard  //  Scientific Reports : online journal. - Macmillan Publishers Limited, 2015. - Iss. 5 . — ISSN 2045-2322 . - doi : 10.1038/srep17875 . Arkiverad från originalet den 5 april 2017.
  12. ↑ Pareek CS, Błaszczyk P., Dziuba P., Czarnik U., Fraser L., Sobiech P., Pierzchała M., Feng Y., Kadarmideen HN, Kumar D. Upptäckt av singelnukleotidpolymorfism i bovin lever med hjälp av RNA-seq-teknologi  // PLoS One : log. - 2017. - Februari ( vol. 12 , nummer 2 ). - doi : 10.1371/journal.pone.0172687 . — PMID 28234981 . Arkiverad från originalet den 15 april 2017.
  13. ↑ Robinson KM, Crabtree J., Mattick JS, Anderson KE, Dunning Hotopp JC Att skilja potentiella bakterie-tumörassociationer från kontaminering i en sekundär dataanalys av offentliga cancergenomsekvensdata  // Microbiome: journal. - London, Storbritannien: BioMed Central, 2017. - Januari ( vol. 5 , nummer 1 ). — ISSN 2049-2618 . — PMID 28118849 . Arkiverad från originalet den 5 april 2017.
  14. ↑ Li Heng, Durbin Richard. Snabb och exakt kortläsningsjustering med Burrows-Wheeler transform  //  Bioinformatics: journal. - Oxford University Press, 2009. - 15 juli ( vol. 25 , iss. 14 ). - P. 1754-1760 . — ISSN 1367-4803 . - doi : 10.1093/bioinformatics/btp324 . — PMID 19451168 . Arkiverad från originalet den 5 april 2017.
  15. ↑ Al-Absi AA, Kang DK Long Read Alignment with Parallel MapReduce Cloud Platform  // BioMed Research International: Journal. - Egypten: Hindawi , 2015. - December. — ISSN 2314-6133 . - doi : 10.1155/2015/807407 . — PMID 26839887 . Arkiverad från originalet den 5 april 2017.
  16. ↑ Li Heng. Justering av sekvensläsningar, klonsekvenser och sammansättning sammanhänger med  BWAMEM . - Cambridge, USA: Oxford University Press, 2016. - 16 mars. - S. 1-3 . - arXiv : 1303.3997 . Arkiverad från originalet den 5 april 2017.
  17. ↑ Peter JA Cock, Christopher J. Fields, Naohisa Goto, Michael L. Heuer, Peter M, Rice. Filformatet Sanger FASTQ för sekvenser med kvalitetspoäng och Solexa/Illumina FASTQ-varianter  //  Nuclear Acid Res : Journal. - 2010. - April ( vol. 38 , utg. 6 ). - P. 1767-1771 . - doi : 10.1093/nar/gkp1137 . — PMID 20015970 . Arkiverad från originalet den 15 april 2017.
  18. ↑ BWA-användning  (engelska)  (länk ej tillgänglig) . Dutch Computing Center. Arkiverad från originalet den 5 april 2017.
  19. ↑ 1 2 Bukowski Robert, Sun Qi, Wang Minghui. Variantanrop . - Bioinformatikanläggning, Institutet för bioteknik. - S. 22 . Arkiverad från originalet den 6 april 2017.
  20. ↑ Arbetsgruppen för SAM/BAM-formatspecifikation. Sequence Alignment/Map Format Specification  (eng.)  (död länk) s. 3. GitHub (28 april 2016). Hämtad 6 april 2017. Arkiverad från originalet 6 april 2017.
  21. ↑ José M. Abuín, Juan C. Pichel, Tomás F. Pena, Jorge Amigo. SparkBWA: Speeding Up the Alignment of High-Throughput DNA Sequencing Data  //  PLoS One: Journal. - 2016. - Vol. 11 , iss. 5 . - doi : 10.1371/journal.pone.0155461 . Arkiverad från originalet den 5 april 2017.
  22. ↑ Justin Chu, Sara Sadeghi, Anthony Raymond, Shaun D. Jackman, Ka Ming Nip, Richard Mar, Hamid Mohamadi, Yaron S. Butterfield, A. Gordon Robertson, Inanç Birol. BioBloom-verktyg: snabb, exakt och minneseffektiv sekvensscreening av värdarter med hjälp av blomfilter  //  Bioinformatics : journal. - 2014. - 1 december ( vol. 30 , utg. 23 ). - P. 3402-3404 . - doi : 10.1093/bioinformatics/btu558 . Arkiverad från originalet den 15 april 2017.
  23. ↑ David Weese, Manuel Holtgrewe, Knut Reinert. RazerS 3: Snabbare, fullt känslig läsmapping  //  Bioinformatics: journal. - Oxford University Press, 2012. - 15 oktober ( vol. 28 , iss. 20 ). - P. 2592-2599 . — ISSN 1367-4803 . - doi : 10.1093/bioinformatics/bts505 . — PMID 22923295 . Arkiverad från originalet den 6 april 2017.
  24. ↑ Barh Debmalya, Khan Muhammad Sarwar, Davies Eric. PlantOmics: The Omics of Plant Science . - Springer, 2015. - S. 56. - 825 sid. — ISBN 8132221729 . — ISBN 9788132221722 . Arkiverad 6 april 2017 på Wayback Machine
  25. ↑ Julio Saez-Rodriguez, Miguel P. Rocha, Florentino Fdez-Riverola, Juan F. De Paz Santana. 8:e internationella konferensen om praktiska tillämpningar av beräkningsbiologi och bioinformatik (PACBB 2014) . - Springer, 2014. - T. 294. - S. 114. - 294 sid. — ISBN 3319075810 . — ISBN 9783319075815 . Arkiverad 6 april 2017 på Wayback Machine
  26. ↑ Gerton Lunter. Anteckningar för Stampy v1.0.20  (engelska)  (nedlänk) . Oxford , Storbritannien : Trust Center for Human Genetics (september 2012). Hämtad 6 april 2017. Arkiverad från originalet 6 april 2017.
  27. ↑ Elsensohn MH., Leblay N., Dimassi S., Campan-Fournier A., ​​​​Labalme A., Roucher-Boulez F., Sanlaville D., Lesca G., Bardel C., Roy P. Statistisk metod för att jämföra massiva parallella sekvenseringspipelines  (engelska)  // BMC Bioinformatics : journal. - London, Storbritannien: BioMed Central, 2017. - 1 mars ( vol. 18 , utg. 1 ). — S. 139 . — ISSN 1471-2105 . - doi : 10.1186/s12859-017-1552-9 . Arkiverad från originalet den 5 april 2017.
  28. ↑ GATK Best Practices  (engelska)  (länk ej tillgänglig) . Breda Institutet. Hämtad 5 april 2017. Arkiverad från originalet 5 april 2017.
  29. ↑ Pevsner Jonathan. Bioinformatik och funktionell genomik . - 3:e uppl. - John Wiley & Sons, 2015. - S. 401. - 1160 sid. — ISBN 9781118581698 . — ISBN 1118581695 . Arkiverad 6 april 2017 på Wayback Machine
  30. ↑ Ishii K., Kazama Y., Hirano T., Hamada M., Ono Y., Yamada M., Abe T. AMAP: En pipeline för detektion av helgenommutationer i Arabidopsis thaliana  //  Genes Genet Syst : magazine. - The Genetics Society of Japan, 2017. - 17 mars ( vol. 91 , iss. 4 ). - S. 229-233 . — ISSN 1341-7568 . - doi : 10.1266/ggs.15-00078 . — PMID 27452041 . Arkiverad från originalet den 5 april 2017.
  31. ↑ SPAdes 3.10.1 Manual  (eng.)  (ej tillgänglig länk) . St. Petersburg Academic University är ett vetenskapligt och pedagogiskt centrum för nanoteknik vid Ryska vetenskapsakademin . Hämtad 5 april 2017. Arkiverad från originalet 5 april 2017.

Litteratur