AU Yin, ZX
   Zhang, FY
   Xu, J
TI A chinese postman problem based on DNA computing
SO JOURNAL OF CHEMICAL INFORMATION AND COMPUTER SCIENCES
AB DNA computing is a novel method for solving a class of
   intractable computational problems, in which the computing can
   grow exponentially with the problem size. Up to now, many
   accomplishments have been achieved to improve its performance
   and increase its reliability. A Chinese Postman Problem has
   been solved by means of molecular biology techniques in the
   paper. A small graph was encoded in molecules of DNA, and the
   "operations" of the computation were performed with standard
   protocols and enzymes. This work represents further evidence
   for the ability of DNA computing to solve NP-complete search
   problems.
BP 222
EP 224
PG 3
JI J. Chem. Inf. Comput. Sci.
PY 2002
PD MAR-APR
VL 42
IS 2
GA 537AF
J9 J CHEM INFORM COMPUT SCI
UT ISI:000174733500011
ER


AU Shao, XG
   Jiang, HY
   Cai, WS
TI Advances in biomolecular computing
SO PROGRESS IN CHEMISTRY
AB Due to the high parallelism and recognition ability of the
   biomolecules in biochemical reactions, biomolecular computing
   behaves great advantage in solving combinatorial optimization
   problems. Biomolecular computing has been successfully applied
   in computing NP complete problems such as Hamiltonion path
   problem, maximal clique problem and SAT problems in Boolean
   calculation, etc. This paper presents a review of fundamental
   ideas, computing methods, applications and advances in
   biomolecular computing. Furthermore, the developmental trend of
   biomolecular computing is described.
BP 37
EP 46
PG 10
JI Prog. Chem.
PY 2002
PD JAN
VL 14
IS 1
GA 533DP
J9 PROG CHEM
UT ISI:000174514400006
ER


AU Raymo, FM
TI Digital processing and communication with molecular switches
SO ADVANCED MATERIALS
AB Molecular switches based on chemical, electrical, or optical
   stimulations are a hot topic as they can provide the future for
   faster computers and internet applications. Basic logic
   operations of AND, NOT, and OR gates have been reproduced
   relying on simple molecular switches (see Figure). The
   fabrication of nanoelectronic circuits and all-optical networks
   from molecular components can be envisaged.
BP 401
EP +
PG 15
JI Adv. Mater.
PY 2002
PD MAR 18
VL 14
IS 6
GA 534EE
J9 ADVAN MATER
UT ISI:000174571000001
ER


AU Rose, JA
   Deaton, RJ
   Hagiya, M
   Suyama, A
TI Equilibrium analysis of the efficiency of an autonomous
   molecular computer
SO PHYSICAL REVIEW E
AB In the whiplash polymerase chain reaction (WPCR), autonomous
   molecular computation is implemented in vitro by the recursive.
   self-directed polymerase extension of a mixture of DNA
   hairpins. Although computational efficiency is known to be
   reduced by a tendency for DNAs to self-inhibit by
   backhybridization, both the magnitude of this effect and its
   dependence on the reaction conditions have remained open
   questions. In this paper, the impact of backhybridization on
   WPCR efficiency is addressed by modeling the recursive
   extension of each strand as a Markov chain. The extension
   efficiency per effective polymerase-DNA encounter is then
   estimated within the framework of a statistical thermodynamic
   model. Model predictions are shown to provide close agreement
   with the premature halting of computation reported in a recent
   in vitro WPCR implementation, a particularly significant
   result. given that backhybridization had been discounted as the
   dominant error process. The scaling behavior further indicates
   completion times to be sufficiently long to render WPCR-based
   massive parallelism infeasible. A modified architecture. PNA-
   mediated WPCR (PWPCR) is then proposed in which the occupancy
   of backhybridized hairpins is reduced by targeted PNA(2)/DNA
   triplex formation. The efficiency of PWPCR is discussed using a
   modified form of the model developed for WPCR. Predictions
   indicate the PWPCR efficiency is sufficient to allow the
   implementation of autonomous molecular computation on a massive
   scale.
BP art. no.
EP 021910
PG 13
JI Phys. Rev. E
PY 2002
PD FEB
VL 65
IS 2
PN 1
GA 524XK
J9 PHYS REV E
UT ISI:000174038000075
ER


AU Zimmermann, KH
TI On applying molecular computation to binary linear
SO IEEE TRANSACTIONS ON INFORMATION THEORY
AB Adleman's successful solution of a seven-vertex instance of the
   NP-complete Hamiltonian directed path problem by a DNA
   algorithm initiated the field of biomolecular computing. In
   this correspondence, we describe DNA algorithms based on the
   sticker model to perform encoding, minimum-distance
   computation, and maximum-likelihood (ML) decoding of binary
   linear codes. We also discuss feasibility and limitations of
   the sticker algorithms.
BP 505
EP 510
PG 6
JI IEEE Trans. Inf. Theory
PY 2002
PD FEB
VL 48
IS 2
GA 515FW
J9 IEEE TRANS INFORM THEORY
UT ISI:000173485600010
ER


AU Yin, YM
   Lin, XQ
TI Progress on molecular computer
SO PROGRESS IN CHEMISTRY
AB Fabrication of molecular computer seems to be the only way to
   break through the limits of conventional semiconductor
   electronic computer. This review shows the recent development
   in the field of molecular computer, and emphases on the advance
   of DNA computer. Various and complicated computing mechanism of
   proteins in living cells of bio-organism, which may provide
   models for more speculation and new attempt on the molecular
   computer, is also in our scope. 43 references were cited.
BP 337
EP 342
PG 6
JI Prog. Chem.
PY 2001
PD SEP
VL 13
IS 5
GA 492DW
J9 PROG CHEM
UT ISI:000172154000002
ER


AU Benenson, Y
   Paz-Elizur, T
   Adar, R
   Keinan, E
   Livneh, Z
   Shapiro, E
