7 ms·

Darwin: a genomics co-processor provides up to 15,000x acceleration

158 points by godelmachine 9y ago

lewisinc 9y ago
Oh no, someone should tell them that darwin is the name for the kernel inside of iOS/MacOS.
- _of 9y ago
  ... as well as a british biologist.
  - ShinTakuya 9y ago
    That was clearly the joke.
noobermin 9y ago
Very interesting write up too! I often read that computational biology is a different beast than the rest of the computational landscape (which usually revolve around solving PDE's fundamentally) and this was a nice picture into at least one problem on that side of the pond. A "best substring" search to me sounds closer to the kind of problems CS people think about than what computational cats do.
tradedash 9y ago
Serious question: if the processing problems are classified as NP, then couldn't that processing be outsourced to a blockchain? Why have miners solve for useless problems that have no long lasting impact like "number of zeros in a SHA string" instead of processing data such as this? I can easily see it being the case that the mining problem in a given blockchain could be based on real scientific problems that needs solving. I'm looking for someone to help me understand why the above isn't possible.
- AndrewDucker 9y ago
  Would the solving of the problem have a "difficulty" that could be adjusted to ensure that blocks appeared approximately every ten minutes? Is checking that the solution is valid a very fast operation? Are we sure that there is no "final" answer which would make the calculation unusable at some point? (Those are the three main factors for choosing what kind of work to do, as far as I can see)
  - tradedash 9y ago
    > Would the solving of the problem have a "difficulty" that could be adjusted to ensure that blocks appeared approximately every ten minutes I am fairly certain you can design your problem to behave in a similar manner or in some manner that increases the complexity based on some criteria > Is checking that the solution is valid a very fast operation? That's the NP part in my question. Plenty of scientific problems out there that are fast to verify hard to compute. Ex. Prime Factorization > Are we sure that there is no "final" answer which would make the calculation unusable at some point? I would argue, and I might be wrong due to my ignorance on the subject here, that we can never "know" that. That's why P=NP is still an open question
- sspiff 9y ago
  Generally, blockchain "mining" requires a problem that is hard to solve, easy to verify. If I understand it correctly, the genome sequencing problem is hard to solve, hard to verify.
  - tradedash 9y ago
    What you just said is the "definition" of NP problems which is why I had it in my question to begin with. Even if genome sequencing is not a good problem for mining. There are plenty of other scientific problems that are. Yet mining today is not tackling any of them :/
    - ewjordan 9y ago
      The miner's identity (more or less) has to be one of the inputs to the problem, so that everyone is actually working on a different problem and you can't "steal" a block just by broadcasting another person's solution faster and wider. Maybe there could be useful problems with this property, but it's not trivial to find them.
Scaevolus 9y ago
Slides from a talk by the author that give a good introduction to the landscape and the previous algorithms: https://platformlab.stanford.edu/Seminar%20Talks/Yatish_Turakhia.pdf https://platformlab.stanford.edu/Seminar%20Talks/Yatish_Tura...
klmr 9y ago
> The long read technology comes with a drawback though – high error rates in sequencing of between 15%-40% These error rate estimates are seriously outdated (the quoted number is from a 2015 paper but it was obsolete pretty much as soon as that paper was published). Long-read technologies are evolving rapidly, so this is important. The state of the art is working with error rates of at most 15% (but usually much less), which, after correction, go down below 8% [1]. This is crucial because it makes the difference between a successful and a failed assembly: 40% error rate essentially means that you need different algorithms to perform sequence assembly (as the article notes, error correction takes up “orders of magnitude” more time than actual assembly). I’d therefore be curious how this Darwin setup performs against conventional, state-of-the-art sequence assembly with state-of-the-art long read sequencing data. [1] https://www.nature.com/articles/nbt.4060 https://www.nature.com/articles/nbt.4060
- azeotropic 9y ago
  In general, error correction requires alignment, so the correct comparison is error correction using Darwin for alignment vs. error correction using whatever long-read aligner you consider state-of-the-art.
- stochastic_monk 9y ago
  Read page 8 [206] of this paper to see the numbers they're providing. The PacBio reads are listed at up to 15% error rate. Their experiments were synthetic data from 15-40% error rates. A few comments: 1. This was published in ASPLOS, not a comp bio journal, which should raise some eyebrows. 2. As another commenter said, error correction requires a reference, either by alignment, kmer filtering, or consensus. However, this is usually part of any assembly pipeline. 3. Like you said, they failed to compare to actual state of the art alignment tools. They do cite Canu, but they don't use it as their baseline. The issue here is that the current best long read assemblers use locality-sensitive hashing. The Canu paper even states that miniasm can produce a higher-quality assembly for CHM1 in 1/400 the CPU time (though their discussion of the table selectively ignores this fact). Considering that a combination of algorithm and implementation is able to provide a 400x speedup makes this result seem significantly less impressive, and that a comparison of CPU time is slightly unfair to miniasm considering how perfectly it threadscales, which would make the other tools look even worse by comparison. Additionally, for problems where you really need the improvement in performance, the GPU RAM limitations and communication overhead would likely incur significant penalties to their method. It's not simply a matter of how many reads a second you can process because it's a quadratic overlap problem.
dekhn 9y ago
There have been a lot of co-processors in the genomics and sequencing world. They have all failed for obvious business reasons. It's not even clear that any genomics problem that exists today can't be solved with conventional hardware. Most genomics programs reach a few percent of the capacity of the hardware, so I think more software tuning and design is the right approach.
- searine 9y ago
  I agree. The problem in genomics isn't how fast alignment is going, it is where to put the gobs and gobs of data. The bottleneck in speed is how fast you can flip a DNA sequencer, which right now with an illumina Novaseq that bottleneck is a few days per run. That gives plenty of time to process each runs data on an HPC on current software for alignment and snp calling. However, when each runfolder takes up 30Tb and you're flipping 20 runfolders a week. The scale of storage get large, fast.
  - klmr 9y ago
    That’s why compression of sequencing data is becoming so important. CRAM is nowhere near the theoretical limit (CRAM achieves ~2x over BAM; commercial products currently achieve up to 6x). (COI disclaimer: I work for such a company.)
    - heuermh 9y ago
      No need for the disclaimer, post a link to your benchmarking results. We don't compress as well as CRAM, but distributed reads across an Apache Spark cluster are much more efficient via Parquet http://adam.readthedocs.io/en/latest/benchmarks/storage/ http://adam.readthedocs.io/en/latest/benchmarks/storage/
    - dekhn 9y ago
      It's not clear you want to store your sequence data maximally compressed unless you have it archived. If you're doing live work on the data, it's better to have it modestly compressed with a fast decompressor, and a good index so you can minimize your total access.
daemonk 9y ago
Cool. But I think the current state of the art is using minhashes (minimap2) to avoid doing expensive all vs all alignments. There is still a place for more sensitive alignments though.
m3kw9 9y ago
“Up to x% faster” another marketing term that used to work.

158 points by godelmachine 9y ago

lewisinc 9y ago

Oh no, someone should tell them that darwin is the name for the kernel inside of iOS/MacOS.

_of 9y ago
... as well as a british biologist.
- ShinTakuya 9y ago
  That was clearly the joke.

noobermin 9y ago

Very interesting write up too! I often read that computational biology is a different beast than the rest of the computational landscape (which usually revolve around solving PDE's fundamentally) and this was a nice picture into at least one problem on that side of the pond. A "best substring" search to me sounds closer to the kind of problems CS people think about than what computational cats do.

tradedash 9y ago

Serious question: if the processing problems are classified as NP, then couldn't that processing be outsourced to a blockchain? Why have miners solve for useless problems that have no long lasting impact like "number of zeros in a SHA string" instead of processing data such as this? I can easily see it being the case that the mining problem in a given blockchain could be based on real scientific problems that needs solving. I'm looking for someone to help me understand why the above isn't possible.

AndrewDucker 9y ago
Would the solving of the problem have a "difficulty" that could be adjusted to ensure that blocks appeared approximately every ten minutes? Is checking that the solution is valid a very fast operation? Are we sure that there is no "final" answer which would make the calculation unusable at some point? (Those are the three main factors for choosing what kind of work to do, as far as I can see)
- tradedash 9y ago
  > Would the solving of the problem have a "difficulty" that could be adjusted to ensure that blocks appeared approximately every ten minutes I am fairly certain you can design your problem to behave in a similar manner or in some manner that increases the complexity based on some criteria > Is checking that the solution is valid a very fast operation? That's the NP part in my question. Plenty of scientific problems out there that are fast to verify hard to compute. Ex. Prime Factorization > Are we sure that there is no "final" answer which would make the calculation unusable at some point? I would argue, and I might be wrong due to my ignorance on the subject here, that we can never "know" that. That's why P=NP is still an open question
sspiff 9y ago
Generally, blockchain "mining" requires a problem that is hard to solve, easy to verify. If I understand it correctly, the genome sequencing problem is hard to solve, hard to verify.
- tradedash 9y ago
  What you just said is the "definition" of NP problems which is why I had it in my question to begin with. Even if genome sequencing is not a good problem for mining. There are plenty of other scientific problems that are. Yet mining today is not tackling any of them :/
  - ewjordan 9y ago
    The miner's identity (more or less) has to be one of the inputs to the problem, so that everyone is actually working on a different problem and you can't "steal" a block just by broadcasting another person's solution faster and wider. Maybe there could be useful problems with this property, but it's not trivial to find them.

Scaevolus 9y ago

Slides from a talk by the author that give a good introduction to the landscape and the previous algorithms: https://platformlab.stanford.edu/Seminar%20Talks/Yatish_Turakhia.pdf https://platformlab.stanford.edu/Seminar%20Talks/Yatish_Tura...

klmr 9y ago

> The long read technology comes with a drawback though – high error rates in sequencing of between 15%-40% These error rate estimates are seriously outdated (the quoted number is from a 2015 paper but it was obsolete pretty much as soon as that paper was published). Long-read technologies are evolving rapidly, so this is important. The state of the art is working with error rates of at most 15% (but usually much less), which, after correction, go down below 8% [1]. This is crucial because it makes the difference between a successful and a failed assembly: 40% error rate essentially means that you need different algorithms to perform sequence assembly (as the article notes, error correction takes up “orders of magnitude” more time than actual assembly). I’d therefore be curious how this Darwin setup performs against conventional, state-of-the-art sequence assembly with state-of-the-art long read sequencing data. [1] https://www.nature.com/articles/nbt.4060 https://www.nature.com/articles/nbt.4060

azeotropic 9y ago
In general, error correction requires alignment, so the correct comparison is error correction using Darwin for alignment vs. error correction using whatever long-read aligner you consider state-of-the-art.
stochastic_monk 9y ago
Read page 8 [206] of this paper to see the numbers they're providing. The PacBio reads are listed at up to 15% error rate. Their experiments were synthetic data from 15-40% error rates. A few comments: 1. This was published in ASPLOS, not a comp bio journal, which should raise some eyebrows. 2. As another commenter said, error correction requires a reference, either by alignment, kmer filtering, or consensus. However, this is usually part of any assembly pipeline. 3. Like you said, they failed to compare to actual state of the art alignment tools. They do cite Canu, but they don't use it as their baseline. The issue here is that the current best long read assemblers use locality-sensitive hashing. The Canu paper even states that miniasm can produce a higher-quality assembly for CHM1 in 1/400 the CPU time (though their discussion of the table selectively ignores this fact). Considering that a combination of algorithm and implementation is able to provide a 400x speedup makes this result seem significantly less impressive, and that a comparison of CPU time is slightly unfair to miniasm considering how perfectly it threadscales, which would make the other tools look even worse by comparison. Additionally, for problems where you really need the improvement in performance, the GPU RAM limitations and communication overhead would likely incur significant penalties to their method. It's not simply a matter of how many reads a second you can process because it's a quadratic overlap problem.

dekhn 9y ago

There have been a lot of co-processors in the genomics and sequencing world. They have all failed for obvious business reasons. It's not even clear that any genomics problem that exists today can't be solved with conventional hardware. Most genomics programs reach a few percent of the capacity of the hardware, so I think more software tuning and design is the right approach.

searine 9y ago
I agree. The problem in genomics isn't how fast alignment is going, it is where to put the gobs and gobs of data. The bottleneck in speed is how fast you can flip a DNA sequencer, which right now with an illumina Novaseq that bottleneck is a few days per run. That gives plenty of time to process each runs data on an HPC on current software for alignment and snp calling. However, when each runfolder takes up 30Tb and you're flipping 20 runfolders a week. The scale of storage get large, fast.
- klmr 9y ago
  That’s why compression of sequencing data is becoming so important. CRAM is nowhere near the theoretical limit (CRAM achieves ~2x over BAM; commercial products currently achieve up to 6x). (COI disclaimer: I work for such a company.)
  - heuermh 9y ago
    No need for the disclaimer, post a link to your benchmarking results. We don't compress as well as CRAM, but distributed reads across an Apache Spark cluster are much more efficient via Parquet http://adam.readthedocs.io/en/latest/benchmarks/storage/ http://adam.readthedocs.io/en/latest/benchmarks/storage/
  - dekhn 9y ago
    It's not clear you want to store your sequence data maximally compressed unless you have it archived. If you're doing live work on the data, it's better to have it modestly compressed with a fast decompressor, and a good index so you can minimize your total access.

daemonk 9y ago

Cool. But I think the current state of the art is using minhashes (minimap2) to avoid doing expensive all vs all alignments. There is still a place for more sensitive alignments though.

m3kw9 9y ago

“Up to x% faster” another marketing term that used to work.