David Weese

1 Departamentul de Informatică, Universitatea Liberă din Berlin, 14195 Berlin, Germania;

razers

Anne-Katrin Emde

1 Departamentul de Informatică, Universitatea Liberă din Berlin, 14195 Berlin, Germania;

Tobias Rausch

2 Școala internațională de cercetare Max Planck pentru biologie computațională și calcul științific, 14195 Berlin, Germania

Andreas Döring

1 Departamentul de Informatică, Universitatea Liberă din Berlin, 14195 Berlin, Germania;

Knut Reinert

1 Departamentul de Informatică, Universitatea Liberă din Berlin, 14195 Berlin, Germania;

Abstract

Tehnologiile de secvențiere de a doua generație furnizează date de secvență ADN la un randament ridicat fără precedent. Comun pentru majoritatea aplicațiilor biologice este o mapare a citirilor la un genom de referință aproape identic sau foarte similar. Datorită cantităților mari de date, algoritmi și implementări eficiente sunt cruciale pentru această sarcină. Vă prezentăm un instrument de cartografiere a citirii eficient numit RazerS. Permite utilizatorului să alinieze citirile secvențiale de lungime arbitrară utilizând fie distanța de Hamming, fie distanța de editare. Instrumentul nostru poate funcționa fie fără pierderi, fie cu o rată de pierdere definită de utilizator la viteze mai mari. Având în vedere rata pierderilor, vă prezentăm o abordare care garantează să nu pierdeți mai multe citiri decât cele specificate. Acest lucru permite utilizatorului să se adapteze la problema la îndemână și oferă un compromis perfect între sensibilitate și timpul de funcționare.

Tehnologiile de secvențiere de a doua generație revoluționează domeniul analizei secvenței ADN, deoarece cantități mari de date de secvențiere pot fi obținute la rate crescânde și scăzând dramatic costurile. Aplicațiile biologice sunt multiple, inclusiv resecvențierea genomului întreg pentru detectarea variației genomice, de exemplu, polimorfisme cu nucleotide unice (SNP) (Bentley și colab. 2008; Hillier și colab. 2008; Ley și colab. 2008; Wang și colab. 2008) sau variații structurale mari (Chen și colab. 2008), secvențierea ARN pentru descoperirea ARN necodificatoare sau profilarea expresiei (Morin și colab. 2008), aplicații de metagenomică (Huson și colab. 2007) și secvențierea ADN-ului imunoprecipitat cu cromatină, de exemplu pentru identificarea siturilor de legare a ADN-ului și a modelelor de modificare a histonelor (Barski et al. 2007).

Fundamentala pentru toate aceste aplicații este problema mapării tuturor citirilor secvențiate împotriva unui genom de referință, denumit problema de mapare a citirii. Poate fi formalizat după cum urmează: dat un set de secvențe de citire, o secvență de referință G și o distanță, găsiți toate șirurile de caractere g ale G care se află la distanța k de o citire. Aparițiile lui g în G se numesc potriviri. Măsurile comune ale distanței sunt distanța Hamming sau distanța de modificare; prima interzicea inserțiile și ștergerile (adică indels) în aliniere, cea de-a doua permițând nepotriviri și indels deopotrivă.

Deoarece noile tehnologii de secvențiere sunt capabile să producă milioane de citiri pe parcurs, sunt necesari algoritmi eficienți pentru maparea citirilor. Citirile sunt de obicei destul de scurte în comparație cu citirile tradiționale Sanger și au distribuții de erori specifice în funcție de tehnologia utilizată.

O varietate de instrumente au fost proiectate și dezvoltate special în scopul cartografierii citirilor scurte. O compilație a unor instrumente populare este prezentată în Tabelul 1 împreună cu câteva caracteristici cheie ale algoritmilor.

tabelul 1.

Instrumente de cartografiere citite pe scurt cu caracteristicile lor

Majoritatea abordărilor existente de mapare a citirii utilizează o strategie în doi pași. În primul rând, se aplică un algoritm de filtrare pentru a identifica regiunile candidate care pot conține o potrivire. Aceasta include construirea unei structuri de date index, fie pe setul de citiri, fie pe secvența de referință. În al doilea rând, regiunile candidate sunt examinate pentru potriviri adevărate într-o etapă de verificare care consumă mai mult timp. În implementările actuale trebuie să distingem cu atenție dacă ambele etape, etapa de filtrare și etapa de verificare, sunt adecvate pentru distanța aleasă (Hamming sau distanța de editare). Unele implementări, de exemplu, verifică potrivirile folosind calitățile apelului de bază, dar filtrează regiunile candidate folosind o distanță fixă ​​de Hamming sau de editare (H Li și colab. 2008). Metodele de filtrare utilizate se bazează pe semințe unice (Kent 2002; Ma și colab. 2002) sau multiple (Li și colab. 2003; Lin și colab. 2008), principiul porumbel (Navarro și Raffinot 2002; H Li și colab. 2008 ); R Li și colab. 2008; AJ Cox, ELAND: Aliniere locală eficientă a datelor nucleotidice, nepublicată), Sau bazată pe numărarea lemelor folosind (gapped) q-gram (Burkhardt și colab. 1999; Rasmussen și colab. 2006; Rumble și Brudno 2008). Metodele de verificare cuprind algoritmi de aliniere semiglobali pentru Hamming sau editează distanța (Levenshtein 1966) sau algoritmi de aliniere locală (Smith și Waterman 1981).

