Localizzazione degli eBWT cluster attraverso il Metodo 1

6.2 Localizzazione degli eBWT cluster

6.2.1 Localizzazione degli eBWT cluster attraverso il Metodo 1

La teoria del Prefix-Free Parsing, e pi`u in particolare il Lemma 5.5 (nella Sezione 5.1), dimostra che la permutazione che ordina lessicograficamente gli elementi di 𝑍 ordina lessicograficamente anche i suffissi di 𝑠. I suffissi dell’insieme 𝑍 possono essere calcolati, come suggerito dall’implementazione eseguita da Boucher et al., attraverso l’algoritmo gSACAK. Il suffix array e l’array LCP, rispettivamente denotati con SAZe lcpZ, prodotti da gSACAK contengono le informazioni che gli

autori originariamente hanno utilizzato per stabilire (una parte) dell’ordine dei caratteri della BWT, ed alcune di quelle informazioni sono importanti per noi al fine di localizzare gli eBWT cluster. Per garantire la correttezza della teoria del Prefix-Free Parsing, in SAZsi considerano i soli suffissi con

lunghezza almeno 𝑤.

È importante tenere presente che calcolare la eBWT di un insieme di stringhe produce risultati distinti se queste vengono concatenate con un terminatore univoco, oppure se utilizzato lo stesso per tutte le stringhe. Inoltre, si ricorda che è necessario appendere un terminatore differente alla fine di ogni stringa per garantire la reversibilità della eBWT, anche se tale proprietà non è importante per il nostro utilizzo della eBWT. L’array lcpZcontiene la lunghezza del prefisso più lungo

in comune tra due suffissi degli elementi di 𝐷 consecutivi nel rispettivo suffix array SAZ. L’utilizzo

di un terminatore univoco per tutti i read, come stabilito dal Prefix-Free Parsing, produce delle informazioni per il nostro scopo non del tutto corrette. In particolare, esiste la possibilit`a che due suffissi presentino lo stesso carattere terminatore in una delle posizioni precedenti alla posizione contenente il carattere che li differenzia e che stabilisce il loro ordine lessicografico. Tali condizioni sono la causa di una differenza tra l’array lcpZcalcolato e l’array LCP calcolato sui suffissi ordina-

ti di stringhe che terminano con un carattere univoco. Si ipotizzi quindi di poter calcolare l’array lcp'

Zdefinito come segue.

Definizione 6.1: L’array lcp'_Z[1, | 𝑍 |] memorizza la lunghezza del prefisso pi`u lungo in comune tra due elementi di 𝑍 consecutivi nel rispettivo suffix array SAZ, ma per cui considera il carattere

terminatore univoco.

In altri termini, se il prefisso comune pi`u lungo 𝛼 tra i suffissi 𝑧, 𝑧

'

∈ 𝑍 contiene la prima occorrenza del carattere terminatore in posizione 𝓁 allora lcp'

Zmemorizza il valore 𝓁 − 1 (vedi Figura 6.2). 𝑧 = 𝑧'= … # … … # … < 𝓁 1 𝛼 𝛼

Figura 6.2: Illustrazione del caso in cui il prefisso comune pi`u lungo𝛼 tra i suffissi 𝑧, 𝑧' _{∈ 𝑍}

contiene la prima occorrenza del carattere terminatore in posizione 𝓁, lcpZe lcp'Zmemorizzano

CAPITOLO 6. Variant calling con il Prefix-Free Parsing 6.2. Localizzazione degli eBWT cluster Lemma 6.1: Una volta calcolato lcp'

Z[1, | 𝑍 |] `e possibile localizzare gli eBWT cluster individuando

i minimi locali contenuti in lcp' Z.

Dimostrazione. Il Teorema 4.2 (Sezione 4.1.2) specifica che i cluster sono delimitati dai minimi locali dei valori dell’array lcp'

Z; in particolare, prova che con alta probabilit`a i cluster corrispondono a

