Prefix-Free Parsing come struttura dati - Identificazione reference-free e assembly-free di pol

∙

che `e il suffisso di un unico elemento di 𝐷, `e preceduto dal carattere 𝑐 con una frequenza 𝑘, allora viene scritta nella BWT una sequenza di 𝑐 lunga 𝑘;

∙

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

∙

che coincide con una frase 𝑑 del dizionario 𝐷, allora i caratteri da scrivere nella BWT vengono ricavati dall’array 𝐴 nelle posizioni stabilite dalla inverted-list di 𝑑.

Utilizzando le informazioni calcolate in Figura 5.4 possiamo applicare la procedura per calcolare ad esempio il carattere antecedente al suffisso 𝑧 = #GATTAC ∈ {𝑍 ∩ 𝐷}, che ha un rango 0 sia in 𝐷 che in 𝑍, denotiamo quindi 𝑧0= 𝑑0= 𝑧. L’inverted-list di 𝑑0contiene solo

l’indice 2, quindi il carattere che precede 𝑧0corrisponde a 𝐴[2] = A (come calcolato in Figura 5.1).

Ipotizzando invece di calcolare l’ordine dei caratteri antecedenti a 𝑧 = TAC ∈ 𝑍 che è un suffisso di due elementi di 𝐷, uno con rango 0 in cui è preceduto da T, 𝑑0, e l’altro con rango 3 in cui è

preceduto da A, 𝑑3. L’unione delle inverted-list di 𝑑0e 𝑑3risulta [2, 3] e stabilisce che i caratteri

che precedono il suffisso 𝑧 nella BWT compariranno nell’ordine TA.

𝑀′ 0 1 3 1 4 2 1 3 1 4 2 0 1 4 2 0 1 3 2 0 1 3 1 4 3 1 4 2 0 1 4 2 0 1 3 1 𝑖 BWT 1 2 2 0 3 3 4 4 5 1 6 1 inverted-list 0: [2] 1: [5,6] 2: [1] 3: [3] 4: [4] (a) BWT e inverted-list. 𝑖 𝑃 1 0 2 1 3 3 4 1 5 4 6 2 BWT 2 0 3 4 1 1 𝑝'𝑖 4 2 1 1 0 3 𝐴 T A A A T T (b) Array 𝐴.

Figura 5.4: (a) BWT, inverted-list e (b) array𝐴 per 𝑃 = [0,1,3,1,4,2]. I prefissi sottolineati nella matrice 𝑀

'

corrispondono ai suffissi del parser ordinati precedentemente visti in Figura 5.2. Esempio.

Gli autori del Prefix-Free Parsing suggeriscono anche la possibilità di velocizzare la procedura parallelizzando il lavoro con una tecnica multi-thread (versione del tool ancora in via di sviluppo). La prima fase, in cui vengono calcolati il dizionario 𝐷 e il parser 𝑃, può essere parallelizzata suddi- videndo l’input in blocchi di stesse dimensioni e assegnando ciascun blocco ad un thread. L’ultima fase, in cui viene costruita la BWT dal suffix array e dalle inverted-list delle frasi contenute in 𝐷, può essere invece parallelizzata utilizzando un thread principale che scansiona il SA di 𝐷 e ogni volta in cui individua un intervallo con gli stessi suffissi assegna ad un altro thread il compito di calcolare e scrivere la porzione di BWT sul disco. Aumentando il numero di thread non avviene però un miglioramento sostanziale e le cause possono essere l’aggiornamento del dizionario da parte di tutti i thread durante la fase di parsing, oppure il bottleneck creato dagli accessi su disco causati dalla scrittura della porzione di BWT che ogni thread deve eseguire.

5.3 Prefix-Free Parsing come struttura dati

Assunto di aver gi`a calcolato il parser 𝑃 e il dizionario 𝐷 per una data stringa 𝑠[1, 𝑛], utilizzano l’implementazione descritta nella sezione precedente, si stabilisce adesso che la frase 𝑠[𝑖, 𝑗] contiene un

CAPITOLO 5. Prefix-Free Parsing 5.3. Prefix-Free Parsing come struttura dati carattere 𝑠[𝑘] se 𝑖 ≤ 𝑘 ≤ (𝑗 − 𝑤). Cos`ı facendo, nonostante due frasi consecutive si sovrappongono di 𝑤 caratteri (vedi Figura 5.3), ogni carattere di 𝑠 `e contenuto in una sola frase, eccetto per gli ultimi 𝑤 caratteri di 𝑠. Per eliminare questa eccezione, si considera che la stringa 𝑠 sia ciclica e che inizia con una stringa appartenente ad 𝐸. Ricordando che un suffisso proprio di una frase 𝑠

'

[1, 𝑛

'

] `e un qualsiasi suffisso 𝑠

