Dna Computing Seminar

Department Of Instrumentation

DNA Computing Seminar Kunal Ray 7th Semester.

09

DNA Computing – Seminar Introduction: A DNA computer is basically a “nano-computer that uses DNA or deoxyribonucleic acid to store information and perform calculations”. 1 Basically speaking, DNA computers are the next generation microprocessors which use DNA, chemistry and molecular biology instead of the regular or traditional silicon based computer technologies. DNA computing or more generally, molecular computing, is a fast developing inter-disciplinary area. Millions of natural supercomputers exist inside living organisms, include homo-sapiens. The DNA molecules, which make up our genes, have the potential to perform calculations millions of times faster than the world’s fastest man-made computers. It has been forecasted that DNA might one day be integrated into a computer chip to create a so-called biochip that will have the capability of pushing computers even faster. DNA molecules have already been harnessed to perform complex mathematical calculations. While still in their infancy, DNA computers shall be able to store billions of times more data than the conventional computers. History: DNA computing as a field was first developed by Leonard Adleman of the University of Southern California, in 1994.2 Adleman demonstrated a proof of concept use of DNA as a form of computation which solved the seven point Hamiltonian path problem. Since the initial Adleman experiments, advances have been made and various Turing machines have been constructed. “Turing machines are basic abstract symbol manipulating devices which, despite their simplicity, can be adapted to simulate the logic of any computer algorithm. They were described in 1936 by Alan Turing”.3

1

DNA Computer – Definition, http://www.webopedia.com/TERM/D/DNA_computer.html th Retrieved On July 5 , 2009. 2 Adleman, Leonard M., 1994, Molecular Computation Of Solutions To Combinational Problems, Science Journal. 3 Turing Machine – Wikipedia, The Free Encyclopedia, http://en.wikipedia.org/wiki/Turing_machine Retrieved On July 5th, 2009.

2

Kunal Ray, CUSAT

DNA Computing – Seminar “In 2002, researchers at the Weizmann Institute of Science in Rehovot, Israel, unveiled a programmable molecular computing machine composed of enzymes and DNA molecules instead of silicon microchips”.4 On April 28th, 2004, Ehud Shapiro, Yakov Benenson, Binyamin Gil, Uri Ben Dor and Rivka Adar at the Weizmann Institute announced in the journal Nature that they had constructed a DNA computer. “This was coupled with an input and output module and is capable of diagnosing cancerous activity within a cell, and then releasing an anti-cancer drug upon diagnosis”. 5 A schematic for the above can be shown as below:

Fig: Disease diagnosis and drug administration using DNA computers. A more detailed explanation shall be provided as we progress with the topic. The design was one of its kinds and hailed as “the smallest bio-molecular computer ever”, according to the Guinness Book of World Records.

4

Computer made from DNA and enzymes, http://news.nationalgeographic.com/news/2003/02/0224_030224_DNAcomputer.html Retrieved On July 5th, 2009. 5 Adar, Rivka et al, 2004, An autonomous molecular computer for logical control of gene expression, Nature Journal.

3

Kunal Ray, CUSAT

DNA Computing – Seminar Capability: The DNA computers shall come with a variety of definite advantages over normal/conventional microprocessors using silicon chips. Some of them are discussed below. Parallel Computing: DNA computers by their inherent nature, work on the principle of parallel computing. “Parallel computing is a principle according to which, many calculations are carried out simultaneously”. 6 This means that a DNA computer breaks down a given large problem into several smaller modules and these are then solved concurrently. This essentially means that initially complex problems which a conventional computer would take years to solve can be solved within hours using DNA computers. In order to understand the ability of parallel computing in DNA consider the fact that a test tube filled with DNA can contain trillions of strands. Each operation on the test tube of DNA is carried out on all strands of the tube in parallel. Hence typically we have-

300,000,000,000,000 molecules at a time Memory: A DNA computer a memory capacity much larger than any conventional computer available at present. The picture below shows 1 gm of DNA on a CD. The average CD has a storage space of 800 MB. But a DNA computer can hold about 1× 6

MB of data.

Almasi, G.S., Gottlieb, A., 1989, Highly Parallel Computing, Benjamin Cummings Publishers, Redwood City, CA.