intervalli ebwt[𝑎𝑒, 𝑏𝑒] che non contengono un minimo locale nella sezione lcp'Z[𝑎, 𝑏], ossia nessun

indice 1 < 𝑎 ≤ 𝑖 ≤ 𝑏 < 𝑛 soddisfa lcp'

Z[𝑖 − 1] ≥ lcp'Z[𝑖] < lcp'Z[𝑖 + 1]. ■

Fino ad ora stiamo trattando una versione dell’eBWT cluster che possiamo definire “astratta”, in quanto la BWT non `e ancora stata effettivamente calcolata. Seguendo concettualmente il processo implementativo del Prefix-Free Parsing, siamo fermi prima della sua ultima fase, quella in cui viene costruita la BWT dal suffix array e dalle inverted-list delle frasi contenute in 𝐷. Non essendo il nostro obiettivo quello di calcolare l’intera BWT, possiamo considerare l’idea di ridurre ulteriormente le operazioni di calcolo recuperando i soli caratteri contenuti nella sottostringa interessata, secondo il procedimento del Prefix-Free Parsing, solo dopo aver localizzato l’eBWT cluster. In particolare, dopo aver calcolato le inverted-list delle frasi di 𝐷 e l’array 𝐴 (vedere Sezione 5.2 e Figura 5.4), per ciascun suffisso di SAZ[𝑎, 𝑏] valgono le seguenti propriet`a:

∙

se `e il suffisso di un unico elemento di 𝐷, `e preceduto dal carattere 𝑐 con una frequenza 𝑘, allora si estraggono 𝑘 copie di 𝑐;

∙

se coincide con una frase 𝑑 del dizionario 𝐷, allora si recuperano i caratteri attraverso l’array 𝐴 nelle posizioni stabilite dalla inverted-list di 𝑑;

∙

se `e un suffisso proprio di pi`u elementi di 𝐷, allora si utilizza una struttura heap per unire le rispettive inverted-list e recupera un carattere ogni volta che viene eseguita l’operazione di pop dalla struttura heap.

La Figura 6.3 riporta una sezione dell’eBWT e degli array LCP lcp_Ze lcp' Z cal-

colati per l’insieme 𝑍 dei suffissi degli elementi dell’insieme 𝐷 in esempio. Le righe evidenziate rappresentano l’eBWT cluster localizzato attraverso i minimi locali in lcp'

Si osservi che localizzando invece l’eBWT cluster identificando i minimi locali in lcp_Zsi sarebbe ridotto il cluster alle sole prime tre righe. In questo esempio specifico, ogni suffisso si presenta con frequenza 1 nell’insieme 𝑍, pertanto gli indici dell’eBWT cluster e degli array lcp'

Ze SAZ coincidono. eBWT SAZ lcpZ lcp'Z … … … … C GC###### … … T GCGA#ATGCGAT#ATGCGC 2 2 T GCGAT#ATGCGC 4 4 C GCGAT#GATGCGATA#ATGCGC 6 5 C GCGAT#T 6 5 T GCGATA#ATGCGC 5 5 C GCGATC#GATGCGC 5 5 T GCGC###### 3 3 T GCGCGAT#GATGCGATA#ATGCGC 4 4 … … … …

Figura 6.3: eBWT cluster localizzato con il Metodo 1 e l’array lcp' Z.

CAPITOLO 6. Variant calling con il Prefix-Free Parsing 6.2. Localizzazione degli eBWT cluster Si consideri però, che in ciascuno dei casi precedentemente elencati, esiste la possibilità che ad un suffisso in SAZ[𝑎, 𝑏] venga associato più di un carattere, uguale o diverso, della BWT finale. Per tale

ragione, nella realizzazione del Metodo 1, `e opportuno denotare l’eBWT cluster con ebwt[𝑎𝑒, 𝑏𝑒]

riferito alle sezioni SAZ[𝑎, 𝑏] e lcp'Z[𝑎, 𝑏].

Lemma 6.2: Se almeno un suffisso in SAZ[𝑎, 𝑏] (i) coincide con un elemento di 𝐷, oppure (ii) `e