TI Programmable and autonomous computing machine made of
   biomolecules
SO NATURE
AB Devices that convert information from one form into another
   according to a definite procedure are known as automata. One
   such hypothetical device is the universal Turing machine(1),
   which stimulated work leading to the development of modern
   computers. The Turing machine and its special cases(2),
   including finite automata(3), operate by scanning a data tape,
   whose striking analogy to information-encoding biopolymers
   inspired several designs for molecular DNA computers(4-8).
   Laboratory-scale computing using DNA and human-assisted
   protocols has been demonstrated(9-15), but the realization of
   computing devices operating autonomously on the molecular scale
   remains rare(16-20). Here we describe a programmable finite
   automaton comprising DNA and DNA-manipulating enzymes that
   solves computational problems autonomously. The automaton's
   hardware consists of a restriction nuclease and ligase, the
   software and input are encoded by double-stranded DNA, and
   programming amounts to choosing appropriate software molecules.
   Upon mixing solutions containing these components, the
   automaton processes the input molecule via a cascade of
   restriction, hybridization and ligation cycles, producing a
   detectable output molecule that encodes the automaton's final
   state, and thus the computational result. In our implementation
   10(12) automata sharing the same software run independently and
   in parallel on inputs (which could, in principle, be distinct)
   in 120 mul solution at room temperature at a combined rate of
   10(9) transitions per second with a transition fidelity greater
   than 99.8%, consuming less than 10(-10) W.
BP 430
EP 434
PG 5
JI Nature
PY 2001
PD NOV 22
VL 414
IS 6862
GA 494UP
J9 NATURE
UT ISI:000172304500038
ER


AU Appelbaum, I
   Wang, TR
   Fan, SH
   Joannopoulos, JD
   Narayanamurti, V
TI Can silicon dimers form logic gates?
SO NANOTECHNOLOGY
AB We have performed density functional theory calculations to
   show how a tungsten scanning probe can mediate the interactions
   between bistable Si(100) surface dimers. Interpreting the state
   of each dimer as a bit of information, we demonstrate the use
   of this mediated interaction to construct a NOR logic gate.
BP 391
EP 393
PG 3
JI Nanotechnology
PY 2001
PD SEP
VL 12
IS 3
GA 480GR
J9 NANOTECHNOL
UT ISI:000171454100032
ER


AU Chen, WC
   Chen, ZH
   Qui, HX
   Wang, ZQ
TI Progress in DNA computer
SO PROGRESS IN BIOCHEMISTRY AND BIOPHYSICS
AB DNA computer is a new research field which combines both the
   computer science and molecular biology. DNA computer is
   proposed to solve a class of hard problems of mathematical
   complexity by using a set of DNA sequences encoding all
   candidate solutions to the computational problem of interest
   and find out the correct answers by serial manipulations of
   biochemical reactions. DNA computer is exactly a biomolecular
   computer which stores a vast quantity of information with high
   density. DNA computer, by means of its huge parallel
   computation and brute force search strategy, can solve the NP
   complete problems with polynomial time. The recent advances and
   principle of DNA computer are introduced. The future
   development and the bioinformatical significance of DNA
   computer are also analyzed and discussed.
BP 156
EP 159
PG 4
JI Prog. Biochem. Biophys.
PY 2001
PD APR
VL 28
IS 2
GA 425WR
J9 PROG BIOCHEM BIOPHYS
UT ISI:000168315100007
ER


AU Hug, H
   Schuler, R
TI Strategies for the development of a peptide computer
SO BIOINFORMATICS
AB Motivation: We devise a computational model using protein-
   protein interactions. Results: Peptide-antibody interactions
   can be used to perform a large number of small logical
   operations in parallel. We show for example how a sequence of
   operations can be used to compare the number of occurrences of
   an element in two sets and how to estimate the number of
   occurrences of an element in a set. Similar to DNA-computing,
   these techniques could in principle be extended to solve
   instances of NP-complete problems. We give as an example a
   procedure to solve examples of the satisfiability problem.
BP 364
EP 368
PG 5
JI Bioinformatics
PY 2001
PD APR
VL 17
IS 4
GA 425ZY
J9 BIOINFORMATICS
UT ISI:000168325600010
ER


AU Dongarra, JJ
   Walker, DW
TI The quest for petascale computing
SO COMPUTING IN SCIENCE & ENGINEERING
AB Although the challenges to achieving petascale computing within
   the next decade are daunting, several software and hardware
   technologies are emerging that could help us reach this goal.
   The authors review these technologies and consider new
   algorithms capable of exploiting a petascale computer's
   architecture.
BP 32
EP 39
PG 8
JI Comput. Sci. Eng.
PY 2001
PD MAY-JUN
VL 3
IS 3
GA 424CA
J9 COMPUT SCI ENG
UT ISI:000168213500010
ER


AU Wu, HY
TI An improved surface-based method for DNA computation
SO BIOSYSTEMS
AB DNA computing is a novel method for solving a class of
   intractable computational problems, in which the computing time
   can grow exponentially with problem size. Up to now, many
   accomplishments have been achieved to improve its performance
   and increase its reliability, among which a surface-based
   method is an efficient candidate. In this paper, the surface-
   based approach proposed by Liu, Q., Wang, L., Frutos, A.G.,
   Condon, A.E., Corn, R.M., and Smith, L.M. 2000, DNA computing
   on surfaces. Nature 403, 175-179 is analyzed and an improved
   surface-based method for DNA computation (i.e. the hybrid
   DNA;optical computing method) is proposed. Compared with Liu et
   al.'s approach, our method has some significant advantages such
   as low cost, short operating time, reusable surface and simple
   experimental steps. Moreover, the concept of combining easily
   patterned DNA computing steps with equally parallel, but
   generally uniform and not easily patterned optical computing
   steps is an important new direction. (C) 2001 Elsevier Science
   Ireland Ltd. All rights reserved.
BP 1
EP 5
PG 5
JI Biosystems
PY 2001
PD JAN
VL 59
IS 1
GA 411DU
J9 BIOSYSTEMS
UT ISI:000167483500001
ER


AU Wasiewicz, P
   Malinowski, A
   Nowak, R
   Mulawka, JJ
   Borsuk, P
   Weglenski, P
   Plucienniczak, A
TI DNA computing: implementation of data flow logical operations
SO FUTURE GENERATION COMPUTER SYSTEMS
AB Self-assembly of DNA is considered a fundamental operation in
   realization of molecular logic circuits. We propose a new
   approach to implementation of data flow logical operations
   based on manipulating DNA strands. In our method the logic
   gates, input, and output signals are represented by DNA
   molecules. Each logical operation is carried out as soon as the
   operands are ready. This technique employs standard operations
   of genetic engineering including radioactive labeling as well
   as digestion by the second class restriction nuclease and
   polymerase chain reaction (PCR). To check practical utility of
   the method a series of genetic engineering experiments have
   been performed. The obtained information confirms interesting
   properties of the DNA-based molecular data flow logic gates.
   Some experimental results demonstrating implementation of a
   single logic NAND gate and only in one vessel calculation of a
   tree-like Boolean function with the help of the PCR are
   provided. These techniques may be utilized in massively
   parallel computers and on DNA chips. (C) 2001 Elsevier Science
   B.V. All rights reserved.
BP 361
EP 378
PG 18
JI Futur. Gener. Comp. Syst.
PY 2001
PD JAN
VL 17
IS 4
GA 397FN
J9 FUTURE GENER COMPUT SYST
UT ISI:000166682800004
ER


AU Marrow, P
TI Nature-inspired computing technology and applications
SO BT TECHNOLOGY JOURNAL
AB Increasing demands upon current computer systems, along with
   technological changes, create a need for more flexible and
   adaptable systems. Natural systems provide many examples of the
   type of versatile system required This paper reviews examples
   of nature-inspired computing, drawing inspiration from many
   different areas of living systems including evolution, ecology,
   development and behaviour. The implications for the future
   development of computing technology and applications are also
   discussed
BP 13
EP 23
PG 11
JI BT Technol. J.
PY 2000
PD OCT
VL 18
IS 4
GA 386VQ
J9 BT TECHNOL J
UT ISI:000166082600003
ER


AU Beigel, R
   Fu, B
TI Molecular computing, bounded nondeterminism, and efficient
   recursion
SO ALGORITHMICA
AB The maximum number of strands used is an important measure of a
   molecular algorithm's complexity. This measure is also called
   the volume used by the algorithm. Every problem that can be
   solved by an NP Turing machine with b(n) binary
   nondeterministic choices can be solved by molecular computation
   in a polynomial number of steps, with four test tubes, in
   volume 2(b(n)). We identify a large class of recursive
   algorithms that can be implemented using bounded
   nondeterminism. This yields improved molecular algorithms for
   important problems like 3-SAT, independent set, and 3-
   colorability.
BP 222
EP 238
PG 17
JI Algorithmica
PY 1999
PD OCT-NOV
VL 25
IS 2-3
GA 379YY
J9 ALGORITHMICA
UT ISI:000165671800005
ER


AU Ogihara, M
   Ray, A
TI Simulating Boolean circuits on a DNA computer
SO ALGORITHMICA
AB 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 frequently
   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 fan-in Boolean circuits with a
   logarithmic slowdown in computation time. Also, for the class
   NC1, the slowdown can be reduced to a constant. In this
   algorithm 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
   sequence-specific annealing, ligation, separation by size,
   amplification, sequence-specific cleavage, and detection by
   size. Additional steps of amplification are not necessary for
   NC1 circuits. The feasibility of the DNA algorithm has been
   successfully tested on a small circuit by actual biochemical
   experiments.
BP 239
EP 250
PG 12
JI Algorithmica
PY 1999
PD OCT-NOV
VL 25
IS 2-3
GA 379YY
J9 ALGORITHMICA
UT ISI:000165671800006
ER


AU Forbes, N
TI Biologically inspired computing
SO COMPUTING IN SCIENCE & ENGINEERING
BP 83
EP 87
PG 5
JI Comput. Sci. Eng.
PY 2000
PD NOV-DEC
VL 2
IS 6
GA 369HU
J9 COMPUT SCI ENG
UT ISI:000165060500013
ER


AU Leier, A
   Richter, C
   Banzhaf, W
   Rauhe, H
TI Cryptography with DNA binary strands
SO BIOSYSTEMS
AB Biotechnological methods can be used for cryptography. Here two
   different cryptographic approaches based on DNA binary strands
   ale shown. The first approach shows how DNA binary strands can
   be used for steganography, a technique of encryption by
   information hiding, to provide rapid encryption and decryption.
   It is shown that DNA steganography based on DNA binary strands
   is secure under the assumption that an interceptor has the same
   technological capabilities as sender and receiver of encrypted
   messages. The second approach shown here is based on
   steganography and a method of graphical subtraction of binary
   gel-images. II can be used to constitute a molecular checksum
   and can be combined with the first approach to support
   encryption. DNA cryptography might become of practical
   relevance in the context of labelling organic and inorganic
   materials with DNA 'barcodes'. (C) 2000 Elsevier Science
   Ireland Ltd. All rights reserved.
BP 13
EP 22
PG 10
JI Biosystems
PY 2000
PD JUN
VL 57
IS 1
GA 341MV
J9 BIOSYSTEMS
UT ISI:000088594900002
ER


AU Chen, JH
   Wood, DH
TI Computation with biomolecules
SO PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED
   STATES OF AMERICA
BP 1328
EP 1330
PG 3
JI Proc. Natl. Acad. Sci. U. S. A.
PY 2000
PD FEB 15
VL 97
IS 4
GA 285VU
J9 PROC NAT ACAD SCI USA
UT ISI:000085409600005
ER


AU Kari, L
   Gloor, G
   Yu, S
TI Using DNA to solve the Bounded Post Correspondence Problem
SO THEORETICAL COMPUTER SCIENCE
AB Theoretical research in DNA computing includes designing
   practical experiments for solving various computational
   problems by means of DNA manipulation. This paper proposes a
   DNA algorithm for an NP-complete problem, The Bounded Post
   Correspondence Problem. The proposed experiment can be used to
   test several standard molecular biology laboratory procedures
   for their usability as bio-operations in DNA computing. (C)
   2000 Elsevier Science B.V. All rights reserved.
BP 193
EP 203
PG 11
JI Theor. Comput. Sci.
PY 2000
PD JAN 28
VL 231
IS 2
GA 272LA
J9 THEOR COMPUT SCI
UT ISI:000084650500006
ER


AU Cukras, AR
   Faulhammer, D
   Lipton, RJ
   Landweber, LF
TI Chess games: a model for RNA based computation
SO BIOSYSTEMS
AB Here we develop the theory of RNA computing and a method for
   solving the 'knight problem' as an instance of a satisfiability
   (SAT) problem. Using only biological molecules and enzymes as
   tools, we developed an algorithm for solving the knight problem
   (3 x 3 chess board) using a 10-bit combinatorial pool and
   sequential RNase H digestions. The results of preliminary
   experiments presented here reveal that the protocol recovers
   far more correct solutions than expected at random, but the
   persistence of errors still presents the greatest challenge.
   (C) 1999 Elsevier Science Ireland Ltd. All rights reserved.
BP 35
EP 45
PG 11
JI Biosystems
PY 1999
PD OCT
VL 52
IS 1-3
GA 261NY
J9 BIOSYSTEMS
UT ISI:000084016300005
ER


AU Manca, V
   Martin-Vide, C
   Paun, G
TI New computing paradigms suggested by DNA computing: computing
   by carving
SO BIOSYSTEMS
AB Inspired by the experiments in the emerging area of DNA
   computing, a somewhat unusual type of computation strategy was
   recently proposed by one of us: to generate a (large) set of
   candidate solutions of a problem, then remove the non-solutions
   such that what remains is the set of solutions. This has been
   called a computation by carving. This idea leads both to a
   speculation with possible important consequences-computing non-
   recursively enumerable languages-and to interesting theoretical
   computer science (formal language) questions. (C) 1999 Elsevier
   Science Ireland Ltd. All rights reserved.
BP 47
EP 54
PG 8
JI Biosystems
PY 1999
PD OCT
VL 52
IS 1-3
GA 261NY
J9 BIOSYSTEMS
UT ISI:000084016300006
ER


AU Jonoska, N
   Karl, SA
   Saito, M
TI Three dimensional DNA structures in computing
SO BIOSYSTEMS
AB We show that 3-dimensional graph structures can be used for
   solving computational problems with DNA molecules. Vertex
   building blocks consisting of Fc-armed (k = 3 or 4) branched
   junction molecules are used to form graphs. We present
   procedures for the 3-SAT and 3-vertex-colorability problems.
   Construction of one graph structure (in many copies) is
   sufficient to determine the solution to the problem. In our
   proposed procedure for S-SAT, the number of steps required is
   equal to the number of variables in the formula. For the 3-
   vertex-colorability problem, the procedure requires a constant
   number of steps regardless of the size of the graph. (C) 1999
   Elsevier Science Ireland Ltd. All rights reserved.
BP 143
EP 153
PG 11
JI Biosystems
PY 1999
PD OCT
VL 52
IS 1-3
GA 261NY
J9 BIOSYSTEMS
UT ISI:000084016300016
ER


AU Toha, J
   Soto, MA
TI Biochemical identification of prime numbers
SO MEDICAL HYPOTHESES
AB A biochemical technique is proposed whereby prime numbers may
   be identified. (C) 1999 Harcourt Publishers Ltd.
BP 361
EP 361
PG 1
JI Med. Hypotheses
PY 1999
PD OCT
VL 53
IS 4
GA 256EW
J9 MED HYPOTHESES
UT ISI:000083713800016
ER


AU Lee, CM
   Kim, SW
   Kim, SM
   Sohn, U
TI DNA computing the Hamiltonian path problem
SO MOLECULES AND CELLS
AB The directed Hamiltonian path (DHP) problem is one of the hard
   computational problems for which there is no practical
   algorithm on a conventional computer available. Many problems,
   including the traveling sales person problem and the longest
   path problem, can be translated into the DHP problem, which
   implies that an algorithm for DHP can also solve all the
   translated problems. To study the robustness of the laboratory
   protocol of the pioneering DNA computing for the DHP problem
   performed by Leonard Adleman (1994), we investigated how the
   graph size, multiplicity of the Hamiltonian paths, and the size
   of oligonucleotides that encode the vertices would affect the
   laboratory procedures, We applied Adleman's protocol with 18-
   mer oligonucleotide per node to a graph with 8 vertices and 14
   edges containing two Hamiltonian paths (Adleman used 20-mer
   oligonucleotides for a graph with 7 nodes, 14 edges and one
   Hamiltonian path). We found that depending on the graph
   characteristics such as the number of short cycles, the
   oligonucleotide size, and the hybridization conditions that
   used to encode the graph, the protocol should be executed with
   different parameters from Adleman's.
BP 464
EP 469
PG 6
JI Mol. Cells
PY 1999
PD OCT 31
VL 9
IS 5
GA 250TA
J9 MOL CELLS
UT ISI:000083403200002
ER


AU Karp, RM
   Kenyon, C
   Waarts, O
