Vai ai contenuti. | Spostati sulla navigazione | Spostati sulla ricerca | Vai al menu | Contatti | Accessibilità

| Crea un account

Schimd, Michele (2015) Quality value based models and methods for sequencing data. [Tesi di dottorato]

Full text disponibile come:

[img]
Anteprima
Documento PDF (Schimd Michele PhD Thesis) - Versione sottomessa
1164Kb

Abstract (inglese)

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.

Abstract (italiano)

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.

Statistiche Download - Aggiungi a RefWorks
Tipo di EPrint:Tesi di dottorato
Relatore:Bilardi, Gianfranco
Dottorato (corsi e scuole):Ciclo 26 > Scuole 26 > INGEGNERIA DELL'INFORMAZIONE > SCIENZA E TECNOLOGIA DELL'INFORMAZIONE
Data di deposito della tesi:02 Febbraio 2015
Anno di Pubblicazione:02 Febbraio 2015
Parole chiave (italiano / inglese):sequencing, ngs, nect generation sequencing, dna, probabilistic, model, de-novo assembly, phred, quality values, model, pacbio, sanger, mapping, alignment, metagenomics, clustering, qcluster, qfilter, binning
Settori scientifico-disciplinari MIUR:Area 09 - Ingegneria industriale e dell'informazione > ING-INF/05 Sistemi di elaborazione delle informazioni
Struttura di riferimento:Dipartimenti > Dipartimento di Ingegneria dell'Informazione
Codice ID:7983
Depositato il:23 Nov 2015 15:37
Simple Metadata
Full Metadata
EndNote Format

Bibliografia

I riferimenti della bibliografia possono essere cercati con Cerca la citazione di AIRE, copiando il titolo dell'articolo (o del libro) e la rivista (se presente) nei campi appositi di "Cerca la Citazione di AIRE".
Le url contenute in alcuni riferimenti sono raggiungibili cliccando sul link alla fine della citazione (Vai!) e tramite Google (Ricerca con Google). Il risultato dipende dalla formattazione della citazione.

D. Aloise, A. Deshpande, et al. Np-hardness of euclidean sum-of-squares clustering. Machine Learning, 75(2):245–248, 2009. Cerca con Google

S. F. Altschul, W. Gish, et al. Basic local alignment search tool. Journal of Molecular Biology, 215(3):403 – 410, 1990. Cerca con Google

G. Baruzzo. A maximum likelihood approach to genome assembly. Master’s thesis, Department of Information Engineering, Padova, Italy, 2013. Cerca con Google

E. Birney. Assemblies: the good, the bad, the ugly. Nature methods, 8(1):59–60, 2011. Cerca con Google

E. Bao, T. Jiang, et al. Seed: efficient clustering of next-generation sequences. Bioinformatics, 27(18):2502–2509, 2011. Cerca con Google

B. E. Blaisdell. A measure of the similarity of sets of sequences not requiring sequence alignment. Proceedings of the National Academy of Sciences, 83(14):5155–5159, 1986. Cerca con Google

H. Breu. A theoretical understanding of 2 base color codes and its application to annotation, error detection, and error correction. Technical report, Applied biosystems by life technologies, 2010. Cerca con Google

M. Comin and M. Antonello. Fast computation of entropic profiles for the detection of conservation in genomes. In Pattern recognition in bioinformatics, pages 277–288 (Springer), 2013. Cerca con Google

P. J. A. Cock, C. J. Fields, et al. The sanger fastq file format for sequences with quality scores, and the solexa/illumina fastq variants. Nucleic Acids Research, 38(6):1767–1771, 2010. Cerca con Google

G. Churchill. Stochastic models for heterogeneous dna sequences. Bulletin of Mathematical Biology, 51:79–94, 1989. 10.1007/BF02458837. Cerca con Google

T. H. Cormen, C. E. Leiserson, et al. Introduction to algorithms, volume 2 (MIT press Cambridge), 2001. Cerca con Google

M. Comin, A. Leoni, and M. Schimd. Qcluster: Extending alignment-free measures with quality values for reads clustering. In Algorithms in Bioinformatics, pages 1–13 (Springer), 2014. Cerca con Google

M. Comin, A. Leoni, and M. Schimd. Clustering of reads with alignment-free measures and quality values. Algorithms for Molecular Biology, To appear, 2015. Cerca con Google

M. Carneiro, C. Russ, et al. Pacific biosciences sequencing technology for genotyping and variation discovery in human data. BMC Genomics, 13(1):375, 2012. Cerca con Google

M. Comin and M. Schimd. Assembly-free genome comparison based on next-generation sequencing reads and variable length patterns. BMC Bioinformatics, 15(Suppl 9):S1, 2014. Cerca con Google

