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 ofIntelligence 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 AnnualBulletin 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 UniversalComputer 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.

F A C U L T Y O F S C I E N C E Department of Physics & Institute of Computational and Theoretical Studies JOINT COLLOQUIUM Structure and Reactivity in Biocatalytic Centers: DFT Studies on Vanadium Oxo-peroxo Species Prof. Klaus E. Hermann T909 Science Tower, HK Baptist University Abstract The identification of structural details in biocatalysts i

Shropshire Archives ASPECTS OF MEDIEVAL LIFE AS ILLUSTRATED BY SOME DOCUMENTS IN THE LILLESHALL COLLECTION Excommunication was the commonest punishment in church courts. It took two forms: lesser, merely excluded the individual from church services; greater, theoretically imposed social death. The punishment was rarely meant to punish but to enforce the judgment of the court and acceptan