[attachment=2514]


DNA COMPUTING
DNA and DNA Computing in Security Practices “ Is the Future in Our Genes?
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 todayâ„¢s security world. DNA authentication on the other hand, has exhibited great promise with real world examples already surfacing on the marketplace today.
Introduction
The world of encryption appears to be ever shrinking. Several years ago the thought of a 56-bit encryption technology seemed forever safe, but as mankind'sâ„¢ collective computing power and knowledge increases, the safety of the worldâ„¢s encryption methods seems to disappear equally as fast. Mathematicians and physicists attempt to improve on encryption methods while staying within the confines of the technologies available to us. Existing encryption algorithms such as RSA have not yet been compromised but many fear the day may come when even this bastion of encryption will fall. There is hope for new encryption algorithms on the horizon utilizing mathematical principles such as Quantum Theory however the science of our very genetic makeup is also showing promise for the information security world.
The concepts of utilizing DNA computing in the field of data encryption and DNA authentication methods for thwarting the counterfeiting industry are subjects that have been surfacing in the media of late. How realistic are these concepts and is it feasible to see these technologies changing the security marketplace of today?
What is DNA?
Before delving into the principles of DNA computing, we must have a basic understanding of what DNA actually is. All organisms on this planet are made of the same type of genetic blueprint which bind us together. The way in which that blueprint is coded is the deciding factor as to whether you will be bald, have a bulbous nose, male, female or even whether you will be a human or an oak tree.
Within the cells of any organism is a substance called Deoxyribonucleic Acid (DNA) which is a double-stranded helix of nucleotides which carries the genetic information of a cell. This information is the code used within cells to form proteins and is the building block upon which life is formed.
Strands of DNA are long polymers of millions of linked nucleotides. These nucleotides consist of one of four nitrogen bases, a five carbon sugar and a phosphate group. The nucleotides that make up these polymers are named after the nitrogen base that it consists of; Adenine (A), Cytosine ©, Guanine (G) and Thymine (T). These nucleotides will only combine in such a way that C always pairs with G and T always pairs with A.
The two strands of a DNA molecule are antiparallel where each strand runs in an opposite direction. Figure 1 illustrates two strands of DNA and the bonding priciples of of the 4 types of nucleotides and the Figure 2 illustrates the double helix shape of DNA.


Fig 1 “ Graphical representation of inherent bonding properties of DNA [11] Fig 2 “ Illustration of double helix shape of DNA. [11]

The combination of these 4 nucleotides in the estimated million long polymer strands can result in billions of combinations within a single DNA double-helix. These massive amount of combinations allows for the multitude of differences between every living thing on the planet from the large scale (mammal vs. plant), to the small (blue eyes vs. green eyes).
With the advances in DNA research in projects such as the Human Genome project (a research effort to characterize the genomes of human and selected model organisms through complete mapping and sequencing of their DNA ) and a host of others, the mystery of DNA and its construction is slowly being unraveled through mathematical means. Distinct formulae and patterns have emerged that may have implications well beyond those found in the fields of genetics.
What does all this chemistry and biology have to do with security you might ask? To answer that question we must first look at how biological science can be applied to mathematical computation in a field known as DNA computing.
Basics and Origins of DNA Computing
The idea is that with an appropriate setup and enough DNA, one can potentially solve huge mathematical problems by parallel search. Basically this means that you can attempt every solution to a given problem until you came across the right one through random calculation. Utilizing DNA for this type of computation can be much faster than utilizing a conventional computer.
Leonard Adleman, a computer scientist at the University of Southern California was the first to pose the theory that the makeup of DNA and itâ„¢s multitude of possible combining nucleotides could have application in brute force computational search techniques.
In early 1994, Adleman put his theory of DNA computing to the test on a problem called the Hamiltonian Path problem or sometimes referred to as the Traveling Salesman Problem known as the non deterministic polynomial time problem(NP). The crux of the problem is that the salesman must find a route to travel that passes through each city (A through G) exactly once, with a designated beginning and end. (Fig. 3)

Fig. 3 “ Basic outline of ˜Traveling Salesman™ Problem representing the 7 cities and one way streets between them.

The NP problem was chosen for Adlemanâ„¢s DNA computing test as it is a type of problem that is difficult for conventional computers to solve. The inherent parallel computing ability of DNA combination however is perfectly suited for NP problem solving.
Adleman, using a basic 7 city, 13 street model for the Traveling Salesman Problem, created randomly sequenced DNA strands 20 bases long to chemically represent each city and a complementary 20 base strand that overlaps each cityâ„¢s strand halfway to represent each street (Fig. 4). This representation allowed each multi-city tour to become a piece of double stranded DNA with the cities linked in some order by the streets.

Fig 4. “ Representation of 20 base DNA strand representing a city showing the bonding tendencies of nucleotides to DNA strands representing pathways between the cities.
By placing a few grams of every DNA city and street in a test tube and allowing the natural bonding tendencies of the DNA building blocks to occur, the DNA bonding created over answers in less than one second. Of course, not all of those answers that came about in that one second were right answers as Adleman only needed to keep those paths that exhibited the following properties:0
1. The path must start at city A and end at city G.
2. Of those paths, the correct paths must pass through all 7 cities at least once.
3. The final path(s) must contain each city in turn.
The Ëœcorrectâ„¢ answer was determined by filtering the strands of DNA according to their end-bases to determine which strands begin from city A and end in city G and discarding those that did not. The remaining strands were then measured through electrophoreic techniques to determine if the path they represent has passed through all 7 cities.
Adleman found his one true path for the ËœSalesmanâ„¢ in his problem and the possible future of DNA computing opened up in front of him. The ability to solve problems with larger numbers of cities and paths using the same techniques was immediately feasible.
CHESS PROBLEM:
For example a group of researchers at Princeton in early 2000 demonstrated an RNA computer similar to Adlemanâ„¢s which had the ability to solve a chess problem involving how many ways there are to place knights on a chess board so that none can take the others.
Adleman instantly envisioned the use of DNA computing for any type of computational problems that require massive amounts of parallel computing. The possibility existed of the very genetic makeup of an individual being used in the encryption/decryption of data from/to that person. The possibility was also seen that the DNA of an individual will give them the Ëœwho you areâ„¢ portion of the Ëœwho you areâ„¢, Ëœwhat you knowâ„¢, Ëœwhat you haveâ„¢ aspects of security authentication.
There has been much speculation of the use of this type of technology for cryptographic and steganographic means that would take advantage of the parallel computation possibilities available with DNA computing.
DNA CRYPTOGRAPHY
ËœDNA-based Cryptographyâ„¢ which puts an argument forward that the high level computational ability and incredibly compact information storage media of DNA computing has the possibility of DNA based cryptography based on one time pads. They argue that current practical applications of cryptographic systems based on one-time pads is limited to the confines of conventional electronic media whereas as small amount of DNA can suffice for a huge one time pad for use in public key infrastructure (PKI). [1]
To put this into terms of the common Alice and Bob description of secure data transmission and reception, they are basing their argument of DNA cryptography on Bob providing Alice his public key, and Alice will use it to send an encrypted message to him. The potential eavesdropper, Eve, will have an incredible amount of work to perform to attempt decryption of their transmission than either Alice or Bob.
Public key encryption splits the key up into a public key for encryption and a secret key for decryption. It's not possible to determine the secret key from the public key. Bob generates a pair of keys and tells everyone his public key, while only he knows his secret key. Anyone can use Bob's public key to send him an encrypted message, but only Bob knows the secret key to decrypt it. This scheme allows Alice and Bob to communicate in secret without having to physically meet as in symmetric encryption methods. [15]

