Slashdot Mirror
A Primer On DNA Computing And Software Breeding
There's been some interesting article published lately in the realm of DNA computing and software breeding models - kinda the land where 1s and 0s and Darwin meet. ArtsTechnica has got a primer on DNA computing which goes over the high points of DNA computing, and is accessible to anyone who remembers high school bio. Feed Magazine has got an article that examines breeding software and what that means.
Given a set of cities and routes/distances between them, is there a path that visits every city only once? If so (and there is more than one), which one is the shortest?
It's called the Travelling Salesman Problem because back when salesmen did lots of travelling by car (may be done now too, I don't know), they wanted to maximize their time and minimize their costs. Solving this problem does that.
You can easily model the problem as a graph or network of nodes/vertices (cities) and edges (routes) with weights (distances).
This problem is NP-complete, which means there is no known efficient algorithm to solve it. As soon as the number of vertices gets high, the problem gets really nasty to solve (exponential) and you have to start using heuritics, etc. to find a solution. The highest number of vertices in a solved problem of this nature is something around 13,000. It was done with massively parallel computation and heuristics using convential computation techniques (i.e., not DNA).
Woz
Let me step into devil's advocate mode.
The same could've been said of calculators. When electronic calculators came out they already had slide rules. These did the same job faster and easier and had more uses. Calculators were slow, cumbersome and ugly. Why should they have invested in calculators, they didn't accomplish anything new or better.
Yes they seem kinda stuck. And somewhat limited in the current state. However so were computers when they only used machine code. Or only used vacum tubes. Yet the technology evolved and overcame these limitations and eventually we have what we have today.
Most inventions are just better ways of doing things we already know how to do. We already knew how to get from point A to point B - walk or horse - before cars were invented. And when cars were invented they couldn't move any faster than cars.
Yes it may be hype, but it may also eventually lead to some useful things. Why block that path?
-cpd
There's more to it than doing actual computation. These are arguments that have been had a thousand times over in the past: "I don't see the benefit right now, so what's the point?" It may be excessively useful, it may not. The point is, we have to find out.
:)
Even if DNA computing proves to be too cumbersome to implement, we can still gain lots from it - for example, perhaps hidden deep within it is another model of computation. Maybe we can find something that's better then a Turing machine (i.e., it can check another program for infinite loops and find them). Hell, it may prove to be a useful storage device.
DNA does operations on data. It does remarkable things with them and it can do a lot of things at once. Studying this is not a bad idea, but so is putting all or eggs in one basket. If totally concentrated on shrinking die/chip sizes, we'll probably regret it at some point. Push the limits. It's fun!
Woz
With the amount of design effort required to just to come up with the appropriate dna molecules for processing an NP-Complete problem such as the Hamiltonian circuit problem, any hardware designer worth his salt could have created a piece of dedicated hardware to solve the corresponding problem in parallel in the same amount of time.
DNA computing is interesting, but outdated before it came into existence. Sure, things are tiny, and theoretically that lets you do large amounts of things in parallel, but it's not paradigm shifting. You can build electrical circuitry that runs in parallel just as easily, it would just be slightly larger than the corresponding dna molecules, assuming someday they find an effective means of lining up large quantities of them.
However, the most important reason DNA computing is already obsolete is quantum computing. In the past two years there have been some incredible, and to most unexpectedly early, advancements in quantum computing. Quantum computing, unlike dna computing, is paradigm shifting. Instead of attacking hard problems like NP-Complete problems by doing huge amounts of parallel computation, it does them the right way (by Nondeterministic Polynomial theory) and processes phase 1 nondeterministically.
Nondeterministic computation is, from the simplest description, "magically" getting the right result by applying a process to an uncertain piece of data, whereby the actual processing reduces the data down to the correct answer, from which the correct input is then known. In this manner, problems such as the Hamiltonian circuit are no longer difficult, and can be solved in quite reasonable periods of time.
The important difference between nondeterministic computational power and conventional deterministic computing is that when you take a problem like the Hamiltonian circuit problem, and scale it up to a huge number of vertices, dna computing falls apart because you would have to create an enourmous quantity of dna to correspond to the enourmous number of vertices. Quantum computers will scale quite fine in this area.
go on, click the link, click it, you know you want to :)
the article (go ahead, click on it) agrees with you largely, to quote it:
Physicists generally concede that the task is so formidable that a practical quantum computer won't exist for decades.
The forces of evolution, he claims, may have solved the problem of quantum computing several billion years ago. It's a startling idea--but if true, it could explain a puzzle at the core of biology.
Essentially they're trying to figure out why information in DNA is encoded using 4 base pairs, when binary is way more efficient, and therefore should have won out in an evolutionary context. Apparently, if quantum computing is used at a couple points in DNA replication, 4 becomes more efficient than two, which isn't to say that it *does* it, but only that it might...
Anthony
"I think any time you expose vulnerabilities it's a good thing." -Attorney General Janet Reno
I've done a little bit of work in DNA computing, and my impression of the state of the art is that we're only at the point where we're wiring the vacuum tubes together in order to program (if that).
It's kind of a "Nanotech-Complete" problem, in many respects. The repertoire of available enzymes is limited to those that are otherwise useful in molecular biology (endonucleases, ligases, methylases, etc.), but for some applications, "designer enzymes" are needed, and the technology to produce arbitrary enzymes is just not here yet (though a solution to the "protein folding" problem might be possible, given sufficient conventional computational power, e.g. something like distributed.net, or seti@home).
The biggest problem with DNA computers is I/O, primarily input, or what's called the "encoding problem". Representing arbitrary information as DNA sequences is a computationally hard problem in itself, since one must ensure that the encodings are unique enough to only interact with each other in the desired ways which contribute to the solution of the problem, and most importantly, produce a true solution (i.e. do not corrupt the data).
The output can be handled in a variety of ways, perhaps the most promising of which involves DNA microarrays (a.k.a. "gene chips"), which could potentially serve as an interface between DNA-based computers and conventional silicon-based computers.
But I'm afraid we're a long way from having a general-purpose DNA (or more broadly) molecular biology-based computer. And by the time we have the technology to build one, I suspect the other applications of nanotechnology may have rendered the point moot.
LaoK
Some people actually prefer light text on a dark background. Usually, I don't much care; but when I have to deal with a low refresh rate, that's the only way I can avoid a headache.
On the site in question, I found the small font much harder to deal with than the color scheme. The main body of text should generally be in the font the user has selected for their browser's default; if you're going to specify a different font for the body, make it larger, not smaller!
Tom Swiss | the infamous tms | my blog
You cannot wash away blood with blood
I think you are severly underestimating the abilities of those studying this. Considering genetic research has done "miracles" in the last 20 years with regards to how much it has learned about DNA, how long do you seriously think it will be before lots of practical applications come out of it?
Both computational study and genetic study are new fields. Electricty was a new field 200 years ago. Look what we have now. I know this is a tired argument, but it's very true and must be respected.
Woz
Hmmm. Recoculous, ha? I don't really know what that means, but sounds like you have a case of acute keytyposis.
I would not want your DNA in my computer, that's for sure. It'd probably start stattering on my d's and i's.
You can't handle the truth.
Odd timing for this one, I just finished reading this article over at New Scientist on how DNA may use quantum computing techniques...
Anthony
"I think any time you expose vulnerabilities it's a good thing." -Attorney General Janet Reno
"Software evolution is a controversial theory holding the unproven belief that random, undirected forces produced a world of better software. Use at your own risk."
Yes, they were really gonna put this in the books here. Fortunately, it was thrown out.---
DO NOT DISTURB THE SE
The former (most interesting IMO) is about using evolutionary principles to breed better software - and yes I mean software as we know it, not (necessarily) for these DNA computers
The latter is making a calculator from DNA - still nice but quantum computing is where it's at.
PS: I agree strongly with another poster who said DNA computing should be called genetic computing.
------------------------------------------------ -
"If I can shoot rabbits then I can shoot fascists" -
This may sound like flamebait, but it's not... lately, it seems that there is a lot of hype about biological systems and how it "exploits evolution" or "uses the solution mother nature has been using for all this time", or some such nonsense.
If you actually read till the end of the article, you'll realize that what they have done is merely to re-encode the TSP (travelling salesman problem) in terms of DNA reactions. As far as I can see, there is no gain whatsoever from doing this -- a computer doing a brute-force search on the TSP problem would have yielded the solution much quicker than the DNA method. The only potential advantage of the DNA method appears to be the "compactness" of data and the "stochastic, massively parallel" nature of it. But at the end of the article, it specifically says that this stochastic nature of DNA reactions (or any chemical reaction, that is) itself is the barrier -- it doesn't scale well. WTF??? That means that you have a method of solving TSP which is "massively parallel" (and therefore, by some strange fuzzy reasoning, it is "better" than silicon-based methods) but which doesn't scale well. Big deal, back to square one.
IMNSHO a lot of this hype is just riding on the unfounded assumption that "stochastic" is "better" because "that's what Nature uses". BS, I say. Just because something is stochastic doesn't make it any better (except by superstitious association with "stochastic" processes like evolution or some-such.) You can get something useful like strong cryptography from randomness. But you can also get white noise from randomness. Until it's proven that a particular process actually has its merits (and not merely duplicating what can already be done by an existing computer or other method), it's all just hype.
Granted, the "massively parallel" claim seems to be more credible; but in this case, they've just shot themselves in the foot -- the supposedly good "massively parallel" nature of the DNA method turned out to be a limiting factor, as you wuold need impractical amounts of DNA to conduct any non-trivial computation. Except perhaps for some hype value associated with the phrase "massively parallel" (boy, don't we love that term. Beowulf clusters, "massive" multi-CPU systems, etc.), I see no value whatsoever in this whole thing. As far as I'm concerned, somebody just hit upon something in the lab. Big deal, scientists have been doing that for centuries. Let's see something real produced before it's hyped like the Next Revolution.
Poll Mastah
So, if you repeatedly use legacy code in your new code in an attempt to ensure that your new code will support the same sorts of programs and environments as your old code, do you call that software inbreeding?
And if so, does that make Microsoft a bunch of software rednecks?