Dataset Information

Ternary DNA computing using 3 × 3 multiplication matrices.

ABSTRACT: Non-Boolean computations implementing operations on multi-valued variables beyond base 2 allow enhanced computational complexity. We introduce DNA as a functional material for ternary computing, and in particular demonstrate the use of three-valued oligonucleotide inputs to construct a 3 × 3 multiplication table. The system consists of two three-valued inputs of -1; 0; +1 and a fluorophore/quencher functional hairpin acting as computational and reporter module. The interaction of the computational hairpin module with the different values of the inputs yields a 3 × 3 multiplication matrix consisting of nine nanostructures that are read out by three distinct fluorescence intensities. By combining three different hairpin computational modules, each modified with a different fluorophore/quencher pair, and using different sets of inputs, the parallel operation of three multiplication tables is demonstrated.

SUBMITTER: Orbach R

PROVIDER: S-EPMC5811156 | biostudies-literature | 2015 Feb

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

Ternary DNA computing using 3 × 3 multiplication matrices.

Orbach Ron R Lilienthal Sivan S Klein Michael M Levine R D RD Remacle Francoise F Willner Itamar I

Chemical science 20141114 2

Non-Boolean computations implementing operations on multi-valued variables beyond base 2 allow enhanced computational complexity. We introduce DNA as a functional material for ternary computing, and in particular demonstrate the use of three-valued oligonucleotide inputs to construct a 3 × 3 multiplication table. The system consists of two three-valued inputs of -1; 0; +1 and a fluorophore/quencher functional hairpin acting as computational and reporter module. The interaction of the computation ...[more]

PMID: 29560214

Similar Datasets

Project description:The theory of computer science is based around universal Turing machines (UTMs): abstract machines able to execute all possible algorithms. Modern digital computers are physical embodiments of classical UTMs. For the most important class of problem in computer science, non-deterministic polynomial complete problems, non-deterministic UTMs (NUTMs) are theoretically exponentially faster than both classical UTMs and quantum mechanical UTMs (QUTMs). However, no attempt has previously been made to build an NUTM, and their construction has been regarded as impossible. Here, we demonstrate the first physical design of an NUTM. This design is based on Thue string rewriting systems, and thereby avoids the limitations of most previous DNA computing schemes: all the computation is local (simple edits to strings) so there is no need for communication, and there is no need to order operations. The design exploits DNA's ability to replicate to execute an exponential number of computational paths in P time. Each Thue rewriting step is embodied in a DNA edit implemented using a novel combination of polymerase chain reactions and site-directed mutagenesis. We demonstrate that the design works using both computational modelling and in vitro molecular biology experimentation: the design is thermodynamically favourable, microprogramming can be used to encode arbitrary Thue rules, all classes of Thue rule can be implemented, and non-deterministic rule implementation. In an NUTM, the resource limitation is space, which contrasts with classical UTMs and QUTMs where it is time. This fundamental difference enables an NUTM to trade space for time, which is significant for both theoretical computer science and physics. It is also of practical importance, for to quote Richard Feynman 'there's plenty of room at the bottom'. This means that a desktop DNA NUTM could potentially utilize more processors than all the electronic computers in the world combined, and thereby outperform the world's current fastest supercomputer, while consuming a tiny fraction of its energy.

Project description:Recent efforts in synthetic biology have focussed on the implementation of logical functions within living cells. One aim is to facilitate both internal "re-programming" and external control of cells, with potential applications in a wide range of domains. However, fundamental limitations on the degree to which single cells may be re-engineered have led to a growth of interest in multicellular systems, in which a "computation" is distributed over a number of different cell types, in a manner analogous to modern computer networks. Within this model, individual cell type perform specific sub-tasks, the results of which are then communicated to other cell types for further processing. The manner in which outputs are communicated is therefore of great significance to the overall success of such a scheme. Previous experiments in distributed cellular computation have used global communication schemes, such as quorum sensing (QS), to implement the "wiring" between cell types. While useful, this method lacks specificity, and limits the amount of information that may be transferred at any one time. We propose an alternative scheme, based on specific cell-cell conjugation. This mechanism allows for the direct transfer of genetic information between bacteria, via circular DNA strands known as plasmids. We design a multi-cellular population that is able to compute, in a distributed fashion, a Boolean XOR function. Through this, we describe a general scheme for distributed logic that works by mixing different strains in a single population; this constitutes an important advantage of our novel approach. Importantly, the amount of genetic information exchanged through conjugation is significantly higher than the amount possible through QS-based communication. We provide full computational modelling and simulation results, using deterministic, stochastic and spatially-explicit methods. These simulations explore the behaviour of one possible conjugation-wired cellular computing system under different conditions, and provide baseline information for future laboratory implementations.

Dataset Information

Ternary DNA computing using 3 × 3 multiplication matrices.

Publications

Ternary DNA computing using 3 × 3 multiplication matrices.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets