Short read mapping ( English Short-Read Sequence Alignment, Short-Read Sequence Mapping ) este o metodă bioinformatică de analiză a rezultatelor secvențierii de a doua generație , care constă în determinarea pozițiilor în genomul de referință sau transcriptom, de unde fiecare citire scurtă specifică ar putea să fie obținute cu cea mai mare probabilitate. De obicei, este primul pas în prelucrarea datelor dacă se cunoaște genomul organismului studiat.
Platformele de secvențiere de ultimă generație permit secvențierea eficientă a milioane de secvențe scurte de 50-500 bp. Pentru a face acest lucru, molecula de ADN sau ADNc este împărțită în multe segmente scurte, care sunt apoi secvențiate în paralel. După obținerea secvențelor secvențiate ale acestor segmente scurte (citări), genomul complet sau setul de secvențe ADNc trebuie reconstruit din acestea. Pentru a face acest lucru, este necesar să se determine pentru fiecare citire cea mai probabilă poziție în genomul de referință.
Spre deosebire de reasamblarea de novo , care adună citirile împreună pentru a reconstrui acest genom necunoscut, multe proiecte actuale au un „genom de referință” - un genom apropiat deja cunoscut de la un alt organism. Sau ar putea fi un set de secvențe de referință. În acest caz, pentru a da lecturii un sens, trebuie determinată poziția acesteia în datele de referință. Acest proces se numește mapare sau aliniere . Cartografierea poate avea un aspect ușor diferit pentru diferite sarcini, de exemplu: pentru cartografierea genomică, golurile mari ar trebui să fie absente, în timp ce pentru ARN-seq sunt permise datorită prezenței splicing-ului. În general, sarcinile de cartografiere nu s-au schimbat de la ultima generație de secvențe, dar programele dezvoltate pentru generația anterioară nu sunt proiectate să funcționeze cu volume de date crescute și, de asemenea, nu funcționează bine cu citiri de lungime scurtă.
Problema principală este că genomul studiat diferă de genomul de referință datorită variabilității genomului (de exemplu, datorită SNP - urilor sau indelilor), precum și datorită erorilor de secvențiere. Din acest motiv, alinierea unei citiri și poziția sa „corectă” în genomul de referință pot fi mai diferite decât alinierea acestei regiuni la orice altă locație din genomul de referință, astfel încât programele de cartografiere trebuie să poată găsi potriviri inexacte. Pentru aceasta sunt folosite diverse euristici. Când este suprapusă peste aceasta de posibilitatea de splicing în cazul ARN-seq, problema devine și mai complicată.
Citirile aparținând elementelor repetate sunt, de asemenea, o problemă. În acest caz, nu este întotdeauna posibil să decideți fără echivoc unde să mapați această lectură. O astfel de secvență poate fi mapată aleatoriu la orice site adecvat sau etichetată ca fiind mapată la mai multe site-uri.
Dacă genomul de referință este mare și s-au făcut miliarde de citiri, atunci timpul de cartografiere este o problemă majoră. Alinierea a fost întotdeauna o sarcină extrem de intensivă în resurse, dar în acest caz problema atinge un nivel calitativ nou, necesitând o raționalitate extraordinară și utilizarea eficientă a timpului procesorului și a memoriei din algoritmi.
Există două abordări principale pentru rezolvarea acestor probleme: utilizarea tabelelor hash și utilizarea arborilor sau a matricelor de sufixe.
Procesul de căutare folosind hashing este de multe ori mai rapid și mai puțin costisitor decât alinierea clasică folosind programarea dinamică pentru algoritmul Smith-Waterman .
Această abordare folosește o funcție hash care vă permite să transformați un șir într-o cheie care poate fi folosită pentru căutări rapide. Cea mai ușoară modalitate ar fi să împărțiți genomul în cuvinte care se potrivesc cu lungimea cititului, dar această abordare nu funcționează, deoarece cuvintele lungi sunt mai probabil să fie unice, iar stocarea lor ar ocupa prea mult spațiu de memorie. În schimb, se folosește hashingul secțiunilor mai scurte, care sunt mult mai frecvente. După ce funcția hash a obținut poziții adecvate, se poate încerca să mapați restul citirii la genom. De asemenea, abordarea împărțirii lecturii în mai multe părți vă permite să puneți posibilitatea substituțiilor în algoritm. Deci, în programul Maq, citirea este împărțită în 4 părți, numite semințe (secțiuni scurte cu potriviri exacte). Dacă lectura se potrivește perfect cu referința, atunci toate cele 4 semințe se potrivesc perfect. Dacă există o nepotrivire în citire, care se datorează probabil prezenței SNP -urilor sau erorilor de secvențiere, atunci va cădea într-una dintre semințe, în timp ce celelalte 3 se vor mapa perfect. La fel, cu două înlocuiri, cel puțin două semințe se vor mapa perfect. Astfel, prin cartografierea tuturor perechilor posibile de citiri folosind indexarea (vor fi 6 dintre ele, deoarece semințele trebuie să meargă într-o anumită ordine), vom obține un set limitat de locuri din genom unde poate fi mapată întreaga citire, după pe care este posibil să folosiți alinierea obișnuită pentru a determina care dintre poziții se potrivește cel mai bine (vezi imaginea 1a). SOAP, RMAP și SeqMap funcționează în mod similar.
O modificare a acestei abordări poate fi ideea de a lua în considerare toate k-măsurile de citire, în loc de secțiuni care nu se suprapun de o anumită lungime. Deci pentru citirea ACGT vor fi 3 dintre ele: AC, CG, GT. SHRiMP2 și RazerS funcționează într-un mod similar. Acest lucru va crește sensibilitatea, dar va crește și costul timpului.
Toate aceste informații ocupă mult spațiu de memorie. Pentru a reduce cantitatea de memorie consumată, majoritatea programelor folosesc codificarea pe doi biți a nucleotidelor (A 00, C 01, G 10, T 11), dar acest lucru nu permite utilizarea nucleotidei ambigue N, care poate fi prezentă atât în citiri, cât și în în genomul de referinţă. Programele adoptă abordări diferite pentru a ocoli acest lucru. Deci BWA înlocuiește N cu o nucleotidă aleatorie, iar SOAP2 înlocuiește tot N cu G.
Pot fi folosite diverse îmbunătățiri pentru a accelera algoritmii și pentru a rezolva erorile. De exemplu, folosiți poziții indiferente (să le notăm cu X). Deci, sămânța ACGxACG va fi aliniată atât pe ACGAACG, cât și pe ACGCACG, ceea ce crește sensibilitatea cartografierii (deși crește timpul de procesare, deoarece vor exista mai multe descoperiri pentru fiecare citire). Acesta este utilizat în programe precum Zoom, BFAST, GASSST, SHRiMP2, PerM.
De cele mai multe ori, algoritmii petrec nu căutând semințe, ci verificând mediul lor. Majoritatea programelor folosesc algoritmul Needleman-Wunsch sau modificările acestuia. Alții, precum GASSST, adaugă o etapă intermediară de măsurare a distanței Euler, care pur și simplu ia în considerare numărul de litere identice. De exemplu, dacă încercăm să mapam o citire care conține 5 G la o regiune care conține doar 1 G, atunci vom avea cel puțin 4 înlocuiri. Această abordare vă permite să îndepărtați rapid zonele necorespunzătoare și să aplicați abordări mai precise (dar și costisitoare) numai în regiunile promițătoare.
Este posibil să nu se hash genomul și să se caute citiri în el, ci să se hasheze citirile și să se caute secțiuni ale genomului de aceeași lungime în ele. Versiunile timpurii ale Maq, Rmap și SeqMap au folosit această abordare, dar de atunci numărul de citiri dintr-un experiment a crescut foarte mult și această abordare a încetat să mai fie rațională.
Algoritmii bazați pe hashing nu fac față bine repetărilor, deoarece numărul de semințe care trebuie verificate crește foarte mult. Pentru a rezolva acest lucru se folosesc algoritmi bazați pe arbori de sufixe și tablouri de sufixe . Avantajul acestei abordări, în special, este că repetările nu măresc timpul de rulare al algoritmului, deoarece secțiunile repetate „se prăbușesc” în arborele de sufixe. În forma sa cea mai pură, această abordare va funcționa extrem de rapid, cu condiția să nu existe erori și înlocuiri (de exemplu, este folosită de programul MPscan).
Matricea de sufixe este folosită pentru a economisi mai multă memorie. În general, căutarea printr-o matrice de sufixe nu este fundamental diferită de lucrul cu un arbore de sufixe, dar necesită o abordare puțin mai complexă. Transformarea Burroughs-Wheeler este adesea folosită . După toate transformările, dimensiunea unei astfel de matrice de sufixe este comparabilă cu dimensiunea genomului original. Deci, pentru întregul genom uman, matricea de sufixe creată de programul cu papion durează 2 gigaocteți. În comparație, o bază de date de indici bazați pe hash (cum ar fi cea folosită în programul Maq) ocupă aproximativ 50 de gigaocteți de memorie.
Algoritmul Ferragin-Manizi este folosit pentru a căuta cuvinte .
Într-o formă simplificată, procesul este după cum urmează. Citirile aliniază o nucleotidă la genomul transformat de Burrows-Wheeler. Fiecare nucleotidă aliniată permite programului să restrângă numărul de locuri în care poate merge întreaga citire. Dacă programul nu găsește o poziție în care citirea se potrivește perfect, revine la pasul anterior, face o înlocuire și continuă căutarea. Așa funcționează, de exemplu, SHRiMP. Pe de altă parte, dacă numărul de erori permise este mare, atunci acest lucru începe să încetinească algoritmul. O modificare puțin mai interesantă este utilizată în programul BWA - mai întâi aliniază părțile din stânga și din dreapta ale citirii, presupunând că cel puțin una dintre aceste două regiuni va avea mai puține erori (care se bazează pe faptul că capătul 5' este de obicei mai bine secvențial).
În prezent, există programe care folosesc atât una, cât și cealaltă abordare. În ciuda faptului că programele bazate pe transformarea Burroughs-Wheeler sunt acum mai populare, nu se poate spune că această abordare este mai bună. Aceste programe sunt mai rapide și mai bune în a face față repetărilor decât programele bazate pe hash, dar sunt mai puțin probabil să facă față erorilor. Situația inversă se observă pentru al doilea tip de programe: hashingul vă permite să contabilizați bine erorile, dar începe să consume mult timp atunci când întâlniți repetări.
În acest caz, posibilitatea de îmbinare ar trebui inclusă în considerare. Practic, se folosesc cunoștințele despre exoni și introni deja cunoscuți, ceea ce face posibilă crearea unei baze de date constând din asociații exon-exon și, deja, implementarea algoritmilor convenționali, cum ar fi bowtie sau maq. Evident, această abordare nu ține cont de introni necunoscuți anterior, așa că poate fi combinată cu învățarea automată pentru a prezice îmbinări necunoscute.
O altă abordare ar putea să nu folosească adnotarea deloc. În modul de funcționare fără adnotare, TopHat determină mai întâi potențialii exoni, construiește o bază de date cu potențiale site-uri de îmbinare pe baza acestor informații și apoi hărțile citește folosindu-le. Exonii potențiali sunt determinați de locațiile citirilor ARN-seq adiacente atunci când sunt aliniați la genom. Deoarece mulți exoni sunt mai scurti decât cei generați de secvențierele de citire curente, aceștia nu vor fi detectați în timpul fazei inițiale de mapare. TopHat rezolvă această problemă în principal prin împărțirea citirilor în bucăți mai scurte și maparea lor independent.
TopHat folosește două metode principale în identificarea potențialelor locuri de îmbinare. Primul și principal factor în favoarea unui site potențial de îmbinare este atunci când două segmente dintr-o citire (pentru citiri cu lungimea de 45 de perechi de baze sau mai mult) sunt mapate la o anumită distanță unul de celălalt sau când segmentul intern al citirii nu reușește să fie cartografiat. Un alt factor este apariția perechilor de „insule de acoperire”, care sunt locuri în care multe citiri ARN-seq sunt mapate una lângă alta. Insulele învecinate sunt adesea tăiate împreună și sunt una lângă alta în transcriere, așa că TopHat caută modalități de a le conecta folosind un intron.
Principala problemă a algoritmilor bazați pe adnotări este că aceștia depind foarte mult de calitatea adnotărilor în sine, în timp ce algoritmii care utilizează învățarea automată depind foarte mult de calitatea setului de antrenament. Mai mult, dat fiind că noile adnotări se bazează pe cele vechi, erorile din adnotări se pot „propaga”, devenind din ce în ce mai „semnificative” și mult mai greu de detectat.
Abreviere din engleză. Instrument de căutare rapidă și precisă asemănătoare Blat . Dezvoltatorii programului s-au concentrat pe sensibilitatea programului la erori, SNP -uri și indels, permițându-vă să alegeți un echilibru între viteză și precizie.
Acceptă secvențierea cu sfârșit împerecheat . Utilizează algoritmul Smith-Waterman pentru alinierea finală cu suport pentru goluri și definirea indelilor mici [1] . Capabil să lucreze în mod paralel pe un cluster. Există o versiune a programului bfast+bwa. Suporta formatele de date Illumina, ABI SOLiD, 454, Helicos.
Instrument de aliniere asemănător BLAST. Optimizat pentru viteză prin utilizarea unui index de fragmente K care nu se suprapun, care se potrivește în memoria RAM a computerului [2] .
Permite o înlocuire pe meci.
Utilizează algoritmul Burrows-Wheeler pentru indexare. Programul este optimizat pentru viteza și consumul de memorie, poate folosi mai multe nuclee de procesor. Viteza declarată care depășește de 35 de ori viteza MAQ și de 300 de ori viteza SOAP în aceleași condiții. [3]
Permite nepotriviri.
Bazat pe Bowtie, a fost construit programul TopHat pentru alinierea citirilor ARN-seq.
BWA (Biological Sequence Alignment) este un set de trei programe: BWA-backtrack, BWA-SW și BWA-MEM. BWA-backtrack funcționează cu citirile Illumina de până la 100 bp, BWA-SW și BWA-MEM pot funcționa cu secvențe mai lungi de la 70 la 1 milion bp. BWA-MEM este cea mai recentă versiune, de calitate superioară și mai precisă.
BWA-SW și BWA-MEM sunt capabile să găsească citiri himerice. [patru]
BWA-SW folosește transformarea Burrows-Wheeler împreună cu egalizarea Smith-Waterman. Capabil să lucreze cu secvențe lungi, în timp ce mai precis și mai rapid decât BLAT. [5]
Reprezintă alinierea locală eficientă a datelor de nucleotide. Dezvoltat de Solexa, apoi achiziționat de Illumina.
Utilizează lecturi pereche, este capabil să identifice opțiunile structurale. [6] Poate funcționa numai cu secvențe de până la 32 de perechi de baze, permite până la două diferențe, dar nu poate funcționa cu indels. [7]
Produce aliniere fără goluri. Pentru citirile single-end, poate găsi până la 2 sau 3 nepotriviri, în funcție de opțiunile de lansare. Permite până la 1 nepotrivire pentru citirile cu sfârșit pereche. [opt]
Construiește consens pe baza unui model statistic. [9]
Aliniază citirile single-end și paired-end de la Illumina, paired-end de la 454. Poate detecta aliniamentele cu goluri sau nepotriviri. Poate raporta o aliniere multiplă. [zece]
SHRiMP2 pune accent pe acuratețe, permițând citirilor să fie aliniate cu polimorfisme sau erori de secvențiere.
Utilizează algoritmul Smith-Waterman. Versiunea 1 a indexat citirile, versiunea 2 a indexat genomul, datorită căreia a atins o viteză mai mare.
Suportă citirile Illumina/Solexa, Roche/454 și AB/SoliD, acceptă calculul paralel. [unsprezece]
Poate alinia fragmente cu o singură citire și perechi. Capabil să lucreze cu introni.
Algoritmul folosește indexul 2way-BWT (2BWT) [12] . Versiunea SOAP3 este optimizată pentru GPU și folosește un index special GPU-2BWT [13] .
Programul de aliniere a citirii ARN-seq bazat pe Bowtie.
A fost creat pentru a funcționa cu citirile produse de Analizorul genomului Illumina, dar a fost folosit cu succes cu citirile generate de alte tehnologii. Optimizat pentru citiri cu lungimea de 75 de perechi de baze sau mai mult. Nu permite amestecarea citirilor asociate și cu un singur capăt.
| Program | Algoritm | pereche-capăt/single-end | Lacune (introni) | indelii | Înlocuiri | Lungimea citirii (bp) |
|---|---|---|---|---|---|---|
| BFAST | Smith-Waterman. Există o versiune cu BWT | +/+ | + | + | ||
| BLAT | Măsuri K (ca BLAST) | + | 1-2 | 1-2 | ||
| Papion | Burroughs-Wheeler | -/+ | + | <=100 [14] , 70-1M [15] | ||
| BWA | Burrows-Wheeler + Smith-Waterman | +/+ | + | |||
| ELAND | Hașarea semințelor? | +/? | - | <=2 | pana la 32 | |
| MAQ | Hașarea semințelor | +/+ | - | + [16] | 2-3 [17] pentru single-end, 1 pentru paired-end | <=63 [18] |
| Novoalign | +/+ | + | + | |||
| Crevetă | K-măsuri + Smith–Waterman | +/+ | + | + | + | |
| SĂPUN | Burroughs-Wheeler | +/+ | + | <=2 | <=60 | |
| pălărie de sus | Burroughs-Wheeler | +/+ [19] | + | + | <=2 [20] | >=75 [21] |