Variant calling per gli SNP e le INDEL - Identificazione reference-free e assembly-free di poli

presentano dei brevi contesti, l’algoritmo richiede un valore minimo (𝑘min) di LCP condiviso tra

suffissi nel cluster, ossia lcp[𝑖] ≥ 𝑘minper 𝑎 ≤ 𝑖 ≤ 𝑏.

4.1.3 Strutture dati compresse

Con la prima presentazione del framework [39] ogni eBWT cluster veniva, secondo il Teorema 4.2, localizzato tramite i valori contenuti nell’array LCP calcolato attraverso specifici tool in grado di produrre anche il suffix array generalizzato (GSA) e l’eBWT (come BCR[42], eGSA[37] o gSA- CAK[43]). Nei successivi sviluppi del framework, Prezza et al., hanno preso in considerazione l’implementazione della loro strategia senza il calcolo del GSA e dell’intero array LCP, ma bens`ı localizzando gli eBWT cluster attraverso strutture dati ausiliarie create sulla base dei risultati al- goritmici di un loro ulteriore studio [44]. Pi`u precisamente, i minimi locali nell’array LCP vengono calcolati durante l’esecuzione del framework simulando una visita del suffix tree mediante l’utiliz- zo della sola eBWT in un tempo 𝑂(𝑛 log | Σ |) ed uno spazio di 𝑜(𝑛 log | Σ |) bit. Inoltre, nella nuova implementazione, gli autori hanno utilizzato la backward search e la FL-mapping (vedi Sezione 3.2) per calcolare il contesto.

Le strutture dati ausiliarie necessarie alla localizzazione dei cluster consistono in tre bit-vector: (1) Kmin[1, 𝑛], per indicare le posizioni in cui la lunghezza del longest common prefix `e maggiore

della soglia minima 𝑘min; (2) localMin[1, 𝑛], per indicare le posizioni in cui la lunghezza del longest

common prefix `e un minimo locale nell’array LCP; (3) Kright[1, 𝑛], per indicare le posizioni da cui

estrarre i 𝑘rightnucleotidi che formano il contesto 𝑌. Tecnicamente calcolati secondo le seguenti

formule: Kmin[𝑖] = ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 1 se lcp[𝑖] ≥ kmin 0 altrimenti (4.2) localMin[𝑖] = ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 1 se lcp[𝑖 − 1] ≥ lcp[𝑖] < lcp[𝑖 + 1] 0 altrimenti (4.3) Kright[𝑖] = ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 1 se lcp[𝑖] ≥ kright 0 altrimenti (4.4)

Attraverso queste strutture dati ausiliarie un eBWT cluster corrisponde alla massima sottostringa ebwt[𝑎, 𝑏] tale per cui, per ogni valore 𝑎 ≤ 𝑖 ≤ 𝑏 si ha che Kmin[𝑖] = 1 e localMin[𝑖] = 0.

4.2 Variant calling per gli SNP e le INDEL

Nel caso in cui la collezione dei read analizzata contiene delle variazioni, l’eBWT positional clustering, appena descritto, può essere utilizzato per rilevarle. Il framework ha la peculiarità di operare direttamente sui read grezzi, senza la richiesta di assemblaggio delle sequenze o la necessità di un genoma di riferimento, individuando posizioni del genoma che mostrano caratteri distinti, ma se- guiti dallo stesso contesto.

CAPITOLO 4. Framework positional clustering 4.2. Variant calling per gli SNP e le INDEL questo framework per scoprire SNP si basava sulla scansione delle strutture dati eBWT, LCP e GSA dell’insieme dei read senza allinearli n´e mapparli su un genoma di riferimento.

L’algoritmo `e stato successivamente migliorato [40] fino ad essere in grado di individuare sia SNP che INDEL nella collezione di read fornita come input pi`u efficacemente una volta calcolati i bit-vector Kmin, localMin e Krightdescritti in precedenza.

Per ogni cluster ebwt[𝑎, 𝑏], se il cluster non contiene almeno due caratteri distinti, ognuno dei quali ricorre almeno mincovvolte, allora viene scartato; altrimenti si procede come descritto di

