Logical computation with self-assembling electric circuits.

Inspired by self-assembled biological growth, the Circuit Tile Assembly Model (cTAM) was developed to provide insights into signal propagation, information processing, and computation in bioelectric networks. The cTAM is an abstract model that produces a family of circuits of different sizes that is amenable to exact analysis. Here, the cTAM is extended to the Boolean Circuit Tile Assembly Model (bcTAM) that implements a computationally complete set of Boolean gates through self-assembled and self-controlled growth. The proposed model approximates axonal growth in neural networks and thus, investigates the computational capability of dynamic biological networks, for example, in growing networks of axons. Thus, the bcTAM models the effect of electrical activity on growth and shows how that growth might implement Boolean computations. In this sense, given a set of input voltages, the bcTAM is a system that is able to monitor and make decisions about its own growth.

Systems of axon-like circuits for self-assembled and self-controlled growth of bioelectric networks.

By guiding cell and chemical migration and coupling with genetic mechanisms, bioelectric networks of potentials influence biological pattern formation and are known to have profound effects on growth processes. An abstract model that is amenable to exact analysis has been proposed in the circuit tile assembly model (cTAM) to understand self-assembled and self-controlled growth as an emergent phenomenon that is capable of complex behaviors, like self-replication. In the cTAM, a voltage source represents a finite supply of energy that drives growth until it is unable to overcome randomizing factors in the environment, represented by a threshold. Here, the cTAM is extended to the axon or alternating cTAM model (acTAM) to include a circuit similar to signal propagation in axons, exhibiting time-varying electric signals and a dependence on frequency of the input voltage. The acTAM produces systems of circuits whose electrical properties are coupled to their length as growth proceeds through self-assembly. The exact response is derived for increasingly complex circuit systems as the assembly proceeds. The model exhibits complicated behaviors that elucidate the interactive role of energy, environment, and noise with electric signals in axon-like circuits during biological growth of complex patterns and function.

In vitro molecular machine learning algorithm via symmetric internal loops of DNA.

Programmable biomolecules, such as DNA strands, deoxyribozymes, and restriction enzymes, have been used to solve computational problems, construct large-scale logic circuits, and program simple molecular games. Although studies have shown the potential of molecular computing, the capability of computational learning with DNA molecules, i.e., molecular machine learning, has yet to be experimentally verified. Here, we present a novel molecular learning in vitro model in which symmetric internal loops of double-stranded DNA are exploited to measure the differences between training instances, thus enabling the molecules to learn from small errors. The model was evaluated on a data set of twenty dialogue sentences obtained from the television shows Friends and Prison Break. The wet DNA-computing experiments confirmed that the molecular learning machine was able to generalize the dialogue patterns of each show and successfully identify the show from which the sentences originated. The molecular machine learning model described here opens the way for solving machine learning problems in computer science and biology using in vitro molecular computing with the data encoded in DNA molecules.

Probabilistic Analysis of Pattern Formation in Monotonic Self-Assembly.

Inspired by biological systems, self-assembly aims to construct complex structures. It functions through piece-wise, local interactions among component parts and has the potential to produce novel materials and devices at the nanoscale. Algorithmic self-assembly models the product of self-assembly as the output of some computational process, and attempts to control the process of assembly algorithmically. Though providing fundamental insights, these computational models have yet to fully account for the randomness that is inherent in experimental realizations, which tend to be based on trial and error methods. In order to develop a method of analysis that addresses experimental parameters, such as error and yield, this work focuses on the capability of assembly systems to produce a pre-determined set of target patterns, either accurately or perhaps only approximately. Self-assembly systems that assemble patterns that are similar to the targets in a significant percentage are "strong" assemblers. In addition, assemblers should predominantly produce target patterns, with a small percentage of errors or junk. These definitions approximate notions of yield and purity in chemistry and manufacturing. By combining these definitions, a criterion for efficient assembly is developed that can be used to compare the ability of different assembly systems to produce a given target set. Efficiency is a composite measure of the accuracy and purity of an assembler. Typical examples in algorithmic assembly are assessed in the context of these metrics. In addition to validating the method, they also provide some insight that might be used to guide experimentation. Finally, some general results are established that, for efficient assembly, imply that every target pattern is guaranteed to be assembled with a minimum common positive probability, regardless of its size, and that a trichotomy exists to characterize the global behavior of typical efficient, monotonic self-assembly systems in the literature.

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.