'

[𝑖, 𝑛

'

] per 2 ≤ 𝑖 ≤ 𝑛

'

, ossia un suo suffisso diverso dalla frase completa. Possiamo quindi (ri)definire 𝑍 come l’insieme dei suffissi appropriati di lunghezza almeno 𝑤 per cui vale il Lemma 5.1, in quanto ogni prefisso proprio di una frase lungo almeno 𝑤 termina con una stringa appartenete a 𝐸 e non presenta al suo interno sottostringhe appartenenti ad 𝐸.

Nella sezione in cui viene descritta l’implementazione del Prefix-Free Parsing `e stato appurato che i simboli null, appesi e anteposti per l’elaborazione della stringa in input, possono essere gli stessi. Si considera quindi la stringa 𝑠 = GATTACAT!GATACAT!GATTAGATA, utilizzata come esempio fino adesso, riscritta come 𝑠 = GATTACAT#GATACAT#GATTAGATA. Stabilito 𝑤 = 2, ad 𝑠 viene appesa la stringa ## e viene definito l’insieme 𝐸 = {AC,AG,T#,##}. Considerando la stringa ciclica di seguito faremo riferimento a

1 4 8 12 16 20 24 28

𝑠 = ...##GATTACAT#GATACAT#GATTAGATA##... con 𝑛 = 28, e per la quale al termine della procedura di parsing si ottengono

𝐷 = { ##GATTAC, ACAT#, AGATA##, T#GATAC, T#GATAG }

𝑃 = [ ##GATTAC, ACAT#, T#GATAC, ACAT#, T#GATAG, AGATA## ] = [ 0, 1, 3, 1, 4, 2 ] Esempio.

Dopo aver memorizzato 𝑃 e 𝐷 con una tecnica in grado sia di compattarli che di permettere un rapido accesso casuale; per supportare query rapide sul Prefix-Free Parsing `e necessario implemen- tare cinque ulteriori strutture dati di seguito definite e denominate con 𝐵𝑃, 𝐵BWT, 𝑀, 𝑇 e 𝜋. Tali

strutture richiedono uno workspace proporzionale alla somma della lunghezza di 𝑃 e degli elementi di 𝐷. Se non specificato diversamente, di seguito, l’indice 𝑖 scorre dalla posizione 1 alla posizione 𝑛 della struttura dati trattata (1 ≤ 𝑖 ≤ 𝑛).

𝐵𝑃[1, 𝑛] `e un bit-vector ciclico in cui, 𝐵𝑃[𝑖] = 1 se e solo se la 𝑖-esima posizione di 𝑠 corrisponde

al primo carattere di una stringa in 𝐸. Essendo 𝐵𝑃 ciclico, l’1 che identifica il primo carattere della

stringa in 𝐸 prefisso della prima frase in 𝑠 `e in posizione (𝑛 − 𝑤 + 1).

𝐵BWT[1, 𝑛] `e un bit-vector ciclico in cui, per ogni suffisso proprio di una frase, lungo almeno 𝑤,

𝐵BWT[𝑖] = 1 denota che l’𝑖-esimo carattere nella BWT `e il primo simbolo a precedere un’occorrenza

di tale suffisso in 𝑠. Non `e necessario costruire la BWT di 𝑠 per ottenere 𝐵BWT: si costruisce il SA

e l’array LCP dell’insieme 𝐷 dopo aver appeso un simbolo terminatore univoco a ciascuno dei suoi elementi; si etichetta ogni suffisso con la frequenza in 𝑃 della frase che contiene tale suffisso; quindi si scansionano gli array ignorando i suffissi che sono elementi di 𝐷 (frasi intere) oppure di lunghezza minore di 𝑤 (terminatori esclusi) e aggregando le frequenze dei suffissi che differiscono solo per i terminatori.

Per la stringa ciclica 𝑠 = GATTACAT#GATACAT#GATTAGATA## in esempio si ha 𝐵𝑃 = [0000100100001001000001000010] e

𝐵BWT= [1111110110111110111110110111].

CAPITOLO 5. Prefix-Free Parsing 5.3. Prefix-Free Parsing come struttura dati 𝑀 `e una struttura dati tale per cui 𝑀[𝑖] fornisce (i) la lunghezza dell’𝑖-esimo suffisso proprio 𝛼 di una frase lungo almeno 𝑤; (ii) l’intervallo lessicografico delle frasi inverse che iniziano con 𝛼 invertito. Le lunghezze vengono memorizzate durante la costruzione di 𝐵BWT, e gli intervalli