seguito. Per ogni coppia (𝑐1, 𝑐2) di simboli distinti, ognuno dei quali ricorre almeno mincovvolte

nel cluster, si eseguono i passi seguenti:

∙

Si calcola la stringa consensus 𝐿1e 𝐿2tra i suffissi delle stringhe che precedono e includono

rispettivamente i caratteri 𝑐1 e 𝑐2 nell’eBWT, di lunghezza al massimo 𝑀 = 𝑘left+ maxindel,

dove 𝑘left `e la soglia minima della lunghezza del longest common prefix condiviso all’inter-

no del cluster e maxindel corrisponde al numero massimo dei nucleotidi aggiunti o elimi-

nati a causa di una INDEL. Il consensus viene calcolato utilizzando la backward search, ossia partendo dall’intervallo ebwt[𝑎1, 𝑏1] ottenuto dall’estensione verso sinistra dell’intervallo

ebwt[𝑎, 𝑏] con uno dei due caratteri 𝑐1o 𝑐2, si estende ricorsivamente l’intervallo ebwt[𝑎𝑞, 𝑏𝑞]

per 𝑞 = 1, 2, … , 𝑀 − 1 con la lettera pi`u frequente in ebwt[𝑎𝑞, 𝑏𝑞].

∙

Attraverso la funzione FL viene poi estratto il prefisso 𝑅 di 𝑘rightcaratteri dall’𝑖-esimo suffisso

lessicograficamente minore per un indice arbitrario 𝑎 ≤ 𝑖 ≤ 𝑏 tale per cui Kright[𝑖] = 1.

∙

Viene infine trovato l’allineamento tra 𝐿1e 𝐿2che minimizza la edit-distance(13) dove viene

consentito al massimo un inserimento o una cancellazione all’estremit`a destra delle due stringhe. Se l’allineamento ottimale non include INDEL, si ha uno SNP; mentre se introduce troppe modifiche viene scartato.

∙

L’algoritmo produce in output le sequenze 𝐿1⋅𝑅 e 𝐿2⋅𝑅(14), le informazioni utili per localizzare

lo SNP o l’INDEL e infine la copertura delle due sequenze nella collezione in input.

Ricordando che, il DNA è caratterizzato da due filamenti di direzioni opposte; in generale, le INDEL individuati dai read che si allineano sul filamento con una determinata direzione risultano spostati a sinistra, mentre quelli localizzati dai read che si allineano sul filamento di DNA con direzione opposta risulteranno spostati a destra. Questa caratteristica, condivisa da più strumenti di individuazione delle INDEL, si basa sul fatto che non è possibile, con le sole informazioni contenute nei read, stabilire il corretto spostamento delle INDEL. Solitamente, per risolvere questo tipo di ambiguità, si utilizzano strumenti di post-elaborazione in grado di normalizzare lo spostamento delle INDEL.

Di seguito viene riportato un esempio di esecuzione dell’algoritmo di variant calling che Prezza et al. hanno presentato nel loro paper [40, p. 8]. La Figura 4.4 schematizza i quattro passaggi della strategia per identificare gli SNP e le INDEL. Nell’esempio si fa riferimento ad un genotipo (sconosciuto) che presenta al suo interno una INDEL (Figura 4.4 - 1). Il

Esempio.

(13)_{In informatica, la edit-distance `e un metodo per quantificare quanto due stringhe differiscono tra loro contando il numero}