T. M. Cover and J. A. Thomas. Elements of information theory 2nd edition. 2006. Cerca con Google

M. Comin and D. Verzotto. Alignment-free phylogeny of whole genomes using underlying subwords. Algorithms for Molecular Biology, 7(1), 2012. Cerca con Google

M. Comin and D. Verzotto. Whole-genome phylogeny by virtue of unic subwords. In Database and Expert Systems Applications (DEXA), 2012 23rd International Workshop on, pages 190–194 (IEEE), 2012. Cerca con Google

N. G. de Bruijn and P. Erdos. A combinatorial problem. Koninklijke Nederlandse Akademie v. Wetenschappen, 49(49):758–764, 1946. Cerca con Google

S. Djebali, C. A. Davis, et al. Landscape of transcription in human cells. Nature, 489(7414):101–108, 2012. Cerca con Google

J. C. Dohm, C. Lottaz, et al. Sharcgs, a fast and highly accurate short read assembly algorithm for de novo genomic sequencing. Genome research, 17(11):1697–1706, 2007. Cerca con Google

R. Durbin. Biological sequence analysis: probabilistic models of proteins and nucleic acids (Cambridge university press), 1998. Cerca con Google

Q. Dai and T. Wang. Comparison study on k-word statistical measures for protein: From sequence to ‘sequence space’. BMC bioinformatics, 9(1):394, 2008. Cerca con Google

D. Earl, K. Bradnam, et al. Assemblathon 1: A competitive assessment of de novo short read assembly methods. Genome research, 21(12):2224–2241, 2011. Cerca con Google

J. Eid, A. Fehr, et al. Real-time dna sequencing from single polymerase molecules. Science, 323(5910):133–138, 2009. Cerca con Google

B. Ewing and P. Green. Base-calling of automated sequencer traces using phred. ii. error probabilities. Genome research, 8(3):186–194, 1998. Cerca con Google

B. Ewing, L. Hillier, et al. Base-calling of automated sequencer traces usingphred. i. accuracy assessment. Genome research, 8(3):175–185, 1998. Cerca con Google

L. Gao and J. Qi. Whole genome molecular phylogeny of large dsdna viruses using composition vector method. BMC evolutionary biology, 7(1):41, 2007. Cerca con Google

J. G ̈ke, M. H. Schulz, et al. Estimation of pairwise sequence similarity of mammalian enhancers with word neighbourhood counts. Bioinformatics, 28(5):656–663, 2012. Cerca con Google

R. W. Hamming. Error detecting and error correcting codes. Bell System technical journal, 29(2):147–160, 1950. Cerca con Google

J. E. Hopcroft, R. Motwani, and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation (3rd Edition) (Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA), 2006. Cerca con Google

M. Holtgrewe. Mason–a read simulator for second generation sequencing data. Technical Report FU Berlin, 2010. Cerca con Google

K. Kozl and C. Listy. Biochemical nomenclature and related documents. Chem. Listy, 72:288–305, 1978. Cerca con Google

M. R. Kantorovitz, G. E. Robinson, and S. Sinha. A statistical method for alignment-free comparison of regulatory sequences. Bioinformatics, 23(13):i249–i255, 2007. Cerca con Google

D. C. Koboldt, K. M. Steinberg, et al. The next-generation sequencing revolution and its impact on genomics. Cell, 155(1):27–38, 2013. Cerca con Google

V. I. Levenshtein. Binary codes capable of correcting deletions, insertions and reversals. In Soviet physics doklady, volume 10, page 707. 1966. Cerca con Google

R. A. Lippert, H. Huang, and M. S. Waterman. Distributional regimes for the number of k-word matches between two random sequences. Proceedings of the National Academy of Sciences, 99(22):13980–13989, 2002. Cerca con Google

E. S. Lander, L. M. Linton, et al. Initial sequencing and analysis of the human genome. Nature, 409(6822):860–921, 2001. Cerca con Google

H. Li, J. Ruan, and R. Durbin. Mapping short dna sequencing reads and calling variants using mapping quality scores. Genome Research, 18(11):1851–1858, 2008. Cerca con Google

R. Li, H. Zhu, et al. De novo assembly of human genomes with massively parallel short read sequencing. Genome research, 20(2):265–272, 2010. Cerca con Google

M. L. Metzker. Sequencing technologiesthe next generation. Nature Reviews Genetics, 11(1):31–46, 2009. Cerca con Google

A. McKenna, M. Hanna, et al. The genome analysis toolkit: a mapreduce framework for analyzing next-generation dna sequencing data. Genome research, 20(9):1297–1303, 2010. Cerca con Google

J. R. Miller, S. Koren, and G. Sutton. Assembly algorithms for nextgeneration sequencing data. Genomics, 95(6):315 – 327, 2010. Cerca con Google

M. Mitzenmacher and E. Upfal. Probability and computing: Randomized algorithms and probabilistic analysis (Cambridge University Press), 2005. Cerca con Google

N. Nagarajan and M. Pop. Parametric complexity of sequence assembly: theory and applications to next generation sequencing. Journal of computational biology, 16(7):897–908, 2009. Cerca con Google

S. B. Needleman and C. D. Wunsch. A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of molecular biology, 48(3):443–453, 1970. Cerca con Google

R. K. Patel and M. Jain. Ngs qc toolkit: a toolkit for quality control of next generation sequencing data. PloS one, 7(2):e30619, 2012. Cerca con Google

A. Papoulis and S. U. Pillai. Probability, random variables, and stochastic processes (Tata McGraw-Hill Education), 2002. Cerca con Google

M. Pop and S. L. Salzberg. Bioinformatics challenges of new sequencing technology. Trends in Genetics, 24(3):142–149, 2008. Cerca con Google

P. A. Pevzner, H. Tang, and M. S. Waterman. An eulerian path approach to dna fragment assembly. Proceedings of the National Academy of Sciences, 98(17):9748–9753, 2001. Cerca con Google

J. Qi, H. Luo, and B. Hao. Cvtree: a phylogenetic tree reconstruction tool based on whole genomes. Nucleic acids research, 32(suppl 2):W45–W47, 2004. Cerca con Google

G. Reinert, D. Chew, et al. Alignment-free sequence comparison (i): statistics and power. Journal of Computational Biology, 16(12):1615–1634, 2009. Cerca con Google

J. Ren, K. Song, et al. Multiple alignment-free sequence comparison. Bioinformatics, 29(21):2690–2698, 2013. Cerca con Google

C. Shannon. A mathematical theory of communication. Bell System Technical Journal, 27:379–423, 1948. Cerca con Google

G. E. Sims, S.-R. Jun, et al. Alignment-free genome comparison with feature frequency profiles (ffp) and optimal resolutions. Proceedings of the National Academy of Sciences, 106(8):2677–2682, 2009. Cerca con Google

A. Solovyov and W. I. Lipkin. Centroid based clustering of high throughput sequencing reads based on n-mer counts. BMC Bioinformatics, 14(1):268, 2013. Cerca con Google

A. Sasson and T. P. Michael. Filtering error from solid output. Bioinformatics, 26(6):849–850, 2010. Cerca con Google

F. Sanger, S. Nicklen, and A. R. Coulson. Dna sequencing with chain-terminating inhibitors. Proceedings of the National Academy of Sciences, 4(12):5463–5467, 1977. Cerca con Google

K. Song, J. Ren, et al. New developments of alignment-free sequence comparison: measures, statistics and next-generation sequencing. Briefings in bioinformatics, page bbt067, 2013. Cerca con Google

K. Song, J. Ren, et al. Alignment-free sequence comparison based on next-generation sequencing reads. Journal of Computational Biology, 20(2):64–79, 2013. Cerca con Google

R. Staden. A strategy of dna sequencing employing computer programs. Nucleic acids research, 6(7):2601–2610, 1979. Cerca con Google

T. F. Smith and M. S. Waterman. Identification of common molecular subsequences. Journal of molecular biology, 147(1):195–197, 1981. Cerca con Google

T. J. Treangen and S. L. Salzberg. Repetitive dna and next-generation sequencing: computational challenges and solutions. Nature Reviews Genetics, 13(1):36–46, 2011. Cerca con Google

S. Vinga and J. Almeida. Alignment-free sequence comparison – a review. Bioinformatics, 19(4):513–523, 2003. Cerca con Google

J. D. Watson and F. H. Crick. Molecular structure of nucleic acids. Nature, 171(4356):737–738, 1953. Cerca con Google

L. Wan, G. Reinert, et al. Alignment-free sequence comparison (ii): theoretical power of comparison statistics. Journal of Computational Biology, 17(11):1467–1490, 2010. Cerca con Google

R. Xu and I. Wunsch, D. Survey of clustering algorithms. Neural Networks, IEEE Transactions on, 16(3):645–678, 2005. Cerca con Google

D. R. Zerbino and E. Birney. Velvet: algorithms for de novo short read assembly using de bruijn graphs. Genome research, 18(5):821–829, 2008. Cerca con Google

Z. Zhai, G. Reinert, et al. Normal and compound poisson approximations for pattern occurrences in ngs reads. Journal of Computational Biology, 19(6):839–854, 2012. Cerca con Google

Download statistics

Solo per lo Staff dell Archivio: Modifica questo record