Fundamental Algorithms in Deep Sequencing III: Genomic Compression: Storage, Transmission, and ...
summary
Genome data is compressible by exploiting redundancy: reference-free bucketed transforms like Scalce/mintS reorder reads for LZ77, reference-based encodings store loci and tokenized read names, and lossy schemes reduce quality score entropy (Illumina 40→8 binning in CRAM, QBZ rate–distortion, and Quartz smoothing). Quartz achieves about 0.35 bits per quality score and slightly improves variant AUC. Compression also speeds search via compressive accelerated BLAST: store coarse exemplars (70% identity, ≥40 aa), search exemplars then expand, yielding large runtime gains and lower metric entropy-driven search complexity.
AI-written summary · about
chapters (22)
- 0:00Genomic data are growing exponentially
- 1:37Redundancy in data
- 2:40Outline
- 3:39Limits to compression
- 5:01What can we do?
- 5:40Approaching Shannon limit
- 5:55Huffman coding
- 12:45Arithmetic coding
- 16:23Lempel-Ziv
- 18:03Burrows-Wheeler Transform (BWT)
- 18:43Genomic compressors
- 21:42SCALCE [Hach et al. 2012]
- 29:44PathEnc [Kingsford & Patro 2015]
- 34:04MINCE [Patro & Kingsford 2015]
- 37:18The Quality Score Problem
- 38:20Quality scores in SNP-calling
- 43:17Quartz Yu, et al. 2015
- 47:11Approximate k-mer search
- 49:02Result Highlights
- 51:02A word on k-mers
- 54:05Why not longer k-mers?
- 55:26Compression for speed
related talks
30mAlgorithms for DNA Data Storage
28mSome Current Computational Challenges in Bioinformatics
14mBig data, AI, the genome, and everything
08mQ n A with Dr Denis Bauer
27mA Statistical, Reference-Free Algorithm Subsumes Myriad Problems in Genome Science
01h 14mDistributed and concurrent optimization for machine learning
53mApplied Functional Programming in Computational Genomics
42mHow Novel Compute Technology Transforms Life Science Research