Darwin: a genomics co-processor provides up to 15,000x acceleration • Hacker News Board

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

#21

Post by adrianN » Thu, Apr 19, 2018, 9:02 AM UTC

tradedash wrote: post #12

adrianN wrote: post #10

Earlier quoted context omitted.

It's difficult to generate hard instances of problems. Many (all?) NP complete problems are easy on average. For example almost all uniform random SAT instances can be solved quite easily.

That's not my understanding of the NP domain. Take Prime Factorization for example. Which isn't even NP-complete, or Sudoku which is NP-complete. Both of these problems can be made really hard by changing 1 small variable, size. Edit: I understand that your argument is about the average case and not the worst case.

If you pick a random number the chances are really good that it has many small factors and hence is a lot easier to factorize than its number of bits might suggest. Half of all numbers are divisible by two, two thirds of all numbers are divisible by two or three.

Regarding Sudoku, my hunch is that there is a critical density of numbers where random problems are harder than average. That's the case for SAT, there is a phase transition on the number of variables per clause where above a critical value almost all instances are not satisfiable and below the threshold almost all instances are. Instances right at the threshold tend to be hard for our current solvers.

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

#22

Post by ewjordan » Thu, Apr 19, 2018, 9:07 AM UTC

tradedash wrote: post #9

sspiff wrote: post #7

Earlier quoted context omitted.

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.

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 :/

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.

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

#23

Post by ShinTakuya » Thu, Apr 19, 2018, 9:16 AM UTC

_of wrote: post #4

lewisinc wrote: post #2

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

... as well as a british biologist.

That was clearly the joke.

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

#24

Post by klmr » Thu, Apr 19, 2018, 9:48 AM UTC

sspiff wrote: post #7

tradedash wrote: post #5

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 s…

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.

No, a given assembly is easy to verify. The complexity in actual application comes from the fact that performing the sequencing part (the biological/mechanical part) again will yield a different assembly due to biological and technical variability. Another complexity comes from the fact that you can define different measures of “goodness” (and hence optimality), depending on which errors you model.

But from a computational standpoint, sequence assembly (using a given error metric) is simply NP-hard.

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

#25

Post by h4l0 » Thu, Apr 19, 2018, 9:52 AM UTC

tradedash wrote: post #5

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 s…

Seeing this genuinely suprised me. I have been working on exactly the same topic that you have mentioned. Coinami[0], Coin-Application Mediator Interface is a blockchain application where scientific problems are distributed like grid and solvers are awarded by cryptocurrency. I will not go into detail but our first prototype was distributing read mapping to volunteers.

Now, I will list the problems we have encountered along the way.

First, you need problem suppliers. Blockchain does not need a problem supplier, hash puzzle is adjustable.

Second, proof-of-whatever must be very easy to verify. I mean the ratio between solving proof-of-whatever and verifying it must be really high. Unfortunately, read mapping is not a problem like that. Yes it is still NPC but verification takes way longer time than what is required.

Finally, privacy concerns. You must use encrypted, anonymized and distributed data. Current read mapping techniques do not accommodate to such needs. There are proposals[1] to satisfy these requirements but they do focus on hybrid cloud techniques which means network bandwidth is not a concern for them. However, blockchain applications are greatly concerned with network bandwidth.

*edit: references

[0] https://arxiv.org/abs/1602.03031

[1] https://www.nature.com/articles/ncomms15311#

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

#26

Post by [deleted] » Thu, Apr 19, 2018, 9:52 AM UTC

JD557 wrote: post #8

tradedash wrote: post #5

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 s…

I thought about this as well before, but the problem is that you don't want just ANY NP-problem: You want an NP problem (it doesn't even have to be NP-complete) that you can easily adjust the difficulty. How do you adjust the difficulty on something like this? Also, you always have to calculate the "hashes" of the blocks. I guess you could encode a block as a graph and it's "hash" could be the smallest path that visi…

[deleted]

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

#27

Post by klmr » Thu, Apr 19, 2018, 9:59 AM UTC

> 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

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

#28

Post by CJefferson » Thu, Apr 19, 2018, 10:27 AM UTC

tradedash wrote: post #5

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 s…

One fundamental problem is that the problem you solve must in some way "sign" or validate the set of transactions you want to add to the Blockchain. You can't just solve anything and say "I did some work".

So while we could hypothetically use NP complete problems (although there are several issues which arise to do with consistent difficulty), it's hard to do useful work, because we need the input to be fundamentally linked to the transactions in the block (and the hash of the previous block too)

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

#29

Post by azeotropic » Thu, Apr 19, 2018, 10:43 AM UTC

klmr wrote: post #27

> 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 les…

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.

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

#30

Post by txsh » Thu, Apr 19, 2018, 12:05 PM UTC

jacquesm wrote: post #17

tradedash wrote: post #5

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 s…

A blockchain is a data structure, it doesn't have processing power. Miners solve for nonsense problems because that's the simplest kind that you could solve in order to make the proposition work, anything on top of that requires more complexity. So it's not that it isn't possible, it's just that it would be charity from the point of view of the developers of the software to spend brain cycles on something they don't…

I think it’s clear what he meant and you’re being purposefully obtuse. If I said I was going to put a problem “on the internet” you would know I didn’t mean the netowrking infrastructure was going to produce a solution.