Fig 5. Public Key Encryption illustrated.
Injecting DNA cryptography into the common PKI scenario, the researchers from Duke argue that we have the ability to follow the same inherent pattern of PKI but using the inherent massively parallel computing properties of DNA bonding to perform the encryption and decryption of the public and private keys.
It can easily be argued that DNA computing is just classical computing, albeit highly parallelized; thus with a large enough key, one should be able to thwart any DNA computer that can be built. This puts the idea of this form of DNA computing at great risk in the field of cryptography. As well, the obstacles of utilizing this kind of technology outside of a lab are extremely high.
Origins of Steganography
Steganography is a variety of encryption that completely hides text or graphics, usually unencrypted, within other text or graphics that are electronically transmitted.
The term steganography derives from the Greek words steganos meaning hidden and graphein meaning to write. One of the early Grecian methods of steganography was to shave the head of a messenger, tattoo the message to be hidden .
Throughout our history there have been many other forms of steganography used to hide messages such as the use of null ciphers, invisible inks and others. In World War II for example, German cryptographers devised a method of using microdots to conceal messages within messages themselves.
More recently, computer technology and the Internet have provided a medium for steganography that has been unseen in the past. The ability to transfer text and images is now instantaneous and accessible by individuals virtually everywhere on the planet. It has been reported that the Al Queda network of terrorists may have used steganographic means to hide their communications in organizing the September 11th attacks on the United States of America.
Readily available software applications such as the freeware application JPHide and JPSeek will encrypt messages with the common JPG format of graphic files. Other applications give the user the ability to hide data within other graphic formats such as GIF or BMP and audio formats such as MP3. Messages can now be hidden in the inconspicuous advertising banners of web pages and the music files we listen to.
Much like the world of data transmission, the steganographic world is on the lookout for the encryption methods that cannot be broken. Can DNA steganography provide that unbreakable encryption medium?
DNA Steganography
Experiments in DNA Steganography have been conducted by Carter Bancroft and his team at the Mt. Sinai School of Medicine to encrypt hidden messages within microdots.
The principles used in this experiment used a simple code to convert the letters of the alphabet into combinations of the four bases which make up DNA and create a strand of DNA based on that code. A piece of DNA spelling out the message to be hidden is synthetically created which contains the secret encrypted message in the middle plus short marker sequences at the ends of the message. The encoded piece of DNA is then placed into a normal piece of human DNA which is then mixed with DNA strands of similar length. The mixture is then dried on to paper that can be cutup into microdots with each dot containing billions of strands of DNA. Not only is the microdot difficult to detect on the plain message medium but only one strand of those billions within the microdot contains the message.
The key to decrypting the message lies in knowing which markers on each end of the DNA are the correct ones which mean there must be some sort of shared secret that is transmitted previously for this type of transmission to work successfully. Once the strand is determined via identifying the markers, the recipient uses polymerase chain reaction to multiply only the DNA which contains the message and applies the simple code to finally decode the true message. [2] Utilizing these methods, Bancroft and his team were successfully able to encode and decode the famous message ËœJune 6 Invasion: Normandyâ„¢ within a microdot placed in the full stops on a posted typed letter.

Fig 6. DNA Steganography. a, Structure of secret message DNA strand illustrating marker sequences. b, key used to encode message in DNA. c, Gel analysis of DNA strand. d, Sequence of cloned product of PCR amplification and resulting encoded message. [8]
The DNA microdot team does see this technology having applications in another field however “ that of authentication. With the amount of plant and animal genetic engineering that is taking place today and will continue to do so in the future, this methodology would allow engineers to place DNA authentication stamps within organisms they are working with to easily detect counterfeits or copyright infringements.
DNA Authentication
It is worth mentioning that DNA authentication is currently at work in the marketplace today albeit not in the genetic engineering form envisioned by Bancroft and his team. Forms of DNA authentication have already been used for such items as the official clothing from the Sydney Olympic Games, sports collectibles and limited edition art markets such as original animation cells distributed by the Hanna Barbara group of artists.
In the case of the clothing used in the Sydney Olympic Games, a Canadian company named DNA Technologies was able to showcase its DNA-tagging abilities on the world stage in the summer of 2000. All Olympic merchandise from shirts and hats to pins and coffee mugs were tagged with special ink that contained DNA taken from an unnamed Australian athlete. DNA was taken via saliva samples from the athlete and mixed into existing ink compounds which was in turn used in the regular merchandise manufacturing process. A hand held scanner is then used to scan the inked area of the clothing to determine if a piece of merchandise is authentic or not. As it is estimated that the human genome is roughly 3 billion base pairs in size, and the samples taken were from a random athlete from a Olympic team of hundreds, the possibility of counterfeiting this merchandise is difficult to say the least. For the Sydney games, DNA inks were applied too nearly 50 million items at a cost of about five cents each, including licensing, databasing , and back-end support.
There are possibilities of this type of technology to be used in the arenas of currency and other such brandable items where existing authentication methods such as holograms are proving ineffective and costly. DNA-tagging is much cheaper in comparison and ultimately more difficult to thwart.
Advantages of DNA computing
Speed “ Conventional computers can perform approximately 100 MIPS (millions of instruction per second). Combining DNA strands as demonstrated by Adleman, made computations equivalent to or better, arguably over 100 times faster than the fastest computer. The inherent parallelism of DNA computing was staggering.
Minimal Storage Requirements “ DNA stores memory at a density of about 1 bit per cubic nanometer where conventional storage media requires cubic nanometers to store 1 bit. In essence, mankinds collective knowledge could theoretically be stored in a small bucket of DNA solution.
Minimal Power Requirements - There is no power required for DNA computing while the computation is taking place. The chemical bonds that are the building blocks of DNA happen without any outside power source. There is no comparison to the power requirements of conventional computers.
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:
1. Gehani, Ashish. La Bean, Thomas H. Reif, John H. DNA-Based Cryptography. Department of Computer Science, Duke University. June 1999, http://cs.duke.edu/~reif/paper/DNAcrypt/crypt.pdf
2. Gupta, Gaurav. Mehra, Nipun. Chakraverty, Shumpa. DNA Computing. The Indian Programmer. June 12, 2001. http://theindianprogrammertechnology/dna_computing.htm
3. Peterson, Ivars. Hiding in DNA. Science News Online. April 8, 2000. http://sciencenews20000408/mathtrek.asp
4. Blahere, Kristina. DNA Computing. CNET. April 26, 2000. http://cnettechtrends
5. Frequently Asked Questions About Todayâ„¢s Cryptography 4.1 - Section 7.19 What is DNA Computing. RSA Laboratories. http://rsasecurityrsalabs/faq/7-19.html
6. Friedman, Yali. DNA Based Computers. http://dna2zdnacpu/dna2.html
7. Gehani, Ashish. La Bean, Thomas H. Reif, John H. DNA-Based Cryptography. Department of Computer Science, Duke University. June 1999, http://cs.duke.edu/~reif/paper/DNAcrypt/crypt.pdf
8. Gupta, Gaurav. Mehra, Nipun. Chakraverty, Shumpa. DNA Computing. The Indian Programmer. June 12, 2001. http://theindianprogrammertechnology/dna_computing.htm
9. Peterson, Ivars. Hiding in DNA. Science News Online. April 8, 2000. http://sciencenews20000408/mathtrek.asp
10. Blahere, Kristina. DNA Computing. CNET. April 26, 2000. http://cnettechtrends
11. Frequently Asked Questions About Todayâ„¢s Cryptography 4.1 - Section 7.19 What is DNA Computing. RSA Laboratories. http://rsasecurityrsalabs/faq/7-19.html
12. Friedman, Yali. DNA Based Computers. http://dna2zdnacpu/dna2.html

[attachment=4049]


DNA-based Computation

