21-06-2012, 03:19 PM
DNA Computing and its Application
DNA Computing and its Application.pdf (Size: 595.5 KB / Downloads: 104)
Introduction
The objectives of this chapter are twofold: firstly to introduce DNA computation,
and secondly to demonstrate how DNA computing can be applied to
solve large, complex combinatorial problems, such as the optimal scheduling
of a group of elevators servicing a number of floors in a multi-storey building.
Recently, molecular (or wet) computing has been widely researched not only
within the context of solving NP-complete/NP-hard problems that are the
most difficult problems in NP, but also implementation by way of digital
(silicon-based) computers [21]. We commence with a description of the basic
concepts of ‘wet computation’, then present recent results for the efficient
management of a group of elevators.
DNA Computing
The main idea behind DNA computing is to adopt a biological (wet) technique
as an efficient computing vehicle, where data are represented using strands of
DNA. Even though a DNA reaction is much slower than the cycle time of a
silicon-based computer, the inherently parallel processing offered by the DNA
process plays an important role. This massive parallelism of DNA processing
is of particular interest in solving NP-complete or NP-hard problems.
It is not uncommon to encounter molecular biological experiments which
involve 6 × 1016/ml of DNA molecules. This means that we can effectively
realize 60,000 TeraBytes of memory, assuming that each string of a DNA
molecule expresses one character. The total execution speed of a DNA computer
can outshine that of a conventional electronic computer, even though
the execution time of a single DNA molecule reaction is relatively slow. A
DNA computer is thus suited to problems such as the analysis of genome information,
and the functional design of molecules (where molecules constitute
the input data).
2 Junzo Watada
DNA consists of four bases of molecule structure, named adenine (A), guanine
(G), cytosine © and thymine (T). Moreover, constraints apply to connections
between these bases: more specifically, A can connect only with T,
and G only with C – this connecting rule is referred to as ‘Watson-Crick
complementarity’. This property is essential to realize the separate operation
(discussed later). In other words, it is possible to separate a partial string of
characters ‘ad’ so that a DNA sequence complementary to the DNA denoting
‘ad’ is marked, input into a test tube, hybridized to form a double strand
helix of DNA, then abstracted. Further, this property enables us to randomly
create a set of character strings according to some rule.
Since [1] described a method for solving a directed Hamiltonian path problem
with 7 cities using DNA molecules, researchers have pursued theoretical studies
to realize general computation using DNA molecules [for example, [23]. [2]
has developed a computational model to realize – via experimental treatment
of DNA molecules – operations on multiple sets of character strings, following
the encoding of finite alphabet characters onto DNA molecules.
As previously mentioned, DNA molecules can be used as information storage
media. Usually, DNA sequences of around 8-20 base-pairs are used to represent
bits, and numerous methods have been developed to manipulate and evaluate
these. In order to manipulate a wet technology to perform computations, one
or more of the following techniques are used as computational operators for
copying, sorting, splitting or concatenating the information contained within
DNA molecules:
• ligation,
• hybridization,
• polymerase chain reaction (PCR),
• gel electrophoresis, and
• enzyme reaction.
In the following subsection we briefly describe the specific bio-chemical
process which serves as the basis of our DNA computing approach.
A DNA computer performs wet computation based on the high ability of
special molecule recognition executed in reactions among DNA molecules.
Molecular computation was first reported in [1], where it was found that a
DNA polymerase – which incorporates an enzyme function for copying DNA
– is very similar in function to that of a Turing machine. DNA polymerase
composes its complementary DNA molecule using a single strand helix of
a DNA molecule as a mold. On the basis of this characteristic, if a large
amount of DNA molecules are mixed in a test tube, then reactions among
them occur simultaneously. Therefore, when a DNA molecule representing
data or code reacts with other DNA molecules, this corresponds to superparallel
processing and/or a huge amount of memory in comparison with a
conventional (electronic) computer.
DNA Computing and its Application 3
Encoding Scheme
In any DNA computational procedure, the main challenge is to encode each
object of interest into a DNA sequence. A correct design is essential in order
to ensure optimal results; an incorrect design could result in wrong sequences
following the ligation process.
Ligation and Hybridization
When DNA sequences are dropped in a test tube using a micro pipettor (Figure
1), the DNA sequences recombine with each other by means of some enzyme
reaction, this process being referred to as ‘ligation’. All DNA sequences
to be used in the experiment – together with their complements – are mixed
together in a single test tube. Normally the oligonucleotide or DNA mixture
is heated to 95o centigrade (celsius) and cooled to 20oC at 1oC per minute
for hybridization, as indicated in Figure 1. The reaction is then subjected
to a ligation. At the end of this process, a certain DNA sequence will ligate
together with another DNA sequence in order to produce a new sequence.
Polymerase Chain Reaction (PCR)
Polymerases perform several functions, including the repair and duplication
of DNA. PCR is a method for amplifying DNA in vitro. PCR is a process that
quickly amplifies the amount of specific DNA molecules in a given solution,
using primer extension by polymerase. Each cycle of the reaction doubles the
quantity of this molecule, leading to an exponential growth in the number of
sequences. It consists of the following key processes: