The Desperate Quest for Genomic Compression Algorithms

https://spectrum.ieee.org/computing/software/the-desperate-quest-for-genomic-compression-algorithms

by yaseen-rob • 8 years ago

95 43 8 years ago

spectrum.ieee.org

bra-ket• 8 years ago

you can either compress the data for general use, or optimize for particular application , i.e. search index, in the latter case the compression ratio can be orders of magnitude better than general-purpose

I think improving general compression is of marginal importance given the abundance of existing compression algorithms, it is mostly a solved problem with many decades of productive research behind it

the biggest ‘bang for the buck’ is in optimizing for particular applications such as search, gene detection, snp calling, alignment etc

trhway• 8 years ago

The files are also very redundant, which stems from the fact that any two human genomes are nearly identical. On average, they differ in about one nucleotide per 1,000, and it’s typically these genetic differences that are of interest.

git diff

sjg007• 8 years ago

I thought one idea was to store only the differences from a reference genome.

phkahler2• 8 years ago

That is mentioned and IMHO seem like the best possible way given the 1/1000 mutation/variation rate. But they also have a quality score indicating confidence that the data is correct, and they want to compress the quality data as well.

tonto• 8 years ago

Here is one approach for that https://github.com/jkbonfield/crumble https://blog.dnanexus.com/2018-07-23-breaking-down-crumble/

chaosfox• 8 years ago

yes, see CRAM format: http://www.internationalgenome.org/faq/what-are-cram-files/

phkahler2• 8 years ago

> And it turns out that a histogram plot of the distance between adjacent genetic variations, measured in DNA base pairs, looks like a double power law, with the crossover point between the two power laws happening at around 1,000 DNA base pairs [see graph, “Double Power Law”]. It’s an open question as to what evolutionary process created this distribution, but its existence could potentially enable improved compression.

My first thought was it's due to some issue/error/phenomena with the sequencing process and not inherent in the underlying data. Hopefully it's known not to be that, but it would be interesting.

T-A• 8 years ago

Or we could just store it all in DNA:

https://www.wired.com/story/the-rise-of-dna-data-storage/

lainga• 8 years ago

I'll have you know that I sequenced and compressed both my parents' DNA at a very young age, although the process was about 50% lossy.

fubar2018aug• 8 years ago

hasn't everyone?

TD-Linux2• 8 years ago

This article totally failed to justify why compression algorithms are so important for this application. How big is the human genome, how much can we compress it by, and why does this matter?

I took a look and zipped FASTA files are about 800MB. Large, sure, but people are streaming Netflix movies far bigger than this every night.

It's really hard for me to see the MPEG-G effort as anything but a money grab for compression patents and licensing.

mjburgess• 8 years ago

1 Human = 100 GB

500,000 Humans is a small sample of the UK population one company is looking to create.

All this is in the article.

TD-Linux2• 8 years ago

The article doesn't say that 1 human = 100GB anywhere. It does say a reference genome is ~1GB, which sounds similar to a zipped FASTA.

500k humans would make this 400TB of data. Really not that much, especially compared to the $500 million dollars it would take to sequence all those humans at $1,000 each.

epicureanideal• 8 years ago

It seems to be more like 1.5GB rather than 100 GB, and someone else commented that compressed is around 800 MB.

https://bitesizebio.com/8378/how-much-information-is-stored-...

Even at 1.5 GB, this doesn't seem like an insurmountable problem at the current cost of storage.

750,000 GB = 750 TB, and you can buy an 8 TB hard drive for $150. So for $15,000 you can store 500,000 human genomes.

If $15,000 is too expensive for a company, that company is doing something very wrong, when any salary will be many multiples of that.

chrchang523• 8 years ago

It's necessary to distinguish between the raw output of the sequencing instrument and the actual genomic variables of interest here.

Adequate compression of the latter, with appropriate confidence estimates attached, is a solved problem for the most common applications, even when hundreds of thousands of samples are involved: the UK Biobank has released a dataset describing whole-genome variation for almost 500000 British people, and many research groups around the world are successfully analyzing this data today with freely available software running on commodity hardware.

