DNA
could crack code
By
Kimberly Patch,
Technology Research NewsKnowledge that electrical engineers have gained from laying out components on circuit boards could make it easier to coax DNA molecules to do computations. The result may make it possible to crack a code that requires 3,000 years to solve on today's computers.
DNA computers use the same type of molecules that make up the genetic code for all life on earth and are potentially very powerful because they can perform computations on many molecules at once.
A strand of DNA is a long string of phosphates, each attached to one of four bases: adenine, cytosine, guanine and thymine. Various types of enzymes can cut the long molecules in places where the bases appear in a certain order, causing the strands to reassemble. This setup can be co-opted to perform the logic of computing.
Researchers have already plotted the minimum requirements needed to build a DNA computer. This involves a set of standard DNA molecules, or tiles, that each handle two inputs and two outputs. The tiles compute by interacting with each other, and the answer is extracted from the resulting structural changes.
Researchers from Ruhr University in Germany and Accenture Technology Labs in France are proposing to redesign the DNA tiles that make up a DNA computer to look more like the layout of an electronic circuit.
"Because the computation is done through the spatial arrangement of DNA tiles, you have to be really careful in the way you design your tiles," said Andre Weimerskirch, a graduate student at Ruhr University. "It turns out that the schoolbook layout of an electronic circuit designed to perform multiplication can be easily translated into a design for DNA tiles," he said.
These more complicated tile designs, which the researchers equate to DNA programming, would make DNA computers easier to use, Weimerskirch said. "To make it simple, imagine a jigsaw puzzle. There's only one way [the pieces] all fit together, because there are rules governing their matching," he said. The DNA tiles are similar to the pieces of a jigsaw puzzle. "Your knowledge of the problem is encoded in the pieces, and the results of the computation is the whole jigsaw puzzle. The beauty is that you don't need to assemble the jigsaw puzzle yourself, it self-assembles," he said.
The researchers designed a multiplication tile, then went on to design even more complicated tiles. "We realized that we could do even more complicated operations... with few modifications," Weimerskirch said.
In theory, the design could be used to break a strong public key encryption system in a couple of days rather than the 3,000 years it would take an electronic computer, said Weimerskirch. The key needed to decrypt the NTRU Cryptosystems, Inc. encryption scheme is one in a very large number of possibilities: around 1,460 billion billion billion billion billion, which can also be represented as 2 to the 160th power.
The DNA computing scheme is fast; in addition, it can find an answer without having to try every number until one fits, according to Weimerskirch. Using the different types of tiles, the researchers can logically cut down on the possibilities in order to reduce the number that must be weeded out using brute force. This is essentially a type of programming. "The design of our tiles gives us the flexibility to... program the attack. The type of programming we can do is still rather crude, but we think this is... an important step in the right direction," said Weimerskirch.
There are several hurdles to carrying out the scheme on real DNA, according to the researchers.The first step is to make DNA tiles that conform to the designs. "This should not be too difficult and is within the reach of current technology," said Weimerskirch. The second challenge has to do with the error rate, he said. "We're currently performing simulations that will hopefully help us understand the problem better and hopefully allow us to give advice to the experimentalists" who may want to carry out the scheme, he said.
The researchers are also looking to find new tile designs that will solve even more complex problems, Weimerskirch said.
Doing computations using self-assembly is a very powerful method, said Nadrian Seeman, a chemistry professor at New York University. "The work... takes advantage of the notion of computation by self-assembly. However, the work remains a theoretical suggestion and its ultimate value will depend on its experimental implementation," he said.
It looks feasible to build tiles like the researchers have suggested, however, said Seeman. "We're not at this time building tiles exactly like those suggested by the authors, but we may well be able to do so in the foreseeable future," he said.
Because DNA computing is inherently more powerful than electronic computing, it could eventually be applied to many difficult problems like scheduling and cryptanalysis, said Weimerskirch. It is likely to take at least five years to overcome the experimental hurdles, he said.
Weimerskirch's research colleague was Oliver Pelletier of Accenture Technology Labs. The research was funded by Accenture Technology Labs.
Timeline: 5 years
Funding: Corporate
TRN Categories: Biological, Chemical, DNA and Molecular Computing;Cryptography and Security
Story Type: News
Related Elements: Technical paper, "Algorithmic Self-assembly of DNA Tiles and Its Application to Cryptanalysis," posted on the arXiv physics archive at http://xxx.lanl.gov/abs/cs.CR/0110009.
Advertisements:
October 24, 2001
Page One
DNA could crack code
Transistor sports molecule-thin layer
Molecule connects contacts
PC immortalizes ancient temple
Laser boosts liquid computer
News:
Research News Roundup
Research Watch blog
Features:
View from the High Ground Q&A
How It Works
RSS Feeds:
News
| Blog
| Books 
Ad links:
Buy an ad link
| Advertisements:
|
 |
Ad links: Clear History
Buy an ad link
|
TRN
Newswire and Headline Feeds for Web sites
|
© Copyright Technology Research News, LLC 2000-2006. All rights reserved.