4

Kunal Ray, CUSAT

DNA Computing – Seminar

Energy Consumption: The energy consumption for a DNA computer has been reported to be very low when compared to conventional computers. Structure of 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 (C). 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 basic structure of a DNA molecule can be illustrated below. 5

Kunal Ray, CUSAT

DNA Computing – Seminar

Fig: Structure of DNA (deoxyribonucleic acid) 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. Technology – DNA Separation: Working with individual DNA molecules is tricky. Current technologies involve chemically binding each DNA molecule to a plastic bead, then trapping and moving the bead by hitting it with an intense beam of photons from a laser. A team of researchers from Japan has found a way to drag 6

Kunal Ray, CUSAT

DNA Computing – Seminar DNA molecules around without attaching them to a larger object. The researchers' first approach was to sandwich the DNA between unconnected beads and move the DNA indirectly by bombarding the beads with a laser. A schematic can be shown below.

Fig: Laser Snatching Free Floating DNA. 7 Although that method worked, it required a high degree of skill to carry out. The researchers went on to find an easier way: they made the beads much smaller and used many more of them. Key to the method is the size of the beads. The 7

The DNA Packaging Motor – Seeking The Mechanism, http://www.ncbi.nlm.nih.gov/bookshelf/br.fcgi?book=eurekah&part=A40182 Retrieved On July 6th, 2009.

7

Kunal Ray, CUSAT

DNA Computing – Seminar researchers found that “a laser beam would trap, or aggregate a cluster of more than 40 beads that were 200 nanometers in diameter, but would only trap a few beads half that size. To demonstrate the technique, the researchers put the DNA in a solution that contained 200-nanometer beads. When they focused a laser beam into the solution, a group of beads aggregated at the point of focus. When they focused the beam at the end of a single DNA molecule, a group of beads packed tightly together around that point, and the researchers used the bead cluster to drag the end of the molecule”. 8 The molecule can be released and re-trapped by switching the laser off and on, and a single DNA molecule can be manipulated at any point along its length. Combined with florescent labeling, which tags a molecule so that it can be seen through an optical florescent microscope, the method allows for real-time handling of DNA molecules. Salient Properties of DNA Molecules: The DNA molecules have some salient properties which differentiate it from other silicon based microprocessors and add to their usefulness. Some of the properties of DNA molecules used for the purpose of DNA computing are as follows. It is important that one understands the procedures mentioned below to have a complete insight regarding the manufacturing of a DNA computer. Replication: Replication is one of the most important properties used in DNA computing. Replication is the method by which any molecule can form an exact replica of itself and the DNA gets embedded in both these daughter molecules. “For a cell to divide, it must first replicate its DNA. The process is initiated at specific points within the DNA molecule, known as origins”. 9 8

Laser Snatch Free Floating DNA, http://www.trnmag.com/Stories/2002/032002/Lasers_snatch_freefloating_DNA_032002.html Retrieved On July 6th, 2009. 9 Alberts B. et al, 2002, Molecular Biology Of The Cell, Garland Science, Chapter 5, DNA Replication Mechanisms.

8

Kunal Ray, CUSAT

DNA Computing – Seminar These origins are targeted by proteins that separate the two strands and initiate DNA synthesis. A schematic showing DNA replication can be given below.

Fig: DNA Replication – Schematic10

DNA Extraction: In this method, it is possible to separate and bring together different strands of DNA that are of the same type. Suppose that we have a test tube containing DNA in which some of the molecules contain the strand “s”. Then it is possible to separate all the strands in the test tube that contain “s” as a subsequence and separate from those strands that do not contain these subsequences. A schematic for the above operation is shown below and the operation of separation and effectively extraction of DNA molecules illustrated.

10

DNA Replication And Synthesis, http://library.thinkquest.org/C006188/basics/replication.htm Retrieved On July 6th, 2009.

9

Kunal Ray, CUSAT

DNA Computing – Seminar

Fig: Separation & Extraction, DNA Strands. 11 DNA Annealing: This is the method by which two DNA strands can be brought together and then paired together or melted to form one single entity. A highly simplistic model can be shown below.

