Biomolecular Computing - Bionanoelectronics: Bioinquiring and Bioinspired Devices - page 192

different wavelengths: 447 nm and 474 nm. Of course, only a small number of bits
can be encoded in the fluorescein molecule, and the computation rate is determined
by the (slow) diffusion rate of the inputs. However, this example reveals that
biological computers are fundamentally different than their electronic counterparts.
Therefore, besides searching for true biological computers, an alternative route to
increase the computational power of present-day computers is to mimic nature
and, in particular, the highly interconnected and reconfigurable biological neural
networks, by creating programmable neural network architectures; an example of
such an approach can be found in Harkin et al. ( 2009 ).
Reviews on biological computations can be found in Ezziane ( 2006 ), Szaciłowski
( 2008 ), Sager et al. ( 2008 ), and Dragoman and Dragoman ( 2009 ). There is a recent
surge in interest in this subject. This chapter is by no means a comprehensive review
of the field, but offers some insights in this fascinating subject.

7.2 Boolean Biomolecular Computing

Boolean computing is performed in digital systems, where the information is
encoded in bits with logical values 0 and 1, which are represented in electronic sys-
tems as low and high voltages on circuit elements such as transistors or capacitances.
Biomolecular computing, and in particular, DNA computation, is based on encoding
information in the sequence of nucleotides and developing algorithms to operate
with these bits of information. A single-stranded DNA (ssDNA) molecule has the
potentiality of high data density of 10 22 by/g since the nucleotides are separated
by only 0.35 nm; in two dimensions, the data density stored in DNA would be
10 6 Gb=in 2 , whereas in a typical hard drive, it is of the order of 10 Gb=in 2 ( Ezziane
2006 ). DNA computers are comparable to teraflop supercomputers in terms of
parallelism, which can reach 10 20 operations/s, but scores quite poorly in error
correction performances. Despite the sequence specificity of DNA hybridization
and the repair enzymes that can correct the eventual errors, in DNA replication one
error occurs at about 10 9 copied bases, while in electronic computers performant
correction algorithms reduce errors to one at every 10 13 operations ( Ezziane 2006 ).
The first demonstration of biomolecular computing took place in 1994 ( Adleman
1994 ) when the problem that was tackled was that of the directed traveling salesman
(also known as the Hamilton path problem), which involves finding a path that
connects several cities without going through any city twice. In this case, each
city was encoded in a ssDNA molecule composed of 20 nucleotides (nt), and the
possible connections/paths between cities was encoded as a ssDNA consisting of
the last 10 nt of the starting city and the first 10 nt of the finishing city. Although
apparently trivial, the traveling salesmen problem is of the NP (nondeterministic
polynomial time)-type, and the optimal route through 50 cities is a task that can
only be solved in few years by electronic computers. Adleman ( 1994 ) solved the
7-city problem by hybridization and ligation, i.e., by mixing the DNA strands with
ligase, adding adenosine triphosphate (ATP), and finally filtering out the incorrect