TI Error-resilient DNA computation
SO RANDOM STRUCTURES & ALGORITHMS
AB The DNA model of computation, with test tubes of DNA molecules
   encoding bit sequences, is based on three primitives: Extract-
   A-Bit, which splits a test tube into two test tubes according
   to the value of a particular bit x, Merge-Two-Tubes, and
   Detect-Emptiness, if perfect, these operations can test the
   satisfiability of any boolean formula in linear time. However,
   in reality the Extract operation is faulty and misclassifies
   some of the strands. We consider the following reduction
   problem: given an algorithm based on perfect Extract, Merge,
   and Detect operations, convert it: to an algorithm that is
   correct with high probability even though the Extract operation
   is faulty. The fundamental problem in such a reduction is the
   simulation of a single highly reliable Extract operation. We
   determine the number of faulty Extract operations to simulate a
   highly reliable Extract operation, with matching upper and
   lower bounds (up to a constant factor). We then propose a
   reduction to convert any algorithm based on error-free
   operations to an error-resilient algorithm. In the case of
   simple n-variable boolean functions. Conjunction, Disjunction,
   and Parity, we prove that our error-resilient algorithms are
   optimal. (C) 1999 John Wiley & Sons, Inc.
BP 450
EP 466
PG 17
JI Random Struct. Algorithms
PY 1999
PD OCT-DEC
VL 15
IS 3-4
GA 250CQ
J9 RANDOM STRUCT ALGORITHM
UT ISI:000083371800012
ER


AU Sipper, M
TI The emergence of cellular computing
SO COMPUTER
AB The von Neumann architecture-which is based upon the principle
   of one he von Neumann architecture-which is based upon the
   principle of one complex processor that sequentially performs a
   single complex task at a given moment-has dominated computing
   technology for the past 50 years. Recently, however,
   researchers have begun exploring alternative computational
   systems based on entirely different principles. Although
   emerging from disparate domains, the work behind these systems
   shares a common computational philosophy, which the author
   calls cellular computing. This philosophy promises to provide
   new means for doing computation more efficiently-in terms of
   speed, cost, power dissipation, information storage, and
   solution quality. Simultaneously, cellular computing offers the
   potential of addressing much larger problem instances than
   previously possible, at least for some application domains.
   Cellular computing has attracted increasing research interest.
   Work in this field has produced results that hold prospects for
   a bright future. Yet questions must be answered before cellular
   computing can become a mainstream paradigm. What classes of
   computational tasks are most suited to it? How do we match the
   specific properties and behaviors of a given model to a
   suitable class of problems?
BP 18
EP +
PG 10
JI Computer
PY 1999
PD JUL
VL 32
IS 7
GA 212TE
J9 COMPUTER
UT ISI:000081231700010
ER


AU Landweber, LF
TI The evolution of cellular computing
SO BIOLOGICAL BULLETIN
BP 324
EP 325
PG 2
JI Biol. Bull.
PY 1999
PD JUN
VL 196
IS 3
GA 210KR
J9 BIOL BULL
UT ISI:000081104800020
ER


AU Hagiya, M
TI Perspectives on molecular computing
SO NEW GENERATION COMPUTING
AB In 1996, we began a research project on molecular computers
   under the new program "Research for the Future" funded by the
   Japan Society for the Promotion of Science. In this paper, we
   first summarize the research that has been completed in the
   field of DNA computing and the research problems that must be
   overcome. We also report some achievements of our research
   project in the first two years. We then propose a new direction
   in research towards autonomous molecular computers, and
   describe the author's work on the implementation of state
   machines using DNA molecules. We finally discuss the future
   perspectives on molecular computing based on our experiences.
BP 131
EP 151
PG 21
JI New Gener. Comput.
PY 1999
VL 17
IS 2
GA 185FD
J9 NEW GENERATION COMPUT
UT ISI:000079656700001
ER


AU Cox, JC
   Cohen, DS
   Ellington, AD
TI The complexities of DNA computation
SO TRENDS IN BIOTECHNOLOGY
AB Over the past few years, a handful of insightful researchers
   have bridged the gap between biological computing theory and
   actual DNA-based computation. By using ingenious encoding
   techniques and clever molecular-biological manipulations,
   simple versions of computationally complex problems have been
   experimentally approached or resolved. However, the technical
   problems revealed during the execution of these scientific set
   pieces make it unlikely that DNA will ever rival silicon for
   the solution of any real-world problem.
BP 151
EP 154
PG 4
JI Trends Biotechnol.
PY 1999
PD APR
VL 17
IS 4
GA 181AR
J9 TRENDS BIOTECH
UT ISI:000079418900003
ER


AU Krishnamurthy, V
   Krishnamurthy, EV
TI Rule-based programming paradigm: a formal basis for biological,
   chemical and physical computation
SO BIOSYSTEMS
AB A rule-based programming paradigm is described as a formal
   basis for biological, chemical and physical computations. In
   this paradigm, the computations are interpreted as the outcome
   arising out of interaction of elements in an object space. The
   interactions can create new elements (or same elements with
   modified attributes) or annihilate old elements according to
   specific rules. Since the interaction rules are inherently
   parallel, any number of actions can be performed cooperatively
   or competitively among the subsets of elements, so that the
   elements evolve toward an equilibrium or unstable or chaotic
   state. Such an evolution may retain certain invariant
   properties of the attributes of the elements. The object space
   resembles Gibbsian ensemble that corresponds to a distribution
   of points in the space of positions and momenta (called phase
   space). It permits the introduction of probabilities in rule
   applications. As each element of the ensemble changes over
   time, its phase point is carried into a new phase point. The
   evolution of this probability cloud in phase space corresponds
   to a distributed probabilistic computation. Thus, this paradigm
   can handle tor deterministic exact computation when the initial
   conditions are exactly specified and the trajectory of
   evolution is deterministic. Also, it can handle probabilistic
   mode of computation if we want to derive macroscopic or bulk
   properties of matter. We also explain how to support this rule-
   based paradigm using relational-database like query processing
   and transactions. (C) 1999 Elsevier Science Ireland Ltd. All
   rights reserved.
BP 205
EP 228
PG 24
JI Biosystems
PY 1999
PD MAR
VL 49
IS 3
GA 171PW
J9 BIOSYSTEMS
UT ISI:000078873400003
ER


AU Lusth, JC
   Dixon, B
TI A characterization of important algorithms for quantum-dot
   cellular automata
SO INFORMATION SCIENCES
AB Feature sizes in chip manufacturing are becoming so small that
   quantum mechanical behavior will. soon have a deleterious
   effect on the function of devices. Quantum-dot cellular
   automats (QDCA) have been proposed as computing devices which
   are helped, rather than hindered, by the quantum behavior of
   electrons. QDCA compute by relaxing to a configuration of
   minimal energy. Previously, it has been shown that a quantum-
   dot device may not compute properly if all of its relaxed
   configurations are not equal in energy level. Such an automaton
   is termed unbalanced. A necessary condition for an automaton to
   be balanced is that the number of distinguished configurations
   with minimum energy should equal the number of input
   combinations the automaton handles. Does an efficient algorithm
   for determining the number of distinguished ground states
   exist? If so, it will be difficult to find, as such an
   algorithm is shown to be NP-hard. Furthermore, the related
   problem of determining the minimum energy level of arbitrary
   automata is also shown to be NP-hard, These results have
   important implications for simulating and analyzing QDCA on
   conventional computers. (C) 1999 Elsevier Science Inc. All
   rights reserved.
BP 193
EP 204
PG 12
JI Inf. Sci.
PY 1999
PD FEB
VL 113
IS 3-4
GA 151AL
J9 INFORM SCIENCES
UT ISI:000077698700002
ER


AU Freund, R
   Kari, L
   Paun, G
TI DNA computing based on splicing: The existence of universal
   computers
SO THEORY OF COMPUTING SYSTEMS
AB We prove that splicing systems with finite components and
   certain controls on their work are computationally complete
   (they can simulate any Turing Machine); moreover, there are
   universal splicing systems (systems with all components fixed
   which can simulate any given splicing system, when an encoding
   of the particular system is added-as a program-to the universal
   system). Splicing systems are based on the splicing operation
   which is a model for DNA recombination. Informally, a prefix of
   a word is catenated to a suffix of another word, thus yielding
   a (possibly) new word. Cutting occurs at specific sites which
   correspond to specific sequences in DNA strands as they can be
   recognized by restriction enzymes. When no additional control
   is assumed, splicing systems with finitely many starting words
   (axioms) and finitely many splicing rules are known to
   characterize only regular languages (those recognized by finite
   automata). However, when a splicing rule is allowed to be used
   (1) only in the presence of certain symbols ("catalyst") or (2)
   only in the absence of certain symbols ("inhibitors"), then we
   can characterize the recursively enumerable languages
   (recognized by Turing Machines); the same result is obtained
   when counting the number of copies of (some of) the words used.
   From the proofs, we also infer the existence of universal
   (hence programmable) splicing systems.
BP 69
EP 112
PG 44
JI Theor. Comput. Syst.
PY 1999
PD JAN-FEB
VL 32
IS 1
GA 141WG
J9 THEORY COMPUT SYST
UT ISI:000077166800003
ER


AU Bach, E
   Condon, A
   Glaser, E
   Tanguay, C
TI DNA models and algorithms for NP-complete problems
SO JOURNAL OF COMPUTER AND SYSTEM SCIENCES
AB A goal of research on DNA computing is to solve problems that
   are beyond the capabilities of the fastest silicon-based
   supercomputers. Adleman and Lipton present exhaustive search
   algorithms for 3Sat and 3-coloring, which can only be run on
   small instances and, hence, are not practical. In this paper,
   we show how improved algorithms can be developed for the 3-
   coloring and independent set problems. Our algorithms use only
   the DNA operations proposed by Adleman and Lipton, but combine
   them in more powerful ways and use polynomial preprocessing on
   a standard computer to tailor them to the specific instance to
   be solved. The main contribution of this paper is a more
   general model of DNA algorithms than that proposed by Lipton.
   We show that DNA computation for NP-complete problems can do
   more than just exhaustive search. Further research in this
   direction will help determine whether or not DNA computing is
   viable for NP-hard problems. A second contribution is the first
   analysis of errors that arise in generating the solution space
   for DNA computation. (C) 1998 Academic Press.
BP 172
EP 186
PG 15
JI J. Comput. Syst. Sci.
PY 1998
PD OCT
VL 57
IS 2
GA 138JL
J9 J COMPUT SYST SCI
UT ISI:000076968700005
ER


AU Forbes, NA
   Lipton, RJ
TI DNA computing: A possible efficiency boost for specialized
   problems
SO COMPUTERS IN PHYSICS
BP 304
EP 306
PG 3
JI Comput. Phys.
PY 1998
PD JUL-AUG
VL 12
IS 4
GA 114MX
J9 COMPUT PHYS
UT ISI:000075614200004
ER

PT Book in series
AU Landweber, LF
   Lipton, R
TI DNA (2)DNA computations: A potential "killer app"?
SO AUTOMATA, LANGUAGES AND PROGRAMMING
BP 56
EP 64
PG 9
SE LECTURE NOTES IN COMPUTER SCIENCE
PY 1997
VL 1256
GA BL41H
J9 LECT NOTE COMPUT SCI
UT ISI:000075412600006
ER

PT Book in series
AU Beigel, R
   Fu, B
TI Molecular computing, bounded nondeterminism, and efficient
   recursion
SO AUTOMATA, LANGUAGES AND PROGRAMMING
AB The maximum number of strands used is an important measure of
   a. molecular algorithm's complexity. This measure is also
   called the space used by the algorithm. We show that every NP
   problem that can be solved with b(n) bits of nondeterminism can
   be solved by molecular computation in a polynomial number of
   steps, with four test tubes, in space 2(b(n)). In addition, we
   identify a large class of recursive algorithms that can be
   implemented using bounded nondeterminism. This yields improved
   molecular algorithms for important problems Like 3-SAT:
   independent set, and 3-colorability.
BP 816
EP 826
PG 11
SE LECTURE NOTES IN COMPUTER SCIENCE
PY 1997
VL 1256
GA BL41H
J9 LECT NOTE COMPUT SCI
UT ISI:000075412600076
ER


AU Adleman, LM
TI Computing with DNA
SO SCIENTIFIC AMERICAN
BP 54
EP 61
PG 8
JI Sci.Am.
PY 1998
PD AUG
VL 279
IS 2
GA 101JB
J9 SCI AMER
UT ISI:000074864900026
ER


AU Rocha, AF
   Rebello, MP
   Miura, K
TI Toward a theory of molecular computing
SO INFORMATION SCIENCES
AB The recent interest in using knowledge about genetic systems to
   develop a theory of molecular computation, and the increasing
   challenge for the development of formal tools to handle the
   huge amount of knowledge acquired in big projects like the
   Human Genome Project, inspired to present paper the purpose of
   which is to show that the theory of Fuzzy Formal Language (FFL)
   may provide the answer X to such claims. However, it is also
   pointed here, that much remains to be done to fully develop
   this theory for such a purpose. (C) 1998 Elsevier Science Inc.
   All rights reserved.
BP 123
EP 157
PG 35
JI Inf. Sci.
PY 1998
PD APR
VL 106
IS 1-2
GA ZV792
J9 INFORM SCIENCES
UT ISI:000074341700008
ER


AU Heath, JR
   Kuekes, PJ
   Snider, GS
   Williams, RS
TI A defect-tolerant computer architecture: Opportunities for
   nanotechnology
SO SCIENCE
AB Teramac is a massively parallel experimental computer built at
   Hewlett-Packard Laboratories to investigate a wide range of
   different computational architectures. This machine contains
   about 220,000 hardware defects, any one of which could prove
   fatal to a conventional computer, and yet it operated 100 times
   faster than a high-end single-processor workstation for some of
   its configurations. The defect-tolerant architecture of
   Teramac, which incorporates a high communication bandwith that
   enables it to easily route around defects, has significant
   implications for any future nanometer-scale computational
   paradigm. It may be feasible to chemically synthesize
   individual electronic components with less than a 100 percent
   yield, assemble them into systems with appreciable uncertainty
   in their connectivity, and still create a powerful and reliable
   data communications network. Future nanoscale computers may
   consist of extremely large-configuration memories that are
   programmed for specific tasks by a tutor that locates and tags
   the defects in the system.
BP 1716
EP 1721
PG 6
JI Science
PY 1998
PD JUN 12
VL 280
IS 5370
GA ZU446
J9 SCIENCE
UT ISI:000074197800032
ER


AU Kulic, IM
TI Evaluating polynomials on the molecular level - a novel
   approach to molecular computers
SO BIOSYSTEMS
AB In the past few years two fascinating and new scientific
   fields, the science of DNA-structure and topology and the
   theory of molecular computers have been growing independently.
   The main goal of this paper is to establish an interesting
   connection between them and to propose a novel paradigm for the
   future construction of DNA-computing devices based on supercoil
   energetics. The basic principle of the proposed model can also
   be applied to describe the communication between topologically
   closed segments in real genomes, which is believed to take part
   in the complex process of gene regulation. An implementation of
   the recent model is proposed by which polynomials of one real
   variable can be evaluated in a simple in vitro recombination
   assay. (C) 1998 Elsevier Science Ireland Ltd.
BP 45
EP 57
PG 13
JI Biosystems
PY 1998
PD JAN
VL 45
IS 1
GA YV929
J9 BIOSYSTEMS
UT ISI:000071878600005
ER


AU Deaton, R
   Garzon, M
   Murphy, RC
   Rose, JA
   Franceschetti, DR
   Stevens, SE
TI Reliability and efficiency of a DNA-based computation
SO PHYSICAL REVIEW LETTERS
AB DNA-based computing uses the tendency of nucleotide bases to
   bind (hybridize) in preferred combinations to do computation.
   Depending on reaction conditions, oligonucleotides can bind
   despite noncomplementary base pairs. These mismatched
   hybridizations are a source of false positives and negatives,
   which limit the efficiency and scalability of DNA-based
   computing. The ability of specific base sequences to support
   error-tolerant Adleman-style computation is analyzed, and
   criteria are proposed to increase reliability and efficiency. A
   method is given to calculate reaction conditions from estimates
   of DNA melting.
BP 417
EP 420
PG 4
JI Phys. Rev. Lett.
PY 1998
PD JAN 12
VL 80
IS 2
GA YQ975
J9 PHYS REV LETT
UT ISI:000071444000053
ER


AU Young, WC
   Sheu, BJ
TI Unraveling the future of computing
SO IEEE CIRCUITS & DEVICES
BP 14
EP &
PG 9
JI IEEE Circuits Devices
PY 1997
PD NOV
VL 13
IS 6
GA YH706
J9 IEEE CIRCUITS DEVICES
UT ISI:A1997YH70600005
ER


AU Rambidi, NG
TI Biomolecular computer: roots and promises
SO BIOSYSTEMS
AB There are two basic issues inherent in contemporary molecular
   and biomolecular computing and urgent for its future
   development. They are: (i) fundamentals, that is general
   principles, starting points and correlation's between different
   approaches to design biomolecular information processing
   devices, (ii) working criteria, that is goals and principles
   for the choice of the device designing characteristics to
   achieve these goals. These issues are common to all major
   approaches of contemporary biomolecular computing. Increasing
   behavioral complexity of an information processing device seems
   to be a criterion for designing biomolecular means capable of
   solving problems of high computational complexity. (C) 1997
   Elsevier Science Ireland Ltd.
