DNA solution of hard computational problems

Something has to give: scaling combinatorial computing by biological agents exploring physical networks encoding NP-complete problems

On-chip network-based computation, using biological agents, is a new hardware-embedded approach which attempts to find solutions to combinatorial problems, in principle, in a shorter time than the fast, but sequential electronic computers. This analytical review starts by describing the underlying mathematical principles, presents several types of combinatorial (including NP-complete) problems and shows current implementations of proof of principle developments. Taking the subset sum problem as example for in-depth analysis, the review presents various options of computing agents, and compares several possible operation 'run modes' of network-based computer systems. Given the brute force approach of network-based systems for solving a problem of input size C, 2C solutions must be visited. As this exponentially increasing workload needs to be distributed in space, time, and per computing agent, this review identifies the scaling-related key technological challenges in terms of chip fabrication, readout reliability and energy efficiency. The estimated computing time of massively parallel or combinatorially operating biological agents is then compared to that of electronic computers. Among future developments which could considerably improve network-based computing, labelling agents 'on the fly' and the readout of their travel history at network exits could offer promising avenues for finding hardware-embedded solutions to combinatorial problems.

DNA computing over the ring ℤ4[v]/〈v2 − v〉

In this paper, we discuss the DNA construction of general length over the finite ring [Formula: see text], with [Formula: see text], which plays a very significant role in DNA computing. We discuss the GC weight of DNA codes over [Formula: see text]. Several examples of reversible cyclic codes over [Formula: see text] are provided, whose [Formula: see text]-images are [Formula: see text]-linear codes with good parameters.

Design of DNA-based innovative computing system of digital comparison

Despite great potential and extensive interest in developing biomolecule-based computing, the development of even basic molecular logic gates is still in its infancy. Digital comparator (DC) is the basic unit in traditional electronic computers, but it is difficult to construct a system for achieving large-scale integration. Here, we construct, for the first time, a novel logic computing system of DCs that can compare whether two or more numbers are equal. Our approach is by taking advantage of facile preparation and unique properties of graphene oxide and DNA. The DC system reported in this work is developed by the DNA hybridization and effective combination of GO and single-stranded DNA, which is regarded as the reacting platform. On the basis of this platform and reaction principle, we have developed 2-inputs, 3-inputs, and 4-inputs DCs to realize the comparison of two or more binary numbers. We predict that such a state-of-the-art logic system enables its functionality with large-scale input signals, providing a new direction toward prototypical DNA-based logic operations and promoting the development of advanced logic computing. STATEMENT OF SIGNIFICANCE: The overarching objective of this paper is to explore the construction of a novel DNA computing system of digital comparator driven by the interaction of DNA and graphene oxide (GO). GO can efficient bind the dye-labeled, single-stranded DNA probe and then quench its fluorescence. In the case of the target appearing, specific binding between the single-stranded probe and its target occurs, changing the conformation and relationship with GO, then restoring the fluorescence of the dye. We have developed the 2-inputs, 3-inputs, and 4-inputs digital comparator circuits, which are expected to realize the comparison of large-scale input signals and can avoid the problems of design complexity and manufacturing cost of integrated circuits in traditional computing.

Ionic decision-maker created as novel, solid-state devices

Decision-making is being performed frequently in areas of computation to obtain better performance in a wide variety of current intelligent activities. In practical terms, this decision-making must adapt to dynamic changes in environmental conditions. However, because of limited computational resources, adaptive decision-making is generally difficult to achieve using conventional computers. The ionic decision-maker reported here, which uses electrochemical phenomena, has excellent dynamic adaptabilities, as demonstrated by its ability to solve multiarmed bandit problems (MBPs) in which a gambler given a choice of slot machines must select the appropriate machines to play so as to maximize the total reward in a series of trials. Furthermore, our ionic decision-maker successfully solves dynamic competitive MBPs, which cause serious loss due to the collision of selfish users in communication networks. The technique used in our devices offers a shift toward decision-making using the motion of ions, an approach that could find myriad applications in computer science and technology, including artificial intelligence.

3-Input/1-Output Logic Implementation Demonstrated by DNA Algorithmic Self-Assembly

Although structural DNA nanotechnology is a well-established field, computations performed using DNA algorithmic self-assembly is still in the primitive stages in terms of its adaptability of rule implementation and experimental complexity. Here, we discuss the feasibility of constructing an M-input/ N-output logic gate implemented into simple DNA building blocks. To date, no experimental demonstrations have been reported with M > 2 owing to the difficulty of tile design. To overcome this problem, we introduce a special tile referred to as an operator. We design appropriate binding domains in DNA tiles, and we demonstrate the growth of DNA algorithmic lattices generated by eight different rules from among 256 rules in a 3-input/1-output logic. The DNA lattices show simple, linelike, random, and mixed patterns, which we analyze to obtain errors and sorting factors. The errors vary from 0.8% to 12.8% depending upon the pattern complexity, and sorting factors obtained from the experiment are in good agreement with simulation results within a range of 1-18%.

