rango lessicografico) frase della BWT(𝑃) con la sua posizione in 𝑃 otteniamo la frase in 𝑃 che contiene la posizione di partenza del 𝑗-esimo suffisso lessicograficamente minore di 𝑠 che inizia con 𝛼; ed essendo a conoscenza di | 𝛼 | da 𝑀, possiamo usare 𝐵𝑃 per trovare SA[𝑖].
Per la stringa 𝑠 in esempio il 25-esimo (𝑖 = 25) suffisso lessicograficamente mi- nore `e dato da 𝑠[12, 28] = TACAT#GATTAGATA##, quindi SA[25] = 12. Secondo la procedura descritta, per ottenere il risultato alla query SA[25], si inizia calcolando 𝑟 = 𝐵BWT.rank(25) = 20
e 𝑟
'
= 25 − 𝐵BWT.select(20) = 25 − 24 = 1. Accedendo poi a 𝑀[20] = (3, [2, 3]) si ottiene il va-lore di 𝑘 = 2, e, in quanto 𝜋(𝑘 + 1) = 𝜋(3) = 3 e il primo valore di 𝑀[20] `e 3, si ha che il suffis- so 𝑠[SA[25]] `e il terzo carattere dalla fine della frase 𝑃[3] = T#GATAC. Quindi, essendo 𝑤 = 2, l’indice del bit che precede il terzo 1 in 𝐵𝑃 corrisponde al nostro risultato, SA[25] = 12.
Esempio.
LCP-query e BWT-query. L’array LCP[1, 𝑛] di 𝑠 viene calcolato impostando, per 1 < 𝑖 ≤ 𝑛 il valore calcolato come LCP[𝑖] = LCE (SA[𝑖 − 1], SA[𝑖]), e LCP[1] = 0. `E quindi possibile ri- spondere a query LCP attraverso query SA e LCE. Infine, `e banalmente possibile ricavare il valore BWT[𝑖] calcolando SA[𝑖] e ritornando 𝑠[SA[𝑖] − 1], ma `e inulte applicare 𝜋 in quanto, una volta trovato l’indice della frase contenente BWT[𝑖] in BWT(𝑃), possiamo estrarre BWT[𝑖] direttamente dall’insieme 𝐷.
5.4
Performance del Prefix-Free Parsing
Gli esperimenti svolti da Boucher et al. per valutare le performance del Prefix-Free Parsing, hanno mostrato una notevole capacit`a nella compressione dei dati in input e una quantit`a di memoria e di tempo, per calcolare la BWT, inferiore a quella necessaria ad un algoritmo basato sul suffix array. Si ricorda che la scelta dei parametri 𝑤 e 𝑝, che corrispondono, rispettivamente, alla dimensione della finestra che scorre sulla stringa in input e al numero primo su cui viene calcolato il modulo della fingerprint, influiscono sulla dimensione del dizionario e sul numero di frasi del parser. In generale, sia per il tempo di esecuzione che per il picco di memoria richiesto, il valore ottimale di 𝑤 e 𝑝 differisce e dipende dall’input.
Le osservazioni seguenti fanno riferimento agli esperimenti realizzati da Boucher et al. su un database di genomi della Salmonella per un numero di genomi nell’intervallo [50, 100, 500, 1 000, 5 000, 10 000] e per differenti combinazioni di valori assegnati ai parametri 𝑤 e 𝑝, (𝑝, 𝑤) = {(6, 20), (8, 50), (10, 100)}. La somma dello spazio occupato dai dizionari e dai parser calcolati su tale database (vedere [46, Tabella 4]) `e compreso tra il 14 e il 44% dello spazio richiesto dai file non compressi. Considerando, per ciascuna combinazione del numero di genomi e dei parametri richiesti, il valore della percentuale pi`u basso, si osserva che tale percentuale diminuisce all’aumentare del numero di genomi. In particolare, il dataset con 10 000 geni richiede circa 50 GB quando non compresso, ma per 𝑤 = 10 e 𝑝 = 100 il dizionario e il parser, insieme, richiedono solo circa 7 GB; e l’elaborazione di 7 GB di dati pu`o tranquillamente avvenire all’interno della RAM di un generico computer attuale. Gli autori hanno inoltre utilizzato i risultati di un tool, denominato simplebwt, come base di ri- ferimento per confrontare e valutare le performance del tempo di calcolo e dei picchi di memoria registrati durante il calcolo della BWT attraverso le il dizionario e il parser del PFP, sullo stesso
CAPITOLO 5. Prefix-Free Parsing 5.4. Performance del Prefix-Free Parsing database dei genomi della Salmonella dei test precedenti. Il simplebwt calcola la BWT di una strin- ga calcolando prima il suffix array attraverso l’algoritmo SACA-K [49], che `e lo stesso che viene utilizzato all’interno dell’implementazione del Prefix-Free Parsing per calcolare la BWT del parser (descritto nella Sezione 5.2). La scelta dell’impiego di questo algoritmo, rispetto ad altri, `e per la sua velocit`a di calcolo e la richiesta di uno workspace costante. I risultati ottenuti (vedere [46, Tabella 5]) mostrano che i picchi di memoria necessaria per calcolare la BWT dal dizionario e dal parser sono da 4 a 10 volte inferiori rispetto a quelli della memoria richiesta da simplebwt. Per le coppie di valori assegnati ai parametri 𝑝 e 𝑤 precedentemente indicate e al variare del numero di genomi compreso tra 50 e 10 000 nell’intervallo definito in precedenza, il picco di memoria pi`u basso si `e verificato sempre per 𝑤 = 6 e 𝑝 = 20; mentre il tempo di esecuzione minore si `e verificato mag- giormente nella combinazione con 𝑤 = 10 e 𝑝 = 100, dove, in particolare per i database con 5 000 e 10 000 genomi, la BWT `e stata creata, attraverso le informazioni elaborate dal PFP, con un fattore rispettivamente del 2, 4 e del 4, 3 inferiore a quello richiesto da simplebwt.
Per analizzare il tempo, il picco di memoria e lo spazio totale richiesto dall’implementazione delle strutture dati ausiliarie necessarie a permettere al PFP di supportare query rapide, Boucher et al. hanno confrontato la loro implementazione (pfp) con una struttura basata su suffix tree compressi (sdsl) e una fondata sui blocchi dei suffix tree (bt). Gli autori hanno utilizzano le sei collezioni di 50, 100, 500, 1 000, 5 000 e 10 000 genomi della Salmonella su cui sono stati effettuati anche i test delle performance del PFP, e dieci insiemi contenenti un numero di sequenze differenti da 1 a 1 000, con crescita esponenziale, del cromosoma 19 (proveniente dal 1KGP) e in cui ogni insieme `e un super-insieme del precedente. `E per`o importante evidenziare che la sdsl ha impiegato oltre 15 ore di esecuzione per calcolare le informazioni sulla collezione di 10 000 geni della Salmonella e sull’insieme di 1 000 sequenze del cromosoma 19; mentre la bt non `e stata in grado di elaborare le collezioni con oltre 100 geni della Salmonella con pi`u di 8 sequenze differenti del cromosoma 19.
Dai risultati ottenuti si nota che il tempo di costruzione della pfp `e sempre minore di quello richiesto dalle altre due strutture compresse; e la massima speed-up della pfp risulta pari ad un fattore di 29, 2 e 7, 7 rispetto alla sdsl per elaborare rispettivamente la collezione del cromosoma 19 e della Salmonella, e pari ad un fattore di 210 e 202 rispetto alla bt per elaborare rispettivamente le stesse collezioni precedenti [47, Figura 3(a), 3(c)]. Inoltre, su entrambi i dataset, la pfp presenta un picco di memoria richiesta sempre inferiore a quello delle altre due strutture compresse; e uno spazio di memoria maggiore rispetto alla sdsl e alla bt, escluso per le collezioni con oltre 64 sequenze differenti del cromosoma 19, in cui la pfp occupa uno spazio inferiore [47, Figura 3(b), 3(d)].
Infine, per testare il tempo di risposta alle query impiegato dalle strutture dati prese in considera- zione, sono stati generati dieci mila indici casualmente distribuiti sulla dimensione dell’input per le SA e le LCP-query, e dieci mila coppie di incidi (sempre casualmente distribuiti) per le LCE-query. La pfp `e risultata sempre pi`u rapida delle altre due strutture compresse per le LCE-query, e su tutti gli insiemi del cromosoma 19 e sulle collezioni con oltre 100 genomi della Salmonella per le SA e le LCP-query [47, Figura 4].
Fornite le basi teoriche e le tecniche di implementazione sia del framework positional clustering, descritte nel Capitolo 4, che dell’algoritmo di pre-processing Prefix-Free Parsing (PFP), appena trattate, di seguito si vuole introdurre l’analisi svolta sull’utilizzo del PFP alla base dell’algoritmo di variant calling del positional clustering per individuare i polimorfismi di singolo nucleotide (SNP).
CAPITOLO 5. Prefix-Free Parsing 5.4. Performance del Prefix-Free Parsing
CAPITOLO
6
Variant calling con il Prefix-Free Parsing
Come descritto nel Capitolo 4, fornito in input un insieme di read, la prima versione della pipe- line presentata da Prezza et al. [39], crea inizialmente l’eBWT e successivamente il suffix array generalizzato (GSA) e l’array LCP per localizzare i cosiddetti eBWT positional cluster, che infine vengono elaborati per stabilire se effettivamente riflettono un polimorfismo a singolo nucleotide (SNP). L’ammontare di spazio e di tempo richiesto per la creazione delle strutture dati elencate, soprattutto per un insieme di dati massiccio come pu`o essere quello proveniente da un processo di sequenziamento, `e un punto debole dell’intera procedura. Gli stessi autori, un anno dopo, ten- tando di ridurre i tempi di esecuzione e introducendo la possibilit`a di individuare anche le INDEL oltre che gli SNP, hanno hanno sviluppato una nuova versione del framework [40]. Elaborando i dati grezzi, la nuova pipeline crea inizialmente la eBWT della collezione in input come la pipeline originaria, e poi, anzich´e memorizzare l’array LCP e calcolare il GSA, utilizza, rispettivamente, un bit-vector per localizzare i cluster nella eBWT e la FL-mapping (vedi Sezione 3.2) per ricavare le medesime informazioni precedentemente estratte dal GSA.
La nuova versione del framework risulta sia pi`u veloce nella sua esecuzione, che pi`u efficiente per quanto riguarda la quantit`a di memoria su disco utilizzata, diminuita di un ordine di grandezza grazie alle strutture dati compresse. A convalidare il miglioramento delle performance vi sono i ri- sultati delle validazioni, effettuate utilizzando entrambe le procedure, di una collezione di dati reali con copertura 20× riportate da Prezza et al. nel loro studio [40]. Gli esiti degli esperimenti eviden- ziano che il tempo di calcolo delle strutture necessarie `e stato ridotto da 14 ore a 2 ore circa, mentre il tempo di analisi `e aumentato da 30 minuti a un’ora e 30 minuti circa. Sebbene con il nuovo algo- ritmo il tempo di analisi `e maggiore, in quanto oltre agli SNP vengono individuati anche le INDEL, il tempo complessivo `e stato comunque ridotto di 12 ore. Invece, per quanto riguarda la memoria utilizzata, si osserva che lo spazio su disco `e stato ridotto da 73 GB a 9, 5 GB, e contemporaneamen- te l’utilizzo della memoria RAM `e cresciuta da 1 GB a 8, 3 GB. Nonostante tali migliorie, secondo ulteriori esperimenti, e come descritto nella Sezione 4.3, il tempo richiesto per calcolare la eBWT
CAPITOLO 6. Variant calling con il Prefix-Free Parsing
corrisponde comunque al 56 − 60% del tempo complessivo impiegato dal positional clustering tra la costruzione delle strutture e il tempo di analisi.
L’introduzione della procedura di pre-processing del Prefix-Free Parsing (PFP) potrebbe per- mettere di ridurre ulteriormente il tempo di calcolo complessivo e la memoria utilizzata dalla pi`u recente pipeline di Prezza et al. per calcolare la BWT. Lo scopo di Boucher et al. `e stato fin da subito quello di utilizzare le informazioni calcolate dal Prefix-Free Parsing durante la fase di pre- processing in modo calcolare successivamente la BWT in un tempo lineare rispetto alla lunghezza della stringa in input, pur richiedendo uno workspace proporzionale alla somma della lunghezza di 𝑃 e degli elementi contenuti in 𝐷 (Teorema 5.1 nella Sezione 5.1).
Il Prefix-Free Parsing risulta essere pi`u efficiente nella costruzione della BWT quando confronta- to con un algoritmo basato su SACA-K [49], con picchi di memoria per calcolare la BWT attraverso il dizionario e il parser da 4 a 10 volte inferiori rispetto a quelli della memoria richiesta da SACA-K. Ulteriormente, il PFP si mostra pi`u performante e rapido nel rispondere a query sulle informazioni del SA, LCP ed LCE, quando confrontato con strutture dati basate sui suffix tree compressi oppure sui blocchi dei suffix tree.
Analizzando i promettenti esiti degli esperimenti svolti da Boucher et al. per valutare le per- formance del PFP sia per calcolare la BWT che per il supporto di query efficienti (Sezione 5.4), la domanda che sorge spontaneamente, e alla quale si intende rispondere con questo studio, `e se esiste o meno la possibilit`a di eseguire un processo di variant calling su una collezione di read attraverso le informazioni contenute all’interno del Prefix-Free Parsing. Questo capitolo ha l’obiet- tivo di mostrare come sia possibile modificare l’algoritmo del Prefix-Free Parsing per utilizzare il solo dizionario 𝐷 e il parser 𝑃, evitando l’intero calcolo della BWT e costruendo ulteriori strutture ausiliarie, individuare gli SNP nella collezione di read fornita in input sulla base dell’idea del fra- mework positional clustering. La procedura si basa su due metodi, decritti in seguito, attraverso cui ottenere le informazioni dal PFP e tre fasi consecutive da svolgere su una collezione di read:
Fase di pre-processing, nella quale viene creata la stringa𝑠[1, 𝑛] concatenando i read e sulla quale viene eseguito il parsing per ottenere il dizionario 𝐷 e il parser 𝑃 (descritta in Sezione 6.1 e schematizzata in viola in Figura 6.1).
Localizzazione degli eBWT cluster, passaggio in cui attraverso i minimi locali dell’array LCP, calcolato con uno dei due metodi di seguito presentati, si localizzano gli eBWT cluster (trattata in Sezione 6.2 e schematizzata in verde in Figura 6.1).
Identificazione degli SNP, fase in cui si calcola il contesto destro e sinistro per ogni eBWT cluster per stabilire se questo rappresenta o meno uno SNP nella collezione di dati in input (descritta in Sezione 6.3 e schematizzata in rosa in Figura 6.1).
Il framework positional clustering, indifferentemente da quale versione della pipeline conside- riamo, `e basato sostanzialmente sulle informazioni contenute nella (e)BWT (ebwt), nel GSA (gsa) e nell’array LCP (lcp) di una collezione di read in input. Ricordando la Definizione 4.1, per una posizione 1 ≤ 𝑖 ≤ 𝑛 di un genoma 𝐺, l’eBWT cluster di 𝑖 corrisponde alla sottostringa ebwt[𝑎, 𝑏] tale per cui i suffissi contenuti nell’intervallo gsa[𝑎, 𝑏], sono prefissati dallo stessa stringa detta contesto, che compare univocamente in 𝐺. Lo scopo `e quello di mostrare come possiamo utilizza- re le informazioni rappresentate con il dizionario 𝐷 e il parser 𝑃, prima per localizzare gli eBWT cluster, e poi per stabilire la presenza di possibili SNP nell’insieme di read.
CAPITOLO 6. Variant calling con il Prefix-Free Parsing
Collezione 𝑆 di 𝑚 read.
Creazione della stringa 𝑠[1, 𝑛] concatenando gli 𝑚 read a ciascuno dei quali si appendende un carattere terminatore.
Parsing della stringa 𝑠 per ottenere il dizionario 𝐷 e il parser 𝑃.
Localizzazione degli eBWT cluster tramite uno dei due Metodi.
Localizzazione degli eBWT cluster attraverso i minimi locali dell’array lcp'
Zche memorizza
la lungehzza del LCP in comune tra due suffissi consecutivi nell’array SAZconsiderando
il carattere terminatore univoco. Calcolo dei soli caratteri degli eBWT cluster ebwt[𝑎𝑒, 𝑏𝑒] attraverso la teoria del PFP.
Creazione delle cinque strutture ausiliarie per il supporto delle query.
Localizzazione degli eBWT cluster attraverso i minimi locali dell’array lcpM2che memorizza il
risultato delle LCP-query sui suffissi consecutivi di 𝑠 considerando il carattere terminatore univoco.
Cacolo dei soli caratteri degli eBWT cluster ebwt[𝑎, 𝑏] attraverso le BWT-query.
Per ogni eBWT cluster con almeno due caratteri distinti 𝑐1e 𝑐2(ognuno almeno
mincovvolte) si procede come segue.
Estrazione del prefisso 𝑅 di 𝑘right
caratteri con uno dei due metodi.
Estrazione di 𝑅, per ebwt[𝑎𝑒, 𝑏𝑒], dall’𝑖-esimo
suffisso lessicograficamente minore contenuto in SAZ[𝑎, 𝑏], per un indice 𝑎 ≤ 𝑖 ≤ 𝑏.
Estrazione di 𝑅, per ebwt[𝑎, 𝑏], effettuando una SA-query per l’𝑖-esimo suffisso lessicografi- camente minore di 𝑠 per un indice 𝑎 ≤ 𝑖 ≤ 𝑏. Calcolo delle stringhe consensus 𝐿1e 𝐿2che
precedono e includono rispettivamente 𝑐1
e 𝑐2, scansionando la collezione dei read 𝑆.
Calcolo dell’allinemento ottimale delle stringhe 𝐿1e 𝐿2.
Produzione in output delle sequenze 𝐿1⋅ 𝑅 e 𝐿2⋅ 𝑅 che evidenziano uno SNP.
Metodo 1 Metodo 2 Metodo 1 Metodo 2 Fase di pre-processing Localizzazione degli eBWT cluster Identificazione degli SNP
Figura 6.1: Schema dei due metodi (Metodo 1 sul lato sinistro e Metodo 2 sul destro), studiati per identificare i polimorfismi a singolo nucleotide (SNP) con le informazioni contenute nel dizionario 𝐷 e nel parser 𝑃 del Prefix-Free Parsing e localizzando gli eBWT cluster.
CAPITOLO 6. Variant calling con il Prefix-Free Parsing 6.1. Fase di pre-processing