A Seminar Report On

DNA Computing
Submitted in Partial Fulfillment of the Requirements for the Degree of M.C.A

SUBMITTED BY:
Gyan Prakash Singh Roll No. 09MC05 Under Guidance of:

Dr. S.S. BEDI COMPUTER SCIENCE AND INFORMATION TECHNOLOGY INSTITUTE OF ENGINEERING AND TECHNOLOG M.J.P.ROHILKHAND UNIVERSITY BAREILLY 2011

Undertaking

I, Gyan prakash Singh, Roll no. 09MC05 hereby declare that this seminar report is prepared by me and submitted in partial fulfillment of the requirement for the award of degree of Master of Computer Application. I also declare that this report has not been submitted in any other form for other degree/diploma before.

Date: -

Gyan Prakash Singh (09MC05)

Certificate

This is certify that Gyan Prakash Singh Student of M.C.A Fifth semester has submitted this seminar report entitled DNA Computing to Department of Computer Science and information technology in partial fulfillment for the award of degree Master of Computer Application in Computer Science and information technology from the Institute of Engineering and technology (I.E.T), M.J.P Rohilkhand University, Bareilly.

Date:-

Dr. S.S. BEDI (Seminar Guide)

ACKNOWLEDGMENT

I wish to extend my sincere gratitude to my seminar guide, Dr. S.S. BEDI , for his valuable guidance and encouragement which has been absolutely helpful in successful completion of this seminar.

Gyan Prakash Singh (09MC05)

Abstract
As modern encryption algorithms are broken, the world of information security looks in new directions to protect the data it transmits. The concept of using DNA computing in the fields of cryptography and steganography has been identified as a possible technology that may bring forward a new hope for unbreakable algorithms. Is the fledgling field of DNA computing the next cornerstone in the world of information security or is our time better spent following other paths for our data encryption algorithms of the future?

This paper will outline some of the basics of DNA and DNA computing and its use in the areas of cryptography, steganography and authentication.

Research has been performed in both cryptographic and steganographic situations with respect to DNA computing. The constraints of its high tech lab requirements and computational limitations combined with the labour intensive extrapolation means, illustrate that the field of DNA computing is far from any kind of efficient use in todays security world. DNA authentication on the other hand, has exhibited great promise with real world examples already surfacing on the marketplace today.

Contents

1. Introduction.................................. 2. Interesting Facts 3. DNA structure. 4. DNA Fundamentals.. 5. What is the Need? .............................. 6. How It Works? 7. Challenges to implementation.. 8. Goals for this Works. 9. Limitations 10.Comparison of DNA computer with conventional computer 11.Advantages. 12.Disadvantages 13.Conclusion..
14.References..1..

Introduction:

DNA (Deoxyribose Nucleic Acid) computing, also known as molecular computing is a new approach to massively parallel computation based on groundbreaking work by Adleman. DNA computing was proposed as a means of solving a class of intractable computational problems in which the computing time can grow exponentially with problem size (the 'NP-complete' or non-deterministic polynomial time complete problems).A DNA computer is basically a collection of specially selected DNA strands whose combinations will result in the solution to some problem, depending on the problem at hand. Technology is currently available both to select the initial strands and to filter the final solution. DNA computing is a new computational paradigm that employs (bio)molecular manipulation to solve computational problems, at the same time exploring natural processes as computational models. In 1994, Leonard Adleman at the Laboratory of Molecular Science, Department of Computer Science, University of Southern California surprised the scientific community by using the tools of molecular biology to solve a different computational problem. The main idea was the encoding of data in DNA strands and the use of tools from molecular biology to execute computational operations. Besides the novelty of this approach, molecular computing has the potential to outperform electronic computers. For example, DNA computations may use a billion times less energy than an electronic computer while storing data in a trillion times less space. Moreover, computing with DNA is highly parallel: In principle there could be billions upon trillions of DNA molecules undergoing chemical reactions, that is, performing computations, simultaneously.

Interesting Facts:
DNA molecule is 1.7 meters long Stretch out the entire DNA in your cells and you could reach the moon 6000 times! DNA is the basic medium of information storage for all living cells. It has contained and transmitted the data of life for billions of years. Roughly 10 trillion DNA molecules could fit into a space the size of a marble. Since all these molecules can process data simultaneously, you could theoretically have 10 trillion calculations going on in a small space at once.

DNA Structure

DNA Fundamentals
DNA (deoxyribonucleic acid) is a double stranded sequence of four nucleotides; the four nucleotides that compose a strand of DNA are as follows: adenine (A), guanine (G), cytosine (C), and thymine (T); they are often called bases. DNA supports two key functions for life: coding for the production of proteins, self-replication. Each deoxyribonucleotide consists of three components: a sugar deoxyribose five carbon atoms: 1 to 5 hydroxyl group (OH) attached to 3 carbon a phosphate group a nitrogenous base.

WHAT IS THE NEED?

Computers have become significantly smaller and more powerful over the past 40 years, but they still have a silicon substrate, and silicon has inherent limitations. The abilities and power of computers to this day have increased, almost exponentially, since the dawn of their creation. This exponential growth of silicon chip speed and inverse of size has come to be known as Moore's Law. Computer chip manufacturers are furiously racing to make the next microprocessor that will topple speed records. As advancements in micro silicon chip production continue, however, more and more obstacles are faced due to the increase in complexities of the problems for which they are required. Chip makers need a new material to produce faster computing speeds. It would be hard to believe where scientists have found the new material they need to build the next generation of microprocessors. Millions of natural supercomputers exist inside living organisms, including our body. 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 molecules have already been harnessed to perform complex mathematical problems. The fastest supercomputers now available can perform about 109 (1 billion) operations per second. By using DNA molecules, it would be possible to achieve effective speeds of as much as 1017 operations per second

HOW IT WORKS? DNA computation is based on the fact that technology allows us to 'sequence' (design) single DNA strands which can be used as representations of bits of binary data. Technology also allows us to massively 'amplify' (reproduce) individual strands until there are sufficient numbers to solve complex computational problems. DNA input molecule The famous double-helix structure discovered by Watson and Crick consists of two strands of DNA wound around each other. Each strand has a long polymer backbone built from repeating sugar molecules and phosphate groups. Each sugar group is attached to one of four "bases". These four bases - guanine (G), cytosine (C), adenine (A) and thymine (T) - form the genetic alphabet of the DNA, and their order or "sequence" along the molecule constitutes the genetic code. Generic Code In the cell, DNA is modified biochemical by a variety of enzymes, which are tiny protein machines that read and process DNA according to nature's design. Just like a CPU has a basic suite of operations like addition, bitshifting, 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. 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. Pairs of molecules on a strand of DNA represent data and two naturally occurring enzymes act as the hardware to read copy and manipulate the code.

Challenges to Implementation:
Practical protocols for input and output of data into the memory. A Representation of data in DNA sequences. An Understand the information capacity of the hybridization interactions in large collections of many different DNA sequences. Appropriate physical models to guide design and experimentation

Goals for This Work:

LIMITATIONS: However, there are certain shortcomings to the development of the DNA computers: A factor that places limits on his method is the error rate for each operation. Since these operations are not deterministic but stochastically driven, each step contains statistical errors, limiting the number of iterations one can do successively before the probability of producing an error becomes greater than producing the correct result. Algorithms proposed so far use relatively slow molecular-biological operations. Each primitive operation takes hours when you run them with a small test tube of DNA. Some concrete algorithms are just for solving some concrete problems. Every Generating solution sets, even for some relatively simple problems, may require impractically large amounts of memory. Also, with each DNA molecule acting as a separate processor, there are problems with transmitting information from one molecule to another that have yet to be solved.

Comparison of DNA computers with convention al Computer: Computing with DNA is a completely new method among the quantum computing. Alternative to electronic/semiconductor technology, computing with DNA use biochemical process based on DNA. Computing with DNA is also known as molecular computing, a new approach to massive parallel computation based on groundbreaking work by Leonard Adleman. DNA plays the role of information storage in nature. DNA is the genetic material containing the whole information of an organism to be copied into the next generation of the species. DNA computing is a computational paradigm that uses synthetic (or natural) DNA molecules as information storage media. The techniques of molecular biology, such as polymerase chain reaction (PCR), gel electrophoresis, and enzymatic reactions, are used as computational operators for copying, sorting, and splitting/concatenating the information in the DNA molecules, respectively. Computing with DNA molecules has many advantages over conventional computing methods that utilize solid-state semiconductors. The properties of DNA computing compared with conventional computers are summarized in Table 1. Though DNA computing performs individual operations slowly, it can execute billions of operations simultaneously. This is contrasted with the electronic digital computers where individual operations are very fast; however, the operations are executed basically sequentially. The massive parallelism of DNA computing comes from the huge number of molecules, which chemically interact, in a small volume. DNA also provides a high storage capacity since they encode information on the molecular scale.

Basics Storage Media Memory Capacity Operators Operations Speed of each Operation Process

DNA Computers Nucleic acids Ultra-High Biochemical Operations Simultaneous (Parallel) Slow Stochastic

Conventional Computers Semiconductors High Logical Operations (and, or, not) Bitwise (Sequential) Fast Deterministic