Abstract
Computing Science is in the middle of a major paradigm shift, driven by Molecular Biology. Adleman by his breath-taking paper announced the arrival of computers based on biochemical operations and has showed that a large class of difficult and computationally hard problems is best solved not by pushing electrons through wires in a computing laboratory, but by mixing solutions in test tubes in a molecular biology laboratory. As the computationally hard problems are the stumbling blocks for the contemporary Von Neumann computers, the DNA based computation is poised to play a greater role in computing. This article discussed about this novel idea of DNA based computation.
1. Introduction
Today's computers are millions of times more powerful than their crude ancestors in the 40's and 50's. Almost every two years, computers have become twice as fast whereas their components have assumed only half the space and however, it has also been realized that integrated circuit-technology is running against its limits and it has been a hotly debated question whether computers of an entirely new kind, quantum-mechanical computers or computers based on Molecular Biology is in the offing. One of the recently introduced unconventional paradigms, which promises to have a tremendous influence on the theoretical and practical progress of computer science is DNA computing, which under some circumstances might be an elegant alternative to the classical Turing/Von Neumann notion of computing. It is sure that the union of two of science's most fertile fields, molecular biology and computer science is to produce some remarkable offsprings.
In 1994, Adleman invented a method for solving a small instance of a Directed Hamiltonian Path (DHP) Problem by an in vitro DNA-recombination assay which he performed experimentally using hybridization, several agarose-gel separations, and PCR by handling DNA sequences in a test tube. Before discussing about this experiment, here is an overview about DNA molecules, which make the way for this sort of innovative computing model.
2. The Structure and manipulation of DNA
DNA (deoxyribonucleic acid) 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 by the pairwise attraction of bases; A 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
AACGCGTACGTACAAGTGTCCGAATGGCCAATG
TTGCGCATGCATGTTCACAGGCTTACCGGTTAC
3. Operations on DNA sequences
The following operations can be done on DNA sequences in a test tube to program the DNA computer
Synthesis: synthesis of a desired strand
Separation: separation of strands by length
Merging: pour two test tubes into one to perform union
Extraction: extract those strands containing a given pattern
Melting/Annealing: break/bond two single strand DNA molecules with complementary sequences.
Amplification: use PCR to make copies of DNA strands
Cutting: cut DNA with restriction enzymes
Ligation: Ligate DNA strands with complementary sticky ends using ligase.
Detection: Confirm presence/absence of DNA in a given test tube.
The Hamiltonian Path Problem(HPP) may be phrased as follows: given a set of n cities connected by one-way and two-way roads, does there exist a path through this network starting at the first city and ending at the last city such that each city is visited once and only once?.
The problem is deceptively easy to describe, but in fact belongs to the notoriously intractable class of NP-complete problems, which signifies the class of problems solvable in Nondeterministic Polynomial(NP) time. Typically, these problems involve a search where at each point in the search there is an exponential increase in the number of possibilities to be searched through, but where each possibility can be searched through polynomial time.
Consider a map with five cities linked by one-way and two-way roads. Adleman's approach was to encode each city and each route between two cities in DNA strands, put into a test tube.
For example, the strand coding for cities 1 and 2 could be AATGCCGG, TTTAAGCC respectively. A road from city 1 to 2 is encoded in such a way that the first part is the complementary strand to the second half of strand for city 1, and the second part is the complementary strand to the first half of the strand for city 2, i.e. GGCCAAAT.
That is, GGCC is the complementary version of the last four bases of city 1, and AAAT is the complementary version of the first four bases of city 2. Thus the edge joining the cities 1 and 2 is being encoded as follows.
GGCCAAAT
AATGCCGGTTTAAGCC
Similarly the DNA molecules strands can be formed for all the nodes and edges representing all possible routes in the directed graph in the test tube. The first stage of Adleman's computation was to extract those long strands which start with city 1 and store these in a separate test tube.
The second stage was to extract those strands which corresponded to a certain length which signified exactly 5 cities being passed through. If each city is represented by 8 DNA bases, all strands of 40 bases would be extracted and stored in a separate test tube.
The third stage is to extract all those strands containing the DNA sequence for city 1, then those containing the DNA sequence for city 2, and so on. If there is a solution to this route problem, it will be found in the strands extracted for the last city 5.
4. The case for DNA computing
The possible advantages of DNA-based computer architecture became immediately apparent:
Computing with DNA offers the advantage of massive degrees of miniaturization and parallelism over conventional silicon-based machines. For example, a square centimeter of silicon can currently support around a million transistors, whereas current manipulation techniques can handle to the order of 1020 strands of DNA.
Size: 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(electrophoretic separation, ligation, PCR-amplifications) 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: 1019 operations per Joule. This is about a billion times more energy efficient than today's electronic devices.
The research in this field had both experimental and theoretical aspects. The experiments that have actually been carried out are not numerous so far. P.Kaplan replicated Adleman's experiment, a Wisconsin team of computer scientists and biochemists made a partial progress in solving a 5-variable instance of SAT problem, an another NP-complete problem, by using a surface-based approach. F.Guarnieri and his team have used a horizontal chain-reaction for DNA-based addition.
Also, various aspects of the implementability of DNA computing have been experimentally investigated: the effect of good encodings on the solutions of Adleman's problem were addressed; the complications raised by using the Polymerase Chain Reaction (PCR) were studied; the usability of self-assembly of DNA was studied; the experimental gap between the design and assembly of unusual DNA structures was pointed out; joining and rotating data with molecules was reported; concatenation with PCR was studied; evaluating simple Boolean formulas was started; ligation experiments in computing with DNA were conducted.
The theoretical work on DNA computing consists, on one side, of designing potential experiments for solving various problems by means of DNA manipulation. Descriptions of such experiments include the Satisfiability Problem, breaking the Data Encryption Standard (DES), expansions of symbolic determinants, matrix multiplication, graph connectivity and knapsack problem using dynamic programming, road coloring problem, exascale computer algebra problems, and simple Horn clause computation.
On the other side, the theoretical research on DNA computing comprises attempts to model the process in general, and to give it a mathematical foundation. To this aim, models of DNA computing have been proposed and studied from the point of view of their computational power and their in-vitro feasibility. Some of them are given below.
5. Models and Formats of DNA Computation
In the two years that followed, a lot of theoretical work has been done on generalizing Adleman's approach in order to define a general-purpose DNA-based molecular computer that could also be implemented by an in vitro system. Lipton generalized Adleman's model and showed how his model can encompass solutions to other NP-complete problems. The other model is by splicing operation proposed by Head and vigrously followed by many researchers using formal language theory. It is shown that the generative power of finite extended splicing systems is equal to that of Turing Machines. Afterwords, Paun and others introduced the so-called sticker model. Unlike previous models, the sticker mode has a memory that can both read and written to, and employs reusable DNA. Also there is a proposal about the tendency of DNA structures to self-assemble as a computational tool. They show that the self-assembly of complex branches known as double cross-overs into two-dimensional sheets or three-dimensional solids is a computationally powerful model.
However, there are some impediments to effective computation by these models. It is a common feature of all the proposed implementations that the biological operations to be used are assumed to be error-free. An operation central to and frequently employed in most models is the extraction of DNA strands containing a certain sequence (known as removal by DNA hybridization). The most important problem with this method is that extraction is not 100% efficient and may at times inadvertently remove strands that do not contain the specified sequence. Especially for a large problem, the number of extractions required may run into hundreds, or even thousands resulting a high probability of incorrect hybridization.
Thus, a novel error-resistant model of DNA computation has been proposed by Alan Gibbons and his team that obviates the need for hybridization extraction within the main body of the computation.
Like previous models, this model is particularly effective for algorithmic description. It is sufficiently strong to solve any of the problems in the class NC and the authors have given DNA algorithms for 3-vertex-colorability problem, Permutations Problem, Hamiltonian Path Problem, the Subgraph isomorphism problem, and the Maximum clique and maximum independent set problem.
There are two general formats in which complex combinatorial sets of DNA molecules may be manipulated.
¢ in solution ( solution-phase format)
¢ attached to a surface (solid-phase format)
The solid-phase format possesses many important advantages over the solution-phase format.
 Facilitated sample handling.
With the DNA molecules attached to a support, the experimental manipulations are very simple. They are addition of a solution to the support and removal (washing) to a solution from the support. These steps are readily automated.
 Decreased losses during sample handling
 Reduction of interference between oligonucleotides
 Solid-phase chemistry permits facile purification of the DNA molecules at every step of the process.