un suffisso proprio di pi`u elementi di 𝐷, oppure (iii) si presenta con frequenza maggiore di 1 nell’insieme 𝑍; allora le sezioni SAZ[𝑎, 𝑏] e lcp'Z[𝑎, 𝑏] denotano l’eBWT cluster ebwt[𝑎𝑒, 𝑏𝑒].

Dimostrazione. Tale affermazione `e verificata in quanto, considerato un suffisso𝑧 ∈ 𝑍 appartenente all’eBWT cluster con ebwt[𝑎𝑒, 𝑏𝑒], se vengono mappati almeno 𝑘 ≥ 2 valori o uno stesso valore con

frequenza 𝑘 ≥ 2 allo stesso suffisso 𝑧, allora per allineare gli indici 𝑎𝑒e 𝑏𝑒della sottostringa della

eBWT con gli indici 𝑎 e 𝑏 degli array SAZe lcp'Z`e necessario avere 𝑘 ripetizioni dei valori contenuti

in SAZe lcp'_Zper il suffisso 𝑧 (vedi Figura 6.4). ■

𝑖 Carattere_mappato SAZ Frequenza lcp'Z

… … … … … GCGA# … 2 𝑎 G GCGACC. . . 1 4 T,A GCGAG. . . 1 4 C GCGAT. . . 1 4 𝑏 T GCGATC. . . 2 5 … GTA# … 1 … … … … 𝑖 eBWT SAZ lcp … … … … GCGA# 2 𝑎𝑒 G GCGACC. . . 4 T GCGAG. . . 4 A GCGAG. . . 4 C GCGAT. . . 4 T GCGATC. . . 5 𝑏𝑒 T GCGATC. . . 5 … GTA# 1 … … …

Figura 6.4: Differenza degli indici degli array SAZ[𝑎, 𝑏] e lcp'Z[𝑎, 𝑏] con quelli della sottostringa

coperta dall’eBWT cluster, che qui corrisponde a ebwt[𝑎𝑒, 𝑏𝑒] = GTACTT.

Tra i casi possibili si ha in particolare quello in cui gli indici indici 𝑎𝑒e 𝑏𝑒della sottostringa della

BWT sono allineati con gli indici 𝑎 e 𝑏 degli array SAZe lcp'Z.

Lemma 6.3: Se ogni suffisso in SAZ[𝑎, 𝑏] `e il suffisso proprio di un solo elemento di 𝐷 che si

presenta con frequenza 1 nell’insieme 𝑍, allora 𝑎𝑒= 𝑎 e 𝑏𝑒 = 𝑏 e di conseguenza possiamo denotare

ebwt[𝑎𝑒, 𝑏𝑒] = ebwt[𝑎, 𝑏].

Dimostrazione. Gli indici𝑎𝑒 e 𝑏𝑒 della sottostringa della eBWT e gli indici 𝑎 e 𝑏 degli array SAZe

lcp'_Zsono allineati per ogni suffisso 𝑧 ∈ 𝑍 appartenente a SAZ[𝑎, 𝑏] in quanto a 𝑧 viene mappato un

unico carattere, ed essendo la frequenza 1 tale carattere comparir`a una sola volta nella sottostringa

della BWT (vedi Figura 6.5). ■

𝑖 Carattere_mappato SAZ Frequenza lcp'Z

… … … … … GCGA# … 2 𝑎 G GCGACC. . . 1 4 T GCGAG. . . 1 4 C GCGAT. . . 1 4 𝑏 T GCGATC. . . 1 5 … GTA# … 1 … … … … 𝑖 eBWT SAZ lcp … … … … GCGA# 2 𝑎𝑒 G GCGACC. . . 4 T GCGAG. . . 4 C GCGAT. . . 4 𝑏𝑒 T GCGATC. . . 5 … GTA# 1 … … …

Figura 6.5: Coincidenza degli indici degli array SAZ[𝑎, 𝑏] e lcp'Z[𝑎, 𝑏] con quelli della sottostrin-