Features of DNA computer: Storage capacity: The information density could go up to 1 bit/nm3. High parallelism: every molecule could act as a small processor on nano-scale and the number of such processors per volume would be potentially enormous. In an in vitro assay we could handle easily with about 1018 processors working in parallel. Speed: Although the elementary operations (electrophoresis separation, legation, and PCRamplifications) would be slow compared to electronic computers, their parallelism would strongly prevail, so that in certain models the number of operations per second could be of order 1018 operations per second, which is at least 100,000 times faster than the fastest supercomputers existing today. Energy efficiency: It performs 1019 operations per Joule. This is about a billion times more energy efficient than today's electronic devices.

DNA BASICS: DNA encodes the genetic information of cellular organisms. It consists of polymer chains, commonly referred to as DNA strands. Each strand may be viewed as a chain of nucleotides, or bases. An n- letter sequence of consecutive bases is known as an n-mer or an oligonucleotide of length n. The four DNA nucleotides are adenine, guanine, cytosine and thymine, commonly abbreviated to A, G, C and T respectively. Each strand has, according to chemical convention, a 5' and a 3' end, thus any single strand has a natural orientation. The classical double helix of DNA is formed when two separate strands bond together. Bonding occurs due to complimentary base pairing. Bonds with T and G bonds with C. The pairs (A, T) and (G, C) are therefore known as Watson-Crick complementary base pairs. Thus a hypothetical DNA molecule sequence is 5-ACGCGTACGTACAAGTGTCCGAAT-3 3-TGCGCATGCATGTTCACAGGCTTA-5

Fig. The classical double helix of DNA showing Watson-Crick complementary base pairs (A, T, G, C)
.

Deoxyadenylate (A) is in blue Deoxythymidylate (T) is in green Deoxyguanylate (G) is in red Deoxycytidylate (C) is in orange

ADVANTAGES:
DNA computers derive their potential advantage over conventional computers from their ability to: Perform millions of operations simultaneously. The massively parallel processing capabilities of DNA computers may give them the potential to find tractable solutions to otherwise intractable problems, as well as potentially speeding up large, but otherwise solvable, polynomial time problems requiring relatively few operations. Another advantage of the DNA approach is that it works in "parallel," processing all possible answers simultaneously. Therefore it enables to conduct large parallel searches and generate a complete set of potential solutions. DNA can hold more information in a cubic centimeter than a trillion CDs, thereby enabling it to efficiently handle massive amounts of working memory. The DNA computer also has very low energy consumption, so if it is put inside the cell it would not require much energy to work and its energy-efficiency is more than a million times that of a PC.

Disadvantages
Generating solution sets, even for some relatively simple problems, may require impractically large amounts of memory (lots and lots of DNA strands are required) Many empirical uncertainties, including those involving: actual error rates, the generation of optimal encoding techniques, and the ability to perform necessary bio-operations conveniently in vitro (for every correct answer there are millions of incorrect paths generated that are worthless). DNA computers could not (at this point) replace traditional computers. They are not programmable and the average dunce can not sit down at a familiar keyboard and get to work.

Conclusion
The field of DNA computing is still in its infancy and the applications for this technology are still not fully understood.Is DNA computing viable perhaps, but the obstacles that face the field such as the extrapolation and practical computational environments required are daunting. DNA authentication methods on the other hand have shown great promise in

the marketplace of today and it is hoped that its applications will continue to expand. The beauty of both these DNA research trends is found in the possibility of mankinds utilization of its very life building blocks to solve its most difficult problems. DNA computing research has resulted in significant progress towards the ability to create molecules with the desired properties . This ability could have important applications in biology ,chemistry and medicine,a strong argument for continued research.

References:
Gehani, Ashish. La Bean, Thomas H. Reif, John H. DNA-Based Cryptography. Department of Computer Science, Duke University. June 1999,
http://www.cs.duke.edu/~reif/paper/DNAcrypt/crypt.pdf

Gupta, Gaurav. Programmer. Peterson, Ivars.

Mehra, Nipun. Chakraverty, Shumpa. DNA Computing. The Indian June 12, 2001. Hiding in DNA. Science News Online. April 8, 2000.

http://www.theindianprogrammer.com/technology/dna_computing.htm http://www.sciencenews.org/20000408/mathtrek.asp

Blahere, Kristina. DNA Computing. CNET. April 26, 2000. http://www.cnet.com/techtrends Frequently Asked Questions About Todays Cryptography 4.1 - Section 7.19 What is DNA Computing. RSA Laboratories. http://www.rsasecurity.com/rsalabs/faq/7-19.html