19-07-2011, 04:27 PM
Abstract
We demonstrate that DNA computers can simulate
Boolean circuits with a small overhead. Boolean circuits
embody the notion of massively parallel signal processing
and are jrequen,tly encountered in many parallel algorithms.
Many important problems such as sorting, integer arithmetic,
and matrix multiplication are known to be computable
by small size Boolean circuits much faster than by ordinary
sequential digital computers. This paper shows that DNA
chemistry allows one to simulate large semi-unbounded janin
Boolean circuits with a logarithmic slowdown in computation
time. Also, for the class NC’, the slowdown can be
reduced to a constant. In this algorathm we have encoded
the inputs, the Boolean AND gates, and the OR gates to
DNA oligonucleotide sequences. We operate on the gates
and the inputs by standard molecular techniques of sequencespecific
annealing, ligation, separation by size, amplification,
sequence-specific cleavage, and detection by size. Additional
steps of amplification are not necessary for NC” circuits.
Preliminary biochemical experiments on a small test circuit
have produced encouraging results. Further confirmatory experiments
are in progress.
1 Introduction
Adleman [Ad194], subsequently Lipton [Lip951 showed
the potential of Recombinant DNA-based combinatorial
chemistry as a tool for solving computationally difficult
search problems. The massive parallelism of liquid phase
DNA chemistry, coupled with the encoding of information in
DNA strands, raises the hope for solving “intractable” problems.
These novel approaches to computation also raise the
*Department of Computer Science, University of Rochester,
Rochester, NY 14627. email: ogihara[at]cs.rochester.edu.
‘Department of Biology, University of Rochester, Rochester, NY
14627. Supported in part by National Science Foundation Grant
MCB-9630402. email: ray[at]ar.biology.rochester.edu.
permission to make digital/h,ard copies of all or parl of this mderi.ll for
paonal or classroom use is granted without fee provided that the copies
are not made or distributed for profit or commercial advantage, the COPYri&
t notice, the title of the publication and its date appear, and notice is
given tint copyright is by permission of the ACM, Inc. TO copy otherwise,
to republish, to post on serverS or to redistribute to list.?, requires specific
permission and/or fee.
RECOMB 97. Santa Fe New Mexico WA
Copyright 1997 ACM O-89791-882-8/97/01 ..$3.50
question whether the DNA computers as a devise for simulating
existing massively parallel computation models can
go beyond the limit of digital computers.
Among many massively parallel computation models,
typical are the Parallel Random Access Machines (PRAM)
and the Boolean circuits. In the PRAM model, the computation
is carried out by ordinary serial processors that
have as storage a shared, global memory. The processors
execute individual programs. All processors can read from
or write to the global memory “in parallel” (at the same
time), and depending on the outcome of the simultaneous
read and the simultaneous write, various PRAM models
are defined. The complexity of a PRAM algorithm is mcasured
by the number of processors involved and the running
time. Recently, Reif [Rei95] formulated an abstract parallel
DNA computation model, the Parallel Associative Memory
model, and showed that his parallel model can simulate the
Concurrent-Read, Exclusive-Write PRAM model (CREW
PR.AM model), with a small time overhead. More precisely,
a CREW PRAM algorithm running in time T on P processors
with the total memory size A4 can be simulated by a
Parallel Associative Memory algorithm in time O(T+log” S)
and space polynomial in S where 5’ = PM. Implement,ing
the abstract model on DNA computers with Recombinant,
DNA techniques results in O(log S) slowdown. Thus, in this
case, the time complexity becomes O(T log S + log” S).
On the other hand, in the Boolean circuit model, the
computation is carried out by a network of signal processors
(called gates) computing simple Boolean functions, the AND
and the OR. These gates have no memory and process their
incoming signals only once during the computation. The
complexity of a Boolean circuit is measured by the size (thr
number of gates) and the depth (the length of the longest
directed path). Depending on the input capacity of the AND
and the OR, three Boolean circuit models are defined. They
are (i) the unbounded fan-in circuits (the input capacit,y is
unlimited for both the AND gate and the OR gate), (ii) the
semi-unbounded fan-in circuits (the input capacity is two for
the AND and unlimited for the OR), and (iii) the hounded
fan-in circuits (the input capacity is two for both the AND
gate and the OR gate).
Download full report
http://www.googleurl?sa=t&source=web&cd=...1.108.1282%26rep%3Drep1%26type%3Dpdf&ei=amIlTvb3DIe8rAeWrrCzCQ&usg=AFQjCNFo_IK7AOuUn9TICvk1h50osCDeew&sig2=oJLYT_8RCitgW6qKK6cxyQ
We demonstrate that DNA computers can simulate
Boolean circuits with a small overhead. Boolean circuits
embody the notion of massively parallel signal processing
and are jrequen,tly encountered in many parallel algorithms.
Many important problems such as sorting, integer arithmetic,
and matrix multiplication are known to be computable
by small size Boolean circuits much faster than by ordinary
sequential digital computers. This paper shows that DNA
chemistry allows one to simulate large semi-unbounded janin
Boolean circuits with a logarithmic slowdown in computation
time. Also, for the class NC’, the slowdown can be
reduced to a constant. In this algorathm we have encoded
the inputs, the Boolean AND gates, and the OR gates to
DNA oligonucleotide sequences. We operate on the gates
and the inputs by standard molecular techniques of sequencespecific
annealing, ligation, separation by size, amplification,
sequence-specific cleavage, and detection by size. Additional
steps of amplification are not necessary for NC” circuits.
Preliminary biochemical experiments on a small test circuit
have produced encouraging results. Further confirmatory experiments
are in progress.
1 Introduction
Adleman [Ad194], subsequently Lipton [Lip951 showed
the potential of Recombinant DNA-based combinatorial
chemistry as a tool for solving computationally difficult
search problems. The massive parallelism of liquid phase
DNA chemistry, coupled with the encoding of information in
DNA strands, raises the hope for solving “intractable” problems.
These novel approaches to computation also raise the
*Department of Computer Science, University of Rochester,
Rochester, NY 14627. email: ogihara[at]cs.rochester.edu.
‘Department of Biology, University of Rochester, Rochester, NY
14627. Supported in part by National Science Foundation Grant
MCB-9630402. email: ray[at]ar.biology.rochester.edu.
permission to make digital/h,ard copies of all or parl of this mderi.ll for
paonal or classroom use is granted without fee provided that the copies
are not made or distributed for profit or commercial advantage, the COPYri&
t notice, the title of the publication and its date appear, and notice is
given tint copyright is by permission of the ACM, Inc. TO copy otherwise,
to republish, to post on serverS or to redistribute to list.?, requires specific
permission and/or fee.
RECOMB 97. Santa Fe New Mexico WA
Copyright 1997 ACM O-89791-882-8/97/01 ..$3.50
question whether the DNA computers as a devise for simulating
existing massively parallel computation models can
go beyond the limit of digital computers.
Among many massively parallel computation models,
typical are the Parallel Random Access Machines (PRAM)
and the Boolean circuits. In the PRAM model, the computation
is carried out by ordinary serial processors that
have as storage a shared, global memory. The processors
execute individual programs. All processors can read from
or write to the global memory “in parallel” (at the same
time), and depending on the outcome of the simultaneous
read and the simultaneous write, various PRAM models
are defined. The complexity of a PRAM algorithm is mcasured
by the number of processors involved and the running
time. Recently, Reif [Rei95] formulated an abstract parallel
DNA computation model, the Parallel Associative Memory
model, and showed that his parallel model can simulate the
Concurrent-Read, Exclusive-Write PRAM model (CREW
PR.AM model), with a small time overhead. More precisely,
a CREW PRAM algorithm running in time T on P processors
with the total memory size A4 can be simulated by a
Parallel Associative Memory algorithm in time O(T+log” S)
and space polynomial in S where 5’ = PM. Implement,ing
the abstract model on DNA computers with Recombinant,
DNA techniques results in O(log S) slowdown. Thus, in this
case, the time complexity becomes O(T log S + log” S).
On the other hand, in the Boolean circuit model, the
computation is carried out by a network of signal processors
(called gates) computing simple Boolean functions, the AND
and the OR. These gates have no memory and process their
incoming signals only once during the computation. The
complexity of a Boolean circuit is measured by the size (thr
number of gates) and the depth (the length of the longest
directed path). Depending on the input capacity of the AND
and the OR, three Boolean circuit models are defined. They
are (i) the unbounded fan-in circuits (the input capacit,y is
unlimited for both the AND gate and the OR gate), (ii) the
semi-unbounded fan-in circuits (the input capacity is two for
the AND and unlimited for the OR), and (iii) the hounded
fan-in circuits (the input capacity is two for both the AND
gate and the OR gate).
Download full report
http://www.googleurl?sa=t&source=web&cd=...1.108.1282%26rep%3Drep1%26type%3Dpdf&ei=amIlTvb3DIe8rAeWrrCzCQ&usg=AFQjCNFo_IK7AOuUn9TICvk1h50osCDeew&sig2=oJLYT_8RCitgW6qKK6cxyQ