6. Pitfalls of DNA Computing
The idea of using DNA to solve computational problems is certainly intriguing and elegant, and DNA does provide a massive parallelism far beyond what is available on existing silicon-based computers. However, there are many technological hurdles to overcome. We give below one of the huge fundamental problem to be solved to attain the goal of designing universally programmable molecular computer.
The fundamental problem is that, the function of 2n is exponential whether it counts time or molecules. It has been estimated that Adleman's Hamiltonian path problem, if enhanced to 50 or 100 cities, would require tons of DNA. The minimum amount of required DNA for Lipton's SAT method needs a few grams of DNA molecules for 70 variables. If this is increased to 100 variables, the minimum DNA requirement of millions of kilograms.
Thus raw idea of brute-force enumeration is not going to work beyond modest problem sizes. Thus it is imperative to bring forth new revolutionary ideas to make this notion of DNA-based computing to work realistically. Only time and investment will tell where the initial ideas for DNA computing from those experts will lead. Many enhancive ideas have been published but all of them suffer under this fundamental problem. Hopefully the future molecular computation methods may bring forth new revolutionary ideas to overcome this very fundamental as well as significant hurdle
7. The future of DNA Computing
The significance of this research is two-fold: it is the first demonstrable use of DNA molecules for representing information, and also the first attempt to deal with an NP-complete problem. But still much more work needs to be done to develop error-resistant and scalable laboratory computations. Designing experiments that are likely to be successful in the laboratory and algorithms that proceed through polynomial-sized volumes of DNA is the need of the hour. It is unlikely that DNA computers will be used for tasks like word processing, but they may ultimately find a niche market for solving large-scale intractable combinatorial problems. The goal of automating, miniaturizing and integrating them into a general-purpose desktop DNA computer may take much longer time.

All the best!

hey pls help me with a seminar report and ppt on dna computing

[attachment=4999]

---

Introduction

Need of DNA computer?

-Moore’s Law states that silicon microprocessors double in complexity roughly every two years.
-One day this will no longer hold true when miniaturisation limits are reached. Intel scientists say it will happen in about the year 2018.
-Require a successor to silicon.

What is DNA?


-DNA stands for Deoxyribonucleic Acid
-DNA represents the genetic blueprint of living creatures
-DNA contains “instructions” for assembling cells
-Every cell in human body has a complete set of DNA
-DNA is unique for each individual

[attachment=7584]

INTRODUCTION
Contemporary technology used for computing :- Silicon Based Semiconductor Technology
Upper Limits in Terms of Speed and Size
Alternative Technology : DNA Computing or Molecular Computing.
DNA Computing :- Still an Emerging Field
BEYOND SILICON
Moore’s Law : The Speed of Computing Chip will Double Roughly Every 18 months
Silicon Based Semiconductor Technology can’t Sustain Moore’s Predictions.
Physical Limits Posed By Silicon Based Technology
An Issue of Muller :- The Narrowest Feature of Semiconductor Device- The Gate-Oxide will Reach its Fundamental Physical Limits.

What is DNA Computing ?
DNA and RNA computing (also sometimes referred to as bio-molecular computing or molecular computing) is a new computational paradigm that harnesses biological molecules to solve computational problems.

What is DNA?
DNA is Deoxyribonucleic Acid.
It is a Double-Stranded Helix of Nucleotides that Carries the genetic information of a cell.
These Nucleotides consists of one of the 4 bases-Adenine(A), Thymine(T), Guanine(G), Cytosine©.
A pairs with T, G pairs with C.

Origins of DNA Computing
Dr. Leonard Adleman : the Father of DNA Computing.
By using strands of DNA annealing to each other, he was able to compute a solution to an instance of the Hamiltonian path problem (HPP).
This is Also Known as The Travelling Salesman Problem(TSP).

Conditions
The Path Must Start at City A and End at City E
Of Those Paths, The Correct Paths Must Pass Through All 5 Cities at Least Once.
The Final Path(s) must Contain Each City in Turn.
Advantages Of DNA Computers:-
Unmatchable Speed
Due To Inherent Parallelism 100 Times Faster Than Fastest Super Computer.
Minimal Storage Requirement:-
DNA stores Memory at a Density of About One Bit Per Cubic Nanometer.

Advantages:-
Minimal Power Requirement : Because of The Chemical Bonds.
Clean, Cheap and Available.
Suitable for Combinatorial Problems .
Disadvantages of DNA Computer
Occasionally Slow
Hydrolysis : The DNA Molecules Can Fracture
COMPARISON OF DNA AND CONVENTIONAL  ELECTRONIC COMPUTERS 
Similarities
Transformation of Data :- Both Use Boolean Logic.
Manipulation of Data :- Both Store Information in Strings.
Computation Ability

Differences
Size
Representation of Data : Base 4 For DNA Computers
Parallelism : DNA Computers inherently Parallel.
Material

An Overview of the Evolutionary Trends in Molecular Computing using DNA
The incipient paradigm of using the biochemical molecule of DNA to
solve computational problems is addressed by this article. In DNA computing, the strands of DNA are used to perform the computing operations. the instruction strands and the input data strands are the two types of strands that are present in the computer. The the input data strands are spliced by the instruction strands to produce the output. They can be classified as the true computers according to the the Turing machine concept, because he instruction strands are generic nucleotide codes for the various operations. the potential storage capacity of DNA is the greatest advantage that experts proclaim for this computer. The storage capacity of the DNA strands is far greter than the latest silicon technology. the difficulty of predicting circuit performance at the design stage is the most important challenge that the designers face . This means that significant experimental effort must be put in to verify the actual design. This disadvantage has been overcome by the evolutionary simulations which has been used to create new circuit components and optimize circuit performance of DNA computing devices.
Report:
[attachment=7879]

---

[attachment=7891]

BY
S.SUBH


Definition
DNA structure
Solving Hamiltonian Path problem
Different generations
Conclusion



DEFINITION
Need of DNA computer?
Moore’s Law states that silicon microprocessors double in complexity roughly every two years.
One day this will no longer hold true when miniaturisation limits are reached. Intel scientists say it will happen in about the year 2018.
Require a successor to silicon.


What is DNA?
Source code to life
Instructions for building and regulating cells
Data store for genetic inheritance
Think of enzymes as hardware, DNA as software

What is DNA made of?
Composed of four nucleotides (+ sugar-phosphate backbone)
A – Adenine
T –Thymine
C – Cytosine
G – Guanine

Bond in pairs
A – T
C – G

APPLICATIONS
DNA chips
Genetic programming
Pharmaceutical applications
Cracking of coded messages

---

Presented By
SOMYA JAIN

---

[attachment=9757]
What is DNA ?
 DNA stands for Deoxyribonucleic Acid
 All organisms on this planet are made of the same type of genetic element.
 DNA carries the genetic information of a cell.
 Within the cells of any organism is a substance called DNA which is a double stranded helix of
nucleotides.
Each strand is a series of
4 different nucleotides
Adenine (A)
Guanine (G)
Thymine (T)
Cytosine ©
DNA Structure :-
 The key thing to note about the structure of
DNA is it’s inherent complementarity
 A binds with T and G binds with C
 One strand is therefore the “mirror image of another”
 Complement of AGGCT is TCCGA
 Complement of TAGGA is ATCCT
 Complement of GATTACCA is CTAATGGT
Interesting Facts :
 DNA molecule is 1.7 meters long
 Stretch out all the DNA in your cells and you can reach the moon 6000 times!
DNA Computing :-
 Around 1950 first idea (Precursor Feynman)
 First important experiment 1994: Leonard Adleman
Molecular level (just greater than 10-9 meter)
 In only 5 grams of DNA we get around 1021 bases !
 Each DNA strand represents a processor !

Submitted By
JOM JOY KURIAN

---

[attachment=10068]
ABSTRACT
Molecular biologists are beginning to unravel the information-processing tools such as
enzymes that evolution has spent billions of years refining. These tools are now been
taken in large numbers of DNA molecules and using them as biological computer
processors.
Dr. Leonard Adleman, a well-known scientist, found a way to exploit the speed and
efficiency of the biological reactions to solve the “Hamiltonian path problem”, also
known as the “traveling salesman problem”.
Based on Dr. Adleman’s experiment, we will explain DNA computing, its algorithms,
how to manage DNA based computing and the advantages and disadvantages of DNA
computing.
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, tha is, performing computations, simultaneously.
History & Motivation
"Computers in the future may weigh no more than 1.5 tons." So said Popular Mechanics in 1949. Most of us today, in the age of smart cards and wearable PCs would find that statement laughable. We have made huge advances in miniaturization since the days of room-sized computers, yet the underlying computational framework has remained the same. Today's supercomputers still employ the kind of sequential logic used by the mechanical dinosaurs of the 1930s. Some researchers are now looking beyond these boundaries and are investigating entirely new media and computational models. These include quantum, optical and DNA-based computers. It is the last of these developments that this paper concentrates on.
The current Silicon technology has following limitations:
 Circuit integration dimensions
 Clock frequency
 Power consumption
 Heat dissipation.
