14-06-2009, 01:40 AM
DNA COMPUTING
A SEMINAR REPORT
Submitted by
JOBIN RAJ
in partial fulfillment for the award of the degree
of
BACHELOR OF TECHNOLOGY
in
COMPUTER SCIENCE & ENGINEERING
SCHOOL OF ENGINEERING
COCHIN UNIVERSITY OF SCIENCE AND
TECHNOLOGY,
COCHIN “ 682022
NOVEMBER 2008Page 2
DIVISION OF COMPUTER ENGINEERING
SCHOOL OF ENGINEERING
COCHIN UNIVERSITY OF SCIENCE AND
TECHNOLOGY, COCHIN “ 682022
Bonafide Certificate
Certified that this seminar report titled DNA Computing is the bona
fide work done by Jobin Raj who carried out the work under my
supervision.
Preetha S
SEMINAR GUIDE
Lecturer,
Division of Computer Science
SOE, CUSAT
Dr. David Peter S
Head of the Department
Division of Computer
Science
SOE, CUSAT
DatePage 3
ACKNOWLEDGEMENT
I thank my seminar guide Mrs. Preetha S, Lecturer, CUSAT, for
her proper guidance, and valuable suggestions. I am indebted to Mr.
David Peter, the HOD, Computer Science division & other faculty
members for giving me an opportunity to learn and present the seminars. If
not for the above mentioned people my seminar would never have been
completed successfully. I once again extend my sincere thanks to all of
them.
Jobin RajPage 4
Abstract
DNA (deoxyribonucleic acid) molecules, the material our genes are
made of, have the potential to perform calculations many times faster
than the world's most powerful human-built computers. DNA might one
day be integrated into a computer chip to create a so-called biochip that
will push computers even faster. DNA molecules have already been
harnessed to perform complex mathematical problems. While still in their
infancy, DNA computers will be capable of storing billions of times more
data than your personal computer. The technology is still in development,
and didn't even exist as a concept a few years ago. DNA computers have
the potential to take computing to new levels, picking up where Moore's
Law leaves off. The DNA computers are unlikely to feature word
processing, e-mailing and solitaire programs. Instead, their powerful
computing power will be used by national governments for cracking
secret codes, or by airlines wanting to map more efficient routes.
Studying DNA computers may also lead us to a better understanding of a
more complex computer -- the human brain.Page 5
i
Table of Contents
Chapter No.
Title
Page No.
List of Tables
List of Figures
List of Symbols, Abbreviations and
Nomenclature
v
vi
vii
1
Introduction
1
2
DNA
3
2.1 What is DNA?
2.2 Structure of DNA
2.3 Operations on DNA
2.4 DNA as a software
3
4
5
6
3
Significance of DNA
3.1 DNA: A unique data structure
3.2 Operations in parallel
7
7
8
4
DNA vs. Silicon
9
5
The Adleman Experiment
11
6
Conclusion
18
7
References
19Page 6
ii
List of Tables
Sl. No.
Tables
Page No.
2.1
Operations on DNA
5
4.1
5.1
Comparison of a DNA computer and Conventional
Computer
TSP “ City Encoding
10
12Page 7
iii
List of figures
Sl. No.
Images
Page No.
2.1
Structure of DNA
4
5.1
Travelling Salesman Problem - Graph
11
5.2
TSP “ City Encoding
13
5.3
TSP “ Route Encoding
13
5.4
Gel Electrophoresis
15
5.5
Affinity Purification
16Page 8
iv
List of Symbols, Abbreviations and Nomenclature
Sl. No.
Item
Definition
1
DNA
Deoxyribonucleic Acid
2
RNA
Ribonucleic Acid
3
mRNA
Messenger RNA
4
A
Adenine
5
T
Thymine
6
G
Guanine
7
C
Cytosine
8
U
Uracil
9
RAID
Redundant Array of Inexpensive
Disks
10
TSP
Travelling Salesman ProblemPage 9
DNA Computing
Division of Computer Science, School of Engineering, CUSAT
1
1. Introduction
In 1994, Leonard M. Adleman solved an unremarkable computational problem
with a remarkable technique. It was a problem that a person could solve it in a few
moments or an average desktop machine could solve in the blink of an eye. It took
Adleman, however, seven days to find a solution. Nevertheless, this work was
exceptional because he solved the problem with DNA. It was a landmark
demonstration of computing on the molecular level.
The type of problem that Adleman solved is a famous one. It's formally known as a
directed Hamiltonian Path (HP) problem, but is more popularly recognized as a
variant of the so-called "travelling salesman problem." In Adleman's version of the
travelling salesman problem, or "TSP" for short, a hypothetical salesman tries to find
a route through a set of cities so that he visits each city only once. As the number of
cities increases, the problem becomes more difficult until its solution is beyond
analytical analysis altogether, at which point it requires brute force search methods.
TSPs with a large number of cities quickly become computationally expensive,
making them impractical to solve on even the latest super-computer. Adlemanâ„¢s
demonstration only involves seven cities, making it in some sense a trivial problem
that can easily be solved by inspection. Nevertheless, his work is significant for a
number of reasons.
?
It illustrates the possibilities of using DNA to solve a class of problems that is
difficult or impossible to solve using traditional computing methods.
?
It's an example of computation at a molecular level, potentially a size limit
that may never be reached by the semiconductor industry.
?
It demonstrates unique aspects of DNA as a data structure
?
It demonstrates that computing with DNA can work in a massively parallel
fashion.
In 2001, scientists at the Weizmann Institute of Science in Israel announced that
they had manufactured a computer so small that a single drop of water would hold a
trillion of the machines. The devices used DNA and enzymes as their software and
hardware and could collectively perform a billion operations a second. Now the same
team, led by Ehud Shapiro, has announced a novel model of its biomolecular machine Page 10
DNA Computing
Division of Computer Science, School of Engineering, CUSAT
2
that no longer requires an external energy source and performs 50 times faster than its
predecessor did. The Guinness Book of World Records has crowned it the world's
smallest biological computing device.
Many designs for minuscule computers aimed at harnessing the massive
storage capacity of DNA have been proposed over the years. Earlier schemes have
relied on a molecule known as ATP, which is a common source of energy for cellular
reactions, as a fuel source. But in the new set up, a DNA molecule provides both the
initial data and sufficient energy to complete the computation.
We propose a new class of algorithms to be implemented on a DNA computer.
The algorithms we are going to introduce will not be affected much by the initial
condition change. This will give DNA computers great extensibility. Knapsack
problems are classical problems solvable by this method. It is unrealistic to solve
these problems using conventional electronic computers when the size of them gets
large due to the NP-complete property of these problems.
DNA computers using our method can solve substantially large size problems
because of their massive parallelism.Page 11
DNA Computing
Division of Computer Science, School of Engineering, CUSAT
3
2. DNA
2.1 What is DNA?
DNA (deoxyribonucleic acid) is the primary genetic material in all living
organisms - a molecule composed of two complementary strands that are wound
around each other in a double helix formation. The strands are connected by base
pairs that look like rungs in a ladder. Each base will pair with only one other: adenine
(A) pairs with thymine (T), guanine (G) pairs with cytosine ©. The sequence of each
single strand can therefore be deduced by the identity of its partner.
Genes are sections of DNA that code for a defined biochemical function,
usually the production of a protein. The DNA of an organism may contain anywhere
from a dozen genes, as in a virus, to tens of thousands of genes in higher organisms
like humans. The structure of a protein determines its function. The sequence of bases
in a given gene determines the structure of a protein. Thus the genetic code
determines what proteins an organism can make and what those proteins can do. It is
estimated that only 1-3% of the DNA in our cells codes for genes; the rest may be
used as a decoy to absorb mutations that could otherwise damage vital genes.
mRNA (Messenger RNA) is used to relay information from a gene to the
protein synthesis machinery in cells. mRNA is made by copying the sequence of a
gene, with one subtle difference: thymine (T) in DNA is substituted by uracil (U) in
mRNA. This allows cells to differentiate mRNA from DNA so that mRNA can be
selectively degraded without destroying DNA. The DNA-o-gram generator simplifies
this step by taking mRNA out of the equation.
The genetic code is the language used by living cells to convert information
found in DNA into information needed to make proteins. A protein's structure, and
therefore function, is determined by the sequence of amino acid subunits. The amino
acid sequence of a protein is determined by the sequence of the gene encoding that
protein. The "words" of the genetic code are called codons. Each codon consists of
three adjacent bases in an mRNA molecule. Using combinations of A, U, C and G, Page 12
DNA Computing
Division of Computer Science, School of Engineering, CUSAT
4
there can be sixty four different three-base codons. There are only twenty amino acids
that need to be coded for by these sixty four codons. This excess of codons is known
as the redundancy of the genetic code. By allowing more than one codon to specify
each amino acid, mutations can occur in the sequence of a gene without affecting the
resulting protein.
The DNA-o-gram generator uses the genetic code to specify letters of the
alphabet instead of coding for proteins.
2.2 Structure of DNA
Fig 2.1 Structure of DNAPage 13
DNA Computing
Division of Computer Science, School of Engineering, CUSAT
5
2.3 Operations on DNA
Annealing
? Double stranded DNA strands are dissolved in
to single strands (Denaturing)
? Heating breaks the hydrogen bonds between
complementary strands
Hybridization
? Base-pairing between two complimentary
single-strand molecules to form a double
stranded DNA molecule (Cooling)
Ligation
? Joining DNA molecules together
? Ligase enzymes are used to concatenate free
floating double stranded DNA
? Often invoked after annealing and
hybridization operation
Replication (Amplify)
? DNA can also be replicated, taking a single
molecule and multiplying it a thousand fold
? Possible by Polymerase Chain Reaction (PCR)
? PCR alternates between two phases: separate
DNA into single strands using heat; convert
into double strands using primer and
polymerase reaction
? PCR rapidly amplifies a single DNA molecule
into billions of molecules
? Make 2
n
copies ( n: number of iteration )
Sorting
(Gel Electrophoresis)
? Electrophoresis is the movement of charged
molecules in an electric field
? Technique for sorting DNA strands by size
? Based on the fact that DNA molecules are
negatively charged
? Rate of migration of molecules in aqueous
solution (gel) depends on its shape (size) and
electrical chargePage 14
DNA Computing
Division of Computer Science, School of Engineering, CUSAT
6
? Smaller molecules migrate faster through the
gel, thus sorting them according to size
? Gel ( made of agarose, polyacrylamide or
combination of both )
Filtering
(Affinity Purification)
? Filtering of DNA containing a specific
sequence form a sample of mixed DNA
? Attach compliment of the sequence to be
filtered to substrate like magnetic bead
? Beads are mixed with DNA
? DNA which contains the specific sequence
hybridizes with their compliment in the bead
? Beads are then retrieved and the DNA is
isolated
Table 2.1 Operations on DNA
2.4 DNA as Software:
Think of DNA as software, and enzymes as hardware. Put them together in a
test tube. The way in which these molecules undergo chemical reactions with each
other allows simple operations to be performed as a by-product of the reactions. The
scientists tell the devices what to do by controlling the composition of the DNA
software molecules. It's a completely different approach to pushing electrons around a
dry circuit in a conventional computer.
To the naked eye, the DNA computer looks like clear water solution in a test
tube. There is no mechanical device. A trillion bio-molecular devices could fit into a
single drop of water. Instead of showing up on a computer screen, results are analyzed
using a technique that allows scientists to see the length of the DNA output molecule.
"Once the input, software, and hardware molecules are mixed in a solution it
operates to completion without intervention," said David Hawksett, the science judge Page 15
DNA Computing
Division of Computer Science, School of Engineering, CUSAT
7
at Guinness World Records. "If you want to present the output to the naked eye,
human manipulation is needed."
3. Significance of DNA
3.1 DNA: A unique data structure
The amount of information gathered on the molecular biology of DNA over
the last 40 years is almost overwhelming in scope. So instead of getting bogged down
in biochemical and biological details of DNA, we'll concentrate on only the
information relevant to DNA computing.
The data density of DNA is impressive. Just like a string of binary data is
encoded with ones and zeros, a strand of DNA is encoded with four bases, represented
by the letters A, T, C, and G. The bases (also known as nucleotides) are spaced every
0.35 nanometres along the DNA molecule, giving DNA a remarkable data density of
nearly 18 Mbits per inch. In two dimensions, if you assume one base per square
nanometre, the data density is over one million Gbits per square inch. Compare this to
the data density of a typical high performance hard drive, which is about 7 Gbits per
square inch -- a factor of over 100,000 smaller.
Another important property of DNA is its double stranded nature. The bases A and T,
and C and G, can bind together, forming base pairs. Therefore every DNA sequence
has a natural complement. For example if sequence S is ATTACGTCG, its
complement, S', is TAATGCAGC. Both S and S' will come together (or hybridize) to
form double stranded DNA. This makes DNA a unique data structure for computation
and can be exploited in many ways. Error correction is one example. Errors in DNA
happen due to many factors. Occasionally, DNA enzymes simply make mistakes,
cutting where they shouldn't, or inserting a T for a G. DNA can also be damaged by
thermal energy and UV energy from the sun. If the error occurs in one of the strands
of double stranded DNA, repair enzymes can restore the proper DNA sequence by
using the complement strand as a reference. In this sense, double stranded DNA is
similar to a RAID 1 array, where data is mirrored on two drives, allowing data to be
recovered from the second drive if errors occur on the first. In biological systems, this Page 16
DNA Computing
Division of Computer Science, School of Engineering, CUSAT
8
facility for error correction means that the error rate can be quite low. For example, in
DNA replication, there is one error for every 10^9 copied bases or in other words an
error rate of 10^-9. (In comparison, hard drives have read error rates of only 10^-13
for Reed-Solomon correction).
3.2 Operations in parallel
In the cell, DNA is modified biochemically by a variety of enzymes, which are
tiny protein machines that read and process DNA according to nature's design. There
is a wide variety and number of these "operational" proteins, which manipulate DNA
on the molecular level. For example, there are enzymes that cut DNA and enzymes
that paste it back together. Other enzymes function as copiers and others as repair
units. Molecular biology, Biochemistry, and Biotechnology have developed
techniques that allow us to perform many of these cellular functions in the test tube.
It's this cellular machinery, along with some synthetic chemistry, that makes up the
palette of operations available for computation. Just like a CPU has a basic suite of
operations like addition, bit-shifting, logical operators (AND, OR, NOT NOR), etc.
that allow it to perform even the most complex calculations, DNA has cutting,
copying, pasting, repairing, and many others. And note that in the test tube; enzymes
do not function sequentially, working on one DNA at a time. Rather, many copies of
the enzyme can work on many DNA molecules simultaneously. This is the power of
DNA computing, that it can work in a massively parallel fashion.Page 17
DNA Computing
Division of Computer Science, School of Engineering, CUSAT
9
DNA vs. Silicon
DNA, with its unique data structure and ability to perform many parallel
operations, allows you to look at a computational problem from a different point of
view. Transistor-based computers typically handle operations in a sequential manner.
Of course there are multi-processor computers, and modern CPUs incorporate some
parallel processing, but in general, in the basic von Neumann architecture computer,
instructions are handled sequentially. A von Neumann machine, which is what all
modern CPUs are, basically repeats the same "fetch and execute cycle" over and over
again; it fetches an instruction and the appropriate data from main memory, and it
executes the instruction. It does these many, many times in a row, really, really fast.
The great Richard Feynman, in his Lectures on Computation, summed up von
Neumann computers by saying, "the inside of a computer is as dumb as hell, but it
goes like mad!" DNA computers, however, are non-von Neuman, stochastic machines
that approach computation in a different way from ordinary computers for the purpose
of solving a different class of problems.
Typically, increasing performance of silicon computing means faster clock cycles
(and larger data paths), where the emphasis is on the speed of the CPU and not on the
size of the memory. For example, will doubling the clock speed or doubling your
RAM give you better performance? For DNA computing, though, the power comes
from the memory capacity and parallel processing. If forced to behave sequentially,
DNA loses its appeal. For example, let's look at the read and write rate of DNA. In
bacteria, DNA can be replicated at a rate of about 500 base pairs a second.
Biologically this is quite fast (10 times faster than human cells) and considering the
low error rates, an impressive achievement. But this is only 1000 bits/sec, which is a
snail's pace when compared to the data throughput of an average hard drive. But look
what happens if you allow many copies of the replication enzymes to work on DNA
in parallel. First of all, the replication enzymes can start on the second replicated
strand of DNA even before they're finished copying the first one. So already the data
rate jumps to 2000 bits/sec. But look what happens after each replication is finished -
the number of DNA strands increases exponentially (2^n after n iterations). With each
additional strand, the data rate increases by 1000 bits/sec. So after 10 iterations, the Page 18
DNA Computing
Division of Computer Science, School of Engineering, CUSAT
10
DNA is being replicated at a rate of about 1Mbit/sec; after 30 iterations it increases to
1000 Gbits/sec. This is beyond the sustained data rates of the fastest hard drives.
Now let's consider how you would solve a nontrivial example of the travelling
salesman problem (# of cities > 10) with silicon vs. DNA. With a von Neumann
computer, one naive method would be to set up a search tree, measure each complete
branch sequentially, and keep the shortest one. Improvements could be made with
better search algorithms, such as pruning the search tree when one of the branches
you are measuring is already longer than the best candidate. A method you certainly
would not use would be to first generate all possible paths and then search the entire
list. Why? Well, consider that the entire list of routes for a 20 city problem could
theoretically take 45 million GBytes of memory (18! routes with 7 byte words)! Also
for a 100 MIPS computer, it would take two years just to generate all paths (assuming
one instruction cycle to generate each city in every path). However, using DNA
computing, this method becomes feasible! 10^15 is just a nanomole of material, a
relatively small number for biochemistry. Also, routes no longer have to be searched
through sequentially. Operations can be done all in parallel.
DNA Computers
Conventional
Computers
Storage Media
Nucleic acids
Semiconductors
Memory Capacity
Ultra-High
High
Type of Operations
Biochemical
Operations
Logical Operations
(and, or, not)
Nature of Operations
Parallel
Sequential
Speed of each Operation
Slow
Fast
Process
Stochastic
Deterministic
Table 4.1 Comparison of a DNA computer and a Conventional ComputerPage 19
DNA Computing
Division of Computer Science, School of Engineering, CUSAT
11
4. The Adleman Experiment
There is no better way to understand how something works than by going through
an example step by step. So letâ„¢s solve our own directed Hamiltonian Path problem,
using the DNA methods demonstrated by Adleman. The concepts are the same but the
example has been simplified to make it easier to follow and present.
Suppose that I live in LA, and need to visit four cities: Houston, Chicago, Miami,
and NY, with NY being my final destination. The airline Iâ„¢m taking has a specific set
of connecting flights that restrict which routes I can take (i.e. there is a flight from
L.A. to Chicago, but no flight from Miami to Chicago). What should my itinerary be
if I want to visit each city only once?
Fig 5.1 Travelling Salesman Problem - Graph
It should take you only a moment to see that there is only one route. Starting
from L.A. you need to fly to Chicago, Dallas, Miami and then to N.Y. Any other
choice of cities will force you to miss a destination, visit a city twice, or not make it to
N.Y. For this example you obviously donâ„¢t need the help of a computer to find a
solution. For six, seven, or even eight cities, the problem is still manageable.
However, as the number of cities increases, the problem quickly gets out of hand.
Assuming a random distribution of connecting routes, the number of itineraries you
need to check increases exponentially. Pretty soon you will run out of pen and paper
listing all the possible routes, and it becomes a problem for a computer...Page 20
DNA Computing
Division of Computer Science, School of Engineering, CUSAT
12
...or perhaps DNA. The method Adleman used to solve this problem is basically the
shotgun approach mentioned previously. He first generated all the possible itineraries
and then selected the correct itinerary. This is the advantage of DNA. Itâ„¢s small and
there are combinatorial techniques that can quickly generate many different data
strings. Since the enzymes work on many DNA molecules at once, the selection
process is massively parallel.
Specifically, the method based on Adlemanâ„¢s experiment would be as follows:
1. Generate all possible routes.
2. Select itineraries that start with the proper city and end with the final city.
3. Select itineraries with the correct number of cities.
4. Select itineraries that contain each city only once.
All of the above steps can be accomplished with standard molecular biology
techniques.
Part I: Generate all possible routes
Strategy: Encode city names in short DNA sequences. Encode itineraries by
connecting the city sequences for which routes exist.
DNA can simply be treated as a string of data. For example, each city can be
represented by a "word" of six bases:
Los Angeles
GCTACG
Chicago
CTAGTA
Dallas
TCGTAC
Miami
CTACGG
New York
ATGCCG
Table 5.1 TSP - City Encoding
The entire itinerary can be encoded by simply stringing together these DNA
sequences that represent specific cities. For example, the route from L.A --> Chicago
--> Dallas --> Miami --> New York would simply be GCTACG CTAGTA TCGTAC Page 21
DNA Computing
Division of Computer Science, School of Engineering, CUSAT
13
CTACGG ATGCCG or equivalently it could be represented in double stranded form
with its complement sequence.
So how do we generate this? Synthesizing short single stranded DNA is now a
routine process, so encoding the city names is straightforward. The molecules can be
made by a machine called a DNA synthesizer or even custom ordered from a third
party. Itineraries can then be produced from the city encodings by linking them
together in proper order. To accomplish this you can take advantage of the fact that
DNA hybridizes with its complimentary sequence. For example, you can encode the
routes between cities by encoding the compliment of the second half (last three
letters) of the departure city and the first half (first three letters) of the arrival city. For
example the route between Miami (CTACGG) and NY (ATGCCG) can be made by
taking the second half of the coding for Miami (CGG) and the first half of the coding
for NY (ATG). This gives CGGATG. By taking the complement of this you get,
GCCTAC, which not only uniquely represents the route from Miami to NY, but will
connect the DNA representing Miami and NY by hybridizing itself to the second half
of the code representing Miami (...CGG) and the first half of the code representing
NY (ATG...). For example:
Fig 5.2 TSP “ City Encoding
Random itineraries can be made by mixing city encodings with the route
encodings. Finally, the DNA strands can be connected together by an enzyme called
ligase. What we are left with are strands of DNA representing itineraries with a
random number of cities and random set of routes. For example
age 22DNA Computing
Division of Computer Science, School of Engineering, CUSAT
14
Fig 5.3 TSP - Route Encoding
We can be confident that we have all possible combinations including the
correct one by using an excess of DNA encodings, say 10^13 copies of each city and
each route between cities. Remember DNA is a highly compact data format, so
numbers are on our side.
Part II: Select itineraries that start and end with the correct cities
Strategy: Selectively copy and amplify only the section of the DNA that starts with
LA and ends with NY by using the Polymerase Chain Reaction.
After Part I, we now have a test tube full of various lengths of DNA that
encode possible routes between cities. What we want are routes that start with LA and
end with NY. To accomplish this we can use a technique called Polymerase Chain
Reaction (PCR), which allows you to produce many copies of a specific sequence of
DNA. PCR is an iterative process that cycle through a series of copying events using
an enzyme called polymerase. Polymerase will copy a section of single stranded DNA
starting at the position of a primer, a short piece of DNA complimentary to one end of
a section of the DNA that you're interested in. By selecting primers that flank the
section of DNA you want to amplify, the polymerase preferentially amplifies the
DNA between these primers, doubling the amount of DNA containing this sequence.
After many iterations of PCR, the DNA you're working on is amplified exponentially.
So to selectively amplify the itineraries that start and stop with our cities of interest,
we use primers that are complimentary to LA and NY. What we end up with after
PCR is a test tube full of double stranded DNA of various lengths, encoding
itineraries that start with LA and end with NY.Page 23
DNA Computing
Division of Computer Science, School of Engineering, CUSAT
15
Part III: Select itineraries that contain the correct number of cities.
Strategy: Sort the DNA by length and select the DNA whose length corresponds to 5
cities.
Our test tube is now filled with DNA encoded itineraries that start with LA
and end with NY, where the number of cities in between LA and NY varies. We now
want to select those itineraries that are five cities long. To accomplish this we can use
a technique called Gel Electrophoresis, which is a common procedure used to resolve
the size of DNA. The basic principle behind Gel Electrophoresis is to force DNA
through a gel matrix by using an electric field. DNA is a negatively charged molecule
under most conditions, so if placed in an electric field it will be attracted to the
positive potential. However since the charge density of DNA is constant (charge per
length) long pieces of DNA move as fast as short pieces when suspended in a fluid.
This is why you use a gel matrix. The gel is made up of a polymer that forms a
meshwork of linked strands. The DNA now is forced to thread its way through the
tiny spaces between these strands, which slows down the DNA at different rates
depending on its length. What we typically end up with after running a gel is a series
of DNA bands, with each band corresponding to a certain length. We can then simply
cut out the band of interest to isolate DNA of a specific length. Since we known that
each city is encoded with 6 base pairs of DNA, knowing the length of the itinerary
gives us the number of cities. In this case we would isolate the DNA that was 30 base
pairs long (5 cities times 6 base pairs).
Fig 5.4 Gel ElectrophoresisPage 24
DNA Computing
Division of Computer Science, School of Engineering, CUSAT
16
Part IV: Select itineraries that have a complete set of cities
Strategy: Successively filter the DNA molecules by city, one city at a time. Since the
DNA we start with contains five cities, we will be left with strands that encode each
city once.
DNA containing a specific sequence can be purified from a sample of mixed
DNA by a technique called affinity purification. This is accomplished by attaching the
compliment of the sequence in question to a substrate like a magnetic bead. The beads
are then mixed with the DNA. DNA, which contains the sequence you're after then
hybridizes with the complement sequence on the beads. These beads can then be
retrieved and the DNA isolated.
Fig 5.5 Affinity purification
So we now affinity purify five times, using a different city complement for
each run. For example, for the first run we use L.A.'-beads (where the ' indicates
compliment strand) to fish out DNA sequences which contain the encoding for L.A.
(which should be the entire DNA because of step 3), the next run we use Dallas'-
beads, and then Chicago'-beads, Miami'-beads, and finally NY'-beads. The order isnâ„¢t
important. If an itinerary is missing a city, then it will not be "fished out" during one
of the runs and will be removed from the candidate pool. What we are left with are the
itineraries that start in LA, visit each city once, and end in NY. This is exactly what
we are looking for. If the answer exists we would retrieve it at this step.Page 25
DNA Computing
Division of Computer Science, School of Engineering, CUSAT
17
Reading out the answer
One possible way to find the result would be to simply sequence the DNA
strands. However, since we already have the sequence of the city encodings we can
use an alternate method called graduated PCR. Here we do a series of PCR
amplifications using the primer corresponding to L.A., with a different primer for
each city in succession. By measuring the various lengths of DNA for each PCR
product we can piece together the final sequence of cities in our itinerary. For
example, we know that the DNA itinerary starts with LA and is 30 base pairs long, so
if the PCR product for the LA and Dallas primers was 24 base pairs long, you know
Dallas is the fourth city in the itinerary (24 divided by 6). Finally, if we were careful
in our DNA manipulations the only DNA left in our test tube should be DNA itinerary
encoding LA, Chicago, Miami, Dallas, and NY. So if the succession of primers used
is LA & Chicago, LA & Miami, LA & Dallas, and LA & NY, then we would get PCR
products with lengths 12, 18, 24, and 30 base pairs.
Caveats
Adleman's experiment solved a seven city problem, but there are two major
shortcomings preventing a large scaling up of his computation. The complexity of the
traveling salesman problem simply doesnâ„¢t disappear when applying a different
method of solution - it still increases exponentially. For Adlemanâ„¢s method, what
scales exponentially is not the computing time, but rather the amount of DNA.
Unfortunately this places some hard restrictions on the number of cities that can be
solved; after the Adleman article was published, more than a few people have pointed
out that using his method to solve a 200 city HP problem would take an amount of
DNA that weighed more than the earth. Another factor that places limits on his
method is the error rate for each operation. Since these operations are not
deterministic but stochastically driven (we are doing chemistry here), each step
contains statistical errors, limiting the number of iterations you can do successively
before the probability of producing an error becomes greater than producing the
correct result. For example an error rate of 1% is fine for 10 iterations, giving less
than 10% error, but after 100 iterations this error grows to 63%.Page 26
DNA Computing
Division of Computer Science, School of Engineering, CUSAT
18
5. Conclusion
The most significant technology in the future of engineering is DNA
computers. DNA is what makes up your genes and stores all the information about
you inside your cells. It is the instructions for what you look like and how your
function. Each microscopic cell in your body contains the entire DNA needed to build
you, which is a lot of information. DNA not only has huge data storage potential but
also the potential to solve complicated calculations and mathematical problems.
DNA computers are a very new concept. The idea was conceived just few years
ago. But in these few years, scientists have already been able to use DNA to solve
moderately difficult math problems. DNA computers are still decades away from
being able to compete with silicon based computers, but will eventually be much
more powerful than silicon based computers. The first DNA computers will not be
like a home PC. They will be used to solve huge, complicated mathematical problems,
such as breaking codes.
DNA computers will be thousands of times smaller and more powerful than
silicon based computers. One pound of DNA has ability to store more data than every
electronic devices ever made to date. A water droplet sized DNA computers will have
more computing power than today's most powerful supercomputers. Another
advantage of DNA computing over silicon based computers is the ability to do
parallel calculations. Silicon based microprocessors can only do on calculation at a
time while DNA computer will be able to do many simultaneous calculations.Page 27
DNA Computing
Division of Computer Science, School of Engineering, CUSAT
19
6. References
1. Adleman L. M., Molecular computation of solutions to
combinatorial problems, 1994.
2. Paun G., Rozenberg G. and Salomaa A., DNA Computing,
Springer, 1998
