Eldar.cz

Recent Developments in DNA-Computing
Am Exerzierplatz 3, 97072 W¨urzburg, Germany Abstract
computing time to solve the task are in good proportion.
Adleman’s procedure uses polynomial computing time, but In 1994 Adleman published the description of a lab ex- so far there are only exponential time algorithms known to periment, where he computed an instance of the Hamilto- compute the Hamiltonian path problem on a sequential ma- nian path problem with DNA in test tubes. He initiated chine, and this does not rank as efficiently computable.
a flood of further research on computing with molecular A Hamiltonian path is a sequence of edges in a graph, means in theoretical computer science. A great number which touches every vertice exactly once. The Hamiltonian of models was introduced and examined, concerning their path problem is to decide, whether a graph has a Hamilto- computional power (universality as well as time and space nian path or not. This problem is a typical representative complexity), their efficiency and their error resistance. The of the important complexity class NP. That means that it main results are presented in this survey. shares many of its properties, including those mentionedabove, with every problem in NP. Adlemans method hasinitiated great interest, as one can hope to learn something Introduction
new about all of the problems in NP by analysing this spe-cial case.
The pioneering achievement that every problem can be Massively parallel features are the reason for the gain computed, providing that one can verbalize a method to of time (considering larger inputs). The solution space is solve it, belongs to the second third of our century. Si- completely coded, each possible solution is mapped to a multanously the answer to the question “how to do it” was DNA molecule. Subsequently some necessary conditions found. The necessary information was encoded binary, and for a correct solution are checked step by step. In each the code words were implemeted by a sequence of high and of the steps all molecules are modified in parallel: those low voltage. This was the beginning of the phenomenal ex- molecules that fit to the tested condition are seperated from pansion of computers. A lot of innovations supported its breakthrough. But the idea to store and modify data by elec- A possible solution to the Hamiltonian path problem is tronic means has not changed in practice.
a sequence of the graph’s vertices. There are exponen- The description of a biological experiment caused a sen- tially many sequences, but each of them has only polyno- sation among theoretical computer scientists in December mial length and therefore it differs from other sequences at 1994. A well-known scientist succeeded in computing the most at polynomially many positions. Consequently at most solution of an instance of a problem recognized to be hard, polynomially many conditions have to be tested. As all pos- by means of biochemical manipulation of DNA (desoxyri- sible solutions are tested in parallel, their huge number is of bonuclein acid): Adleman solved the Hamiltonian path no consequence when counting the time.
problem for a graph with seven vertices using a soup of If we generalize Adleman’s method we get a parallel model of computation. We view molecules as distributed Though in this computation the means of storage was data storage and molecular manipulations as parallel opera- new the result was not. For a long time it has been possible tions. In a test tube a soup of millions of molecules can be to search for Hamiltonian paths in graphs of this size, and manipulated whereas silicon-based parallel computers are the usual method in this case is much faster than the new one bounded to about ten thousand processors nowadays.
by Adleman. However, the complexity theoretical analysis Such considerations encourage to ask, whether DNA- of this experiment indicates that the input length and the computers can break the “exponential border” and there- fore problems , that are not computable in a practical sense if there is a path of edges starting with nowadays (as this would take thousands of years), could be solved in a sensible time. But simple means of calcu- exactly once. The directed Hamiltonian path problem is the lation shows, that Adleman’s procedure would need more molecules than the earth is able to give, for computing the Hamiltonian path problem for a graph with two hundred Adleman uses the following (nondeterministic) algo- rithm to solve the directed Hamiltonian path problem for It is the task of theoretical computer science to find out the chances and the borders of the new computational model. The survey in hand first presents the article that initi- ated research on molecular computing. We consider the de- scription of the experiment as well as Adleman’s hopes and doubts concerning this procedure (Section 2). In Section 3 we explain the first abstractions of Adleman’s method to- wards a parallel computation model and its complexity the-oretic analysis. Some more molecular operations and tests 4. Extract all paths that contain every vertice at most are mentioned which are expected to be realizable. “Is ev- erything computable by DNA-computers?” We trace thisquestion in the Section 4. In fact there are different DNA 5. Accept if there are any paths left, otherwise reject.
models that have the power of an universal computer. There Those steps are now realized as molecular computation are many problems which can only be solved with the ma- chines of the preceeding sections taking great consumption mers. Ligation builds DNA strands that represent random of time and DNA resourses into the bargain. The efficient (step 1). The Watson-Crick complements of the algorithms of the fifth section for example reduce the con- sumption of molecules considerably, compared with naive the correct beginning and end (step 2). In order to get cod- methods. In Section 6 we face the objection that molecular operations are probabilistic – so error analysis and strategies (step 3). Next we denaturate the DNA, and we check each for error resistence are necessary. Finally (Section 7) we vertice (using the Watson-Crick complement of its coding) present a research area from the theory of formal languages: for only single appearance in a path (step 4). To get the splicing systems model a biological prototype where DNA result, again we use gel electrophorese for testing whether molecules are reorganized by the means of enzymes and there is any strand left or not (step 5). In between the steps ligation. Many classes of languages can be characterized polymere chain reaction (PCR) is used to amplify the inter- by different modifications of splicing systems.
Adleman’s article caused a flood of further research work The execution of the experiment took seven days of lab in various aspects and developments of molecular models.
work. But Adleman remarks that optimizing the algorithms For that reason it is impossible to give a complete state of and the molecular implementation of the operations can re- research in this presentation. Instead we select some pa- duce the time substantially. However, the time used for pers which seem to be interesting to us and which afford longer inputs grows only linearly with the number of ver- an insight into the ways research on molecular computing tices. On the other hand the number of different paths grows has taken. For clearing the basics of theoretical computer exponentially with the number of vertices – and so does the science we recommend for example [49].
amount of DNA. Adleman himself poses some questions.
He consideres that the proceeding has probabilistic proper- Adleman’s Experiment
ties. That means it has to be examined how many equalstrands must be initialized, to reach high probability for the In a well-noticed article from December 1994 Adleman existence of at least one of the required coding in every step.
describes a completely new process for solving a combi- All together careful error analysis and the examination of natorial problem that he performed for an examplary in- the realizability of the method is necessary [2, 28].
put in lab [1]. He takes the NP-complete Hamiltonian path For all that Adleman rates the potential of his DNA problem as representative of an important complexity class model to be promissing. While modern supercomputers which is supposed to have exponential worst case time com- erations per second to be realistic for molecular manipula- tions. Similar impressive views concern the consumption of is called to have a Hamiltonian path energy and the capacity of memory: supercomputers need To construct an algorithm for the model, on the one hand the set of commands of classical Pascal, on the other hand a set of molecular operations and tests are allowed. Some DNA stores information with a density of one bit per cubic variants of this DNA-Pascal are inspected, they differ in the set of valid molecular operations and tests. If we bound the It depends on future research whether the prototype of resulting programming languages to polynomial computing a reliable bio-computer or even industrial mass production time, they define different problem classes that can be char- will be reality. However, Adleman got an avalanche under- acterized by classical complexity classes. The pure Pascal commands do not influence the magnitude of those classesbecause polynomially time-bounded Pascal exactly charac- First Reactions
We can summarize the results of [44] in the following figure. The vertices of the graph are combinations of op- The first who takes up Adleman’s method is Lipton eration properties. A tabular is attached to each of the ver- [30, 32]. He makes some idealized assumptions and gets tices. It shows the computational power of polynomially a deterministic parallel computation model. The molecular time-bounded DNA-Pascal using operations with the prop- operations union, initialization, extraction, and amplifica- erties in the vertices and different tests.
tion and an emptiness test are applicable on DNA in testtubes. By that he builds an abstraction of the molecular computation in Adleman’s experiment. The main results of those papers are a concrete DNA algorithm for the 3-SAT problem and the proof that any problem in NP can be solved Inspired by Lipton’s abstraction Rooß and Wagner pick up his model and expand it with other molecular operations and tests that are supposed to be realizable [43, 44]. Forthe exact definition of the operations refer to the original articles, because the computational power depends on a few properties. In detail we can categorize the operations as Operations have the block property if they preserve thefact that all strands of a certain length are contained in Operations have the select property if they can excludecertain strands from a test tube (and probably modify If only block operations are used no molecular test can increase the power of polynomially time-bounded DNA-Pascal above P. Non-block operations without select prop- Operations have the identify property if they can iden-tify different strands (i. e. by identifying or cutting cer- erty and at most simple identify operations lift polynomially time-bounded DNA-Pascal to the magnitude of The select property seems to turn the scale for the power We call the operations with the block property block op- of EM: with select operations and EM (or SU) polynomially erations, those with the select property select operations time-bounded DNA-Pascal is as powerful as and those with the identify property identify operations. A model can be classified at this point, its power is exactly non-block operation does not have block property, an opera- tion with the identify and the block property is called simple not have an influence on the power of the programming lan- Lipton uses the emptiness test (EM) that is true, if there A non-block identify operation lifts the power to are no strands in a test tube in question. Additionally we examine another two DNA tests: The membership test (ME) effect if only simple identify operations but additionally se- is true, if there is a certain strand in the test tube in question; the subset test (SU) is true, if the contents of a certain test There are other operations which raise the power of Lip- tube is as a subset in the test tube in question.
ton’s model even to PSPACE. If the strands are logarithmi- cally length-bounded then DNA-Pascal with Lipton’s oper- Set problem. Ogihara utilizes the Monien-Speckenmeyer ations and test is exactly characterized by the class L [43].
algorithm to construct a DNA algorithm for 3-SAT that in-creases the maximal input length from Universal Computers
[35]. Nature has a method to comb huge so- lution spaces: repeated selection cycles on much smaller The term universal computer originates from recursion subspaces. Dynamical programming picks up this idea to theory and describes a machine that is able to solve any reduce the number of required DNA strands [48, 8].
computable problem. As an input it obtains a program Moreover, there are several other algorithms for famous which implements an algorithm for solving a computable difficult problems. E. g. the #P-complete problem of per- problem, and a parameter for that program. There are many mantent calculation in a matrix is solved in [50, 29] by a equal models which fit for a universal computer. Probably the Turing machine is the most important one. Each Turing Not only the decision of sets with DNA computation is of computation is represented by a sequence of configurations.
interest. If molecular models want to compete with silicon- Each configuration encodes a single step in the computa- based models, the computation of functions must be pos- tion. Successor configurations differ only at a few locally sible. Within that the addition plays an important part; a bounded positions. A Turing machine accepts an input, if corresponding DNA algorithm is presented in [22]. Molec- there is a sequence of successor configurations that begins ular matrix multiplication is the theme in [37] and a quite with the start configuration and ends with the accepting con- early paper by Beaver deals with a factorisation algorithm figuration. The commonly accepted Thesis of Church says that any intuitively computable problem is computable by Boolean circuits are one of the profound studied parallel a Turing machine. According to these standards every new computation models. Their processors are gates that exe- computational model is going to be examined whether it is cute the boolean functions “not”, “and” and “or”. The com- plexity of those circuits are given by the fan-in and fan-out Beaver describes a molecular universal computer in [10]: (the maximal number of inputs and outputs, resp. of a gate), he simulates a Turing machine by coding all its configu- the size (the number of gates) and the depth (the longest rations in DNA strands. During that he starts with pairs way through the circuit). Often the fan-in of and-gates is of successor configurations. Similar to the dominoes game bounded to two whereas the fan-in of or-gates is arbitrary; (where one chain of dominoes must be put together) longer such circuits are called semi-unbounded. The simulation of and longer parts of the computation grow (in parallel) by boolean circuits by DNA-computers is among others exam- clever recombination of these strands. Finally it is to check, ined in [31, 12, 27]. Ogihara and Ray [36] specify a molec- whether there is a strand with the coding of the start con- ular algorithm that simulates semi-unbounded boolean cir- figuration in the beginning and the accepting configuration in the end. In [45, 51] similar ligation-based methods are proposed to simulate Turing machines. From [43] it fol- particular this makes it possible to run the simulation of the lows that without time bounds Lipton’s model can already DNA molecules in solution have an alternative in DNA DNA Algorithms
molecules that are fixed to a surface. Liu et al. [33] take inthat biochemical method and develop a molecular compu- Adleman’s and Lipton’s naive algorithms for the Hamil- tation model to simulate circuits efficiently (the number of tonian path and the 3-SAT problem, are valuable contribu- parallel operations is proportional to the size of the circuit) tions to the analysis of the computational power of those machines. But it appears that only small inputs can be pro- Another possible application of molecular computers is cessed in reality. The problem is the extend of solution cryptography. In [11] it is outlined how to break the data encription standard (DES) with Adleman’s model extended can not expect to reduce the solution space for such prob- with some more operations. DES codes information with lems to polynomial size with optimized algorithms because a ✁✔✓ bit key. For an input pair of cipher text and plain this would imply the equality of P and NP [43], nevertheless text a classical algorithm had to sequentially test ✁✖✕✘✗ pos- the number of the actually computable instances grows con- sible keys, what takes some ten thousand years assuming siderably. Bach, Condon, Glaser, and Tanguay [5] present a performance of hundred thousand operations per second.
clever algorithms that use Adleman’s operations and test.
Boneh, Dunworth and Lipton show how to compute the key For example they reduce the DNA consumption to an or- in about four month of lab work. The sticker model by while computing the NP-complete Independent Roweis, Winfree et al. is a computation model that com- bines DNA manipulations and a random access memory language is given by a test tube filled with DNA and a num- [46]. With one gram of DNA and in spite of many error ber of valid operations (realizable with certain enzymes).
possibilities DES can be broken by the sticker model in rea- It consists of mulecular coded strings – the molecules are from the initial set or come off it by enzyme reactions. Theformalization of this idea is called splicing system, consist- Error Resistance
ing of an initial set of strings on a final alphabet and a rule bet. The rules are applied on two strings Most of the models mentioned above base on idealized assumptions, in particular deterministic working methods of molecular operations and tests. Indeed the analysis of the biochemical process as well as the repetition of Adle- man’s experiment that could not deliver definite results [26]let the realization of those assumptions seem to be difficult.
The upper bounds of molecular computation models withperfect operations and tests show limits that surely can notbe broken by realistic implementation. Nevertheless a pro- found error analysis and strategies for error resistance help to improve classification of these models and to give state-ments according their realizability.
The implementation of the extraction operation with The language generated by a splicing system is the set of PCR (as for example in [1]) throw doubts on the finite result all strings that can be produced by a repeated application of of a computation. If we assume PCR to extract the proper the rules on the initial set. In the theory of formal languages strands with a probability of   ✁✂✁ , and we undergo only one two classes of languages have a great importance: the class hundred computation steps, then the probability that exactly of regular languages that is easy to decide and the class of those strands are left which meet the extraction criterion is recursively enumerable languages (r. e.) that not only con- tains the decidable but also the semi-decidable languages.
and Hodgeson implement the extraction operation with the Splicing systems have profoundly been investigated. The means of restriction enzymes that destroy all strands con- generative power of splicing systems is examined among taining a certain pattern. They reach a distinctly lower error others in [24, 38, 40, 41, 21]. Culik and Harju show that probability than with the use of PCR. The reliability of the a splicing system with regular initial set and finite set of extraction operation can also be increased with a proceed- rules generates again only regular sets [17]. But if we allow ing by Karp, Kenyon, and Waarts [27]: they apply PCR to a regular set of rules, then the set of generated languages a series of test tubes instead of only one. Boneh and Lipton is already r. e. [39]. Denninghoff an Gatterdam introduce [13] make their 3-SAT algorithm error resistant by duplicat- the multiplicity of strings in sets [19]: the appearence fre- ing the number of strands periodically.
quency of a string in a set is considered. By this means we Among the first to be engaged in the error analysis implicitely get the possibility to add, subtract and multiply of Adleman’s and Lipton’s operations are Bach, Condon, integers. If the multiplicity of sets is treated, splicing sys- Glaser, and Tanguay [5]. They increase the probability so tems with a finite set of rules can already generate r. e. Also when duplicating test tubes indeed all different strands are the existence of a “universal computer” in form of a splicing in both of the tubes, by using a greater amount of equal system is proved: there are universal splicing systems that can simulate the working method of any arbitrary splicing In [7] Baum is concerned with the coding of strings in system, and they can have regular rule sets or finite rule sets DNA strands. Using strands of sufficent length it can hap- with multiplicity or with an adding mechanism [19, 39, 15].
pen that randomly complementary strands join and so cause That means in particular that splicing systems have the same errors. A clever string coding takes remedial measures.
A variation to linear structures as presented above are splicing systems on circular strings without beginning or Splicing Systems
end. In [25, 47, 42, 52] such cyclic splicing systems are con-sidered, and it turns out that in this case the result of Culik Finally we should not miss to consider a related disposi- and Harju does not hold [47]. Some extensions enable the tion from the theory of formal languages. An article of Head construction of universal splicing systems with finite sets of from 1987 [24] leads this concurrency off. He constructs rules that do not need mulitiplicity [52]. Freund looks at a language theoretical model after a biological example: a A combination of splicing systems with the meaning [8] E. B. Baum and D. Boneh. Running dynamic programming of Head (splicing operations are applied in test tubes) and algorithms on a DNA computer. In Proceedings of the Sec- DNA-computers in the sense of Adleman (new test tubes are ond Annual Meeting on DNA based Computers, 1996.
filled by extraction from old ones) are examined in [16, 18].
[9] D. Beaver. Computing with DNA. Journal of Computational Those distributed splicing systems with finite initial and rule [10] D. Beaver. Molecular computing. Technical report, Penn set already characterize r. e. On its base a universal com- [11] D. Boneh, C. Dunworth, and R. J. Lipton. Breaking DES us- ing a molecular computer. Technical report, Princeton Uni- Final Remark
[12] D. Boneh, C. Dunworth, R. J. Lipton, and J. Sgall. On the computational power of DNA. Technical report, Princeton During the last two and a half years many different DNA models have been developed and analysed under several [13] D. Boneh and R. J. Lipton. Making DNA computers error points of view. It turned out to be quite fruitful that many re- resistant. Technical report, Princeton University, 1996.
searchers with different interests have picked up that theme.
[14] W. Cai, A. E. Condon, R. M. Corn, E. Glaser, Z. Fei, Thereby complexity, stability and realizabilty played an im- T. Frutos, Z. Guo, M. G. Lagally, Q. Liu, L. M. Smith, and A. Thiel. The power of surfaced-based DNA computation.
Even though this chapter of research is still in the begin- Technical report, University of Wisconsin, July 1996.
ning. The results up to now show, that DNA-computers will [15] E. Csuhaj-Varj´u, R. Freund, L. Kari, and G. P˘aun. DNA not turn our insights of efficient computation from upside computation based on splicing: universality results. In Pro- down. Nevertheless they are a powerful instrument for the ceedings of the First Annual Pacific Symposium on Biocom-puting, 1996.
implementation of parallel processes.
[16] E. Csuhaj-Varj´u, L. Kari, and G. P˘aun. Test tube distributed The future of molecular machines could be in a combi- systems based on splicing. Computers and AI, 15(2–3):211– nation with classical computers. Such systems should profit by the specific suitability of the components: well paralliz- [17] K. Culik II and T. Harju. Splicing semigroups of domi- able tasks should be computed with DNA, whereas inher- noes and DNA. Discrete Applied Mathematics, 31:261–277, ently sequential jobs should be done by silicon-based chips.
It is still too early to expect high efficient realizations, but [18] J. Dassow and V. Mitrana. Splicing grammar systems. Com- also in biology a unremittingly search for possibilities for a puters and AI, 15(2–3), 1996.
quick and low cost manipulation of molecules is in process.
[19] K. L. Denninghoff and R. W. Gatterdam. On the undecid- ability of splicing systems. International Journal of Com-puter Mathematics, 27:133–145, 1989.
References
[20] R. Freund. Splicing systems on graphs. In Proceedings of Intelligence in Neural and Biological Systems, pages 189– [1] L. M. Adleman. Molecular computation of solutions to com- binatorial problems. Science, 266:1021–1024, December [21] R. W. Gatterdam. Splicing systems and regularity. Interna- tional Journal of Computer Mathematics, 31:63–67, 1989.
[2] L. M. Adleman. On constructing a molecular computer. In [22] F. Guarnieri, M. Fliss, and C. Bancroft. Making DNA add.
E. B. Baum and R. J. Lipton, editors, DNA based comput- Science, 273:220–223, July 1996.
ers. American Mathematical Society, 1996. Number 27 in [23] J. Hartmanis. On the weight of computations. Bulletin of DIMACS: Series in Discrete Mathematics and Theoretical th European Association for Theoretical Computer Science, [3] L. M. Adleman, P. W. K. Rothemund, S. Roweis, and [24] T. Head. Formal language theory and DNA: an analysis of E. Winfree. On applying molecular computation to the data the generative capacity of specific recombinat behaviours.
encryption standard. In Proceedings of the Second Annual Bulletin of Mathematical Biology, 49:737–759, 1987.
Meeting on DNA based Computers, 1996.
[25] T. Head. Splicing schemes and DNA. Nanobiology, 1:335– [4] M. Amos, A. Gibbons, and D. Hodgson. Error-resistant im- plementation of DNA computations. In Proc. of 2nd Annual [26] P. D. Kaplan, G. Cecchi, and A. Libchaber. Molecular com- Meeting on DNA Based Computers, June 1996.
putation: Adleman’s experiment repeated. Technical report, [5] E. Bach, A. E. Condon, E. Glaser, and C. Tanguay. DNA models and algorithms for NP-complete problems.
[27] R. Karp, C. Kenyon, and O. Waarts. Error resilent DNA Proc. of 11th Conference on Computational Complexity, [6] E. B. Baum. Building an associative memory vastly larger [28] S. A. Kurtz, S. R. Mahaney, J. S. Royer, and J. Simon. Active than the brain. Science, 268:583–585, April 1995.
transport in biological computing (preliminary version). In [7] E. B. Baum. DNA sequences useful for computation. Tech- Proceedings of the Second Annual Meeting on DNA based nical report, NEC Research Institute, 1996.
[29] T. H. Leete, M. D. Schwartz, R. M. Williams, D. H. Wood, [48] W. P. C. Stemmer. The evolution of molecular computation.
J. S. Salem, and H. Rubin. Massively parallel DNA compu- Science, 270:1510, December 1995.
tation: Expansion of symbolic determinants. In Proceedings [49] K. W. Wagner. Einf¨uhrung in die Theoretische Informatik, of the Second Annual Meeting on DNA based Computers, Grundlagen und Modelle. Springer-Verlag, 1994.
[50] R. M. Williams and D. H. Wood. Exascale computer al- [30] R. J. Lipton. Speeding up computations via molecular biol- gebra problems interconnect with molecular reactions and ogy. Technical report, Princeton University, 1994.
complexity theory. In Proceedings of the Second Annual [31] R. J. Lipton. DNA solution of hard computational problems.
Meeting on DNA based Computers, 1996.
Science, 268:542–545, April 1995.
[51] E. Winfree. On the computational power of DNA annealing [32] R. J. Lipton. Using DNA to solve NP-complete problems.
and ligation. In E. B. Baum and R. J. Lipton, editors, DNA Technical report, Princeton University, 1995.
based computers. American Mathematical Society, 1996.
[33] Q. Liu, Z. Guo, A. E. Condon, R. M. Corn, M. G. Lagally, Number 27 in DIMACS: Series in Discrete Mathematics and and L. M. Smith. A surface-based approach to DNA com- putation. In Proceedings of the Second Annual Meeting on [52] T. Yokomori, S. Kobayashi, and C. Feretti.
power of circular splicing systems and DNA computabil- [34] D. A. Mac D´onaill. On the scalability of molecular compu- ity. Technical Report CSIM 95-01, University of Electro- tational solutions to NP problems. The Journal of Universal Computer Science, 2(2):87–95, February 1996.
[35] M. Ogihara. Breadth first search 3SAT algorithms for DNA computers. Technical report, University of Rochester, July1996.
[36] M. Ogihara and A. Ray. Simulating boolean circuits on a DNA computer. Technical report, University of Rochester,August 1996.
[37] J. S. Oliver. Computation with DNA-matrix multiplication.
In Proceedings of the Second Annual Meeting on DNA basedComputers, 1996.
[38] G. P˘aun. On the power of the splicing operation. Interna- tional Journal of Computer Mathematics, 59:27–35, 1995.
[39] G. P˘aun. On the splicing operation. Discrete Applied Math- ematics, 70(1):57–79, September 1996.
[40] G. P˘aun. Regular extended H systems are computationally universal. Journal of Automata, Languages and Combina-torics, 1(1):27–36, 1996.
[41] G. P˘aun, G. Rozenberg, and A. Salomaa. Computing by splicing. Theoretical Computer Science, 168(2):321–336,1996.
[42] D. Pixton. Linear and circular splicing systems. In Proceed- ings of Intelligence in Neural and Biological Systems, pages181–188, May 1995.
[43] D. Rooß and K. W. Wagner. On the power of bio-computers.
Technical report, Universit¨at W¨urzburg, February 1995.
[44] D. Rooß and K. W. Wagner. On the power of DNA comput- ing. Information and Computation, 131(2):95–109, Decem-ber 1996.
[45] P. Rothemund. A DNA and restriction enzyme implemen- tation of Turing machines. In E. B. Baum and R. J. Lip-ton, editors, DNA based computers. American MathematicalSociety, 1996. Number 27 in DIMACS: Series in DiscreteMathematics and Theoretical Computer Science.
[46] S. Roweis, E. Winfree, R. Bourgoyne, N. V. Chelyapov, M. F. Goodman, P. W. K. Rothemund, and L. M. Adleman.
A sticker based architecture for DNA computation. In Pro-ceedings of the Second Annual Meeting on DNA based Com-puters, 1996.
[47] R. Siromoney, K. G. Subramanian, and V. R. Dare. Circu- lar DNA and splicing systems. In Proceedings of the 2ndInternational Conference on Parallel Image Analysis, pages260–273, 1992.

Source: http://eldar.cz/honza/dklub/Recent%20Developments%20in%20DNA-Computing.pdf