The problem's complexity that can be afforded by modern processors grows up, but great challenges require computational capabilities that neither most powerful and distributed systems could reach.
The idea that living cells and molecular complexes can be viewed as potential machinic components dates back to the late 1950s, when Richard Feynman delivered his famous paper describing "sub-microscopic" computers. More recently, several people have advocated the realization of massively parallel computation using the techniques and chemistry of molecular biology. DNA computing was grounded in reality at the end of 1994, when Leonard Adleman, announced that he had solved a small instance of a computationally intractable problem using a small vial of DNA. By representing information as sequences of bases in DNA molecules, Adleman showed how to use existing DNA-manipulation techniques to implement a simple, massively parallel random search. He solved the traveling salesman problem also known as the “Hamiltonian path" problem.
There are two reasons for using molecular biology to solve computational problems.
(i) The information density of DNA is much greater than that of silicon : 1 bit can be stored in approximately one cubic nanometer. Others storage media, such as videotapes, can store 1 bit in 1,000,000,000,000 cubic nanometer.
(ii) Operations on DNA are massively parallel: a test tube of DNA can contain trillions of strands. Each operation on a test tube of DNA is carried out on all strands in the tube in parallel.
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:
1) adenine (A),
2) guanine (G),
3) cytosine©,
4) thymine (T);
they are often called bases. DNA supports two key functions for life:

Presented By
Thierry Metais

---

[attachment=10285]
DNA Computing
Introduction to DNA:
 The life’s molecule:
Introduction:
What is DNA computing ?
 Around 1950 first idea (precursor Feynman)
 First important experiment 1994: Leonard Adleman
 Molecular level (just greater than 10-9 meter)
 Massive parallelism.
 In a liter of water, with only 5 grams of DNA we get around 1021 bases !
 Each DNA strand represents a processor !
A bit of biology
 The DNA is a double stranded molecule.
 Each strand is based on 4 bases:
 Adenine (A)
 Thymine (T)
 Cytosine ©
 Guanine (G)
 Those bases are linked through a sugar (desoxyribose)
IMPORTANT:
 The linkage between bases has a direction.
 There are complementarities between bases (Watson-Crick).
(A)ßà (T)
©ßà(G)
DNA manipulations:
 If we want to use DNA as an information bulk, we must be able to manipulate it .
 However we are talking of handling molecules…
 ENZYMES = Natural CATALYSERS.
 So instead of using physical processes, we would have to use natural ones, more effective:
 for lengthening: polymerases…
 for cutting: nucleases (exo/endo-nucleases)…
 for linking: ligases…
 Serialization: 1985: Kary Mullis à PCR
Thank this reaction we get millions of identical strands, and we are allowed to think of massive parallel computing.
And what now ?
 Situation:
 Molecular level.
 Lots of “agents”. (strands)
 Tools provided by nature. (enzymes)
 How can we use all this? If there is a utility …
Coding the information:
 1994: THE Adleman’s experiment.
 Given a directed graph can we find an hamiltonian path (more complex than the TSP).
 In this experiment there are 2 keywords:
massive parallelism (all possibilities are generated)
complementarity (to encode the information)
 This experiment proved that DNA computing wasn’t just a theoretical study but could be applied to real problems like cryptanalysis (breaking DES ).
Adleman experiment:
 Each node is coded randomly with 20 bases.
 Let Si be a code, h be the complementarity mapping.
h(ATCG) = TAGC.
 Each Si is decomposed into 2 sub strands of length 10: Si = Si’ Si’’
 Edge(i,j) will be encode as h(Si’’Sj’)à( preserve edge orientation).
 Code:
 Input(N) //All vertices and edges are mixed, Nature is working
 NßB(N,S0) //S0 was chosen as input vertice.
 NßE(N,S4) //S4 was chosen as output vertice.
 NßE(N,<=140) // due to the size of the coding.
 For i=1 to 5 do Nß+N(N, Si) //Testing if hamiltonian path
 Detect(N) //conclusion … ‘
New generation of computers?
 In the second part of [1], it is proven through language theory that DNA computing “guarantees universal computations”.
 Many architectures have been invented for DNA computations.
 The Adleman experiment is not the single application case of DNA computing…
 Stickers model:
 Memory complex = Strand of DNA (single or semi-double).
 Stickers are segments of DNA, that are composed of a certain number of DNA bases.
 To use correctly the stickers model, each sticker must be able to anneal only at a specific place in the memory complex.
 To visualize:
 About a stickers machine?
 Simple operations: merge, select, detect, clean.
 à Tubes are considered (cylinders with two entries)
 However for a mere computation (DES):
 Great number of tubes is needed (1000).
 Huge amount of DNA needed as well.
 Practically no such machine has been created….
à Too much engineering issues.
Why don’t we see DNA computers everywhere?
 DNA computing has wonderful possibilities:
 Reducing the time of computations* (parallelism)
 Dynamic programming !
 However one important issue is to find “the killer application”.
 Great hurdles to overcome…
 Some hurdles:
 Operations done manually in the lab.
 Natural tools are what they are…
 Formation of a library (statistic way)
 Operations problems
Conclusion:
 The paradigm of DNA computing has lead to a very important theoretical research.
 However DNA computers won’t flourish soon in our daily environment due to the technologic issues.
 Adleman renouncement toward electronic computing.
 Is all this work lost ?
 NO ! à “Wet computing”

PRESENTED BY
K.SWAPNA

---

[attachment=10601]
DEFINITION
Need of DNA computer?
 Moore’s Law states that silicon microprocessors double in complexity roughly every two years.
 Require a successor to silicon.
FEATURERS OF DNA
What is DNA?
 Source code to life
 Instructions for building and regulating cells
 Data store for genetic inheritance
 Think of enzymes as hardware, DNA as software
What is DNA made of?
 Composed of four nucleotides (+ sugar-phosphate backbone)
 A – Adenine
 T –Thymine
 C – Cytosine
 G – Guanine
 Bond in pairs
 A – T
 C – G
Dense Information Storage
How enormous is the parallelism?
 A test tube of DNA can contain trillions of strands. Each operation on a test tube of DNA is carried out on all strands in the tube in parallel !
 Check this out……. We Typically use
Can DNA Compute?
 DNA itself does not carry out any computation. It rather acts as a massive memory.
 BUT, the way complementary bases react with each other can be used to compute things.
 Proposed by Adelman in 1994
 Technological Developments.
Evolution of the DNA computer
 Began in 1994 when Dr. Leonard Adleman wrote the paper “Molecular computation of solutions to combinatorial problems”.
 He then carried out this experiment successfully – although it took him days to do so!
 DNA computers moved from test tubes onto gold plates.
 First practical DNA computer unveiled in 2002. Used in gene analysis.
 Self-powered DNA computer unveiled in 2003.
 First programmable autonomous computing machine in which the input, output, software and hardware were all made of DNA molecules.
 Can perform a billion operations per second with 99.8% accuracy.
 Biological computer developed that could be used to fight cancers.
 ‘Designer DNA’ identifies abnormal and is attracted to it.
 The Designer molecule then releases chemicals to inhibit its growth or even kill the malignant cells.
 Successfully tested on animals.
DNA COMPUTER Vs SILICON COMPUTER
ADVANTAGES
LIMITATIONS
 DNA computing involves a relatively large amount of error
 Requires human assistance!
 Time consuming laboratory procedures.
 No universal method of data representation.
APPLICATIONS
 DNA chips
 Genetic programming
 Pharmaceutical applications
Conclusion
o DNA computers showing enormous potential, especially for medical purposes as well as data processing applications.
o Many issues to be overcome to produce a useful DNA computer.
o Still a lot of work and resources required to
develop it into a fully fledged product.

DNA Computing Application:Cryptography
PRESENTED BY:
Archana Das

---