DNA-Based Dynamic Reaction Networks

Deriving from logical and mechanical interactions between DNA strands and complexes, DNA-based artificial reaction networks (RNs) are attractive for their high programmability, as well as cascading and fan-out ability, which are similar to the basic principles of electronic logic gates. Arising from the dream of creating novel computing mechanisms, researchers have placed high hopes on the development of DNA-based dynamic RNs and have strived to establish the basic theories and operative strategies of these networks. This review starts by looking back on the evolution of DNA dynamic RNs; in particular' the most significant applications in biochemistry occurring in recent years. Finally, we discuss the perspectives of DNA dynamic RNs and give a possible direction for the development of DNA circuits.

DNA cyclic codes over the ring 𝔽2[u,v]/〈u2 − 1,v3 − v,uv − vu〉

In this paper, our main objective is to find out the necessary and sufficient conditions for a cyclic code of arbitrary length over the ring of four elements [Formula: see text] [Formula: see text] to be a reversible cyclic code. We also obtain the structure of cyclic DNA codes of odd length over the ring [Formula: see text], which plays an important role in Computational Biology. Furthermore, we establish a direct link between the elements of ring [Formula: see text] and 64 codons used in the amino acids of living organisms by introducing a Gray map from [Formula: see text] to [Formula: see text]. Among others, binary images of cyclic codes over [Formula: see text] are also investigated. As applications, some cyclic DNA codes over [Formula: see text] using the Gray map are provided.

DNA multi-bit non-volatile memory and bit-shifting operations using addressable electrode arrays and electric field-induced hybridization

DNA has been employed to either store digital information or to perform parallel molecular computing. Relatively unexplored is the ability to combine DNA-based memory and logical operations in a single platform. Here, we show a DNA tri-level cell non-volatile memory system capable of parallel random-access writing of memory and bit shifting operations. A microchip with an array of individually addressable electrodes was employed to enable random access of the memory cells using electric fields. Three segments on a DNA template molecule were used to encode three data bits. Rapid writing of data bits was enabled by electric field-induced hybridization of fluorescently labeled complementary probes and the data bits were read by fluorescence imaging. We demonstrated the rapid parallel writing and reading of 8 (2³) combinations of 3-bit memory data and bit shifting operations by electric field-induced strand displacement. Our system may find potential applications in DNA-based memory and computations.

DNA based technology holds promise for non-volatile memory and computational tasks, yet the relatively slow hybridization kinetics remain a bottleneck. Here, Song et al. have developed an electric field-induced hybridization platform that can speed up multi-bit memory and logic operations.

Model Checking Temporal Logic Formulas Using Sticker Automata

As an important complex problem, the temporal logic model checking problem is still far from being fully resolved under the circumstance of DNA computing, especially Computation Tree Logic (CTL), Interval Temporal Logic (ITL), and Projection Temporal Logic (PTL), because there is still a lack of approaches for DNA model checking. To address this challenge, a model checking method is proposed for checking the basic formulas in the above three temporal logic types with DNA molecules. First, one-type single-stranded DNA molecules are employed to encode the Finite State Automaton (FSA) model of the given basic formula so that a sticker automaton is obtained. On the other hand, other single-stranded DNA molecules are employed to encode the given system model so that the input strings of the sticker automaton are obtained. Next, a series of biochemical reactions are conducted between the above two types of single-stranded DNA molecules. It can then be decided whether the system satisfies the formula or not. As a result, we have developed a DNA-based approach for checking all the basic formulas of CTL, ITL, and PTL. The simulated results demonstrate the effectiveness of the new method.

Engineering nucleic acid structures for programmable molecular circuitry and intracellular biocomputation

Nucleic acids have attracted widespread attention due to the simplicity with which they can be designed to form discrete structures and programmed to perform specific functions at the nanoscale. The advantages of DNA/RNA nanotechnology offer numerous opportunities for in-cell and in-vivo applications, and the technology holds great promise to advance the growing field of synthetic biology. Many elegant examples have revealed the potential in integrating nucleic acid nanostructures in cells and in vivo where they can perform important physiological functions. In this Review, we summarize the current abilities of DNA/RNA nanotechnology to realize applications in live cells and then discuss the key problems that must be solved to fully exploit the useful properties of nanostructures. Finally, we provide viewpoints on how to integrate the tools provided by DNA/RNA nanotechnology and related new technologies to construct nucleic acid nanostructure-based molecular circuitry for synthetic biology.