Assessing the detection capacity of microarrays as bio/nanosensing platforms.

Microarray is one of the most powerful detection systems with multiplexing and high throughput capability. It has significant potential as a versatile biosensing platform for environmental monitoring, pathogen detection, medical therapeutics, and drug screening to name a few. To date, however, microarray applications are still limited to preliminary screening of genome-scale transcription profiling or gene ontology analysis. Expanding the utility of microarrays as a detection tool for various biological and biomedical applications requires information about performance such as the limits of detection and quantification, which are considered as an essential information to decide the detection sensitivity of sensing devices. Here we present a calibration design that integrates detection limit theory and linear dynamic range to obtain a performance index of microarray detection platform using oligonucleotide arrays as a model system. Two different types of limits of detection and quantification are proposed by the prediction or tolerance interval for two common cyanine fluorescence dyes, Cy3 and Cy5. Besides oligonucleotide, the proposed method can be generalized to other microarray formats with various biomolecules such as complementary DNA, protein, peptide, carbohydrate, tissue, or other small biomolecules. Also, it can be easily applied to other fluorescence dyes for further dye chemistry improvement.

A DNA assembly model of sentence generation.

Recent results of corpus-based linguistics demonstrate that context-appropriate sentences can be generated by a stochastic constraint satisfaction process. Exploiting the similarity of constraint satisfaction and DNA self-assembly, we explore a DNA assembly model of sentence generation. The words and phrases in a language corpus are encoded as DNA molecules to build a language model of the corpus. Given a seed word, the new sentences are constructed by a parallel DNA assembly process based on the probability distribution of the word and phrase molecules. Here, we present our DNA code word design and report on successful demonstration of their feasibility in wet DNA experiments of a small scale.

Independent sets of DNA oligonucleotides for nanotechnology applications.

Independent sets of DNA oligonucleotides, which only bind with their Watson-Crick complements, have potential use in self-assembly of nanostructures, since they minimize errors and inefficiency from unwanted binding. A software tool implemented a thermodynamic model for DNA duplex formation and was used to generate large independent sets of DNA oligonucleotides. The principle of the approach was experimentally verified on a sample set of oligonucleotides.

Coupled equilibrium model of hybridization error for the DNA microarray and tag-antitag systems.

In this work, a detailed coupled equilibrium model is presented for predicting the ensemble average probability of hybridization error per chip-hybridized input strand, providing the first ensemble average method for estimating postannealing microarray/TAT system error rates. Following a detailed presentation of the model and implementation via the software package NucleicPark, under a mismatched statistical zipper model of duplex formation, error response is simulated for both mean-energy and randomly encoded TAT systems versus temperature and input concentration. Limiting expressions and simulated model behavior indicate the occurrence of a transition in hybridization error response, from a logarithmically convex function of temperature for excess inputs (high-error behavior), to a monotonic, log-linear function of temperature for dilute inputs (low-error behavior), a novel result unpredicted by uncoupled equilibrium models. Model scaling behavior for random encodings is investigated versus system size and strand-length. Application of the model to TAT system design is also undertaken, via the in silico evolution of a high-fidelity 100-strand TAT system, with an error response improved by nine standard deviations over the performance of the mean random encoding.

Estimating the sequence complexity of a random oligonucleotide population by using in vitro thermal melting and Cot analyses.

Randomly generated oligonucleotide populations have a high potential to serve as pools for selecting non-cross-hybridizing sequences, which are useful for nanoscale self-assembly and biological and biomedical applications, as well as for DNA computing applications. In this study a nonlinear kinetic model was developed for the complexity estimation of large unknown polynucleotide populations and was experimentally verified. The model was implemented to estimate the sequence complexity of the random 20 base-pair population after in vitro renaturation experiments. The kinetic behaviors of the random 20mers were also evaluated with in vitro thermal melting experiments. This study represents a step in realizing the potential of random oligonucleotides for DNA computing and nanoscale self-assembly applications for biology and medicine.

Equilibrium analysis of the efficiency of an autonomous molecular computer.

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.