VISHVESHWARAIAH TECHNOLOGICAL UNIVERSITY A seminar report on DNA COMPUTING

VISHVESHWARAIAH TECHNOLOGICAL UNIVERSITY

S.D.M COLLEGE OF ENGINEERING AND TECHNOLOGY

A seminar report on

DNA COMPUTING

Submitted by

Prateek Shetty 2SD06CS063 8th semester

DEPARTMENT OF COMPUTER SCIENCE ENGINEERING 2009-10 1

VISHVESHWARAIAH TECHNOLOGICAL UNIVERSITY

S.D.M COLLEGE OF ENGINEERING AND TECHNOLOGY

DEPARTMENT OF COMPUTER SCIENCE ENGINEERING

CERTIFICATE Certified that the seminar work entitled “DNA COMPUTING” is a bonafide work presented by Prateek Shetty bearing USN NO 2SD06CS063 in a partial fulfillment for the award of degree of Bachelor of Engineering in Computer Science Engineering of the Vishveshwaraiah Technological University, Belgaum during the year 2009-10. The seminar report has been approved as it satisfies the academic requirements with respect to seminar work presented for the Bachelor of Engineering Degree.

Staff in charge

H.O.D CSE

Name: Prateek Shetty USN:2SD06CS063

2

INDEX

1. Introduction

4

2. History

4

3. Capability

5

4. Structure of DNA

5

5. Technology-DNA separation

6

6. Salient properties of DNA molecules

7

7. Understanding DNA computing

7

8. Biological implementation of computer logic

11

9. Comparison of conventional and DNA computer

14

10. Conclusion

14

11. References

15

3

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] “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. 4

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.

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 considers 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. Memory: A DNA computer a memory capacity much larger than any conventional computer available at present. The average CD has a storage space of 800 MB. But a DNA computer can hold about 1×1014 MB of data. 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

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 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. 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 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 200nanometer beads. When they focused a laser beam into the solution, a group of beads aggregated 6

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”. [7] 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”. [8] These origins are targeted by proteins that separate the two strands and initiate DNA synthesis. 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. The operation of separation and effectively extraction of DNA molecules illustrated. 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. 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. 7

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.

Delhi (Source) Kolkata

Mumbai

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. Generate all possible routes. Select itineraries that start with the proper city and end with the final city. Select itineraries with the correct number of cities. Select itineraries which contain each city only once.

8

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)

Bangalore CGG

Kochi ATG

Bangalore to Kochi GCCTAG

(ATGCCG)

Kochi G C C TAG (After Hybridization) 9



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) GCTACG





Kochi (Destination) 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”. [9] 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.

10

The procedure can be shown below.

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”. [10] Given below is a comparison of the various operations in a conventional computer and their biological implementation.

11

Given below is a comparison of the various operations in a conventional computer and their biological implementation.

Conventional Logic

Biological Implementation

Sum: This adds a value x to all the numbers inside a set S.

Sum: In this a number is added to all the strands using the RST method.

Subtraction: This operation subtracts a value x from all numbers in a set S.

Subtraction: In this, the same number is removed from all the strands using RST.

Division: This step will separate the set S into two different sets based on the criteria C. If no criterion is given, then components in these two sets are randomly picked from set S and S will be evenly distributed into two sets S1 and S2.

Division: The necessary operation for this step of DNA computing is to separate one tube of strands into two tubes. Each resultant tube will have approximately half of the strands of the original tube. The criteria C can be 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 parallel, all the components of sets S1 and S2 into set S.

Union: This operation will simply pour two tubes of strands into one.

Copy: This will produce a copy of S: S1.

Copy: We need to make copies of DNA 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 element of S following criteria C. If no C is given, then an element is selected randomly.

Select: This procedure will actually extract out the strand we are looking for. So, it will extract strands from tube S following certain criteria C.

12

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.

13

Finally, we can give a comparison of the conventional and DNA computers.

DNA Based Computers

Classical Computers

Slow at individual operations.

Fast at individual operations.

Can do billions of operations simultaneously.

Can do substantially fewer operations simultaneously.

Can provide huge memory in small space. One cubic centimeter of DNA soup could store as much as 10^21bits of information.

Smaller memory. At most 10^14 bits.

Setting up a problem may require considerable preparations

Setting up only requires keyboard input.

DNA is sensitive to chemical deterioration.

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.

14

References: 1] DNA Computer – Definition, http://www.webopedia.com/TERM/D/DNA_computer.html Retrieved On Feb 5th, 2010. 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 Feb 5th, 2010 4] Computer made from DNA and enzymes, http://news.nationalgeographic.com/news/2003/02/0224_030224_DNAcomputer.html Retrieved On Feb 5th, 2010. 5] Adar, Rivka et al, 2004, An autonomous molecular computer for logical control of gene expression, Nature Journal. 6] Almasi, G.S., Gottlieb, A., 1989, Highly Parallel Computing, Benjamin Cummings Publishers, Redwood City, CA. 7] Laser Snatch Free Floating DNA, http://www.trnmag.com/Stories/2002/032002/Lasers_snatch_freefloating_DNA_032002.html retrieved On Feb 6th, 2010. 8] Alberts B. et al, 2002, Molecular Biology Of The Cell, Garland Science, Chapter 5, DNA Replication Mechanisms 9] Gene Almanac, GEL Electrophoresis, http://www.dnalc.org/ddnalc/resources/electrophoresis.html Retrieved on Feb 7th, 2010. 10] DNA Computing Technology, How Stuff Works?, http://computer.howstuffworks.com/dna-computer1.html retrieved on Feb 7th, 2010.

15