Biomolecular computers with multiple restriction enzymes

The development of conventional, silicon-based computers has several limitations, including some related to the Heisenberg uncertainty principle and the von Neumann “bottleneck”. Biomolecular computers based on DNA and proteins are largely free of these disadvantages and, along with quantum computers, are reasonable alternatives to their conventional counterparts in some applications. The idea of a DNA computer proposed by Ehud Shapiro’s group at the Weizmann Institute of Science was developed using one restriction enzyme as hardware and DNA fragments (the transition molecules) as software and input/output signals. This computer represented a two-state two-symbol finite automaton that was subsequently extended by using two restriction enzymes. In this paper, we propose the idea of a multistate biomolecular computer with multiple commercially available restriction enzymes as hardware. Additionally, an algorithmic method for the construction of transition molecules in the DNA computer based on the use of multiple restriction enzymes is presented. We use this method to construct multistate, biomolecular, nondeterministic finite automata with four commercially available restriction enzymes as hardware. We also describe an experimental applicaton of this theoretical model to a biomolecular finite automaton made of four endonucleases.

Quantum information processing with superconducting circuits: a review

During the last ten years, superconducting circuits have passed from being interesting physical devices to becoming contenders for near-future useful and scalable quantum information processing (QIP). Advanced quantum simulation experiments have been shown with up to nine qubits, while a demonstration of quantum supremacy with fifty qubits is anticipated in just a few years. Quantum supremacy means that the quantum system can no longer be simulated by the most powerful classical supercomputers. Integrated classical-quantum computing systems are already emerging that can be used for software development and experimentation, even via web interfaces. Therefore, the time is ripe for describing some of the recent development of superconducting devices, systems and applications. As such, the discussion of superconducting qubits and circuits is limited to devices that are proven useful for current or near future applications. Consequently, the centre of interest is the practical applications of QIP, such as computation and simulation in Physics and Chemistry.

A new parallel DNA algorithm to solve the task scheduling problem based on inspired computational model

As a promising approach to solve the computationally intractable problem, the method based on DNA computing is an emerging research area including mathematics, computer science and molecular biology. The task scheduling problem, as a well-known NP-complete problem, arranges n jobs to m individuals and finds the minimum execution time of last finished individual. In this paper, we use a biologically inspired computational model and describe a new parallel algorithm to solve the task scheduling problem by basic DNA molecular operations. In turn, we skillfully design flexible length DNA strands to represent elements of the allocation matrix, take appropriate biological experiment operations and get solutions of the task scheduling problem in proper length range with less than O(n²) time complexity.

Active matter logic for autonomous microfluidics

Chemically or optically powered active matter plays an increasingly important role in materials design, but its computational potential has yet to be explored systematically. The competition between energy consumption and dissipation imposes stringent physical constraints on the information transport in active flow networks, facilitating global optimization strategies that are not well understood. Here, we combine insights from recent microbial experiments with concepts from lattice-field theory and non-equilibrium statistical mechanics to introduce a generic theoretical framework for active matter logic. Highlighting conceptual differences with classical and quantum computation, we demonstrate how the inherent non-locality of incompressible active flow networks can be utilized to construct universal logical operations, Fredkin gates and memory storage in set-reset latches through the synchronized self-organization of many individual network components. Our work lays the conceptual foundation for developing autonomous microfluidic transport devices driven by bacterial fluids, active liquid crystals or chemically engineered motile colloids.

Reversible Data Hiding Based on DNA Computing

Biocomputing, especially DNA, computing has got great development. It is widely used in information security. In this paper, a novel algorithm of reversible data hiding based on DNA computing is proposed. Inspired by the algorithm of histogram modification, which is a classical algorithm for reversible data hiding, we combine it with DNA computing to realize this algorithm based on biological technology. Compared with previous results, our experimental results have significantly improved the ER (Embedding Rate). Furthermore, some PSNR (peak signal-to-noise ratios) of test images are also improved. Experimental results show that it is suitable for protecting the copyright of cover image in DNA-based information security.

Repressor logic modules assembled by rolling circle amplification platform to construct a set of logic gates

Small molecule metabolites and their allosterically regulated repressors play an important role in many gene expression and metabolic disorder processes. These natural sensors, though valuable as good logic switches, have rarely been employed without transcription machinery in cells. Here, two pairs of repressors, which function in opposite ways, were cloned, purified and used to control DNA replication in rolling circle amplification (RCA) in vitro. By using metabolites and repressors as inputs, RCA signals as outputs, four basic logic modules were constructed successfully. To achieve various logic computations based on these basic modules, we designed series and parallel strategies of circular templates, which can further assemble these repressor modules in an RCA platform to realize twelve two-input Boolean logic gates and a three-input logic gate. The RCA-output and RCA-assembled platform was proved to be easy and flexible for complex logic processes and might have application potential in molecular computing and synthetic biology.

