Information Technology Reference
In-Depth Information
In this chapter, we describe several recent results that illustrate the power of sim-
ulation as the basis of an optimization technique for design of complex systems. In
Section 14.2, we describe the prototype phenomenon being used, DNA and their
molecular interactions, the theme of study in the new field of biomolecular comput-
ing (BMC), also known as DNA computing [17, 1]. In Section 14.3, we describe a
high-fidelity simulation of this phenomenon that has produced comparable results,
using in a fundamental manner once again the resource of massive randomization,
here provided by RNGs (random number generators.) In Section 14.4, we show how
recent developments in BMC provide the basic ingredients to implement large neu-
ronal systems with complex interactions among them. Finally, in Section 14.5 we
discuss some of the challenges in the implementation of the design and discuss some
of the possible applications of the model. We assume that the reader is familiar with
basic facts about molecular biology - see one of several surveys of the field (for
example, [36]) for background details. We also assume that the reader is familiar
with artificial neural networks [19].
14.2 Biomolecular Computing In Vitro
For several millions of years, DNA has demonstrated itself capable of reliably stor-
ing instructions for the makeup of living organisms. Only recently, however, did a
more formal inquiry of DNA begin for its own sake, as an entity of its own, pi-
oneered by [1], where the first successful demonstration of DNA's potential use
for nonbiological purposes, more specifically, a solution to the Hamiltonian path
problem (HPP), was demonstrated. HPP is a computational equivalent of the well-
known traveling salesman problem (TSP). An instance of HPP is a directed graph
(vertices and edges) with two singled out as source and destination vertices. The
problem calls for a Boolean decision whether there exists a Hamiltonian path join-
ing the source to the destination (i.e., a path passing through every vertex exactly
once). Adleman [1] reduces the problem to 10
12
recently available biotechnology by
mapping vertices and edges to DNA oligonucleotides with vertices designed to par-
tially stick to edges so that molecules representing paths in the graph would form
by ligation/ concatenation of smaller edges or chains into longer DNA oligonu-
cleotides. One such chain of the appropriate length and composition would wit-
ness a positive answer to a Hamiltonian graph. Since DNA oligonucleotides can
be synthesized in lengths up to 200 base pairs at low cost for picomoles of the
same species (about copies of a given molecule), edges and vertices are present
in several millions of copies so that the protocol would fully explore all possible
solutions. Extracting the nanoscopic answer has been made possible by the extraor-
dinary advances witnessed in biotechnology in the course of the last two decades.
The seemingly unlimited scalability of this approach to solve these difficult NP-hard
problems of large sizes gave rise to the field of DNA computing, also called BMC
(biomolecular computing). In the last decade, researchers in this field have emerged
with DNA computers capable of solving simple games like TIC-TAC-TOE [24] or