CAPITOLO 6. Variant calling con il Prefix-Free Parsing 6.2. Localizzazione degli eBWT cluster Pertanto la sottostringa della BWT `e lunga almeno tanto quanto la sottostringa delimitata dai minimi locali nell’array lcp'

Z. Questo fatto, comunque, non crea nessun problema dal punto di

vista teorico, pu`o solo causare una variazione tra gli indici che definiscono l’eBWT cluster e quelli delle strutture necessarie alla loro localizzazione che deve essere gestita nell’implementazione.

Seguendo le considerazioni della strategia pi`u recente presentata da Prezza et al., nella pratica possiamo evitare di calcolare l’array lcp'

Zeffettivo memorizzando le informazioni necessarie in una

struttura pi`u compressa. Il bit-vector localMinZ[1, | 𝑍 |], indica le posizioni in cui la lunghezza del

longest common prefix `e un minimo locale nell’array lcp'

Z. Allo stesso tempo possiamo creare il

bit-vector KminZ[1, | 𝑍 |], per indicare le posizioni in cui la lunghezza del longest common prefix `e

maggiore della soglia minima 𝑘min≥ 𝑤 e KrightZ[1, | 𝑍 |], per specificare le posizioni da cui estrarre

i 𝑘right≥ 𝑤 nucleotidi che formano il contesto. Gli array possono essere calcolati modificando le

formule (4.2), (4.3) e (4.4), come segue: KminZ[𝑖] = ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 1 se lcp' Z[𝑖] ≥ kmin 0 altrimenti (6.1) localMinZ[𝑖] = ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 1 se lcp' Z[𝑖 − 1] ≥ lcp'Z[𝑖] < lcp'Z[𝑖 + 1] 0 altrimenti (6.2) Kright_Z[𝑖] = ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 1 se lcp' Z[𝑖] ≥ kright 0 altrimenti (6.3)

Attraverso queste strutture dati compresse, per il Metodo 1, un eBWT cluster corrisponde alla massima sottostringa ebwt[𝑎𝑒, 𝑏𝑒] tale per cui, per ogni valore 𝑎 ≤ 𝑖 ≤ 𝑏 si ha che KminZ[𝑖] = 1 e

localMinZ[𝑖] = 0.

La Figura 6.6 riporta, oltre ad una sezione dell’eBWT e degli array LCP lcp_Ze lcp'

Z, le sezioni dei bit-vector localMinZ, KminZe KrightZcalcolati, per l’insieme 𝑍 dei suffissi

degli elementi dell’insieme 𝐷 in esempio, rispettivamente attraverso le formule (6.2), (6.1) e (6.3) con 𝑘min= 2 e 𝑘right= 2. Le righe evidenziate con colore pi`u intenso rappresentano l’eBWT

cluster localizzato attraverso i bit-vector localMinZe KminZ: per ogni suffisso del cluster si ha

che localMinZ[𝑖] = 0 e KminZ[𝑖] = 1.

eBWT SAZ lcpZ lcp'Z localMinZ KminZ KrightZ

… … … … C GATGCGC 6 6 0 1 1 C GC###### 1 1 1 0 0 T GCGA#ATGCGAT#ATGCGC 2 2 0 1 1 T GCGAT#ATGCGC 4 4 0 1 1 C GCGAT#GATGCGATA#ATGCGC 6 5 0 1 1 C GCGAT#T 6 5 0 1 1 T GCGATA#ATGCGC 5 5 0 1 1 C GCGATC#GATGCGC 5 5 0 1 1 T GCGC###### 3 3 1 1 1 T GCGCGAT#GATGCGATA#ATGCGC 4 4 1 1 1 … … … …

Figura 6.6: eBWT cluster localizzato con i bit-vector localMinZe KminZdel Metodo 1.

CAPITOLO 6. Variant calling con il Prefix-Free Parsing 6.2. Localizzazione degli eBWT cluster

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