Implementazione del Prefix-Free Parsing - Identificazione reference-free e assembly-free di pol

𝑍 con rango 19. Il suffisso TAC in #𝑠 $𝑤 _{risulta essere preceduto da T quando occorre come}

suffisso di #GATTAC ∈ 𝐷, il quale ha un rango 0 in 𝐷, e da A quando occorre come suffisso di T!GATAC∈ 𝐷, il quale ha un rango 3 in 𝐷. Applicando il Lemma 5.7 e attraverso l’ordinamento lessicografico dei suffissi di 𝑃 = [0,1,3,1,4,2] riportato in Figura 5.2, si ha che il suffisso “1 3 1 4 2” successivo a “0” `e lessicograficamente minore al suffisso “1 4 2” successivo a “3”, quindi T precede A nella BWT di 𝑠

'

che alla fine risulta: ATTTTTTCCGGGGAAA!$!AAATATAA.

#GATTACAT!GATACAT!GATTAGATA$$ ACAT!GATACAT!GATTAGATA$$ ACAT!GATTAGATA$$ AGATA$$ T!GATACAT!GATTAGATA$$ T!GATTAGATA$$ 0 1 3 1 4 2 1 3 1 4 2 1 4 2 2 3 1 4 2 4 2

Figura 5.2: Suffissi del parser𝑃 = [0,1,3,1,4,2] ordinati lessicograficamente.

Poich´e `e necessario solo il dizionario 𝐷 e le frequenze dei suoi elementi in 𝑃 per costruire e memorizzare, attraverso il Lemma 5.6, le sottostringhe della BWT di 𝑠

'

composte da tutti i caratteri mappati agli elementi di 𝑍 per cui 𝛽 ha prodotto un solo carattere distinto; `e richiesto uno spazio proporzionale alla lunghezza totale degli elementi di 𝐷. Sebbene poi, le sottostringhe dei caratteri mancanti nell’ordine in cui appaiono nella BWT, costruite mediante il Lemma 5.7, possono occu- pare pi`u spazio della combinazione di 𝐷 e 𝑃; man mano che vengono generate possono essere con- catenate alle sequenze del passaggio precedente, utilizzando quindi uno workspace proporzionale alla somma della lunghezza di 𝑃 e gli elementi di 𝐷.

Supponendo quindi di poter riconoscere rapidamente le stringhe in 𝐸, possiamo calcolare rapidamente 𝐷 e 𝑃 con una scansione su 𝑠. Attraverso 𝐷 e 𝑃, con i Lemmi 5.6 e 5.7, possiamo calcolare la BWT di 𝑠

'

= 𝑠$ ordinando i suffissi degli elementi di 𝐷 e i suffissi di 𝑃. In quanto ad oggi esisto- no algoritmi in grado di eseguire l’ordinamento in tempo e spazio lineare quando si lavora nella memoria interna, vale il risultato teorico espresso nel Teorema 5.1.

5.2 Implementazione del Prefix-Free Parsing

Fornita la dimensione 𝑤 della finestra 𝑊 e selezionato un numero primo 𝑝, l’insieme 𝐸, descritto nella sezione precedente, viene definito come l’insieme delle stringhe 𝑒 tali che |𝑒| = 𝑤 e per cui 𝐻(𝑒) mod 𝑝 = 0, dove 𝐻 `e la funzione hash denominata come Karp-Rabin fingerprint(17)_{. I para-}

𝑒 𝑊

𝑠

𝜑

frase precedente frase successiva

Figura 5.3: Rappresentazione dello scorrimento della finestra𝑊 sulla stringa 𝑠. La frase attuale 𝜑 terminata intercorre tra l’inizio della precedente occorrenza di 𝑒 ∈ 𝐸 e la fine di 𝑊 .