minimo di operazioni (solitamente inserzione, rimozione e sostituzione) richieste per trasformare una stringa nell’altra. In bioinformatica, pu`o essere appunto utilizzata per quantificare la somiglianza delle sequenze di DNA.

(14)_{Il simbolo “⋅”, in questo testo, rappresenta l’operazione di concatenazione di due stringhe, ossia per 𝑠[1, 𝑛] e 𝑠}_'_{[1, 𝑛}_'_{] risulta}

CAPITOLO 4. Framework positional clustering 4.2. Variant calling per gli SNP e le INDEL sequenziamento effettuato in vitro fornisce la collezione dei read (Figura 4.4 - 2), che possono presentare errori di sequenziamento e che compongono i dati in input dell’algoritmo di variant calling. Il passo 3 della Figura 4.4 riporta i valori di eBWT, LCP e il contesto precedente (LEFT) e successivo (RIGHT) a ciascun carattere dell’eBWT; evidenziando l’eBWT cluster con il rettan- golo colorato e i valori minimi nell’array LCP in grassetto. Si consideri che nella pratica viene esplicitamente calcolata la sola eBWT e le altre colonne presenti in figura sono solo a scopo il- lustrativo; i minimi locali dell’array LCP vengono calcolati durante l’esecuzione dell’algoritmo e i contesti precedenti e successivi sono ottenuti attraverso la backward search e la FL-mapping rispettivamente. Pi`u precisamente, nell’eBWT cluster dell’esempio si hanno 𝑐1= T e 𝑐2= C. Sce-

gliendo i parametri 𝑘left= 2 e maxindel= 2, si ottengono (tramite la backward search) le sequenze

consensus𝐿1= AT e 𝐿2= ATGC. Successivamente, con 𝑘right= 2, si estrae (attraverso la funzione

FL) la stringa𝑅 = GC da uno qualsiasi dei contesti presenti in RIGHT (in quanto nell’esempio attuale si ha che Kright[𝑖] = 1 `e soddisfatto per ogni indice 𝑖 del cluster). Infine, l’allineamento

ottimale tra 𝐿1e 𝐿2`e quello che elimina GC da 𝐿2. La INDEL generata in output risulta quindi

TGC→T (Figura 4.4 - 4), spostata a sinistra anche se originariamente (nel genotipo sconosciuto) era spostata a destra.

Attraverso l’algoritmo di variant calling gli SNP vengono individuati attraverso una procedura simile a quella appena descritta nell’esempio, l’unica differenza `e che il miglior allineamento dei contesti di sinistra non introduce inserimenti n´e cancellazioni.

1 Genotipo

4 Output INDEL 2 Collezione dei read

3 eBWT cluster GATGCGCGATATC GATGCG ATATC GATGCGC TGCGCGAT GATGCG GCGCAAT ATGCGCGATC ATGCGCGAT GATGCGA TGCGCT GATGCG GATGCCAT

GATGCGATA ATGCGAT ATGCGC AT GC

LEFT eBWT RIGHT LCP ⋯ ⋯ ⋯ ⋯ GA T GCG$ ⋯ GA T GCG$ 3 GA T GCGA$ 3 A T GCGAT$ 4 ATG C GCGAT$ 5 TG C GCGAT$ 5 GA T GCGATA. . . 5 ATG C GCGATC. . . 5 GA T GCGC$ 3 $ GCGCA. . . 4 ⋯ ⋯ ⋯ ⋯

Figura 4.4: Schema dei passaggi per l’individuazione di una INDEL.

Nel caso in cui sia disponibile un genoma di riferimento, allora le varianti che sono state indivi- duate possono essere allineate al genoma e convertite in file con formato VCF, utile per comparare i risultati dell’algoritmo di variant calling con i database delle varianti conosciute e per validare l’output stesso. Pi`u precisamente, le varianti possono essere filtrate con una soglia di copertura minima e viene creato un file FASTQ(15)_{. Successivamente il file pu`o essere allineato sul genoma di}

riferimento utilizzando BWA-MEM e il file SAM(16)risultate pu`o essere direttamente convertito in un file VCF.

(15)_{Il formato FASTQ `e un formato basato su testo per memorizzare sia una sequenza biologica che i suoi punteggi di qualit`a}

corrispondenti.

(16)_{Il Sequence Alignment Map (SAM) `e un formato basato su testo utilizzato per memorizzare, sequenze biologiche allineate}

CAPITOLO 4. Framework positional clustering 4.3. Performance del framework

Nel documento Identificazione reference-free e assembly-free di polimorfismi a singolo nucleotide con Prefix-Free Parsing (pagine 48-51)