Fig: Two strands bearing s-subsequence coming closer.

11

DNA Separation, http://chemistry2.csudh.edu/rpendarvis/NuclAcids.html Retrieved On July 6th, 2009.

10

Kunal Ray, CUSAT

DNA Computing – Seminar

Fig: Annealed Pair resulting in Single Entity. The concept behind this is that “the hydrogen bonding between two complementary sequences is weaker than the one that links nucleotides of the same sequence. It is therefore possible to pair (anneal) or separate (melt) to anti parallel and complementary single strands”. Understanding DNA Computing – Hamiltonian Problem: There exists a classical problem, known as the Hamiltonian problem or the “Travelling Salesman Problem”, which can be used to explain the usefulness of DNA computing and its definite edge over conventional silicon based microprocessors. Problem Statement: Consider a salesman who has to travel to a number of cities on a daily basis. Now the problem is to find for him the fastest route, without taking him through the same city twice. A schematic for the problem can be shown below. Now the problem seems to be simple enough if the number of cities is 5. But what if the number of cities is 25 or for that matter 500 or even more. In such cases, the conventional computer shall invariably take years to find out the accurate answer. The reason for this is that it must generate a list of all the possible paths and then search out the shortest path, an extremely time consuming task. But using the DNA computing mechanism, the answer can be found accurately within hours.

11

Kunal Ray, CUSAT

DNA Computing – Seminar

Delhi (Source) Mumbai Kolkata

Bangalore Kochi (Destination) Solution: The solution to the above problem can be found out using the property of replication of DNA and by using the fact that we can use fluorescent labeling to tag individual molecules in DNA. A single strand of DNA cannot yield much power. But since DNAs can replicate themselves, so one can have as much DNA as required to perform complex tasks like the one explained above. And since DNA works on the principle of parallel processing, a number of options can be checked simultaneously and the right answer can be arrived at instantly. So far, this method has been successfully applied up to 15 cities. With advances taking place almost daily, the number of cities shall shoot up, provided we have enough DNA to go around with!! So let us see Adleman’s algorithm used to solve the problem at hand. o Generate all possible routes. o Select itineraries that start with the proper city and end with the final city. 12

Kunal Ray, CUSAT

DNA Computing – Seminar o Select itineraries with the correct number of cities. o Select itineraries which contain each city only once. Let us explain all the above steps one by one.  Generating all possible routes: For this purpose, we encode all the cities one by one as shown below. Delhi

GCTACG

Mumbai

CTAGTA

Kolkata

TCGTAC

Bangalore

CTACGG

Kochi

ATGCCG

The short single DNA is synthesized by a technology called DNA synthesizer. In the next step, we encode all the itineraries by connecting the city sequences for which routes exist. This can be shown below.

Bangalore

(CTACGG)

Kochi

Bangalore CGG

Kochi ATG

Bangalore to Kochi GCCTAG

(ATGCCG) GCCTAG (After Hybridization) 13

Kunal Ray, CUSAT

DNA Computing – Seminar  Select the desired itineraries: The next step is to select the itineraries that start and end with the correct route. The strategy is to selectively cope and amplify only that DNA which starts with Delhi and end with Kochi. This can be shown below.

CGATGC

TACGGC

(Start Primer)

(End Primer)

Delhi (source)

Kochi (destination)

GCTACG

ATGCCG

The technique used for the above operation is Polymerase Chain Reaction (PCR). This technique allows the production of many copies of a specific sequence of DNA.  Select itineraries with correct no. of cities: Sort the DNA by length and select the DNA whose length equals to 5 cities. The process can be shown below. Generally, the DNA is a negatively charged molecule, having a constant charge density. The GEL slows down the passing of DNA depending on the lengths therefore, producing bands. “The technique used is GEL Electrophoresis. It is used to differentiate between DNA molecules having different lengths”.12 12

Gene Almanac, GEL Electrophoresis, http://www.dnalc.org/ddnalc/resources/electrophoresis.html

14

Kunal Ray, CUSAT

DNA Computing – Seminar