BP 1
EP 15
PG 15
JI Biosystems
PY 1997
VL 44
IS 1
GA YB469
J9 BIOSYSTEMS
UT ISI:A1997YB46900001
ER


AU Oliver, JS
TI Matrix multiplication with DNA
SO JOURNAL OF MOLECULAR EVOLUTION
AB A DNA-based method for calculating the product of Boolean
   matrices or matrices containing positive, real numbers is
   presented. In the case of matrices containing real numbers, the
   manipulation of reaction conditions allows a quantitative
   calculation to be performed. The use of DNA to perform an
   analog calculation illustrates a new approach to computing with
   DNA.
BP 161
EP 167
PG 7
JI J. Mol. Evol.
PY 1997
PD AUG
VL 45
IS 2
GA XN368
J9 J MOL EVOL
UT ISI:A1997XN36800009
ER

PT Book in series
AU Gibbons, A
   Amos, M
   Hodgson, D
TI Models of DNA computation
SO MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 1996
AB 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. Recently, several papers
   have advocated the realisation of massively parallel
   computation using the techniques and chemistry of molecular
   biology. Algorithms are not executed on a traditional, silicon-
   based computer, but instead employ the test-tube technology of
   genetic engineering. By representing information as sequences
   of bases in DNA molecules, existing DNA-manipulation techniques
   may be used to quickly detect and amplify desirable solutions
   to a given problem. We review the recent spate of papers in
   this field and take a critical view of their implications for
   laboratory experimentation. We note that extant models of DNA
   computation are flawed in that they rely upon certain error-
   prone biological operations. The one laboratory experiment that
   is seminal for current interest and claims to provide an
   efficient solution for the Hamiltonian path problem has proved
   to be unrepeatable by other researchers. We introduce a new
   model of DNA computation whose implementation is likely to be
   far more error-resistant than extant proposals. We describe an
   abstraction of the model which lends itself to natural
   algorithmic description, particularly for problems in the
   complexity class NP. In addition we describe a number of
   linear-time parallel algorithms within our model, particularly
   for NP-complete problems. We describe an ''in vitro''
   realisation of the model and conclude with a discussion of
   future work and outstanding problems.
BP 18
EP 36
PG 19
SE LECTURE NOTES IN COMPUTER SCIENCE
PY 1996
VL 1113
GA BH80B
J9 LECT NOTE COMPUT SCI
UT ISI:A1996BH80B00004
ER


AU Kari, L
TI DNA computing: Arrival of biological mathematics
SO MATHEMATICAL INTELLIGENCER
BP 9
EP 22
PG 14
JI Math. Intell.
PY 1997
PD SPR
VL 19
IS 2
GA WX528
J9 MATH INTELL
UT ISI:A1997WX52800007
ER


AU Gibbons, A
   Amos, M
   Hodgson, D
TI DNA computing
SO CURRENT OPINION IN BIOTECHNOLOGY
AB DNA computation is a novel and exciting recent development at
   the interface of computer science and molecular biology. We
   describe the current activity in this field following the
   seminal work of Adleman, who recently showed how techniques of
   molecular biology may be applied to the solution of a
   computationally intractable problem.
BP 103
EP 106
PG 4
JI Curr. Opin. Biotechnol.
PY 1997
PD FEB
VL 8
IS 1
GA WF599
J9 CURR OPIN BIOTECHNOL
UT ISI:A1997WF59900015
ER


AU Boneh, D
   Dunworth, C
   Lipton, RJ
   Sgall, J
TI On the computational power of DNA
SO DISCRETE APPLIED MATHEMATICS
AB We show how DNA-based computers can be used to solve the
   satisfiability problem for boolean circuits. Furthermore, we
   show how DNA computers can solve optimization problems directly
   without first solving several decision problems. Our methods
   also enable random sampling of satisfying assignments.
BP 79
EP 94
PG 16
JI Discret Appl. Math.
PY 1996
PD DEC 5
VL 71
IS 1-3
GA VX698
J9 DISCRETE APPL MATH
UT ISI:A1996VX69800006
ER


AU Rubin, H
TI Looking for the DNA killer app
SO NATURE STRUCTURAL BIOLOGY
AB The structural and functional properties of nucleic acids may
   form the basis for carrying out elementary and complex
   computational operations with biological molecules. A recent
   meeting on computing with DNA explored the potential of this
   approach.
BP 656
EP 658
PG 3
JI Nat. Struct. Biol.
PY 1996
PD AUG
VL 3
IS 8
GA VA150
J9 NATURE STRUCT BIOLOGY
UT ISI:A1996VA15000003
ER


AU Guarnieri, F
   Fliss, M
   Bancroft, C
TI Making DNA add
SO SCIENCE
AB Recent studies have demonstrated the feasibility of using DNA-
   based experiments to compute solutions to combinatorial
   problems. However, a prerequisite for designing a computer
   useful in a wide range of applications is the ability to
   perform mathematical calculations. The development of a DNA-
   based algorithm for addition is presented. The DNA
   representation of two nonnegative binary numbers is presented
   in a form permitting a chain of primer extension reactions to
   carry out the addition operation. To demonstrate the
   feasibility of this algorithm, a simple example was executed
   biochemically.
BP 220
EP 223
PG 4
JI Science
PY 1996
PD JUL 12
VL 273
IS 5272
GA UW787
J9 SCIENCE
UT ISI:A1996UW78700035
ER


AU Rozen, DE
   McGrew, S
   Ellington, AD
TI Molecular computing: Does DNA compute?
SO CURRENT BIOLOGY
AB The demonstration that DNA molecules can act as parallel
   processors to solve hard problems has excited interest in the
   possibility of developing molecular computers based on
   recombinant DNA techniques.
BP 254
EP &
PG 5
JI Curr. Biol.
PY 1996
PD MAR 1
VL 6
IS 3
GA UC440
J9 CURR BIOL
UT ISI:A1996UC44000015
ER