A general resolution of intractable problems in polynomial time through DNA Computing

Based on a set of known biological operations, a general resolution of intractable problems in polynomial time through DNA Computing is presented. This scheme has been applied to solve two NP-Hard problems (Minimization of Open Stacks Problem and Matrix Bandwidth Minimization Problem) and three co-NP-Complete problems (associated with Hamiltonian Path, Traveling Salesman and Hamiltonian Circuit), which have not been solved with this model. Conclusions and open questions concerning the computational capacity of this model are presented, and research topics are suggested.

A fully programmable 100-spin coherent Ising machine with all-to-all connections

Unconventional, special-purpose machines may aid in accelerating the solution of some of the hardest problems in computing, such as large-scale combinatorial optimizations, by exploiting different operating mechanisms than those of standard digital computers. We present a scalable optical processor with electronic feedback that can be realized at large scale with room-temperature technology. Our prototype machine is able to find exact solutions of, or sample good approximate solutions to, a variety of hard instances of Ising problems with up to 100 spins and 10,000 spin-spin connections.

New Trends of Digital Data Storage in DNA

With the exponential growth in the capacity of information generated and the emerging need for data to be stored for prolonged period of time, there emerges a need for a storage medium with high capacity, high storage density, and possibility to withstand extreme environmental conditions. DNA emerges as the prospective medium for data storage with its striking features. Diverse encoding models for reading and writing data onto DNA, codes for encrypting data which addresses issues of error generation, and approaches for developing codons and storage styles have been developed over the recent past. DNA has been identified as a potential medium for secret writing, which achieves the way towards DNA cryptography and stenography. DNA utilized as an organic memory device along with big data storage and analytics in DNA has paved the way towards DNA computing for solving computational problems. This paper critically analyzes the various methods used for encoding and encrypting data onto DNA while identifying the advantages and capability of every scheme to overcome the drawbacks identified priorly. Cryptography and stenography techniques have been analyzed in a critical approach while identifying the limitations of each method. This paper also identifies the advantages and limitations of DNA as a memory device and memory applications.

A biomimetic colorimetric logic gate system based on multi-functional peptide-mediated gold nanoparticle assembly

In natural biological systems, proteins exploit various functional peptide motifs to exert target response and activity switch, providing a functional and logic basis for complex cellular activities. Building biomimetic peptide-based bio-logic systems is highly intriguing but remains relatively unexplored due to limited logic recognition elements and complex signal outputs. In this proof-of-principle work, we attempted to address these problems by utilizing multi-functional peptide probes and the peptide-mediated nanoparticle assembly system. Here, the rationally designed peptide probes function as the dual-target responsive element specifically responsive to metal ions and enzymes as well as the mediator regulating the assembly of gold nanoparticles (AuNPs). Taking advantage of Zn2+ ions and chymotrypsin as the model inputs of metal ions and enzymes, respectively, we constructed the peptide logic system computed by the multi-functional peptide probes and outputted by the readable colour change of AuNPs. In this way, the representative binary basic logic gates (AND, OR, INHIBIT, NAND, IMPLICATION) have been achieved by delicately coding the peptide sequence, demonstrating the versatility of our logic system. Additionally, we demonstrated that the three-input combinational logic gate (INHIBIT-OR) could also be successfully integrated and applied as a multi-tasking biosensor for colorimetric detection of dual targets. This nanoparticle-based peptide logic system presents a valid strategy to illustrate peptide information processing and provides a practical platform for executing peptide computing or peptide-related multiplexing sensing, implying that the controllable nanomaterial assembly is a promising and potent methodology for the advancement of biomimetic bio-logic computation.

Solving the maximal matching problem with DNA molecules in Adleman–Lipton model

The maximal matching problem (MMP) is to find maximal edge subsets in a given undirected graph, that no pair of edges are adjacent in the subsets. It is a vitally important NP-complete problem in graph theory and applied mathematics, having numerous real life applications in optimal combination and linear programming fields. It can be difficultly solved by the electronic computer in exponential level time. Meanwhile in previous studies deoxyribonucleic acid (DNA) molecular operations usually were used to solve NP-complete continuous path search problems, e.g. HPP, traveling salesman problem, rarely for NP-hard problems with discrete vertices or edges solutions, such as the minimum vertex cover problem, graph coloring problem and so on. In this paper, we present a DNA algorithm for solving the MMP with DNA molecular operations. For an undirected graph with [Formula: see text] vertices and [Formula: see text] edges, we reasonably design fixed length DNA strands representing vertices and edges of the graph, take appropriate steps and get the solutions of the MMP in proper length range using [Formula: see text] time. We extend the application of DNA molecular operations and simultaneously simplify the complexity of the computation.