It's the raw measurements that aren't compressing as well as we'd want today. But there are multiple other solutions to this problem besides better compression: we can become good enough at inferring the relevant genomic variables from the measurements that, once we've done so, we can discard the raw data (we don't do this today because the inference process is still very much a work in progress, so the option of running tomorrow's algorithms on today's measurements is too valuable); or measurement becomes cheap enough and biological sample storage stable enough that the measurement process can simply be repeated when necessary; or entirely different measurement process(es) are developed that yield adequate information without simultaneously generating so much nuisance data to preserve.

evandijk702• 8 years ago

There seems to be confusion in this thread on what exactly is stored.

The human genome is about 3.25 billion bases, or about 6.5 billion bases if you determine both copies of each chromosome. This corresponds to 13 billion bits or about 1.5 Gigabytes, and storing this would be no problem at all, even if there would be a lot of genomes sequenced.

However, the way human genomes are sequenced is different: The genome is fragmented in random pieces of around 500 basepairs long. Illumina sequencing machines typically read 300 basepairs of these fragments with a ~1% error rate.

To be able to determine the entire genome, these reads are mapped to a reference genome, and differences with the reference genome are marked as mutations. However, to distinguish real mutations from random read errors, and to make sure that mutations can be confidently called for regions that where fewer reads mapped a lower coverage through random variation, a ~30x coverage of the genome is needed.

If you want to store the raw sequencing data and not just the called results, a single genome does not require 1.5 GB of storage, but now requires 45 GB storage. It gets even worse when you consider samples from tumours, where biologically relevant mutations are often found in only a subset of cells. To discover these mutations, a coverage of 100x is often recommend, leading to 150 GB of storage for a single genome.

mmt3• 8 years ago

It gets even worse when you consider samples from tumours, where biologically relevant mutations are often found in only a subset of cells. To discover these mutations, a coverage of 100x is often recommend

This point brings up another, implicit, scale multiplier that the average person might assume doesn't exist: that a single individual could need multiple sequences stored.

One can't just estimate required total (uncompressed) storage by multiplying population (mod monozygotic multiple births and chimerism) by the size of one instance of raw sequencing data.

breckuh• 8 years ago

a single individual could need multiple sequences stored.

And multiple sequences could be hundreds, thousands, or more. Example: single-cell RNAseq pipelines that generate sequences for 10k cells at once.

Perhaps in the future--as tech improves--the devices themselves might be equipped to run more real-time in memory QC and emit less--but more accurate--data? I believe this is somewhat how CERN does it, where they only record a filtered subset of the data that comes in.

bane• 8 years ago

You're also forgetting that most of the popular formats just store the bases as 1-byte per base "GATC"= 4 bytes, when 2 bits per base would be fine if your data only has the 4 unambiguous bases. You could fairly trivially drop the storage of most of these formats by just encoding as 2 bits per base.

Another weird thing is that not all possible k-mers appear in DNA and k-mers of most lengths will repeat somewhere at least once. It would probably be best to just pick some useful k-mer length and build a lookup table and just store the byte-encoded indexes that map to the kmers then just gzip that whole mess. You might be able to save more space if it turns out that the indexes turn out to be reusable across genomes and just leave them out of the file.

It may also depend on your application, if all you want to know is "does k-mer==GATTACA" exist in my genome, you can just dump all the kmers into some persistent bloom filter and do searches and lookups really fast. Those would be quite small compared.

ur-whale• 8 years ago

Sort of makes you wonder why the word "sequencing" is used to describe the procedure. Sounds more like throwing the vase on the floor and carefully picking up the pieces.

fapjacks• 8 years ago

That's quite an apt metaphor. Except you do it thirty times in order to make sure you're putting them back together correctly.

otakucode• 8 years ago

It is fairly reassuring that the sum total of that which results in human development and complexity is not easily fit on a USB stick.

DoctorOetker2• 8 years ago

are you talking about all our DNA together, with all the genetic diversity of the global human population? or for one specific individual?

I will assume you are talking about one specific individual. Would you consider the genome of a freshly (before any cell division) fertilized egg cell to contain this "sum total of that which results in human development and complexity" ?

Unless you don't I will assume so. The article states ~3.25 billion base pairs, thats ~6.5 billion bits worst case (either without compression, or for a white noise genome). Thats less than a gigabyte... fits easily on a USB stick!

Of course as the article mentions this does not apply to diversity in whole populations [of humans, or of "body parts" that keep evolving within the human body (such as white blood cells), or of cells from cancerous or virally infected or irradiated tissues]

The reason a single genome (i.e. the freshly fertilized egg cell) does not yet fit in 1GB is because we can not yet simultaneously reliably and cheaply sequence DNA (so we need "error bars")

Scaevolus• 8 years ago

This reads like a puff piece for MPEG-G, which will presumbaly be as patent-encumbered as every other MPEG standard. The double power law for mutation distance is interesting, but the application is feeding an entropy coder more accurate probabilities of match distances. Any decent entropy coder would implicitly discover the distribution after a short period.

There are already good compressors for genetic data. The article briefly mentions them, but oddly doesn't name them explicitly. Here's a 2013 paper summarizing the research (like compressing 6.3GB to 1.1GB or 750MB with a reference): http://journals.plos.org/plosone/article?id=10.1371/journal....

mjevans• 8 years ago

I am completely unaware of all prior art in this specific field.

However the most obvious starting idea to me is that most humans will have mostly the same DNA, with some small 'configuration' changes and maybe variations in some smaller sections.

Thus, the pre-filter would find a good fit against the reference copy, compute a diff that's sparse, and compress that.

Someone more versed in the field could probably provide a better estimate of how to address that. Taking the 3.25Billion bases (addresses) mentioned in another post, 32 bits of storage is sufficient for an unsigned index. The reference variation should also be stored, but I don't know how many variations each section might have.

Probably after a sufficiently large collection is amassed the collections could be better sorted such that the most common have a prefix which is more compressible assigned to them (and they should also be tested first by the compressor).

shusson2• 8 years ago

Thus, the pre-filter would find a good fit against the reference copy, compute a diff that's sparse, and compress that.

Yeah that already happens [1]. But before you can compute the diff, you have to read the genome with a level of confidence, which generates a lot of data.

[1] https://en.wikipedia.org/wiki/Variant_Call_Format

rishav_sharan• 8 years ago

I don't understand this field but wouldn't creating a reference model be an ethical and cultural nightmare? I would assume that researchers will be forced to make a very diluted version of this reference model which cannot be tied to any race, which at the end of the day may not be much useful.

wolco• 8 years ago

It wouldn't be the perfect human rather the commojpn traits. People look for uncommon beauty, no one ever said look how average she/he is.

shusson2• 8 years ago

On average there is only a 0.6% difference between human genomes [1]. And the reference genome already exists and is constantly being updated [2].

[1] https://en.wikipedia.org/wiki/Human_genetic_variation [2] https://en.wikipedia.org/wiki/Reference_genome

ziga2• 8 years ago

Typically, a DNA sequencing machine that’s processing the entire genome of a human will generate tens to hundreds of gigabytes of data. When stored, the cumulative data of millions of genomes will occupy dozens of exabytes.

100GB * 1M = 100 petabytes, not exabytes.

It's also worth quantifying the cost of storing this data. Storing 100GB on Amazon Glacier costs ~$5/year, which is still a small fraction of the total cost of whole genome sequencing.

tofof3• 8 years ago

But researchers don't need to simply backup the data - that is to say write the data once and have it sitting there as a recovery option. That's what Glacier is good for.

We need to be able to interact and compute with the data, search it, compare it, etc. We need to be able to practically store several hundred individuals' genomes for even a modest (n=100) GWAS study. And as the article explains, it's not simply a question of storage, but also of compressing in a way that we can still quickly do computations on the data without having to resort to just completely uncompressing everything.

I'm going to actually run the numbers to show why Glacier would be an exceptionally poor option, but I'll disclaim up front: the poor fit will stem from the fact that Glacier is optimal for store-forever read-never workflows, which is not even close to what our workflow will be.

Let's actually do the math on that modest n=100 study. At 150 GB per individual (see evandijk70's comment), you seem to be thinking 'ok, 15 TB[1], $5/GB/year = $750, no problem'. Now let's actually add the cost of not just the size of the data stored, but the retrievals and data transfers. Let's even assume we're willing to wait the 6 hours (an entire workday!) for a standard Glacier retrieval. If we're extremely conservative about how we use the data, we can possibly get by with only 10 retrievals of each genome: 10 x 15 TB = 150000 gigabytes retrieved, at $0.01 = $1500. Plus the data transfer charge, $0.09 for the first 10000 GB, $0.085 for the next 40000 GB, $0.07 for the remainder: $11300 [2].

