Chess games: a model for RNA based computation

Encoding scheme for data storage and retrieval on DNA computers

There has been exponential growth in the amount of data being generated on a daily basis. Such a huge amount of data creates a need for efficient data storage techniques. Due to the limitations of existing storage media, new storage solutions have always been of interest. There have been recent developments in order to efficiently use synthetic deoxyribonucleic acid (DNA) for information storage. DNA storage has attracted researchers because of its extremely high data storage density, about 1 exabyte/mm3 and long life under easily achievable conditions. This work presents an encoding scheme for DNA-based data storage system with controllable redundancy and reliability, the authors have also talked about the feasibility of the proposed method. The authors have also analysed the proposed algorithm for time and space complexity. The proposed encoding scheme tries to minimise the bases per letter ratio while controlling the redundancy. They have experimented with three different types of data with a value of redundancy as 0.75. In the randomised simulation setup, it was observed that the proposed algorithm was able to correctly retrieve the stored data in our experiments about 94% of the time. In the situation, where redundancy was increased to 1, the authors were able to retrieve all the information correctly in the proposed experiments.

Nanopore Decoding of Oligonucleotides in DNA Computing

In conventional DNA-computation methods involving logic gate operations, the output molecules are detected and decoded mainly by gel electrophoresis or fluorescence measurements. To employ rapid and label-free decoding, nanopore technology, an emerging methodology for single-molecule detection or DNA sequencing, is proposed as a candidate for electrical and simple decoding of DNA computations. This review describes recent approaches to decoding DNA computation using label-free and electrical nanopore measurements. Several attempts have been successful in DNA decoding with the nanopore either through enzymatic reactions or in water-in-oil droplets. Additionally, DNA computing combined with nanopore decoding has clinical applications, including microRNA detection for early diagnosis of cancers. Because this decoding methodology is still in development and not yet widely accepted, this review aims to inform the scientific community regarding usefulness.

Field programmable chemistry: integrated chemical and electronic processing of informational molecules towards electronic chemical cells

The topic addressed is that of combining self-constructing chemical systems with electronic computation to form unconventional embedded computation systems performing complex nano-scale chemical tasks autonomously. The hybrid route to complex programmable chemistry, and ultimately to artificial cells based on novel chemistry, requires a solution of the two-way massively parallel coupling problem between digital electronics and chemical systems. We present a chemical microprocessor technology and show how it can provide a generic programmable platform for complex molecular processing tasks in Field Programmable Chemistry, including steps towards the grand challenge of constructing the first electronic chemical cells. Field programmable chemistry employs a massively parallel field of electrodes, under the control of latched voltages, which are used to modulate chemical activity. We implement such a field programmable chemistry which links to chemistry in rather generic, two-phase microfluidic channel networks that are separated into weakly coupled domains. Electric fields, produced by the high-density array of electrodes embedded in the channel floors, are used to control the transport of chemicals across the hydrodynamic barriers separating domains. In the absence of electric fields, separate microfluidic domains are essentially independent with only slow diffusional interchange of chemicals. Electronic chemical cells, based on chemical microprocessors, exploit a spatially resolved sandwich structure in which the electronic and chemical systems are locally coupled through homogeneous fine-grained actuation and sensor networks and play symmetric and complementary roles. We describe how these systems are fabricated, experimentally test their basic functionality, simulate their potential (e.g. for feed forward digital electrophoretic (FFDE) separation) and outline the application to building electronic chemical cells.

A P system and a constructive membrane-inspired DNA algorithm for solving the Maximum Clique Problem

We present a P system with replicated rewriting to solve the Maximum Clique Problem for a graph. Strings representing cliques are built gradually. This involves the use of inhibitors that control the space of all generated solutions to the problem. Calculating the maximum clique for a graph is a highly relevant issue not only on purely computational grounds, but also because of its relationship to fundamental problems in genomics. We propose to implement the designed P system by means of a DNA algorithm. This algorithm is then compared with two standard papers that addressed the same problem and its DNA implementation in the past. This comparison is carried out on the basis of a series of computational and physical parameters. Our solution features a significantly lower cost in terms of time, the number and size of strands, as well as the simplicity of the biological implementation.

