Kortläsningsmapping ( Engelska Short-Read Sequence Alignment, Short-Read Sequence Mapping ) är en bioinformatisk metod för att analysera resultaten av andra generationens sekvensering , som består i att bestämma positioner i referensgenomet eller transkriptomet, varifrån varje specifik kortläsning skulle kunna erhållas med största sannolikhet. Det är vanligtvis det första steget i databehandlingen om arvsmassan för organismen som studeras är känt.
Nästa generations sekvenseringsplattformar möjliggör effektiv sekvensering av miljontals korta 50-500 bp sekvenser. För att göra detta delas DNA- eller cDNA - molekylen i många korta segment, som sedan sekvenseras parallellt. Efter att ha erhållit de sekvenserade sekvenserna av dessa korta segment (avläsningar), måste hela genomet eller uppsättningen av cDNA-sekvenser rekonstrueras från dem. För att göra detta är det nödvändigt att för varje läsning bestämma den mest sannolika positionen i referensgenomet.
Till skillnad från de novo reassembly , som samlar läsningar för att rekonstruera till detta okända genom, har många aktuella projekt ett "referensgenom" - ett redan känt nära genom från en annan organism. Eller det kan vara en uppsättning referenssekvenser. I detta fall, för att ge avläsningen en viss mening, måste dess position i referensdata bestämmas. Denna process kallas kartläggning eller justering . Kartläggning kan ha något olika utseende för olika uppgifter, till exempel: för genomisk kartläggning bör stora luckor saknas, medan de för RNA-seq är tillåtna på grund av närvaron av splitsning. Generellt sett har kartläggningsuppgifterna inte förändrats sedan den senaste generationen av sequencers, men programmen som utvecklats för den föregående generationen är inte designade för att fungera med ökade datavolymer, och fungerar inte heller bra med korta avläsningar.
Huvudproblemet är att det studerade genomet skiljer sig från referensgenomet på grund av genomets variabilitet (till exempel på grund av SNP eller indels), samt på grund av sekvenseringsfel. På grund av detta kan justeringen av en avläsning och dess "korrekta" position i referensgenomet vara mer annorlunda än anpassningen av denna region till någon annan plats i referensgenomet, så kartläggningsprogram måste kunna hitta inexakta matchningar. Olika heuristik används för detta. När det överlagras på detta av möjligheten till splitsning i fallet med RNA-seq, blir problemet ännu mer komplicerat.
Läsningar som hör till återkommande element är också ett problem. I det här fallet är det inte alltid möjligt att entydigt avgöra var man ska kartlägga denna läsning. En sådan sekvens kan slumpmässigt mappas till vilket lämpligt ställe som helst, eller märkas som kartlagt till flera ställen.
Om referensgenomet är stort och miljarder avläsningar har gjorts är kartläggningstiden ett stort problem. Justering har alltid varit en extremt resurskrävande uppgift, men i det här fallet når problemet en kvalitativt ny nivå, vilket kräver extraordinär rationalitet och effektiv användning av processortid och minne från algoritmer.
Det finns två huvudsakliga metoder för att lösa dessa problem: att använda hashtabeller och att använda suffixträd eller arrayer.
Sökprocessen med hashing är många gånger snabbare och billigare än klassisk anpassning med dynamisk programmering för Smith-Waterman-algoritmen .
Detta tillvägagångssätt använder en hashfunktion som låter dig omvandla en sträng till en nyckel som kan användas för snabba uppslagningar. Det enklaste sättet skulle vara att dela upp genomet i ord som matchar längden på läsningen, men detta tillvägagångssätt fungerar inte, eftersom långa ord är mer benägna att vara unika och deras lagring skulle ta för mycket minnesutrymme. Istället används hashning av kortare avsnitt, som är mycket vanligare. Efter att hashfunktionen har fått lämpliga positioner kan man försöka kartlägga resten av avläsningen till genomet. Tillvägagångssättet att dela upp läsningen i flera delar låter dig också lägga in möjligheten till substitutioner i algoritmen. Så i Maq-programmet är läsningen uppdelad i 4 delar, kallade frön (korta avsnitt med exakta matchningar). Om läsningen passar perfekt med referensen så passar alla 4 frön perfekt. Om det finns en felmatchning i läsningen, vilket troligen beror på närvaron av SNP :er eller sekvenseringsfel, kommer den att falla in i ett av fröna, medan de andra 3 fortfarande kommer att mappa perfekt. På samma sätt, med två ersättningar, kommer minst två frön att kartläggas perfekt. Genom att alltså kartlägga alla möjliga par av läsningar med hjälp av indexering (det kommer att finnas 6 av dem, eftersom fröna måste gå i en viss ordning), kommer vi att få en begränsad uppsättning platser i arvsmassan där hela läsningen kan kartläggas, efter som det är möjligt att använda den vanliga justeringen för att avgöra vilken av positionerna som passar bäst (se bild 1a). SOAP, RMAP och SeqMap fungerar på liknande sätt.
En modifiering av detta tillvägagångssätt kan vara idén att överväga alla k-mått för läsning, istället för icke-överlappande sektioner av en viss längd. Så för att läsa ACGT kommer det att finnas 3 av dem: AC, CG, GT. SHRiMP2 och RazerS fungerar på liknande sätt. Detta kommer att öka känsligheten, men kommer också att öka tidskostnaden.
All denna information tar upp mycket minnesutrymme. För att minska mängden minne som förbrukas använder de flesta program tvåbitars kodning av nukleotider (A 00, C 01, G 10, T 11), men detta tillåter inte användning av den tvetydiga nukleotiden N, som kan finnas både i läsningar och i referensgenomet. Program tar olika tillvägagångssätt för att komma runt detta. Så BWA ersätter N med en slumpmässig nukleotid, och SOAP2 ersätter allt N med G.
Olika förbättringar kan användas för att påskynda algoritmer och undvika fel. Använd till exempel likgiltiga positioner (låt oss beteckna dem med X). Så ACGxACG-fröet kommer att justeras på både ACGAACG och ACGCACG, vilket ökar kartläggningens känslighet (även om det ökar bearbetningstiden, eftersom det blir fler fynd för varje läsning). Detta används i program som Zoom, BFAST, GASSST, SHRiMP2, PerM.
För det mesta ägnar algoritmer åt att inte söka efter frön, utan att kontrollera sin miljö. De flesta program använder Needleman-Wunsch-algoritmen eller dess modifieringar. Andra, som GASSST, lägger till ett mellansteg för att mäta Euler-avståndet, vilket helt enkelt tar hänsyn till antalet identiska bokstäver. Om vi till exempel försöker mappa en läsning som innehåller 5 Gs till en region som bara innehåller 1 G, kommer vi att ha minst 4 ersättningar. Detta tillvägagångssätt gör att du snabbt kan rensa bort olämpliga områden och tillämpa mer exakta (men också kostsamma) tillvägagångssätt endast på lovande regioner.
Det är möjligt att hasha inte genomet och leta efter läsningar i det, utan att hasha läsningar och leta efter delar av genomet av samma längd i dem. Tidiga versioner av Maq, Rmap och SeqMap använde detta tillvägagångssätt, men sedan dess har antalet läsningar i ett experiment ökat kraftigt och detta tillvägagångssätt har upphört att vara rationellt.
Algoritmer baserade på hash klarar inte upprepningar bra, eftersom antalet frön som måste kontrolleras ökar kraftigt. Algoritmer baserade på suffixträd och suffixarrayer används för att lösa detta . Fördelen med detta tillvägagångssätt, i synnerhet, är att upprepningarna inte ökar algoritmens gångtid, eftersom de upprepade sektionerna "kollapsar" i suffixträdet. I sin renaste form kommer detta tillvägagångssätt att fungera extremt snabbt, förutsatt att det inte finns några fel och ersättningar (det används till exempel av MPscan-programmet).
Suffixarrayen används för att spara mer minne. Generellt sett skiljer sig inte sökning genom en suffixarray i grunden från att arbeta med ett suffixträd, utan kräver ett lite mer komplext tillvägagångssätt. Burroughs-Wheeler-transformationen används ofta . Efter alla transformationer är storleken på en sådan suffixarray jämförbar med storleken på det ursprungliga genomet. Så för hela det mänskliga genomet tar suffixarrayen som skapas av bowtie-programmet 2 gigabyte. Som jämförelse tar en databas med hash-baserade index (som den som används i Maq-programmet) upp cirka 50 gigabyte minne.
Ferragin-Manizi-algoritmen används för att söka efter ord .
I en förenklad form är processen som följer. Avläsningarna anpassar en nukleotid till det Burrows-Wheeler-transformerade genomet. Varje justerad nukleotid gör att programmet kan begränsa antalet platser där hela läsningen kan gå. Om programmet inte kan hitta en position där avläsningen passar perfekt, går det tillbaka till föregående steg, gör en ersättning och fortsätter sökningen. Så här fungerar till exempel SHRiMP. Å andra sidan, om antalet tillåtna fel är stort, börjar detta att sakta ner algoritmen. En något mer intressant modifiering används i BWA-programmet - det justerar först de vänstra och högra delarna av läsningen, förutsatt att åtminstone en av dessa två regioner kommer att ha färre fel (vilket är baserat på det faktum att 5'-änden är vanligtvis bättre sekvenserad).
För närvarande finns det program som använder både det ena och det andra tillvägagångssättet. Trots att program baserade på Burroughs-Wheeler-transformationen nu är mer populära, kan det inte sägas att detta tillvägagångssätt är bättre. Dessa program är snabbare och bättre på att hantera upprepningar än hash-baserade program, men de är mindre benägna att hantera fel. Den motsatta situationen observeras för den andra typen av program: hashing låter dig redogöra för fel väl, men det börjar ta mycket tid när du stöter på upprepningar.
I detta fall bör möjligheten till skarvning ingå i övervägandet. I grund och botten används kunskap om redan kända exoner och introner, vilket gör det möjligt att skapa en databas bestående av exon-exon-associationer, och redan på den för att implementera konventionella algoritmer, såsom bowtie eller maq. Uppenbarligen tar detta tillvägagångssätt inte hänsyn till tidigare okända introner, så det kan kombineras med maskininlärning för att förutsäga okända skarvar.
Ett annat tillvägagångssätt kanske inte använder anteckningen alls. I driftsättet utan anteckning bestämmer TopHat först potentiella exoner, bygger en databas med potentiella splitsningsplatser baserat på denna information och kartlägger sedan med hjälp av den. Potentiella exoner bestäms av placeringen av intilliggande RNA-seq-avläsningar när de är anpassade till genomet. Eftersom många exoner är kortare än de som genereras av nuvarande lässekvenserare, kommer de inte att detekteras under den initiala mappningsfasen. TopHat löser detta problem främst genom att dela upp läsningar i kortare bitar och mappa dem oberoende.
TopHat använder två huvudmetoder för att identifiera potentiella skarvningsplatser. Den första och främsta faktorn till förmån för en potentiell skarvningsplats är när två segment från en avläsning (för avläsningar med längd 45 baspar eller mer) mappas på ett visst avstånd från varandra eller när det interna segmentet av avläsningen misslyckas kartlagt. En annan faktor är uppkomsten av par av "täckningsöar", som är platser där många RNA-seq-avläsningar kartläggs sida vid sida. Närliggande öar skärs ofta ihop och ligger bredvid varandra i utskriften, så TopHat letar efter sätt att koppla ihop dem med hjälp av en intron.
Det största problemet med annoteringsbaserade algoritmer är att de är starkt beroende av kvaliteten på själva annoteringarna, medan algoritmer som använder maskininlärning är mycket beroende av kvaliteten på träningsuppsättningen. Dessutom, med tanke på att nya anteckningar är baserade på gamla, kan fel i anteckningar "fortplanta sig", bli mer och mer "signifikanta" och mycket svårare att upptäcka.
Förkortning från engelska. Blat-liknande snabb exakt sökverktyg . Utvecklarna av programmet har fokuserat på programmets känslighet för fel, SNP :er och indelar, så att du kan välja en balans mellan hastighet och noggrannhet.
Stöder parad sekvensering . Använder Smith-Waterman- algoritmen för den slutliga justeringen med stöd för luckor och definitionen av små indelar [1] . Kan arbeta i parallellt läge på ett kluster. Det finns en version av programmet bfast+bwa. Stöder Illumina, ABI SOLiD, 454, Helicos dataformat.
BLAST-liknande inriktningsverktyg. Optimerad för hastighet genom att använda ett index av icke-överlappande K-fragment som passar in i datorns RAM [2] .
Tillåter ett byte per match.
Använder Burrows-Wheeler-algoritmen för indexering. Programmet är optimerat för hastighet och minnesförbrukning, det kan använda flera processorkärnor. Deklarerad hastighet överstiger 35 gånger hastigheten för MAQ och 300 gånger hastigheten för SOAP under samma förhållanden. [3]
Tillåter felmatchningar.
Baserat på Bowtie byggdes TopHat-programmet för justering av RNA-seq-avläsningar.
BWA (Biological Sequence Alignment) är en uppsättning av tre program: BWA-backtrack, BWA-SW och BWA-MEM. BWA-backtrack fungerar med Illumina läser upp till 100 bp, BWA-SW och BWA-MEM kan fungera med längre sekvenser från 70 till 1 miljon bp. BWA-MEM är den senaste versionen, högre kvalitet och mer exakt.
BWA-SW och BWA-MEM kan hitta chimära avläsningar. [fyra]
BWA-SW använder Burrows-Wheeler-transformen tillsammans med Smith-Waterman-utjämningen. Kan arbeta med långa sekvenser, samtidigt mer exakt och snabbare än BLAT. [5]
Står för Efficient Local Alignment of Nucleotid Data. Utvecklad av Solexa, sedan förvärvad av Illumina.
Använder parade avläsningar, kan identifiera strukturella alternativ. [6] Kan bara fungera med sekvenser upp till 32 baspar långa, tillåter upp till två skillnader, men kan inte fungera med indelar. [7]
Ger uppriktning utan mellanrum. För enstaka läsningar kan den hitta upp till 2 eller 3 felmatchningar beroende på startalternativen. Tillåter upp till 1 oöverensstämmelse för läsningar i parade ändar. [åtta]
Bygger konsensus utifrån en statistisk modell. [9]
Justerar single-end och paired-end läser från Illumina, paired-end från 454. Kan upptäcka justeringar med luckor eller felmatchningar. Kan rapportera flera justeringar. [tio]
SHRiMP2 lägger tonvikt på noggrannhet, vilket gör att läsningar kan anpassas till polymorfismer eller sekvenseringsfel.
Använder Smith-Waterman-algoritmen. Version 1 indexerade läser, version 2 indexerade genomet, på grund av vilket det uppnådde högre hastighet.
Stöder Illumina/Solexa, Roche/454 och AB/SOLiD läsningar, stöder parallell beräkning. [elva]
Kan justera enkellästa och parändande fragment. Kan arbeta med introner.
Algoritmen använder 2way-BWT (2BWT) index [12] . SOAP3-versionen är GPU-optimerad och använder ett speciellt GPU-2BWT-index [13] .
RNA-seq avläsningsprogram baserat på Bowtie.
Den skapades för att fungera med läsningar producerade av Illumina Genome Analyzer, men har framgångsrikt använts med läsningar som genererats av andra teknologier. Optimerad för läsningar med längd 75 baspar eller mer. Tillåter inte att parade och ensidiga läsningar blandas ihop.
| Program | Algoritm | paired-end/single-end | Mellanrum (introner) | indels | Byten | Läslängd (bp) |
|---|---|---|---|---|---|---|
| FAST | Smith-Waterman. Det finns en version med BWT | +/+ | + | + | ||
| BLAT | K-mått (som BLAST) | + | 1-2 | 1-2 | ||
| Fluga | Burroughs-Wheeler | -/+ | + | <=100 [14] , 70-1M [15] | ||
| BWA | Burrows-Wheeler + Smith-Waterman | +/+ | + | |||
| ELAND | Fröhashing? | +/? | - | <=2 | upp till 32 | |
| MAQ | Fröhashing | +/+ | - | + [16] | 2-3 [17] för single-end, 1 för paired-end | <=63 [18] |
| Novoalign | +/+ | + | + | |||
| Räka | K-mått + Smith–Waterman | +/+ | + | + | + | |
| TVÅL | Burroughs-Wheeler | +/+ | + | <=2 | <=60 | |
| hög hatt | Burroughs-Wheeler | +/+ [19] | + | + | <=2 [20] | >=75 [21] |