So for a small study, we're talking about not $750, but $13,550 using your proposal of Amazon Glacier. And then the real kicker - if we actually tried to do this, moving 165 TB (1 write, 10 reads) of data around would take more than 5 straight months of 24/7 uploading or downloading at 100 Mbps. And at $13,550, that's literally more than half a biology grad student's salary here at the University of Illinois. For two of these studies, you could just instead hire a third scientist and pay them to do nothing but drive harddrives around.

Obviously that's ridiculous and in no way a realistic solution to anything. Admittedly, today, small GWAS studies are probably closer to n=25, with 30x coverage rather than 100x. But lopping a zero off the costs and transfer times doesn't change anything - it would still be an absurd use of Glacier. But the example should hopefully be eye-opening to the importance of being able to effectively manage this volume of data. The example is the output of a single scientist working for perhaps a month on the actual sequencing, and a couple more months in preparation to get a really good/narrow selection of subjects, etc. So for a 10 person lab working at high efficiency, you can imagine how quickly the data could stack up.

All our data operations -- search, compute on, transfer, and store -- would be improved dramatically if we had compression schemes that approached the efficiency of, say, HEVC or AV1.

As an comparison - uncompressed video, 1920x816 pixels (standard cinema 2.35:1 widescreen), at 23.976 fps, for 1 hr 45 minutes, in 24 bit color = 1920x816 x 23.976 x (60x60+60x45) x 24/8 = 700 GB of data. HEVC at reasonable settings will chop that to about... 2 GB. That sort of 350-fold compression is what this article is talking about hoping to achieve, which is a far cry from the 20-fold you can get from gzipping a genome.