Fig: GEL Electrophoresis.  Select the paths having complete set of cities: In this section, the DNA molecules are successively filtered city by city, one city at a time. The technique used for the above process is Affinity Purification. It is done by attaching the compliment of the sequence in question to a substrate like magnetic bead. The DNA which is contained in the sequence hybridizes with the complement sequence on the beads. Graduated PCRs can be used if we already have the city encodings. The procedure can be shown below.

Retrieved On July 7th, 2009.

15

Kunal Ray, CUSAT

DNA Computing – Seminar

CGATGC

GATCAT

AGCATG

GATGCC

TACGGC

GCTACG

CTAGTA

TCGTAC

CTACGG

ATGCCG

Delhi to Mumbai

Mumbai to Kolkata

Kolkata to Bangalore

Bangalore to Kochi

Hence, as shown above, through DNA computing, the shortest path from one city to another can be calculated and the Hamiltonian problem be solved. Biological Implementation of Computer Logic: The question which arises after all this explanation is that how is it possible to implement the various computer operations with the help of DNA strands. As an answer to this query, scientists have successfully developed mechanisms, which can replicate the logical and computational operations of a conventional computer. "The recent discovery of DNA Logic Gates is the first step towards creating a DNA computer which has a structure similar to an electronic PC”. 13 Given below is a comparison of the various operations in a conventional computer and their biological implementation.

13

DNA Computing Technology, How Stuff Works?, http://computer.howstuffworks.com/dna-computer1.htm Retrieved On July 7th, 2009.

16

Kunal Ray, CUSAT

DNA Computing – Seminar Conventional Logic

Biological Implementation

Sum: This adds a value x to all the Sum: In this a number is added to all the numbers inside a set S.

strands using the RST method.

Subtraction: This operation subtracts a Subtraction: In this, the same number is value x from all numbers in a set S.

removed from all the strands using RST.

Division: This step will separate the set Division: The necessary operation for S into two different sets based on the this step of DNA computing is to criteria C. If no criterion is given, then separate one tube of strands into two components in these two sets are tubes. Each resultant tube will have randomly picked from set S and S will approximately half of the strands of the be evenly distributed into two sets S1 original tube. The criteria C can be and S2.

containing or not containing a certain segment, e.g. ATTCG, and we may use the metal bead method to extract them.

Union: The operation combines, in Union: This operation will simply pour parallel, all the components of sets S1 two tubes of strands into one. and S2 into set S. Copy: This will produce a copy of S: Copy: We need to make copies of DNA S1.

strands of the original tube and double the number of strands we have for this copy operation. Best and easiest method is PCR (explained above).

Select: This operation will select an Select: This procedure will actually element of S following criteria C. If no extract out the strand we are looking for. C is given, then an element is selected So, it will extract strands from tube S randomly.

following certain criteria C. 17

Kunal Ray, CUSAT

DNA Computing – Seminar A schematic of the different logic cells can be given below as per their biological implementation.

Fig: The Genetic NOT Gate.

Fig: The Genetic AND Gate. As shown above, similar genetic analogy exists for other logic gates as well. Finally, we can give a comparison of the conventional and DNA computers. 18

Kunal Ray, CUSAT

DNA Computing – Seminar DNA Based Computers

Classical Computers

Slow at individual operations. Can

do

billions

of

Fast at individual operations. operations Can do substantially fewer operations

simultaneously.

simultaneously.

Can provide huge memory in small Smaller memory. At most 10^14 bits. space. One cubic centimeter of DNA soup could store as much as 10^21bits of information. Setting up a problem may require Setting up only requires keyboard input. considerable preparations. DNA

is

sensitive

deterioration.

to

chemical Electronic data is vulnerable but can be backed up easily.

Conclusion: DNA, the genetic code of life itself has been the molecule of this century and certainly for the next one. The future of DNA manipulation is speed, automation and miniaturization. Perhaps it will not be good enough to play games or surf the web, things traditional computers are good at, but it certainly might be used in the study of logic, encryption, genetic programming and algorithms, automata and lots of other things that haven’t even been invented yet!! Therefore, it won’t be an exaggeration to state that DNA computing is definitely the technology to watch out for in the coming years is certainly here to stay.

19

Kunal Ray, CUSAT