Parallel computation with molecular-motor-propelled agents in nanofabricated networks

The combinatorial nature of many important mathematical problems, including nondeterministic-polynomial-time (NP)-complete problems, places a severe limitation on the problem size that can be solved with conventional, sequentially operating electronic computers. There have been significant efforts in conceiving parallel-computation approaches in the past, for example: DNA computation, quantum computation, and microfluidics-based computation. However, these approaches have not proven, so far, to be scalable and practical from a fabrication and operational perspective. Here, we report the foundations of an alternative parallel-computation system in which a given combinatorial problem is encoded into a graphical, modular network that is embedded in a nanofabricated planar device. Exploring the network in a parallel fashion using a large number of independent, molecular-motor-propelled agents then solves the mathematical problem. This approach uses orders of magnitude less energy than conventional computers, thus addressing issues related to power consumption and heat dissipation. We provide a proof-of-concept demonstration of such a device by solving, in a parallel fashion, the small instance {2, 5, 9} of the subset sum problem, which is a benchmark NP-complete problem. Finally, we discuss the technical advances necessary to make our system scalable with presently available technology.

Prospects for using self-assembled nucleic acid structures

According to the central dogma in molecular biology, nucleic acids are assigned with key functions on storing and executing genetic information in any living cell. However, features of nucleic acids are not limited only with properties providing template-dependent biosynthetic processes. Studies of DNA and RNA unveiled unique features of these polymers able to make various self-assembled three-dimensional structures that, among other things, use the complementarity principle. Here, we review various self-assembled nucleic acid structures as well as application of DNA and RNA to develop nanomaterials, molecular automata, and nanodevices. It can be expected that in the near future results of these developments will allow designing novel next-generation diagnostic systems and medicinal drugs.

A Parallel Biological Optimization Algorithm to Solve the Unbalanced Assignment Problem Based on DNA Molecular Computing

The unbalanced assignment problem (UAP) is to optimally resolve the problem of assigning n jobs to m individuals (m < n), such that minimum cost or maximum profit obtained. It is a vitally important Non-deterministic Polynomial (NP) complete problem in operation management and applied mathematics, having numerous real life applications. In this paper, we present a new parallel DNA algorithm for solving the unbalanced assignment problem using DNA molecular operations. We reasonably design flexible-length DNA strands representing different jobs and individuals, take appropriate steps, and get the solutions of the UAP in the proper length range and O(mn) time. We extend the application of DNA molecular operations and simultaneity to simplify the complexity of the computation.

Controlling Motion at the Nanoscale: Rise of the Molecular Machines

As our understanding and control of intra- and intermolecular interactions evolve, ever more complex molecular systems are synthesized and assembled that are capable of performing work or completing sophisticated tasks at the molecular scale. Commonly referred to as molecular machines, these dynamic systems comprise an astonishingly diverse class of motifs and are designed to respond to a plethora of actuation stimuli. In this Review, we outline the conditions that distinguish simple switches and rotors from machines and draw from a variety of fields to highlight some of the most exciting recent examples of opportunities for driven molecular mechanics. Emphasis is placed on the need for controllable and hierarchical assembly of these molecular components to display measurable effects at the micro-, meso-, and macroscales. As in Nature, this strategy will lead to dramatic amplification of the work performed via the collective action of many machines organized in linear chains, on functionalized surfaces, or in three-dimensional assemblies.

A universal platform for building molecular logic circuits based on a reconfigurable three-dimensional DNA nanostructure

Molecular logic gates are capable of performing various logic tasks for biomarker detection, disease diagnostics and therapy, and controlling biological progress. Herein, we integrated multiple components of a logic device into a single DNA 3D nano-assembly with a triangular prism structure. Compared with the separate construction of each component in previously reported DNA logic gate systems, such an integrated design strategy made the 3D DNA nanoprism universal for logic gates, it can be reconfigured to execute diverse logic operations. Binary basic logic gates (OR, AND, INHIBIT and XOR), combinatorial gates (INHIBIT-OR), and multi-valued logic gates (ternary INHIBIT gate) were readily achieved by taking this DNA nanoprism as a universal platform. Moreover, a logic gate system for identification of even numbers and odd numbers from natural numbers was established successfully by employing only this single DNA nanoprism and four short single-stranded DNA. The universality of this nanoprism greatly simplified the design of DNA logic gate system. Additionally, this nanoprism was able to perform logic operation steadily in a biological matrix, indicating that this box-like DNA nanostructure applies to logic gates in a complicated environment. This study provided a unique opportunity to design versatile 3D DNA nanostructure-based intelligent nanodevices, which show great potential in biocomputing, multi-parameter sensing, and intelligent disease diagnostics and therapy.