BLAT (Kent 2002), ca exemplu al unui singur filtru de semințe, caută aparițiile exacte ale șirurilor scurte de dimensiuni fixe, împărțite de două secvențe. PatternHunter (Ma și colab., 2002) a fost primul care a generalizat această strategie la semințe decalate (subsecvențe discontinue comune), crescând astfel sensibilitatea, menținând în același timp specificitatea. Sensibilitate suplimentară este obținută prin utilizarea mai multor semințe deschise; o abordare implementată în instrumentul de citire a cartografierii Zoom (Lin și colab. 2008), care utilizează o versiune restricționată a distanței de editare cu cel mult un decalaj. După depunerea inițială a acestei lucrări a fost publicată o metodă care utilizează citiri întregi ca semințe, care tolerează un număr mic de nepotriviri, urmărind înapoi toate posibilele înlocuiri ale bazelor de calitate slabă (Langmead și colab. 2009). Folosește genomii transformați de la Burrows-Wheeler și este o abordare eficientă a cartografierii scurte.

Având în vedere două secvențe la distanța k, lema porumbei afirmă că din orice partiție a primei secvențe în k + 1 părți, cel puțin o parte trebuie găsită fără erori în cealaltă secvență. Cu cât această sămânță este mai scurtă, cu atât este mai probabil să întâlniți potriviri aleatorii și, prin urmare, cu atât este mai mică specificitatea filtrului. Astfel, această strategie este destul de limitată și devine impracticabilă cu un număr tot mai mare de erori. Într-o extensie a acestei strategii, prima secvență este împărțită în k + 2 părți. Acum cel puțin două dintre aceste părți vor apărea în cealaltă secvență. Aceste două părți își păstrează pozițiile relative atâta timp cât nu apar indels între ele. ELAND (AJ Cox, nepublicat), MAQ (H Li și colab. 2008) și SOAP (R Li și colab. 2008) folosesc această observație, dar sunt, prin urmare, limitate la distanța Hamming. Mai mult, ELAND și SOAP folosesc întotdeauna o partiție cu patru segmente și MAQ cel mult o partiție cu cinci segmente și, prin urmare, nu pot garanta sensibilitatea deplină pentru k> 2 sau k> 3, respectiv. SeqMap (Jiang și Wong 2008) extinde strategia cu două semințe pentru a modifica distanța și caută cele două părți variind lungimea decalajului cu −k, (, k nucleotide.

O altă abordare este strategia de numărare a q-gramului care a fost folosită pentru prima dată în QUASAR (Burkhardt și colab. 1999). Folosește lema q-gram (Owolabi și McGregor 1988; Jokinen și Ukkonen 1991), care afirmă că două secvențe de lungime n cu distanța Hamming k împart cel puțin t = n + 1 - (k + 1) q șiruri comune de lungime q, așa-numitele q-grame. Această lemă poate fi aplicată și pentru a edita distanța dacă n este lungimea secvenței mai mari. O generalizare pentru q-grame decalate a fost dată de Burkhardt și Kärkkäinen (2002). SHRiMP (Rumble și Brudno 2008) folosește o strategie de numărare de q-grame cu o configurație implicită care nu garantează că este fără pierderi.

În această lucrare prezentăm o implementare a unui versatil maper de citire RazerS bazat pe numărarea q-gram, care se distinge în mai multe privințe de algoritmii existenți. În primul rând, poate mapa citirile utilizând distanța de editare sau Hamming în faza de filtrare și în faza de verificare fără restricții. În al doilea rând, având în vedere o rată de pierdere definită de utilizator (posibil 0 făcând mapatorul exact), am dezvoltat un algoritm pentru a selecta parametrii astfel încât rata de pierdere aleasă să nu fie depășită în așteptare. Algoritmul depinde de un model de eroare derivat din valorile calității apelului de bază. În cele din urmă, implementarea noastră poate mapa citirile de orice lungime cu un număr arbitrar de erori și este în prezent cel mai rapid în raportarea tuturor accesărilor pentru lungimile tipice de citire și ratele de pierdere.

Metode

Definiții și notație

Considerăm șiruri peste alfabetul ordonat finit Σ. Σ * este setul tuturor șirurilor posibile peste Σ și ε denotă șirul gol. Un șir s este o secvență de litere s [1]… s [n], unde fiecare s [i] ∈ Σ; st este concatenarea a două șiruri s și t; | s | denotă lungimea șirului s; și s [i.j] este un subșir de s din poziția i până la j. Dacă t ∈ Σ * este un șir de caractere al lui s, scriem t ≼ s și t ≺ s dacă t ≠ s se menține în plus.

O transcriere (n) (editare) este un șir peste alfabetul Δ = care descrie o transformare de la un șir la altul, vezi Figura 1. Pentru două șiruri r, g ∈ Σ *, se citește o transcriere de la r la g și se aplică de la stânga la dreapta caracterelor unice ale lui r pentru a produce g, prin care M, R, D și I corespund unei potriviri (fără schimbare), o înlocuire, o ștergere și o inserție a unui singur caracter în r, respectiv. Există o relație unu-la-unu între alinieri și transcrieri. Pentru orice transcriere T definim || T || E = | i | T [i] ∈> |, numărul de erori din T. Distanța de editare a două șiruri este numărul minim de erori din toate transcrierile dintre aceste șiruri. Un caz special este transcrierea Hamming cu Δ =. Este definit în mod unic pentru două șiruri de lungime egală, iar distanța Hamming este numărul de erori din acesta.

O transcriere dintr-o lectură într-o parte a genomului. Transcrierea conține șapte potriviri de trei, deci r și g împart cel puțin șapte 3 grame. De fapt, aceștia împărtășesc și un al opt-lea CAG de 3 grame care nu corespunde unui meci de trei din transcriere.

În cele ce urmează luăm în considerare transcrierile de la citirile subst subst la șirurile g ale unui genom G. Spunem că perechea (r, g) este o potrivire adevărată dacă d (r, g) ≤ k, pentru d fiind fie editare, fie distanță Hamming . Un șir M q al transcrierii T se numește q-match. Dacă o transcriere de la r la g conține t q-potriviri, atunci r și g au cel puțin t grame comune. Un filtru (q, t) este un algoritm care detectează orice pereche (r, g) pentru care există o transcriere T de la r la g cu ≥t q-potriviri.

Calculul sensibilității

În această secțiune elaborăm o metodă pentru a determina sensibilitatea filtrelor (q, t). Sensibilitatea unui filtru este probabilitatea ca o potrivire adevărată aleasă la întâmplare (r, g) să fie clasificată de filtru ca o potrivire potențială. Abordările existente de estimare a sensibilității sunt limitate la multiple filtre de semințe (Li și colab. 2003) sau presupun că transcrierile vor fi generate de un proces Markov (Herms și Rahmann 2008). Metoda noastră estimează sensibilitatea la filtrare sub orice distribuție de eroare dependentă de poziție, de exemplu, așa cum se observă în tehnologiile de secvențiere a ADN-ului Sanger sau Illumina (Dohm și colab. 2008).

Sensibilitate la distanță de lovire

Mai întâi luăm în considerare problema cartografierii citite pentru distanța Hamming și o distanță maximă dată k. În cele ce urmează, toate citirile sunt considerate a fi de lungime egală n.

Pentru a determina o limită inferioară pentru sensibilitatea unui (q, t) -filtru am putea enumera toate transcrierile Hamming cu până la k înlocuiri și să rezumăm probabilitățile de apariție ale acelor transcrieri care au cel puțin t subșiruri M q. Deoarece există multe transcrieri diferite, o enumerare completă durează Ω [(n/k) k] timp și nu este fezabilă pentru citiri mari sau rate ridicate de eroare, de exemplu, de lungime n = 200 cu k = 20 erori. Am dezvoltat o abordare de programare dinamică, care este semnificativ mai rapidă, utilizând o recurență similară cu calculul pragului în Burkhardt și Kärkkäinen (2002).

Să presupunem o distribuție de eroare dată care asociază fiecare poziție nucleotidică i într-o citire cu o probabilitate de eroare Pi R, de exemplu, probabilitatea unei greșeli de bază în timpul secvențierii sau a unui SNP. Apoi, probabilitatea de apariție a transcrierii Hamming T este produsul probabilităților de apariție a caracterelor transcripției unice la fiecare poziție p (T) =, cu. Calculăm sensibilitățile pentru meciurile cu e erori pentru fiecare e ≤ k separat. Fie S (n, e, t) suma probabilităților de apariție a transcrierilor de lungime n, având e erori și cel puțin t q-potriviri. Sensibilitatea unui (q, t) -filtru pentru a detecta potrivirile de erori electronice este cel puțin

Vom vedea cum să calculăm S (n, e, t) folosind un algoritm DP. Fie probabilitatea de apariție a subtranscrierii T să apară după j litere ale unei citiri. Definim R (i, e, T2) ca suma probabilităților de apariție a transcrierilor Ti ∈ Δ I, astfel încât T1 are e erori și concatenarea T1T2 conține cel puțin t subșiruri M q. Prin definiția lui S se menține:

Suma trece peste toate capetele transcrierii T de lungime q cu cel mult e erori. Factorul potrivit este probabilitatea ca T să apară la sfârșitul unei transcripții aleatorii de lungime n. Factorul din stânga este suma probabilității de apariție a tuturor începuturilor transcrierii, astfel încât concatenarea începutului și sfârșitului este o transcriere de lungime n cu erori e și cel puțin t q-potriviri. Cu următoarea lemă se poate concepe un algoritm DP pentru a determina R și, prin urmare, sensibilitățile S (n, e, t) pentru toate e = 0, ..., k și t = 1, ..., tmax în (nktmax2 q).

Lema 1. Să i, q ∈; e, t ∈; T ∈ q. R poate fi calculat folosind următoarea recurență: