Compression of DNA Sequencing Data

Produktbeschreibung

Mit der Einführung der neuesten Generationen von Sequenziermaschinen sind die Kosten für die Sequenzierung eines menschlichen Genoms auf weniger als 1.000 US-Dollar gesunken. Es wird prognostiziert, dass die Menge der Sequenzierungsdaten bald die Menge anderer Datentypen, wie z.B. Videodaten, übersteigen wird. Daher werden in dieser Arbeit drei neue Datenkompressionsverfahren zur Verbesserung der Speicherung, Übertragung und Verarbeitung von Sequenzierungsdaten vorgestellt. Die drei Verfahren beschäftigen sich mit der Komprimierung von Sequenzfragmenten, der Quantisierung und Komprimierung von Sequenzierungs-Qualitätswerten, sowie der MPEG-G-konformen Entropiecodierung von Sequenzierungsdaten. Im Vergleich zum Stand der Technik erzielen die Verfahren in separaten Experimenten die jeweils besten Ergebnisse. Abschließend wird die Integration der vorgeschlagenen Verfahren in den MPEG-G-Standard diskutiert

C O N T E N T S
1 introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 State of the Art and Contributions . . . . . . . . . . . . . . 7
1.2.1 Compression of Aligned Reads . . . . . . . . . . . 7
1.2.2 Compression of Quality Scores . . . . . . . . . . . 9
1.2.3 Entropy Coding of DNA Sequencing Data . . . . . 10
1.2.4 Standards and Implementations . . . . . . . . . . . 10
1.3 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2 preliminaries 12
2.1 The Central Dogma of Molecular Biology . . . . . . . . . . 12
2.2 DNA Sequencing . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.1 Basic Methods . . . . . . . . . . . . . . . . . . . . . 15
2.2.2 High-Throughput Methods . . . . . . . . . . . . . . 16
2.3 Representation of DNA Sequencing Data . . . . . . . . . . 18
2.3.1 The FASTA Format . . . . . . . . . . . . . . . . . . 19
2.3.2 The FASTQ Format . . . . . . . . . . . . . . . . . . 19
2.3.3 The SAM/BAM Format . . . . . . . . . . . . . . . . 21
2.4 Data Compression . . . . . . . . . . . . . . . . . . . . . . . 23
2.4.1 Mathematical Preliminaries . . . . . . . . . . . . . . 25
2.4.2 Information Theory . . . . . . . . . . . . . . . . . . 29
2.4.3 Modeling . . . . . . . . . . . . . . . . . . . . . . . . 31
2.4.4 Coding . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.4.5 Quantization . . . . . . . . . . . . . . . . . . . . . . 41
3 compression of aligned reads . . . . 45
3.1 State of the Art and Contribution . . . . . . . . . . . . . . . 46
3.1.1 Genome Compression . . . . . . . . . . . . . . . . . 46
3.1.2 Read Compression . . . . . . . . . . . . . . . . . . . 47
3.1.3 Compression of Aligned Reads . . . . . . . . . . . 47
3.2 TSC Architecture . . . . . . . . . . . . . . . . . . . . . . . . 49
3.3 Integration of TSC in MPEG-G . . . . . . . . . . . . . . . . 52
3.4 Experiment Setup . . . . . . . . . . . . . . . . . . . . . . . . 55
3.5 Results and Discussion . . . . . . . . . . . . . . . . . . . . . 56
3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4 compression of quality scores 61
4.1 State of the Art and Contribution . . . . . . . . . . . . . . . 62
4.2 CALQ Architecture . . . . . . . . . . . . . . . . . . . . . . . 63
4.2.1 Genotype Likelihood Model . . . . . . . . . . . . . 65
4.2.2 Activity-Based Posterior Model . . . . . . . . . . . 70
4.2.3 Entropy Coding . . . . . . . . . . . . . . . . . . . . 76
4.3 Integration of CALQ in MPEG-G . . . . . . . . . . . . . . . 77
4.4 Experiment Setup . . . . . . . . . . . . . . . . . . . . . . . . 79
4.5 Results and Discussion . . . . . . . . . . . . . . . . . . . . . 83
4.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
5 entropy coding of dna sequencing data 91
5.1 State of the Art and Contribution . . . . . . . . . . . . . . . 91
5.2 GABAC Architecture . . . . . . . . . . . . . . . . . . . . . . 93
5.2.1 Input Parsing . . . . . . . . . . . . . . . . . . . . . . 94
5.2.2 3-Step Transformation . . . . . . . . . . . . . . . . . 95
5.2.3 Binarization . . . . . . . . . . . . . . . . . . . . . . . 97
5.2.4 Context Selection and CABAC . . . . . . . . . . . . 98
5.3 Experiment Setup . . . . . . . . . . . . . . . . . . . . . . . . 99
5.3.1 Entropy Coding Methods . . . . . . . . . . . . . . . 99
5.3.2 Test Data . . . . . . . . . . . . . . . . . . . . . . . . 100
5.4 Results and Discussion . . . . . . . . . . . . . . . . . . . . . 102
5.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
6 standards and implementations 112
6.1 The Standardization Landscape . . . . . . . . . . . . . . . . 114
6.2 MPEG-G: The ISO/IEC 23092 Series . . . . . . . . . . . . . 115
6.2.1 Transport and Storage of Genomic Information . . 117
6.2.2 Coding of Genomic Information . . . . . . . . . . . 119
6.2.3 Metadata and Application Programming Interfaces 125
6.2.4 Reference Software and Conformance . . . . . . . 125
6.3 An Open-Source MPEG-G Codec . . . . . . . . . . . . . . . 126
7 conclusions 129
appendix 133
bibliography 133
publications 153

Keywords: Kompression, DNA-Sequenzierung, MPEG-G, compression, DNA sequencing, MPEG-G