A parallel algorithm for solving the n-queens problem based on inspired computational model

DNA computing provides a promising method to solve the computationally intractable problems. The n-queens problem is a well-known NP-hard problem, which arranges n queens on an n × n board in different rows, columns and diagonals in order to avoid queens attack each other. In this paper, we present a novel parallel DNA algorithm for solving the n-queens problem using DNA molecular operations based on a biologically inspired computational model. For the n-queens problem, we reasonably design flexible length DNA strands representing elements of the allocation matrix, take appropriate biologic manipulations and get the solutions of the n-queens problem in proper length and O(n(2)) time complexity. We extend the application of DNA molecular operations, simultaneity simplify the complexity of the computation and simulate to verify the feasibility of the DNA algorithm.

A survey of advancements in nucleic acid-based logic gates and computing for applications in biotechnology and biomedicine

Nucleic acid-based logic devices were first introduced in 1994. Since then, science has seen the emergence of new logic systems for mimicking mathematical functions, diagnosing disease and even imitating biological systems. The unique features of nucleic acids, such as facile and high-throughput synthesis, Watson-Crick complementary base pairing, and predictable structures, together with the aid of programming design, have led to the widespread applications of nucleic acids (NA) for logic gate and computing in biotechnology and biomedicine. In this feature article, the development of in vitro NA logic systems will be discussed, as well as the expansion of such systems using various input molecules for potential cellular, or even in vivo, applications.

Polar organic solvents accelerate the rate of DNA strand replacement reaction

Acceleration of the reaction rate by polar organic solvents during both simple and complicated DNA strand replacement reactions is reported.

A DNA-based pattern classifier with in vitro learning and associative recall for genomic characterization and biosensing without explicit sequence knowledge

Background

Genetic material extracted from in situ microbial communities has high promise as an indicator of biological system status. However, the challenge is to access genomic information from all organisms at the population or community scale to monitor the biosystem’s state. Hence, there is a need for a better diagnostic tool that provides a holistic view of a biosystem’s genomic status. Here, we introduce an in vitro methodology for genomic pattern classification of biological samples that taps large amounts of genetic information from all genes present and uses that information to detect changes in genomic patterns and classify them.

Results

We developed a biosensing protocol, termed Biological Memory, that has in vitro computational capabilities to “learn” and “store” genomic sequence information directly from genomic samples without knowledge of their explicit sequences, and that discovers differences in vitro between previously unknown inputs and learned memory molecules. The Memory protocol was designed and optimized based upon (1) common in vitro recombinant DNA operations using 20-base random probes, including polymerization, nuclease digestion, and magnetic bead separation, to capture a snapshot of the genomic state of a biological sample as a DNA memory and (2) the thermal stability of DNA duplexes between new input and the memory to detect similarities and differences. For efficient read out, a microarray was used as an output method. When the microarray-based Memory protocol was implemented to test its capability and sensitivity using genomic DNA from two model bacterial strains, i.e., Escherichia coli K12 and Bacillus subtilis, results indicate that the Memory protocol can “learn” input DNA, “recall” similar DNA, differentiate between dissimilar DNA, and detect relatively small concentration differences in samples.

Conclusions

This study demonstrated not only the in vitro information processing capabilities of DNA, but also its promise as a genomic pattern classifier that could access information from all organisms in a biological system without explicit genomic information. The Memory protocol has high potential for many applications, including in situ biomonitoring of ecosystems, screening for diseases, biosensing of pathological features in water and food supplies, and non-biological information processing of memory devices, among many.

Electronic supplementary material

The online version of this article (doi:10.1186/1754-1611-8-25) contains supplementary material, which is available to authorized users.

Molecular computing by PNA:PNA duplex formation

Molecular computing is potentially one of the most powerful tools for the development of massive parallel computing protocols. In the present paper, a first example of the use of PNA:PNA interactions in molecular computing is described. A series of short PNA sequences have been designed with a four base stretch coding for variables and solutions. Hybridization of the components in different combinations was tested both in solution and in a microarray format. A series of PNA representing the solutions were spotted on a microarray surface in order to simulate the hardware. A series of PNA representing the variables, labeled with TAMRA, were used to interrogate the device enabling to solve non-deterministic logic operations. The system was shown to be able to solve a two-variable equation with a high signal to noise ratio. This paper intends to provide a proof of principle that PNA, on account of their stability and specificity of binding, are most suitable for constructing organic-type computers.

