Tuesday, October 20, 2009

Welcome Guest,

I am vik , i am thankful to prof. Stephen Marsland,Massey university, NZ for information provided on advanced computing methods. i have researched on two of the latest computing technologies which are DNA computing & Optical Computing. I am presented my work on DNA Computing technology here and will update this blog for regular updates time time. hope you will find this work informative.

regards
vikas sharma

Introduction


“Israeli Scientists have devised a computer that cans perform 330 trillion operations per second, more than 100,000 times the speed of fastest super computer, the secret: It runs on DNA.”
Source: National Geographic news18

December 9th,1959 , At the annual meeting of American Physical society at California institute of technology, there was a visionary speech given by R.P.Feynman11 , which described the possibility of building sub-microscopic computers and Later, in 1994, Leonard Adleman1 solved an unremarkable computational problem with remarkable technique, than it seemed to find the way to construct computing machines which would have the capability to perform trillions operations at a time and could hold ten 10 terabytes of data with in one cubic centimetre. Although the problem solved by Adleman was not too complex, anybody could solve it in few moments or any computer machine could solve it in a blink of eyes but it took Adleman, however, seven days to find out the solution of the problem, the reason was he solved problem with the DNA.
Speed of computation and Power consumption are the two main parameters of any computing devices. Conventional computer carry out operations sequentially, which binds the speed of these devices but if you found a mean to carry out operations in parallel then there would be a great improvement in the speed of computing devices. DNA2 has a capability to carry out reactions in parallel so due to this property it possesses massive parallelism and hence, the speed of DNA computer is enormous. A normal pc can execute approximately 106 operations/sec, the fastest super computer currently available can execute approximately 1012operations/sec but under some condition approximately 1020 operations seems entirely reasonable for DNA computers. After the Adleman’s experiment DNA computing has gained its popularity and there are many researchers who are working hard to find a way to replace the silicon based computers with these extremely small , cheap and fast computers. Here we will discuss some basic terms of biology related to DNA, Adleman’s experiment and some important work done by some other researchers, recent updates about DNA computing, advantages and disadvantages , future and some killer applications .

Biology behind DNA computing



9Proteins are the molecules that accomplish most of the functions of living cell. They make possible all the chemical reactions in the cell by acting as Enzymes that promotes specific chemical reactions, which would occur otherwise so slowly as to be negligible. If proteins are the workhorses of biochemical world, nucleic acids are the drivers; All the genetic information in any living creature is stored in Deoxyribonucleic acid (DNA) and Ribonucleic acid (RNA), which are polymers of four simple nucleic acid units, called nucleotides. There are four nucleotides found in DNA. Each nucleotide consist of three parts: one of two base molecules (a purine & a pyramidine), plus a sugar (ribose in RNA and deoxyribose in DNA) and one or more phosphate groups. The purine nucleotides are Adenine (A) and Guanine (G) and the pyramidine nucleotides are Cytosine (C) and Thymine (T). Nucleotides are also called basis and since, two DNA consist of two complementary strands bonded together, these units are often called base pairs. The nucleotides are linked to each other in the polymer by phophodiester bonds. This bond is directional. A strand of DNA has a Head ( called 5’ end) and a tail( called 3’ end).
One of the property of DNA is that it forms a double helix i.e. two helical strands of polypeptide, running in opposite directions, held together by hydrogen bonds. Adenine bond exclusively with thymine and Guanine with cytosine because of these bonding rules the sequence of in complementary strand is completely determined.

DNA Computing ,Hamiltonian Path Problem and some other NP problems

2The idea of DNA computing came in Adelman’s mind when he was reading the classic text “the molecular biology of the gene”, co-authored by James D.Watson of Watson-Crick family. He resembled the formation of new DNA of operation of Turing machine which is described is in 1936 by Alan M.Turing, the famous British mathematician Turing machine was not intended to be real but rather to be conceptual. He inspired with the DNA polymers, a single molecule that “hops” into a strand of DNA and slids along it, “reading” each base it passes and “writing” it complement onto a new, growing DNA strand which is similar turing machine which had two tapes, moved along the “input” tape reading data while simultaneously moving along “output” tape reading and writing other.
In 1994, Leonard Adleman1 solved a particular type of NP problem14 (nondeterministic polynomial) which is known as Hamiltonian Path Problem1,2,4,6,10 or Travelling Salesman Problem, using DNA. A directed graph G with designated vertices Vin and Vout, is said to have a Hamiltonian path if and only if there exist a sequence of compatible ‘one way’ edges e1,e2…ez, which begins at Vin and ends at Vout and enter every other vertex exactly once. He found the shortest path between seven cities by using the following algorithm:
Generate random paths through the graph.
Keep only those paths which begin with Vin and end with Vout.
If the graph has n vertices than keep only those paths which enter exactly n vertices.
Keep only those paths which enter all the vertices of the graph at least once.
If any path remaining “yes”, otherwise “no”.

He implemented his algorithm on DNA by carrying out various chemical reactions such as first associating some sequence of DNA to each vertex than ligation reaction, amplification, purification and using some gels (Agarose gel). And finally, after seven days of lab work he came across the solution of Hamiltonian path problem.
Inspired by the work of Adleman, on 28th April, 1995, Richard J. Lipton3 proposed a paper to solve famous SAT problem (The Boolean Satisfiability problem) of computer science. A SAT5 problem can be simply described as problem of deciding weather a given Boolean expression has any correct solutions; more precisely ; it can be stated as the following question: Given a Boolean expression, do there exist any assignments of truth values (True and False) to the variables of the expression such that the expression as a whole evaluates to be true? SAT is also a type of NP- problem. Researchers have used DNA computing with Acrydite™ gel7 technology to solve time tabling problem. Apart from this various NP problems such as Clique problem, Knapsack problem8 are solved by researchers by using the DNA computing.
DNA Computing is a new technology which is based on the enormous information capacity, massive parallelism in DNA and also on the biological molecules that can store huge amount of information and able to perform operation similar to that of computers. 18Today’s computer use binary codes – 1’s and 0’s or ON’s and OFF’s, which are basis of all possible calculations that a computer performs. In the same way DNA computer is collection of the strands that have been specially selected to help in the search of solution of some problem.

Merits


DNA computing10,4 is an example of computing at molecular level, potentially a size limit that may never be reached by semiconductor industry and it can be used to solve a class of problem that are difficult or impossible to solve by traditional computers. Energy efficiency is more than a million times a pc because no external power is required while the computation is taking place.
Speed of computation is one of the major advantages because of its massive parallel processing. 13Apart from these DNA has high storage capacity because DNA code can be the any of the four DNA basis (A,G,C,T) while binary code can only be 0 or 1. Binary code of 4 characters can represent 16 discrete things where as DNA code can represents 64 discrete things; this gives DNA a huge storage capacity.

Demerits


Each stage of parallel operation requires time measured in hours & days with extensive human and mechanical intervention between steps.DNA systems are very error prone and messy because it takes some time to extract the final answer from DNA pool formed during computations and DNA strands breakup with time. So the chance of error increases. One of the drawbacks is that so far no one has found a problem that is suitable for DNA computers which means so far no killer application has been found for DNA computers. As remarked by David Harlanwood,”DNA Computing is a solution looking for problem”.
But on the other other hand DNA2DNA computations13 could be regarded as the killer application which involves the use of DNA computing to perform operations on unknown pieces of DNA without having to sequence them first. This could be achieved by recoding and amplifying unknown strands into a redundant form so that the can be operated. Many of the errors that could be seen in other DNA models could be ignored here because of such a high availability of numbers for operation. Another demerit is that the test tube environment used for DNA computing cannot be considered as the practical use. And DNA solution13 looks like water if seen by the naked eye so output is not visible like conventional computers.

Updates


