Quality value based models and methods for sequencing data

First isolated by Friedrich Miescher in 1869 and then identified by James Watson and Francis Crick in 1953, the double stranded DeoxyriboNucleic Acid (DNA) molecule of Homo sapiens took fifty years to be completely reconstructed and to finally be at disposal to researchers for deep studies and analyses. The first technologies for DNA sequencing appeared around the mid-1970s; among them the most successful has been chain termination method, usually referred to as Sanger method. They remained de-facto standard for sequencing until, at the beginning of the 2000s, Next Generation Sequencing (NGS) technologies started to be developed. These technologies are able to produce huge amount of data with competitive costs in terms of dollars per base, but now further advances are revealing themselves in form of Single Molecule Real Time (SMRT) based sequencer, like Pacific Biosciences, that promises to produce fragments of length never been available before. However, none of above technologies are able to read an entire DNA, they can only produce short fragments (called reads) of the sample in a process referred to as sequencing. Although all these technologies have different characteristics, one recurrent trend in their evolution has been represented by the constant grow of the fraction of errors injected into the final reads. While Sanger machines produce as low as 1 erroneous base in 1000, the recent PacBio sequencers have an average error rate of 15%; NGS machines place themselves roughly in the middle with the expected error rate around 1%. With such a heterogeneity of error profiles and, as more and more data is produced every day, algorithms being able to cope with different sequencing technologies are becoming fundamental; at the same time also models for the description of sequencing with the inclusion of error profiling are gaining importance. A key feature that can make these approaches really effective is the ability of sequencers of producing quality scores which measure the probability of observing a sequencing error. In this thesis we present a stochastic model for the sequencing process and show its application to the problems of clustering and filtering of reads. The novel idea is to use quality scores to build a probabilistic framework that models the entire process of sequencing. Although relatively straightforward, the developing of such a model goes through the proper definition of probability spaces and events on such spaces. To keep the model simple and tractable several simplification hypotheses need to be introduce, each of them, however, must be explicitly stated and extensively discussed. The final result is a model for sequencing process that can be used: to give probabilistic interpretation of the problems defined on sequencing data and to characterize corresponding probabilistic answers (i.e., solutions). To experimentally validate the aforementioned model, we apply it to two different problems: reads clustering and reads filtering. The first set of experiments goes through the introduction of a set of novel alignment-free measures D2 resulting from the extension of the well known D2 -type measures to incorporate quality values. More precisely, instead of adding a unit contribution to the k-mers count statistic (as for D2 statistics), each k- mer contributes with an additive term corresponding to its probability of being correct as defined by our stochastic model. We show that this new measures are effective when applied to clustering of reads, by employing clusters produced with D2 as input to the problems of metagenomic binning and de-novo assembly. In the second set of experiments conducted to validate our stochastic model, we applied the same definition of correct read to the problem of reads filtering. We first define rank filtering which is a lossless filtering technique that sorts reads based on a given criterion; then we used the sorted list of reads as input of algorithms for reads mapping and de-novo assembly. The idea is that, on the reordered set, reads ranking higher should have better quality than the ones at lower ranks. To test this conjecture, we use such filtering as pre-processing step of reads mapping and de-novo assembly; in both cases we observe improvements when our rank filtering approach is used.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