Biomolecular computing: Is it ready to take off?

Biomolecular computing is an emerging field at the interface of computer science, biological science and engineering. It uses DNA and other biological materials as the building blocks for construction of living computational machines to solve difficult combinatorial problems. In this article, notable advances in the biomolecular computing are reviewed and challenges associated with this multidisciplinary research are addressed. Finally, several perspectives are given based on the review of biomolecular computing.

Fast parallel molecular algorithms for DNA-based computation: factoring integers

The RSA public-key cryptosystem is an algorithm that converts input data to an unrecognizable encryption and converts the unrecognizable data back into its original decryption form. The security of the RSA public-key cryptosystem is based on the difficulty of factoring the product of two large prime numbers. This paper demonstrates to factor the product of two large prime numbers, and is a breakthrough in basic biological operations using a molecular computer. In order to achieve this, we propose three DNA-based algorithms for parallel subtractor, parallel comparator, and parallel modular arithmetic that formally verify our designed molecular solutions for factoring the product of two large prime numbers. Furthermore, this work indicates that the cryptosystems using public-key are perhaps insecure and also presents clear evidence of the ability of molecular computing to perform complicated mathematical operations.

Solving the 3-SAT problem based on DNA computing

The 3-SAT problem is an NP-complete problem, and many algorithms based on DNA computing have been proposed for solving it since Adleman's pioneering work. This paper presents a new algorithm based on the literal string strategy proposed by Sakamoto et al. Simulation results show that the maximal number of literal strings produced during the computing process is greatly reduced. Moreover, the length of the literal strings is also reduced from m to n at most.

The general form of 0-1 programming problem based on DNA computing

DNA computing is a novel method of solving a class of intractable computational problems, in which the computing speeds up exponentially with the problem size. Up to now, many accomplishments have been made to improve its performance and increase its reliability. In this paper, we solved the general form of 0-1 programming problem with fluorescence labeling techniques based on surface chemistry by attempting to apply DNA computing to a programming problem. Our method has some significant advantages such as simple encoding, low cost, and short operating time.

From molecular biology to nanotechnology and nanomedicine

Great progress in the development of molecular biology techniques has been seen since the discovery of the structure of deoxyribonucleic acid (DNA) and the implementation of a polymerase chain reaction (PCR) method. This started a new era of research on the structure of nucleic acids molecules, the development of new analytical tools, and DNA-based analyses. The latter included not only diagnostic procedures but also, for example, DNA-based computational approaches. On the other hand, people have started to be more interested in mimicking real life, and modeling the structures and organisms that already exist in nature for the further evaluation and insight into their behavior and evolution. These factors, among others, have led to the description of artificial organelles or cells, and the construction of nanoscale devices. These nanomachines and nanoobjects might soon find a practical implementation, especially in the field of medical research and diagnostics. The paper presents some examples, illustrating the progress in multidisciplinary research in the nanoscale area. It is focused especially on immunogenetics-related aspects and the wide usage of DNA molecules in various fields of science. In addition, some proposals for nanoparticles and nanoscale tools and their applications in medicine are reviewed and discussed.

Optically programming DNA computing in microflow reactors

The programmability and the integration of biochemical processing protocols are addressed for DNA computing using photochemical and microsystem techniques. A magnetically switchable selective transfer module (STM) is presented which implements the basic sequence-specific DNA filtering operation under constant flow. Secondly, a single steady flow system of STMs is presented which solves an arbitrary instance of the maximal clique problem of given maximum size N. Values of N up to about 100 should be achievable with current lithographic techniques. The specific problem is encoded in an initial labeling pattern of each module with one of 2N DNA oligonucleotides, identical for all instances of maximal clique. Thirdly, a method for optically programming the DNA labeling process via photochemical lithography is proposed, allowing different problem instances to be specified. No hydrodynamic switching of flows is required during operation -- the STMs are synchronously clocked by an external magnet. An experimental implementation of this architecture is under construction and will be reported elsewhere.