RazerS - mapare rapidă cu control al sensibilității
David Weese
1 Departamentul de Informatică, Universitatea Liberă din Berlin, 14195 Berlin, Germania;
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.