In the first of three brief articles looking at biologically-based or –inspired computing, Norwich senior Nicholas Logan began with a discussion of genetic algorithms. Today he examines computation based on a foundation of terrestrial genetics: deoxyribonucleic acid – better known as DNA. Everything that follows is Mr. Logan’s work with minor edits.
* * *DNA, to build components or to complete computations.
One possible resource for computation is using naturally occurring structures, such as
In the case of DNA, its use for natural computation occupies two fields and each field has unique implications. The first field of DNA manipulation involves solving problems using the DNA as the direct method of computation. The second method of manipulating DNA is the art of folding DNA into shapes.
The traveling-salesman problem is a classic example of how DNA can be used to compute. Karla Hoffman and Manfred Padberg introduce the problem as follows:
The traveling salesman problem (TSP) is one which has commanded much attention of mathematicians and computer scientists specifically because it is so easy to describe and so difficult to solve. The problem can simply be stated as: if a traveling salesman wishes to visit exactly once each of a list of m cities (where the cost of traveling from city i to city j is cij) and then return to the home city, what is the least costly route the traveling salesman can take?
Using DNA, the process begins by assigning DNA strands to cities on a map and to connections between cities. The city strands will bind with the connections and form strands that consist of routes through the different cities. The strands are then sorted so that they connect only the proper number of cities. There is “still the possibility that some of those strands included the same city twice,” so the DNA is passed through filters; each filter collecting only DNA that contains a certain section (each section representing a city). The DNA strands that survive the filters represent all possible routes through the cities.
For extensive discussion of the process, see Shasha, D. E. & C. A. Lazere (2010). Natural computing: DNA, quantum bits, and the future of smart machines. W.W. Norton (ISBN 9-780-39333-683-2), p 112 ff. AMAZON
Natural Computation Risks
The implications of DNA computation are that humans will be able to do massively parallel computation to solve for all possible outcomes simultaneously for problems susceptible to parallel computation. This, in theory, could greatly affect cryptanalysis, since all the possible outcomes of trying to decipher text could theoretically be generated in nearly the same time as it takes for one result to be generated by a single processor; they would then simply have to be sorted through to find natural language patterns that could be the plain text. Leon Adleman, one of the three inventors of public-key cryptography, performed a landmark experiment in 2002, when he used a DNA computer “to find the only correct answer from over a million possible solutions to a computational problem.”
[MK adds: For a slightly more recent scholarly review of issues in DNA-based computing, see Ezziane, Z. (2006). “DNA computing: applications and challenges.” Nanotechnology 17:R27-R39.]
DNA Origami
The first folding of DNA into repeatable patterns was developed by Paul Rothemund and utilizes DNA to fold DNA. As described by the use of DNA staples allows long strands of DNA to be folded into any shape by finding the DNA sequences that will be brought together and then synthesizing a DNA section that, when folded, will bond half of itself to each section. These sections are thus effectively zipped together. Using this method with “about 200 different staples,” Rothemund was able to produce smiley faces at an angstrom scale (a meter is 10 billion angstroms).
Using DNA origami, it may be possible to use DNA to build functional DNA nanotubes which in turn could theoretically be used to build nano-sized computers.
In the last of these three articles, Mr. Logan looks at nanobots.
* * *
Nicholas K. Logan, CEH is a member of the Norwich University Corps of Cadets. After he graduates with his BSc in Computer Security and Information Assurance in May 2011, he will be working for a large Washington, D.C. area consulting firm where he has been an intern working on risk management Monte Carlo modeling. He is a member of the Association for Computing Machinery and has been inducted into the Upsilon Pi Epsilon honor society. In addition to his wide interests in information security and risk management, he is fascinated by computational complexity theory, artificial intelligence, and evolutionary theory.
****
Please support Norwich University ROTC student Zach Wetzel’s fund-raising run for the Semper Fi Injured Marines Fund.