[attachment=11074]
Introduction
 The world of encryption appears to be ever shrinking. Several years ago the thought of a 56-bit encryption technology seemed forever safe, but as mankind's collective computing power and knowledge increases, the safety of the world’s encryption methods seems to disappear equally as fast.
 Mathematicians and physicists attempt to improve on encryption methods while staying within the confines of the technologies available to us.
 Existing encryption algorithms such as RSA have not yet been compromised but many fear the day may come when even this bastion of encryption will fall.
 There is hope for new encryption algorithms however the science of our very genetic makeup is also showing promise for the information security world.
 All organisms on this planet are made of the same type of genetic blueprint which bind us together. The way in which that blueprint is coded is the deciding factor as to whether you will be bald, have a bulbous nose, male, female or even whether you will be a human or an oak tree.
 Within the cells of any organism is a substance called Deoxyribonucleic Acid (DNA) which is a double-stranded helix of nucleotides which carries the genetic information of a cell. This information is the code used within cells to form proteins and is the building block upon which life is formed.
 Strands of DNA are long polymers of millions of linked nucleotides. These nucleotides consist of one of four nitrogen bases, a five carbon sugar and a phosphate group.
 The nucleotides that make up these polymers are named after the nitrogen base that it consists of; Adenine (A), Cytosine ©, Guanine (G) and Thymine (T). These nucleotides will only combine in such a way that C always pairs with G and T always pairs with A.
Nitrogen Bases
 The combination of these 4 nucleotides in the estimated million long polymer strands can result in billions of combinations within a single DNA double-helix.
 These massive amount of combinations allows for the multitude of differences between every living thing on the planet from the large scale (mammal vs. plant), to the small (blue eyes vs. green eyes).
Origins Of DNA Computing
 Leonard Adleman, a computer scientist at the University of Southern California was the first to suggest the theory that the makeup of DNA and it’s multitude of possible combining nucleotides could have application in brute force computational search techniques.
 In early 1994, Adleman put his theory of DNA computing to the test on a problem called the Traveling Salesman Problem.
Basics Of DNA Computing :
 The biological science can be applied to mathematical computation in a field known as DNA computing.
 DNA computing or molecular computing are terms used to describe utilizing the inherent combinational properties of DNA for massively parallel computation.
 The idea is that with an appropriate setup and enough DNA, one can potentially solve huge mathematical problems by parallel search.
 Basically this means that you can attempt every solution to a given problem until you came across the right one through random calculation.
 Utilizing DNA for this type of computation can be much faster than utilizing a conventional computer.
Advantages :
1. Parallelism :
 A test tube of DNA can contain trillions of strands. Each operation on a test tube of DNA is carried out on all strands in the tube in parallel !
2. Speed
Conventional computers can perform approximately 100 MIPS (millions of instruction per second). Combining DNA strands as demonstrated by Adleman, made computations equivalent to or better, arguably over 100 times faster than the fastest computer.
3. Storage Requirements :
 This image shows 1 gram of DNA on a CD. The CD can hold 800 MB of data.
 The 1 gram of DNA can hold about 1x1014 MB of data.
4. Minimal Power Requirements:
 There is no power required for DNA computing while the computation is taking place. The chemical bonds that are the building blocks of DNA happen without any outside power source. There is no comparison to the power requirements of conventional computers.
Example :
 The problem is that the salesman must find a route to travel that passes through each city
(A through G) exactly once, with a designated beginning and end.
 This problem was chosen for Adleman’s DNA computing test as it is a type of problem that is difficult for conventional computers to solve.
 The inherent parallel computing ability of DNA combination however is perfectly suited for the problem solving.
 Adleman, using a basic 7 city, 13 street model for the Traveling Salesman Problem, created randomly sequenced DNA strands 20 bases long to chemically represent each city and a complementary 20 base strand that overlaps each city’s strand halfway to represent each street
 By placing a few grams of every DNA city and street in a test tube and allowing the natural bonding tendencies of the DNA building blocks to occur, the DNA bonding created over answers in less than one second.
 Of course, not all of those answers that came about in that one second were right answers as Adleman only needed to keep those paths that exhibited the following properties:
1. The path must start at city A and end at city G.
2. Of those paths, the correct paths must pass
through all 7 cities at least once.
3. The final path must contain each city in turn.
 The ‘correct’ answer was determined by filtering the strands of DNA according to their end-bases to determine which strands begin from city A and end in city G and discarding those that did not.
 The remaining strands were then measured through electrophoreic techniques to determine if the path they represent has passed through all 7 cities.
 Adleman found his one true path for the ‘Salesman’ in his problem and the possible future of DNA computing opened up in front of him.
 The ability to solve problems with larger numbers of cities and paths using the same techniques was immediately feasible.

hello ,
I am a BE student , i want the seminar report on "dna computing in security" in details .. i need it urgently .. i hope u will send me that soon .... plz i am in need of it urgently ...
send me to
asho005[at]yahoo.com and
prashanthi.hj[at]gmail.com

Presented By
Thierry Metais

---

[attachment=11999]
DNA Computing
Introduction:
What is DNA computing ?
 Around 1950 first idea (precursor Feynman)
 First important experiment 1994: Leonard Adleman
 Molecular level (just greater than 10-9 meter)
 Massive parallelism.
 In a liter of water, with only 5 grams of DNA we get around 1021 bases !
 Each DNA strand represents a processor !
 A bit of biology
 The DNA is a double stranded molecule.
 Each strand is based on 4 bases:
 Adenine (A)
 Thymine (T)
 Cytosine ©
 Guanine (G)
 Those bases are linked through a sugar (desoxyribose)
IMPORTANT:
 The linkage between bases has a direction.
 There are complementarities between bases (Watson-Crick).
(A)ßà (T)
©ßà(G)
DNA manipulations:
 If we want to use DNA as an information bulk, we must be able to manipulate it .
 However we are talking of handling molecules…
 ENZYMES = Natural CATALYSERS.
 So instead of using physical processes, we would have to use natural ones, more effective:
 for lengthening: polymerases…
 for cutting: nucleases (exo/endo-nucleases)…
 for linking: ligases…
 Serialization: 1985: Kary Mullis à PCR
Thank this reaction we get millions of identical strands, and we are allowed to think of massive parallel computing.
 And what now ?
Situation:
 Molecular level.
 Lots of “agents”. (strands)
 Tools provided by nature. (enzymes)
 How can we use all this? If there is a utility …
Coding the information:
 1994: THE Adleman’s experiment.
 Given a directed graph can we find an hamiltonian path (more complex than the TSP).
 In this experiment there are 2 keywords:
massive parallelism (all possibilities are generated)
complementarity (to encode the information)
 This experiment proved that DNA computing wasn’t just a theoretical study but could be applied to real problems like cryptanalysis (breaking DES ).
Adleman experiment:
 Each node is coded randomly with 20 bases.
 Let Si be a code, h be the complementarity mapping.
h(ATCG) = TAGC.
 Each Si is decomposed into 2 sub strands of length 10: Si = Si’ Si’’
 Edge(i,j) will be encode as h(Si’’Sj’)à( preserve edge orientation).
 Code:
 Input(N) //All vertices and edges are mixed, Nature is working
 NßB(N,S0) //S0 was chosen as input vertice.
 NßE(N,S4) //S4 was chosen as output vertice.
 NßE(N,<=140) // due to the size of the coding.
 For i=1 to 5 do Nß+N(N, Si) //Testing if hamiltonian path
 Detect(N) //conclusion …
New generation of computers?
 In the second part of [1], it is proven through language theory that DNA computing “guarantees universal computations”.
 Many architectures have been invented for DNA computations.
 The Adleman experiment is not the single application case of DNA computing…
Stickers model:
 Memory complex = Strand of DNA (single or semi-double).
 Stickers are segments of DNA, that are composed of a certain number of DNA bases.
 To use correctly the stickers model, each sticker must be able to anneal only at a specific place in the memory complex.
To visualize:
 About a stickers machine?
 Simple operations: merge, select, detect, clean.
 à Tubes are considered (cylinders with two entries)
 However for a mere computation (DES):
 Great number of tubes is needed (1000).
 Huge amount of DNA needed as well.
 Practically no such machine has been created….
