Quality value based models and methods for sequencing data

Isolata per la prima volta da Friedrich Miescher nel 1869 ed identificata nel 1953 da James Watson e Francis Crick, la molecola del DNA (acido desossiribonucleico) umano ha richiesto più di 50 anni perchè fosse a disposizione della comunità internazionale per studi e analisi approfondite. Le prime tecnologie di sequenziamento sono apparse attorno alla metà degli anni 70, tra queste quella di maggiore successo è stata la tecnologia denominata Sanger rimasta poi lo standard di fatto per il sequenziamento fino a che, agli inizi degli anni 2000, sequenziatori battezzati di nuova generazione (Next Generation Sequencing (NGS)) sono comparsi sul mercato. Questi ultimi hanno velocemente preso piede grazie ai bassi costi di sequenziamento soprattutto se confrontati con le precedenti macchine Sanger. Oggi tuttavia, nuove tecnologie (ad esempio PacBio di Pacific Biosciences) si stanno facendo strada grazie alla loro capacità di produrre frammenti di lunghezze mai ottenute prima d’ora. Nonostante la continua evoluzione nessuna di queste tecnologie è ancora in grado di produrre letture complete del DNA, ma solo parziali frammenti (chiamati read) come risultato del processo biochimico chiamato sequenziamento. Un trend ricorrente durante l’evoluzione dei sequenziatori è rappresentato dalla crescente presenza di errori di sequenziamento, se nelle read Sanger in media una lettura su mille corrisponde ad un errore, le ultime macchine PacBio sono caratterizzate da un tasso di errore di circa il 15%, una situazione più o meno intermedia è rappresentata dalle read NGS all’interno delle quali questo tasso si attesta su valori attorno al 1%. E’ chiaro quindi che algoritmi in grado di processare dati con diversi caratteristiche in termini di errori di sequenziamento stanno acquisendo maggiore importanza mentre lo sviluppo di modelli ad-hoc che affrontino esplicitamente il problema degli errori di sequenziamento stanno assumendo notevole rilevanza. A supporto di queste tecniche le macchine sequenziatrici producono valori di qualità (quality scores o quality values) che possono esser messi in relazione con la probabilità di osservare un errore di sequenziamento. In questa tesi viene presentato un modello stocastico per descrivere il processo di sequenziamento e ne vengono presentate due applicazioni: clustering di read e il filtraggio di read. L’idea alla base del modello è di utilizzare i valori di qualità come fondamento per la definizione di un modello probabilistico che descriva il processo di sequenziamento. La derivazione di tale modello richiede la definizione rigorosa degli spazi di probabilità coinvolti e degli eventi in essi definiti. Inoltre, allo scopo di sviluppare un modello semplice e trattabile è necessario introdurre ipotesi semplificative che agevolino tale processo, tuttavia tali ipotesi debbono essere esplicitate ed opportunamente discusse. Per fornirne una validazione sperimentale, il modello è stato applicato ai problemi di clustering e filtraggio. Nel primo caso il clustering viene eseguito utilizzando le nuove misure Dq2 ottenute come estensione delle note misure alignment-free D2 attraverso l’introduzione dei valori di qualità. Più precisamente anzichè indurre un contributo unitario al conto della frequenza dei k-mer (come avviene per le statistiche D2), nelle misure Dq2 il contributo di un k-mer coincide con la probabilità dello stesso si essere corretto, calcolata sulla base dei valori di qualità associati. I risultati del clustering sono poi utilizzati per risolvere il problema del de-novo assembly (ricostruzione ex-novo di sequenze) e del metagenomic binning (classificazione di read da esperimenti di metagenomica). Una seconda applicazione del modello teorico è rappresentata dal problema del filtraggio di read utilizzando un approccio senza perdita di informazione in cui le read vengono ordinate secondo la loro probabilità di correttezza. L’idea che giustifica l’impiego di tale approccio è che l’ordinamento dovrebbe collocare nelle posizioni più alte le read con migliore qualità retrocedendo quelle con qualità più bassa. Per verificare la validità di questa nostra congettura, il filtraggio è stato utilizzato come fase preliminare di algoritmi per mappaggio di read e de-novo assembly. In entrambi i casi si osserva un miglioramento delle prestazione degli algoritmi quando le read sono presentate nell’ordine indotto dalla nostra misura. La tesi è strutturata nel seguente modo. Nel Capitolo 1 viene fornita una introduzione al sequenziamento e una panoramica dei principali problemi definiti sui dati prodotti. Inoltre vengono dati alcuni cenni sulla rappresentazione di sequenze, read e valori di qualità. Alla fine dello stesso Capitolo 1 si delineano brevemente i principali contributi della tesi e la letteratura correlata. Il Capitolo 2 contiene la derivazione formale del modello probabilistico per il sequenziamento. Nella prima parte viene schematicamente presentato il processo di produzione di una coppia simbolo qualità per poi passare alla definizione di spazi di probabilità per sequenze e sequenziamento. Mentre gli aspetti relativo alla distribuzione di probabilità per la sequenza di riferimento non vengono considerati in questa tesi, la descrizione probabilistica del processo di sequenziamento è trattata in dettaglio nella parte centrale del Capitolo 2 nella cui ultima parte viene presentata la derivazione della probabilità di correttezza di una read che viene poi utilizzata nei capitoli successivi. Il Capitolo 3 presenta le misure Dq2 e gli esperimenti relativi al clustering i cui risultati sono frutto del lavoro svolto in collaborazione con Matto Comin e Andrea Leoni e pubblicato in [CLS14] e [CLS15]. Il Capitolo 4 presenta invece i risultati preliminari fin qui ottenuti per il filtraggio di read basato sui valori di qualità. Infine il Capitolo 5 presenta le conclusioni e delinea le direzioni future che si intendono perseguire a continuamento del lavoro qui presentato.