(17)_{La fingerprint `e una sequenza alfanumerica, o una stringa di bit, di lunghezza prefissata che identifica un certo file con le}

caratteristiche intrinseche stesse del file. La (Karp-)Rabin fingerprint, proposta da Rabin [48] nel 1981, `e una funzione di rolling hash utilizzata come fingerprint e definita tramite polinomi su un campo finito. La Karp-Rabin fingerprint, ad esempio, viene utilizzata per l’organizzazione dei filesystem oppure per il pattern-matching.

CAPITOLO 5. Prefix-Free Parsing 5.2. Implementazione del Prefix-Free Parsing metri 𝑤 e 𝑝 influenzano la dimensione del dizionario di frasi distinte e il numero di frasi nel parser. Man mano che 𝑊 scorre sulla stringa 𝑠 (vedi Figura 5.3) la frase attuale, qui indicata con 𝜑, corrisponde alla sottostringa che intercorre tra l’inizio della precedente occorrenza di una stringa 𝑒 ∈ 𝐸 e la fine della stringa di 𝑊 . I risultati dell’applicazione di 𝐻 sulla sottostringa coperta da 𝑊 (𝐻(𝑊 )) e sull’intera frase attuale che `e appena stata processata (𝐻(𝜑)) vengono memorizzati. Ogni volta che risulta 𝐻(𝑊 ) = 0 mod 𝑝, la frase attuale termina e la frase successiva inizia dall’inizio della finestra 𝑊 . Inoltre, si antepone un carattere null (che pu`o essere univoco senza la distinzione fatta nella teoria della sezione precedente) alla prima frase (precedentemente indicato con “#”) e si appendono 𝑤 copie del carattere null all’ultima frase (ossia la precedente sequenza $𝑤_).

L’algoritmo tiene traccia, sia dei risultati della funzione hash calcolati sulle frasi contenute nel dizionario 𝐷 attraverso l’insieme 𝐷

'

, che della loro frequenza. Pi`u precisamente, quando la frase attuale 𝜑 termina, il risultato della funzione hash 𝐻(𝜑) viene appeso alla lista 𝑃, e viene verificato se 𝐻(𝜑) `e presente nel dizionario 𝐷

'

. Se 𝐻(𝜑) ∉ 𝐷

'

allora 𝜑 viene aggiunta a 𝐷 e la sua frequenza impostata a 1; se invece 𝐻(𝜑) = 𝐻(𝜑

'

) ∈ 𝐷

'

viene verifico che le due frasi siano effettivamente le stesse, 𝜑 = 𝜑

'

∈ 𝐷, e si incrementa la sua frequenza.

Al termine dello scorrimento della finestra 𝑊 sull’intera stringa 𝑠 e della funzione di parsing, sono stati generati il dizionario 𝐷 e il parser 𝑃 = 𝑝1, 𝑝2, … , 𝑝ℎ, dove ogni frase 𝑝𝑖, con 1 ≤ 𝑖 ≤ ℎ, `e

rappresentata dal proprio risultato della funzione hash. Il passaggio successivo consiste nell’ordinamento lessicografico di 𝐷 e nella sostituzione di ciascuna frase 𝑝𝑖con il rango lessicografico di 𝑝𝑖

in 𝐷. Cos`ı facendo si ottiene il parser come una sequenza di interi di 4 byte ciascuno. La procedura sviluppata da Boucher et al. scrive il dizionario sul disco frase dopo frase nell’ordine lessicografico e utilizzando un terminatore alla fine di ciascuna frase, e memorizza, su un file separato, la frequenza di ciascuna frase con un intero di 4 byte. L’utilizzo di 4 byte per ogni intero memorizzano non garantisce la migliore compressione possibile del file, ma permette di processare pi`u rapidamente i valori nei passaggi successivi. Infine, per elaborare gli elementi di 𝑍 che sono anche elementi di 𝐷, viene memorizzato un array 𝐴 di lunghezza ℎ = | 𝑃 | tale che, per 1 ≤ 𝑖 ≤ ℎ, 𝐴[𝑖] corrisponde al (𝑤 + 1)-esimo carattere di 𝑝𝑖a partire dalla fine, ossia 𝐴[𝑖] = 𝑝𝑖[| 𝑝𝑖| − (𝑤 + 1)].

Successivamente viene calcolata la BWT del parser 𝑃 (in cui gli elementi sono interi da 4 byte) attraverso l’algoritmo SACA-K [49], che tra gli algoritmi che operano in tempo lineare, `e quello che utilizza uno workspace minore. Invece di memorizzare la stringa BWT(𝑃) = 𝐵 = 𝑏1, 𝑏2, … , 𝑏ℎ, per

ogni frase 𝑑𝑖 contenuta nel dizionario 𝐷 lessicograficamente ordinato, si memorizza la lista delle

posizioni degli elementi di 𝐵 in cui appare 𝑑𝑖; tale lista viene anche denominata inverted-list della

frase 𝑑𝑖(vedere Figura 5.4(a)). S osservi che, la lunghezza della inverted-list di una frase corrisponde

alla sua frequenza, ed `e possibile quindi memorizzare la concatenazione delle inverted-list per un totale di 4ℎ byte. Considerata 𝑝

'

𝑖la frase che precede 𝑏𝑖in 𝑃, in questo passaggio vengono permutati

i valori di 𝐴 cos`ı che da adesso 𝐴[𝑖] = 𝑝

'

𝑖[| 𝑝

'

𝑖| − (𝑤 + 1)] (vedere Figura 5.4(b)).

L’ultima fase dell’algoritmo calcola la BWT di 𝑠. Anche in questo caso, la pratica si discosta un po’ del Prefix-Free Parsing: invece di ordinare lessicograficamente i suffissi 𝑧 di 𝐷 per cui | 𝑧 | ≥ 𝑤 vengono ordinati tutti i suffissi 𝑧 escludendo successivamente quelli con lunghezza inferiore o uguale a 𝑤. L’algoritmo utilizzato da Boucher et al. nell’implementazione `e gSACAK [43], che calcola il SA e l’array LCP dell’insieme delle frasi contenute nel dizionario 𝐷. Procedendo poi come descritto nella sezione precedente, se durante la scansione dell’insieme ordinato 𝑍 si incontra 𝑧

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