à Too much engineering issues.
 Why don’t we see DNA computers everywhere?
DNA computing has wonderful possibilities:
 Reducing the time of computations* (parallelism)
 Dynamic programming !
 However one important issue is to find “the killer application”.
 Great hurdles to overcome…
 Some hurdles:
 Operations done manually in the lab.
 Natural tools are what they are…
 Formation of a library (statistic way)
 Operations problems
Conclusion:
 The paradigm of DNA computing has lead to a very important theoretical research.
 However DNA computers won’t flourish soon in our daily environment due to the technologic issues.
 Adleman renouncement toward electronic computing.
 Is all this work lost ?
 NO ! à “Wet computing”

Presented By
Rohit Mistry

---

[attachment=12168]
DNA Computers
Conception
 Moore’s Law states that silicon microprocessors double in complexity roughly every two years.
 One day this will no longer hold true when miniaturisation limits are reached. Intel scientists say it will happen in about the year 2018.
 Require a successor to silicon.
Current Problems
 In the words of Dr. Leonard Adleman, “we simply cannot, at this time, control molecules with the deftness that electrical engineers and physicists control electrons”.
 Use of ‘biochips’ in human bodies may generate opposition from technophobes.
Specifications
 One pound of DNA has the capability to store more information than all the electronic computers ever built.
 One cm3 of DNA can hold approximately 10 terabytes of data
 DNA computer the size of a teardrop would be more powerful than the worlds most powerful supercomputer
Evolution of the DNA computer (1)
 Began in 1994 when Dr. Leonard Adleman wrote the paper “Molecular computation of solutions to combinatorial problems”.
 He then carried out this experiment successfully – although it took him days to do so!
 DNA computers moved from test tubes onto gold plates.
 First practical DNA computer unveiled in 2002. Used in gene analysis.
 Self-powered DNA computer unveiled in 2003.
 First programmable autonomous computing machine in which the input, output, software and hardware were all made of DNA molecules.
 Can perform a billion operations per second with 99.8% accuracy.
 Biological computer developed that could be used to fight cancers.
 ‘Designer DNA’ identifies abnormal and is attracted to it.
 The Designer molecule then releases chemicals to inhibit its growth or even kill the malignant cells.
 Successfully tested on animals.
Advantages of DNA computers
 There is always a plentiful supply of it.
 Since there is a plentiful supply, it is a cheap resource.
 DNA biochips can be made cleanly, unlike the toxic materials used to make traditional microprocessors.
 DNA computers can be made many times smaller than today's computers.
 DNA computers are massively parallel in their computation.
 Excellent for NP problems such as the Knight problem and the Travelling Salesman problem.
 Solutions that would otherwise take months to compute could be found in hours.
Current problems with the DNA computer
 DNA computers are not completely accurate at this moment in time.
 During an operation, there is a 95% chance a particular DNA molecule will ‘compute’ correctly. Would cause a problem with a large amount of operations.
 DNA has a half-life.
 Solutions could dissolve away before the end result is found.
Environment compatibility (1)
 DNA computer must aim to be compatible with seven environments to succeed.
• Intrapsychic – Already complies since it has been conceptualised!
• Construction/manufacture – This will be answered in time.
• Adoption – Should inherit customer base of silicon computers.
• Use – Already seen the potential for this.
• Failure – Inherits this from silicon microprocessors.
• Scrapping – Cleaner to dispose of than current microprocessors.
• Political/ecological – Could face opposition from technophobes.
• Conclusion
 DNA computers showing enormous potential, especially for medical purposes as well as data processing applications.
 Still a lot of work and resources required to develop it into a fully fledged product.

Presented by:
DIBYAKANTA MOHARANA

---

[attachment=13519]
INTRODUCTION
Double-stranded molecule twisted into a helix
Each strand, comprised of a
sugar-phosphate backbone and
attached bases, is connected to
a complementary strand by non
-covalent hydrogen bonding
between paired bases
Bases are:
adenine (A)
thymine (T)
guanine (G).
cytosine ©
A and T are connected by two hydrogen bonds. G and C
are connected by three hydrogen bonds
DNA as computing machine
A DNA-based finite automaton computes via repeated
cycles of self assembly and processing
DNA molecules serve as input, output, and software, and
the hardware consists of DNA restriction and ligation
Enzymes Using ATP as fuel
The reversible self-assembly is driven by hybridization
energy between input/software complementary sticky ends,
followed by an irreversible processing step i.e. an
irreversible software-directed cleavage (hydrolysis of the
Input DNA backbone)of the input molecule,which drives the computation forward by increasing entropy and releasing
heat and hence does not require ATP or heating.
The cleavage uses the restriction enzyme FokI, which serves as the hardware, to operate on a non covalent software/input hybrid.
This automaton use a fixed amount of software and hardware molecules to process any input molecule of any length without external energy supply.
This automaton demonstrate automata per µl
performing transitions per second per µl
dissipating about W/µl as heat .
CONCEPTS OF DNA COMPUTING
• DNA computing is also known as molecular computing. 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.
• Think of DNA as software and enzymes as hardware. Put them together in a test tube. The incredible thing is that once the DNA sequence has been created, simply just add water to initiate the computation.
• DNA computer can be called as a bio-chemical reaction system where they choose specific reactions and use a program to control the order of reactions in which to trigger them.
• The promise of DNA computing is massive parallelism: with the given setup and enough DNA, one can potentially solve huge problems by parallel search. This can be much faster than a conventional computer.
DNA computers using dynamic programming could solve substantially larger instances because their large memory capacity then either conventional computers

[attachment=13883]
DNA Computing
Introduction
DNA computing is a novel technology that seeks to capitalize on the enormous informational capacity of DNA, biological molecules that can store huge amounts of information and are able to perform operations similar to that of a computer, through the deployment of enzymes, biological catalysts that act like software to execute desired operations.
The appeal of DNA computing lies in the fact that DNA molecules can store far more information than any existing conventional computer chip. Also, utilizing DNA for complex computation can be much faster than utilizing a conventional computer. The ability to harness this computational power shall determine the fate of next generation of computing.
DNA computers have the potential to take computing to new levels,
picking up where Moore’s law leave off.
The several advantages of DNA over silicon are:
DNA molecules have a potential to store extensively large amount
of information. It has been estimated that a gram of dried DNA can hold as
much information as a trillion CD’s. More than 10 trillion DNA molecules
can fit into an area of 1 cubic centimeter. With this small amount of DNA
a computer would be able to hold 10 terabytes of data, and perform 10
trillion calculations at a time.
What is DNA?? (Deoxyribo Nucleic Acid)
Structure Of DNA
Structure of DNA
Scope and recent updates
Scientists have taken DNA from the free-floating world of the test tube and anchored it securely to a surface of glass and gold. University of Wiscosnin-Madison researchers have developed a thin, gold-coated plate of glass about an inch square. They believe it is the optimum working surface on which they can attach trillions of strands of DNA. Putting DNA computing on a solid surface greatly simplifies the complex and repetitive steps previously used in rudimentary DNA computers.
Importantly it takes DNA out of the test tube and puts it on a solid surface, making the technology simpler, more accessible and more amenable to the development of large DNA computers capable of tackling the kind of complex problems that conventional computers now handle routinely. Researchers believe that by the year 2010 the first DNA chip will be commercially available.
Applications In Airlines to map efficient routes Biomedical & Pharmaceutical  Information Security Cryptography
Advantages Dis - advantages
Parallel Processing
Easily solve complex problems
No power requirement
Cost-effective method
Require human assistance
Produce errors due to unwanted chemical reactions
Test tube environment is far from practical environment
Human manipulation needed

[attachment=14058]
Conception
Silicon is the life for today's computers.
Moore’s Law states that silicon microprocessors double in complexity roughly every two years.
One day this will no longer hold true when miniaturisation limits are reached. Intel scientists say it will happen in about the year 2018.
Require a successor to silicon.
What is DNA?
DNA stands for Deoxyribonucleic Acid
DNA represents the genetic blueprint of living creatures
DNA contains “instructions” for assembling cells
Every cell in human body has a complete set of DNA
DNA is unique for each individual
Structure of DNA
The DNA is a double stranded molecule.
These two strands run in opposite directions to each other and are therefore anti-parallel.
Each strand is a series of
4 different nucleotides
Adenine (A)
Guanine (G)
Thymine (T)
Cytosine ©
Structure of DNA(continued)
The key thing to note about the structure of
DNA is it’s inherent complementarity.
A binds with T and G binds with C
(A) (T)
©(G)
One strand is therefore the
“mirror image of another”
Complement of AGGCT is TCCGA
DNA Computing
DNA computing is a form of computing which uses DNA, biochemistry and molecular biology, instead of the traditional silicon-based computer technologies.
This field was initially developed by Leonard Adleman of the University of Southern California, in 1994.
Basics And Origin of DNA Computing:
DNA computing is utilizing the property of DNA for massively parallel computation.
With an appropriate setup and enough DNA, one can potentially solve huge problems by parallel search.
Leonard Adleman proposed that the makeup of DNA and its multitude of possible combining nucleotides could have application in computational research techniques.
Adleman demonstrated a proof-of-concept use of DNA as a form of computation which solved the seven-point Hamiltonian path problem.
Computation Algorithm
STEP1:Encode the city names in short DNA sequences . Encode the Itineraries by connecting the city sequences for which the routes exist .
The DNA molecules are generated by a machine called DNA synthesizer
Polymerase chain reaction is used to produce many copies of the DNA
PCR is iterative and uses an enzyme called polymerase
Polymerase copies a section of single stranded DNA starting at the position of the primer, which is DNA complimentary to one end of the Interested section.
Step 2: Sort the DNA by length and select
the DNA whose length Corresponds to 5 cities.
STEP 3:Successively filter the DNA molecules
by city, one city at a Time.
STEP 4:If any DNA is left in the tube, it is the Hamiltonian Path.
Uniqueness of DNA
Why is DNA a Unique Computational Element???
Extremely dense information storage.
Enormous parallelism.
Extraordinary energy efficiency.
Dense Information Storage
This image shows 1 gram of DNA on a CD. The CD can hold 800 MB of data.
The 1 gram of DNA can hold about 1x1014 MB of data.
The number of CDs required to hold this amount of information, lined up edge to edge, would circle the Earth 375 times, and would take 163,000 centuries to listen to.
How Dense is the Information Storage?
with bases spaced at 0.35 nm along DNA, data density is over a million Gbits/inch compared to 7 Gbits/inch in typical high performance HDD.
Check this out………..
How enormous is the parallelism?
A test tube of DNA can contain trillions of strands. Each operation on a test tube of DNA is carried out on all strands in the tube in parallel !
Check this out……. We Typically use
Massive parallel machines (potential) :-
Desktop PC : 109 ops/sec
Supercomputer : 1012 ops/sec
1 µmol of DNA : 1026 reactions…(isn’t amazing)
MAYA-II (First DNA computer) :-
Stand for (Molecular Array of YES and AND logic gate )
Replacing the normally silicon-based circuits, this chip has DNA strands to form the circuit
MAYA-II has more than 100 DNA circuits
Advantages of a DNA Computer:-
Parallel Computing- DNA computers are massively parallel.
Incredibly light weight- With only 1 LB of DNA you have more computing power than all the computers ever made.
Low power- The only power needed is to keep DNA from denaturing.
Solves Complex Problems quickly- A DNA computer can solve hardest of problems in a matter of weeks
Limitations
DNA is redundant.
The process required much human intervention.
DNA has a half-life.
Solutions could dissolve away before the end result is found.
The computation time required to solve problems with a DNA computer does not grow exponentially, but amount of DNA required DOES.
Suited for specific problems, difficult to generalize
Applications of first generation DNA Computers
Gene analysis.
Useful to Government to break secret codes
To Airlines to map efficient routes
To understand about human Brain – the natural Super Computer
Future possibilities
Future
Future is very bright to solving complex problem.
If research gets successful, it will eliminate the Silicon based Super Computers.
More powerful dna computers are likely to be introduced very soon.
Conclusion
DNA computers showing enormous potential, especially for medical purposes as well as data processing applications.
Still a lot of work and resources required to develop it into a fully fledged product.

[attachment=15553]
DNA stands for Deoxyribonucleic Acid
DNA represents the genetic blueprint of
living creatures
DNA contains “instructions” for assembling cells
Every cell in human body has a complete set
of DNA
DNA is unique for each individual
Composed of four nucleotides (+ sugar-phosphate backbone)
– A – Adenine
– T –Thymine
– C – Cytosine
– G – Guanine
Bond in pairs
– A – T
– C – G
Moore’s Law states that silicon microprocessors double in complexity roughly every two years.
One day this will no longer hold true when miniaturisation limits are reached. Intel scientists say it will happen in about the year 2018.
Require a successor to silicon.
With bases spaced at 0.35 nm along DNA, data density is over a million Gbits/inch compared to 7 Gbits/inch in typical high performance HDD.
Check this out………..
A test tube of DNA can contain trillions of strands. Each operation on a test tube of DNA is carried out on all strands in the tube in parallel !
Check this out……. We Typically use
DNA itself does not carry out any computation. It rather acts as a massive memory.
But, the way complementary bases react with each other can be used to compute things.
Proposed by Adelman in 1994
Began in 1994 when Dr. Leonard Adleman wrote the paper “Molecular computation of solutions to combinatorial problems”.
He then carried out this experiment successfully , although it took him days to do so!
DNA computers moved from test tubes onto gold plates.
First practical DNA computer unveiled in 2002. Used in gene analysis.
Self-powered DNA computer unveiled in 2003.
First programmable autonomous computing machine in which the input, output, software and hardware were all made of DNA molecules.
Can perform a billion operations per second with 99.8% accuracy
Biological computer developed that could be used to fight cancers.
‘Designer DNA’ identifies abnormal and is attracted to it.
The Designer molecule then releases chemicals to inhibit its growth or even kill the malignant cells.
Successfully tested on animals.
There is always a plentiful supply of it.
Since there is a plentiful supply, it is a cheap resource.
DNA biochips can be made cleanly, unlike the toxic materials used to make traditional microprocessors.
DNA computers can be made many times smaller than today's computers.
DNA computers are massively parallel in their computation.
Excellent for NP problems such as the Travelling Salesman problem.
Solutions that would otherwise take months to compute could be found in hours.
DNA computing involves a relatively large amount of error.
Requires human assistance.
Time consuming laboratory procedures.
No universal method of data representation.
DNA chips
Genetic programming
Medical diagnosis , drug discovery
Massive parallel problem solving
Cracking of coded messages
DNA computers showing enormous potential, especially for medical purposes as well as data processing applications.
Many issues to be overcome to produce a useful DNA computer.
Still a lot of work and resources required to develop it into a fully fledged product.

plz send me the full report on this topic

to get information about the topic DNA Computer Full Seminar Report Download full report ,ppt and related topic please refer page link bellow

http://studentbank.in/report-dna-compute...t-download

http://studentbank.in/report-dna-computing-full-report

http://studentbank.in/report-dna-computi...ort?page=4

http://studentbank.in/report-dna-computi...?pid=64194

http://studentbank.in/report-dna-computi...ort?page=2

http://studentbank.in/report-dna-computi...ort?page=3

http://studentbank.in/report-biological-...ull-report

http://studentbank.in/report-dna-computi...ort?page=5

http://studentbank.in/report-dna-computi...ars-report

---

to get information about the topic dna computing seminar full report ,ppt and related topic refer the page link bellow

http://studentbank.in/report-dna-compute...t-download

http://studentbank.in/report-dna-computing-full-report

http://studentbank.in/report-dna-computing

http://studentbank.in/report-dna-computi...ort?page=4

http://studentbank.in/report-dna-computi...rity--6866

http://studentbank.in/report-dna-computi...ort?page=2

http://studentbank.in/report-dna-computi...ort?page=3

http://studentbank.in/report-dna-computi...ars-report

http://studentbank.in/report-dna-computi...?pid=49366

http://studentbank.in/report-dna-computing--4455

http://studentbank.in/report-dna-based-computing

http://studentbank.in/report-dna-computi...ort?page=5

http://studentbank.in/report-dna-compute...oad?page=6

---