Digital colloids: reconfigurable clusters as high information density elements

Through the design and manipulation of discrete, nanoscale systems capable of encoding massive amounts of information, the basic components of computation are open to reinvention. These components will enable tagging, memory storage, and sensing in unusual environments - elementary functions crucial for soft robotics and "wet computing". Here we show how reconfigurable clusters made of N colloidal particles bound flexibly to a central colloidal sphere have the capacity to store an amount of information that increases as O(N ln(N)). Using Brownian dynamics simulations, we predict dynamical regimes that allow for information to be written, saved, and erased. We experimentally assemble an N = 4 reconfigurable cluster from chemically synthesized colloidal building blocks, and monitor its equilibrium dynamics. We observe state switching in agreement with simulations. This cluster can store one bit of information, and represents the simplest digital colloid.

The laws of natural deduction in inference by DNA computer

We present a DNA-based implementation of reaction system with molecules encoding elements of the propositional logic, that is, propositions and formulas. The protocol can perform inference steps using, for example, modus ponens and modus tollens rules and de Morgan's laws. The set of the implemented operations allows for inference of formulas using the laws of natural deduction. The system can also detect whether a certain proposition a can be deduced from the basic facts and given rules. The whole protocol is fully autonomous; that is, after introducing the initial set of molecules, no human assistance is needed. Only one restriction enzyme is used throughout the inference process. Unlike some other similar implementations, our improved design allows representing simultaneously a fact a and its negation ~a, including special reactions to detect the inconsistency, that is, a simultaneous occurrence of a fact and its negation. An analysis of correctness, completeness, and complexity is included.

DNA based computing for understanding complex shapes

This study deals with a computing method called DNA based computing (DBC) that takes inspiration from the Central Dogma of Molecular Biology. The proposed DBC uses a set of user-defined rules to create a DNA-like sequence from a given piece of problem-relevant information (e.g., image data) in a dry-media (i.e., in an ordinary computer). It then uses another set of user-defined rules to create an mRNA-like sequence from the DNA. Finally, it uses the genetic code to translate the mRNA (or directly the DNA) to a protein-like sequence (a sequence of amino acids). The informational characteristics of the protein (entropy, absence, presence, abundance of some selected amino acids, and relationships among their likelihoods) can be used to solve problems (e.g., to understand complex shapes from their image data). Two case studies ((1) fractal geometry generated shape of a fern-leaf and (2) machining experiment generated shape of the worn-zones of a cutting tool) are presented elucidating the shape understanding ability of the proposed DBC in the presence of a great deal of variability in the image data of the respective shapes. The implication of the proposed DBC from the context of Internet-aided manufacturing system is also described. Further study can be carried out in solving other complex computational problems by using the proposed DBC and its derivatives.

Aptamer-based sensing platform using three-way DNA junction-driven strand displacement and its application in DNA logic circuit

We proposed a new three-way DNA junction-driven strand displacement mode and fabricated an aptamer-based label-free fluorescent sensing platform on the basis of this mechanism. Assembling the aptamer sequence into the three-way DNA junction makes the platform sensitive to the target of the aptamer. A label-free signal readout method, split G-quadruplex enhanced fluorescence of protoporphyrin IX (PPIX), was used to report the final signal. Here, adenosine triphosphatase (ATP) was taken as a model and detected through this approach, and DNA strand could also be detected by it. The mechanism was investigated by native polyacrylamide gel electrophoresis. Furthermore, on the basis of this molecular platform, we built a logic circuit with ATP and DNA strands as input. Aptamer played an important role in mediating the small molecule ATP to tune the DNA logic gate. Through altering the aptamer sequence, this molecular platform will be sensitive to various stimuli and applied in a wide field.

DNA strand displacement system running logic programs

The paper presents a DNA-based computing model which is enzyme-free and autonomous, not requiring a human intervention during the computation. The model is able to perform iterated resolution steps with logical formulae in conjunctive normal form. The implementation is based on the technique of DNA strand displacement, with each clause encoded in a separate DNA molecule. Propositions are encoded assigning a strand to each proposition p, and its complementary strand to the proposition ¬p; clauses are encoded comprising different propositions in the same strand. The model allows to run logic programs composed of Horn clauses by cascading resolution steps. The potential of the model is demonstrated also by its theoretical capability of solving SAT. The resulting SAT algorithm has a linear time complexity in the number of resolution steps, whereas its spatial complexity is exponential in the number of variables of the formula.