[1] An individual archive on Glacier, by the way, is limited to 40 terabytes, so we're already pushing against that boundary.

[2] The limit on data transfers per month is 500 TB, so with our single study at 150 we're already pushing against that boundary as well.

ziga2• 8 years ago

The article mentioned storing data for a decades, which implies a backup use-case with infrequent access (of course, data only would be deposited in Glacier after the initial analysis is performed). If you expect to retrieve the data frequently, that's clearly not the right storage tier to use. S3 Infrequent Access tier is ~3x the cost, which still supports my point about the relative cost compared to total cost of sequencing.

To address some of your other points: the 40TB limit per archive is not a limit on the amount of data your can store in Glacier. And assuming 100MBps throughput is implying you'd use a single node to analyze the data, which does not make sense at this scale.

beagle3• 8 years ago

The A, G, C, T system is apparently insufficient to completely describe the genome; See[0]. I would not be surprised if, in 20-30 years, there will be a Y2K-style "4 bases" effort to fix all software and databases to account for the missing bases; It's obvious that the extra ones play (at most) a small part, but at some point that small part might be what is stalling progress.

[0] https://www.sciencedaily.com/releases/2011/07/110721142408.h...

no_identd• 8 years ago

This seems like a misleading press release. This article basically talks about (newish[2011], additional) epigenetic mechanisms.

Epigenetic sequencing would indeed require even more storage.

The Desperate Quest for Genomic Compression Algorithms

Related Stories