lessicografici invertendo e ordinando le frasi.

La Figura 5.5 riporta la struttura dati 𝑀 per la stringa di esempio. Per ogni riga si ha il suffisso proprio invertito lungo almeno 𝑤, la sua lunghezza, e infine, l’intervallo lessicografico delle frasi inverse che iniziano con tale suffisso.

1 ## 2 [0] 2 CATAG# 6 [2] 3 CATTAG# 7 [3] 4 GATTAG# 7 [4] 5 ##A 3 [0] 6 CA 2 [2, 3] 7 GA 2 [4] 8 #TA 3 [1] 9 ##ATA 5 [0] 10 CATA 4 [2] 11 CATTA 5 [3] 12 GATTA 5 [4] 13 #TAC 4 [1] 14 ##ATAG 6 [0] 15 CATAG 5 [2] 16 CATTAG 6 [3] 17 GATTAG 6 [4] 18 #T 2 [1] 19 ##AT 4 [0] 20 CAT 3 [2, 3] 21 GAT 3 [4] 22 CATT 4 [3] 23 GATT 4 [4]

Figura 5.5: Struttura dati𝑀. Esempio.

𝑇 `e un wavelet tree(18) _{calcolato sulla BWT degli identificatori delle frasi in 𝑃, in con le fo-}

glie sono etichettate da sinistra a destra con l’insieme degli identificatori delle frasi in ordine co- lessicografico(19)_{. In questo modo, le foglie di 𝑇 etichettate con gli identificatori delle frasi che}

terminano con lo stesso suffisso 𝛼 sono consecutive.

La Figura 5.6 riporta il wavelet tree 𝑇 e la struttura con cui viene rappresentato, per la stringa di esempio. L’albero `e ruotato per allineare le foglie con le righe corrispondenti della griglia di rappresentazione.

2 1 3 0 4 2 0 3 4 1 1 𝐷[2] = AGATA## 𝐷[1] = ACAT# 𝐷[3] = T#GATAC 𝐷[0] = ##GATTAC 𝐷[4] = T#GATTAG BWT(𝑃) - gli elementi di 𝐷 sono ordinati lessicograficamente

gli elementi di 𝐷 sono or dinati co-lessicograficamente 011100 011 𝐷 [2] 𝐷 [1] 101 𝐷 [3] 01 𝐷 [0] 𝐷 [4] 𝑇

Figura 5.6: Struttura dati𝑇. Esempio.

𝜋 `e la permutazione che mappa per ciascuna frase la sua posizione nella BWT di 𝑃 con la propria posizione in 𝑃 stesso.

Per l’esempio considerato, essendo 𝑃 = [0,1,3,1,4,2] e BWT(𝑃) = [2,0,3,4,1,1] risulta: 𝜋(1) = 6, 𝜋(2) = 1, 𝜋(3) = 3, 𝜋(4) = 5, 𝜋(5) = 2, 𝜋(6) = 4.

Esempio.

Una volta calcolate le strutture sopra elencate possiamo effettuare query rapide riguardo la longest common extension (LCE), il suffix array, il longest common prefix (LCP) e la BWT come descritto in seguito. Innanzitutto, considerando sempre la stringa 𝑠[1, 𝑛] e l’array 𝐵𝑃, dato l’indice 1 ≤ 𝑖 ≤ 𝑛

(18)_{Il wavelet tree `e una struttura di dati succinta per memorizzare le stringhe in uno spazio compresso, e che generalizza le}

operazioni di rank e select definite su bit-vector o alfabeti arbitrari.

(19)_{L’ordine co-lessicografico di un insieme di stringhe corrisponde alla sequenza in cui le stringhe risultano ordinate}

CAPITOLO 5. Prefix-Free Parsing 5.3. Prefix-Free Parsing come struttura dati possiamo identificare, prima l’indice 1 ≤ 𝑗 ≤ | 𝑃 | della frase 𝑝𝑗 contenente il carattere 𝑠[𝑖], come

𝑗 = 𝐵𝑃.rank(𝑖) mod | 𝑃 |, e la posizione di 𝑠[𝑖] calcolando il suo offset in 𝑝𝑗. Effettuando infine un

accesso su 𝑃 per identificare 𝑝𝑗e un accesso su 𝐷, possiamo ritornare il carattere 𝑠[𝑖].