RNA nanotechnology for computer design and in vivo computation

Molecular-scale computing has been explored since 1989 owing to the foreseeable limitation of Moore's law for silicon-based computation devices. With the potential of massive parallelism, low energy consumption and capability of working in vivo, molecular-scale computing promises a new computational paradigm. Inspired by the concepts from the electronic computer, DNA computing has realized basic Boolean functions and has progressed into multi-layered circuits. Recently, RNA nanotechnology has emerged as an alternative approach. Owing to the newly discovered thermodynamic stability of a special RNA motif (Shu et al. 2011 Nat. Nanotechnol. 6, 658-667 (doi:10.1038/nnano.2011.105)), RNA nanoparticles are emerging as another promising medium for nanodevice and nanomedicine as well as molecular-scale computing. Like DNA, RNA sequences can be designed to form desired secondary structures in a straightforward manner, but RNA is structurally more versatile and more thermodynamically stable owing to its non-canonical base-pairing, tertiary interactions and base-stacking property. A 90-nucleotide RNA can exhibit 4⁹⁰ nanostructures, and its loops and tertiary architecture can serve as a mounting dovetail that eliminates the need for external linking dowels. Its enzymatic and fluorogenic activity creates diversity in computational design. Varieties of small RNA can work cooperatively, synergistically or antagonistically to carry out computational logic circuits. The riboswitch and enzymatic ribozyme activities and its special in vivo attributes offer a great potential for in vivo computation. Unique features in transcription, termination, self-assembly, self-processing and acid resistance enable in vivo production of RNA nanoparticles that harbour various regulators for intracellular manipulation. With all these advantages, RNA computation is promising, but it is still in its infancy. Many challenges still exist. Collaborations between RNA nanotechnologists and computer scientists are necessary to advance this nascent technology.

A DNA-based semantic fusion model for remote sensing data

Semantic technology plays a key role in various domains, from conversation understanding to algorithm analysis. As the most efficient semantic tool, ontology can represent, process and manage the widespread knowledge. Nowadays, many researchers use ontology to collect and organize data's semantic information in order to maximize research productivity. In this paper, we firstly describe our work on the development of a remote sensing data ontology, with a primary focus on semantic fusion-driven research for big data. Our ontology is made up of 1,264 concepts and 2,030 semantic relationships. However, the growth of big data is straining the capacities of current semantic fusion and reasoning practices. Considering the massive parallelism of DNA strands, we propose a novel DNA-based semantic fusion model. In this model, a parallel strategy is developed to encode the semantic information in DNA for a large volume of remote sensing data. The semantic information is read in a parallel and bit-wise manner and an individual bit is converted to a base. By doing so, a considerable amount of conversion time can be saved, i.e., the cluster-based multi-processes program can reduce the conversion time from 81,536 seconds to 4,937 seconds for 4.34 GB source data files. Moreover, the size of result file recording DNA sequences is 54.51 GB for parallel C program compared with 57.89 GB for sequential Perl. This shows that our parallel method can also reduce the DNA synthesis cost. In addition, data types are encoded in our model, which is a basis for building type system in our future DNA computer. Finally, we describe theoretically an algorithm for DNA-based semantic fusion. This algorithm enables the process of integration of the knowledge from disparate remote sensing data sources into a consistent, accurate, and complete representation. This process depends solely on ligation reaction and screening operations instead of the ontology.

On functional module detection in metabolic networks

Functional modules of metabolic networks are essential for understanding the metabolism of an organism as a whole. With the vast amount of experimental data and the construction of complex and large-scale, often genome-wide, models, the computer-aided identification of functional modules becomes more and more important. Since steady states play a key role in biology, many methods have been developed in that context, for example, elementary flux modes, extreme pathways, transition invariants and place invariants. Metabolic networks can be studied also from the point of view of graph theory, and algorithms for graph decomposition have been applied for the identification of functional modules. A prominent and currently intensively discussed field of methods in graph theory addresses the Q-modularity. In this paper, we recall known concepts of module detection based on the steady-state assumption, focusing on transition-invariants (elementary modes) and their computation as minimal solutions of systems of Diophantine equations. We present the Fourier-Motzkin algorithm in detail. Afterwards, we introduce the Q-modularity as an example for a useful non-steady-state method and its application to metabolic networks. To illustrate and discuss the concepts of invariants and Q-modularity, we apply a part of the central carbon metabolism in potato tubers (Solanum tuberosum) as running example. The intention of the paper is to give a compact presentation of known steady-state concepts from a graph-theoretical viewpoint in the context of network decomposition and reduction and to introduce the application of Q-modularity to metabolic Petri net models.