According to sciencedaily.com22, Tom Ran & Shai Kaplan, research students in the lab of professor Ehud Shapiro of Weizmann institute’s biological, have found a way to make these computing device user friendly, even while programming complex computations & answering complicated queries.
Another article on medicalnewstoday.com23, Researchers at university of Wisconsin-madison, has identified some of the pathways through which single molecule strands of DNA interact and combine to form double helix15. Ultimately, the research could help biologists understand why some hybridization reactions are faster or more robust than other.
IBM scientists and a collaborator form California institute of technology have created computer chip utilizing synthesised DNA molecules24. The approach could help in finding the way to create tiny circuits that could form basis of the smaller, more powerful computer chips.
At the University of Wisconsin23, Researchers created a crude molecular computer “chip” made of small glass plate covered with athin layer of gold. Strands of DNA were cooled to represent solutions to a computational problem wit 16 possible answers. The enzymes were applied to the gold slide to stripe out all the DNA with the incorrect answers and thus, solving the calculation.
According a news article on BBC news website17, Israeli scientists have developed a tiny computer made up of DNA that can answers simple yes or no questions. Strands of DNA are designed to give off the green light corresponding to ‘yes’.

Future aspects and Conclusion



It is clear that the DNA computers or molecular computers have many attractive properties. Some of their properties like extremely dense storage, enormous parallelism, their energy efficiency makes them ideal computer systems, it’s not a here-&-now practical technology20, it’s a pie-in-the-sky research project that needs lot of good ideas, hard work & luck to realize its potential12. As admitted by Prof. Ehud Shapiro, Weizmann institute of science, Israel, to BBC news that it seems to be really difficult to beat electronic computer by DNA computing method in foreseeable future. so a new goal in this field is to try to use DNA computing to do things that traditional computers cannot do.
From the above discussion it can be concluded that presently, DNA computer lies only in the theory, although, in some research institutes21 and universities such as university of southern California with Dr. Adleman, Princeton, Dr. Richard Lipton and his graduate students and other elsewhere are developing new branches in the young field. Advancement are being made in cryptography and Researchers are working on decreasing error in & damage to DNA during computation. But, a functional ‘DNA computer’ of the type that most people are familiar, lies many years in future.

References

  1. Molecular Computation od Solutions To Combinatorial Problems , by Leonard M. Adleman,1994.
  2. Computing with DNA, by Leonard M. Adleman, Scientific American, August 1998.
  3. DNA Solution of Hard Computational Problems, by R. J. Lipton, 1995, Science Vol 268.
  4. DNA Computing and Its Applications, J. Watada & R. Bakar, Wasada uni. , 2008 , IEEE, DOI 10.1109/ISDA 2008.362
  5. Making the SAT decision based on DNA computation, J. Ibershoff, J. W. Jaromczyk, Danny van Noort, 2007 IEEE.
  6. DNA Computing for Travelling Salesman problem, L. Xikui & L. Yan , 2009, IEEE.
  7. A DNA Computing Model Based on Acrydite(tm) Gel Technology to Solve the timetabling Problem, F. Zhang, 2007 , IEEE.
  8. Take Advantage Of The Computing Power Of The DNA Computers, Z. Frank Qui & MI LU, Texas A&M University.
  9. “Molecular Biology for Computer Scientists” by Lawrence Hunter.
  10. DNA Computing , http://www.final-yearprojects.co.cc/
  11. http://www.zyvex.com/nanotech/feynman.html
  12. http://www.neci.nj.nec.com/homepages/eric/eric.html,
  13. http://publish.uwo.ca/~jadams/dnaapps1.htm
  14. http://mathworld.wolfram.com/NP-CompleteProblem.html
  15. http://whyfiles.org/shorties/dna_computer.html
  16. http://tech.suramya.com/dna_computing/
  17. http://news.bbc.co.uk/2/hi/technology/8184033.stm
  18. http://serendip.brynmawr.edu/biology/b103/f00/web1/barrera.html
  19. http://news.nationalgeographic.com/news/2003/02/0224_030224_DNAcomputer.html
  20. http://library.thinkquest.org/3037/dna.htm
  21. http://www.casi.net/D.BioInformatics1/D.Fall2000ClassPage/DC2/dc2.htm
  22. http://www.sciencedaily.com/releases/2009/08/090803092606.htm
  23. http://www.medicalnewstoday.com/articles/166533.php
  24. http://blogs.zdnet.com/emergingtech/?p=1718