LCE-query. Dati due indici1 ≤ 𝑖 ≤ 𝑛 e 1 ≤ 𝑗 ≤ 𝑛, LCE(𝑖, 𝑗) ritorna la lunghezza del longest common prefix di 𝑠[𝑖, 𝑛] e 𝑠[𝑗, 𝑛]. La lunghezza viene calcolata utilizzando 𝐵𝑃 per identificare le

frasi contenenti 𝑠[𝑖] e 𝑠[𝑗] e il loro offset nelle rispettive frasi. Si denotano con 𝛼 e 𝛽 i suffissi delle frasi che iniziano con 𝑠[𝑖] e 𝑠[𝑗], quindi | 𝛼 |, | 𝛽 | > 𝑤. Sappiamo che 𝛼 e 𝛽 non sono prefissi appropriati l’uno dell’altro, quindi i casi possibili sono due:

1. 𝛼[𝑘] ≠ 𝛽[𝑘] per un valore 𝑘 < min(| 𝛼 |, | 𝛽 |) e quindi LCE(𝑖, 𝑗) = | LCP (𝛼, 𝛽) |;

2. 𝛼 = 𝛽 e quindi LCP(𝑖, 𝑗) = | 𝛼 | + LCE (𝑖 + | 𝛼 |, 𝑗 + | 𝛼 |), dove 𝑠[𝑖 + | 𝛼 |, 𝑛] e 𝑠[𝑗 + | 𝛼 |, 𝑛] sono entrambi suffissi di 𝑠 che iniziano immediatamente dopo una stringa elemento di 𝐸. In questo caso `e possibile memorizzare una tabella hash che mappa la posizione di inizio di ciascun suffisso con il suo rango lessicografico di tutti i suffissi, un array LCP dei suffissi e una struttura dati che supporta le Range-Minimum Query (RMQ) sull’array LCP.

Per la stringa 𝑠 in esempio la query LCE(4, 12) = 9 in quanto il longest common prefix tra i suffissi

𝑠[4, 28] = TACAT#GATACAT#GATTAGATA## e 𝑠[12, 28] = TACAT#GATTAGATA##

`e TACAT#GAT. Secondo la procedura descritta, per il suffisso 𝛼 = 𝛽 = TAC si ha quindi che LCE(4, 12) = 3 + LCE(7, 15). La Figura 5.7 riporta i suffissi 𝑠[𝑖, 𝑛] che iniziano dopo un elemento di 𝐸, il loro rango lessicografico e l’array LCP. La tabella hash per l’esempio mappa gli indici ordinati [1, 7, 10, 15, 18, 24] con il rispettivo rango lessicografico [4, 0, 3, 1, 5, 2]. Per stabilire il risultato di LCE(7, 15) si recupera il valore della lunghezza del longest common prefix tra i suffissi di rango 0 e 1, in quanto 7 e 15 sono mappati rispettivamente con 0 e 1, che risulta 6. Quindi alla fine si ottiene che LCE(4, 12) = 3 + LCE(7, 15) = 3 + 6 = 9.

𝑖 rango 𝑠[𝑖 ∶28] LCP 7 0 AT#GATACAT#GATTAGATA## 0 15 1 AT#GATTAGATA## 6 24 2 ATA## 2 10 3 GATACAT#GATTAGATA## 0 1 4 GATTACAT#GATACAT#GATTAGATA## 3 18 5 GATTAGATA## 5 Figura 5.7 Esempio.

SA-query. Una query SA[𝑖] ritorna la posizione dell’𝑖-esimo suffisso lessicograficamente minore in 𝑠. Dato l’indice 𝑖 `e possibile utilizzare 𝑟 = 𝐵BWT.rank(𝑖) per determinare il rango lessicogra-

fico 𝑟 (partendo da zero) del suffisso proprio 𝛼 di una frase lungo almeno 𝑤 che inizia in SA[𝑖]; e 𝑟

'

= 𝑖 − 𝐵BWT.select(𝐵BWT.rank(𝑖)) per ottenere il rango lessicografico 𝑟

'

(partendo da 0) di

𝑠[SA[𝑖], 𝑛] tra i suffissi di 𝑠 che iniziano con 𝛼. Dopodich´e si accede prima ad 𝑀 per trovare la lunghezza di 𝛼 e l’intervallo co-lessicografico delle frasi che terminano con 𝛼; e poi a 𝑊 per trovare l’indice 𝑘 della 𝑗-esima frase nell’intervallo co-lessicografico che appare nella BWT(𝑃).

CAPITOLO 5. Prefix-Free Parsing 5.4. Performance del Prefix-Free Parsing

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