Search

In the decade since the first molecular computation was performed, it has been shown that DNA molecules can perform sophisticated, massively parallel computations avoiding the Von Neumann bottleneck. However, progress in the field has been slow. The largest problem solved to date is an instance of the 20-variable 3-CNF SAT problem. Performing the computation took more than two man-weeks to complete because every aspect of the computation was performed by hand. Molecular computations are extremely labor intensive and error prone-automation is necessary for further progress. The next step, (the second generation DNA computer - that of taking the laborious, laboratory bench protocols performed by hand, and automating them), has been achieved with the construction of an automated DNA computer dubbed EDNAC. It employs the same paradigm that was used to solve the labor-intensive instance of the 20-variable 3-CNF SAT problem. Using a combinatorial DNA library and complementary probes, EDNAC solves instances of the n-variable 3-CNF SAT problem. A 10 variable instance of the 3-CNF SAT problem was essayed. The computation took 28 hours to perform. EDNAC correctly computed nine of the ten variables, with a tenth variable remaining ambiguous. This result is comparable to current results in the molecular computation community. This research tested the critical properties, such as complexity, robustness, reliability, and repeatability necessary for the successful automation of a molecular computer. [ABSTRACT FROM AUTHOR]

The address space in DNA memory can be extended by combining information of spatial position and base sequences. Controlling the states of DNA in a local area is an essential technique to use positional information. In this paper, we focus on a photonic DNA memory, which uses optical techniques for addressing on the basis of positional information. We present the concept of photonic DNA memory and describe the read out method using local area manipulation of DNA molecules. [ABSTRACT FROM AUTHOR]

A new readout approach for the Hamiltonian Path Problem (HPP) in DNA computing based on the real-time polymerase chain reaction (PCR) is investigated. Several types of fluorescent probes and detection mechanisms are currently employed in real-time PCR, including SYBR Green, molecular beacons, and hybridization probes. In this study, real-time amplification performed using the TaqMan probes is adopted, as the TaqMan detection mechanism can be exploited for the design and development of the proposed readout approach. Double-stranded DNA molecules of length 120 base-pairs are selected as the input molecules, which represent the solving path for an HPP instance. These input molecules are prepared via the self-assembly of 20-mer and 30-mer single-stranded DNAs, by parallel overlap assembly. The proposed readout approach consists of two steps: real-time amplification in vitro using TaqMan-based real-time PCR, followed by information processing in silico to assess the results of real-time amplification, which in turn, enables extraction of the Hamiltonian path. The performance of the proposed approach is compared with that of conventional graduated PCR. Experimental results establish the superior performance of the proposed approach, relative to graduated PCR, in terms of implementation time. [ABSTRACT FROM AUTHOR]

Due to the multi-state nature of autonomous computing systems, it is important to develop a simulation model which accounts for process coupling, and allows the precise prediction of the behavior of a composite system formed by a series of competing reactions, in which each intermediate step is difficult to probe. In this work, the statistical thermodynamic apparatus for predicting the efficiency of DNA hairpin-based computers is validated experimentally. The model system employed is a simple competitive folding system, formed by two competing hairpin structures (sub-optimal vs. optimal), with the intent of testing the ability to predict the efficiency of target structure formation in the presence of a non-target structure. System behavior was characterized via a set of fluorescence measurement experiments, to directly determine the fractional occupancy of target structures versus temperature. Predicted and experimental behaviors are compared for both the melting of each of the two isolated hairpin structures (control), and the efficiency of the competitive composite system. Results indicate that the applied equilibrium model provides predictions which consistently agree with experimental results, supporting design for the control and programming of DNA-based systems. [ABSTRACT FROM AUTHOR]

An enormous amount of data such as genomic data can be stored into DNA molecules as base sequences. DNA database is important for organizing and maintaining these data, because extracted data from DNA database can be directly manipulated by chemical reactions. In this paper, we develop a DNA relational database with a simple data model and realize a computational model (relational algebra) of data manipulation as a sequence of chemical experiments. By using the developed database, it is shown that we can execute query operations based on the contents of data (the values of attributes). Furthermore, we propose a conversion scheme of query input to a series of experiment operations. [ABSTRACT FROM AUTHOR]

The MethyLogic method performs flexible and reversible modification of DNA in order to establish the logical value of true or false for a set of clauses. It combines both the biological meaning and experimental procedure with the logical implementation of the basic Boolean operators: OR, AND, and NOT. The original feature of methylation logic, MethyLogic, is the use of the reversibility of DNA methylation of cytosine and adenine. Logic variables can be negated by reversing the DNA methylation status. We introduce four implementation scenarios: three of them use methyl-sensitive restriction enzymes and the fourth uses methyl-binding proteins. Encoding can use either single or double-stranded DNA. In addition, we show how to solve a three variable SAT problem and how to implement a logic circuit. [ABSTRACT FROM AUTHOR]

Whiplash PCR-based methods of biomolecular computation (BMC), while highly-versatile in principle, are well-known to suffer from a simple but serious form of self-poisoning known as back-hybridization. In this work, an optimally re-engineered WPCR-based architecture, Displacement Whiplash PCR (DWPCR) is proposed and experimentally validated. DWPCR's new rule protect biostep, which is based on the primer-targeted strand-displacement of back-hybridized hairpins, renders the most recently implemented rule-block of each strand unavailable, abolishing back-hybridization after each round of extension. In addition to attaining a near-ideal efficiency, DWPCR's ability to support isothermal operation at physiological temperatures eliminates the need for thermal cycling, and opens the door for potential biological applications. DWPCR should also be capable of supporting programmable exon shuffling, allowing XWPCR, a proposed method for programmable protein evolution, to more closely imitate natural evolving systems. DWPCR is expected to realize a highly-efficient, versatile platform for routine and efficient massively parallel BMC. [ABSTRACT FROM AUTHOR]

DNA machines consisting of consecutive hairpins, which we have previously described, have various potential applications in DNA computation. In the present study, a 288-base DNA machine containing four consecutive hairpins was successfully constructed by ligation and PCR. PAGE and fluorescence spectroscopy experiments verified that all four hairpins were successfully opened by four opener oligomers, and that hairpin opening was dependent on the proper openers added in the correct order. Quantitative analysis of the final results by fluorescence spectroscopy indicated that all four hairpins were open in about 1/4 to 1/3 of the DNA machines. [ABSTRACT FROM AUTHOR]

Memory is a fundamental challenge in computing, particularly if they are to store large amounts of interrelated data based on content and be queried associatively to retrieve information useful to the owners of the storage, such as self-assembled DNA structures, cells, and biological organisms. New methods to encode large data sets compactly on DNA chips have been recently proposed in (Garzon & Deaton, 2004) [6]. The method consists of shredding the data into short oligonucleotides and pouring it over a DNA chip with spots populated by copies of a basis set of noncrosshybridizing strands. In this paper, we probe into the capacity of these memories in terms of their ability to discern semantic relationships and discriminate information in complex contexts in two applications, as opposed to their raw capacity to store volumes of uncorrelated data. First, we show that DNA memories can be designed to store information about English texts so that they can "conduct a conversation" about their content with an interlocutor who wants to learn about the subject contained in the memories. In this preliminary approach, the results are competitive, if not better, with state-of-the-art methods in conventional artificial intelligence. In a second application in biology, we show how a biomolecular computing analysis based on similar techniques can be used to re-design DNA microarrays in order to increase their sensitivity to the level required for successful discrimination of conditions that may escape detection by standard methods. Finally, we briefly discuss the scalability of the common technique to large amounts of data given recent advances in the design of noncrosshybridizing DNA oligo sets, as well other applications in bioinformatics and medical diagnosis. Keywords: Semantic analysis and information retrieval; DNA chips and microarrays; question answering; sensitivy analysis; data classification and discrimination. [ABSTRACT FROM AUTHOR]

Microfluidic devices are emerging as an attractive technology for automatically orchestrating the reactions needed in a biological computer. Thousands of microfluidic primitives have already been integrated on a single chip, and recent trends indicate that the hardware complexity is increasing at rates comparable to Moore's Law. As in the case of silicon, it will be critical to develop abstraction layers—such as programming languages and Instruction Set Architectures (ISAs)—that decouple software development from changes in the underlying device technology. Towards this end, this paper presents BioStream, a portable language for describing biology protocols, and the Fluidic ISA, a stable interface for microfluidic chip designers. A novel algorithm translates microfluidic mixing operations from the BioStream layer to the Fluidic ISA. To demonstrate the benefits of these abstraction layers, we build two microfluidic chips that can both execute BioStream code despite significant differences at the device level. We consider this to be an important step towards building scalable biological computers. [ABSTRACT FROM AUTHOR]

There are many forecasting techniques including: exponential smoothing, ARIMA model, GARCH model, neural networks and genetic algorithm, etc. Since financial time series may be influenced by many factors, conventional model based techniques and hard computing methods seem inadequate in the prediction. Those methods, however, have their drawbacks and advantages. In recent years, the innovation and improvement of forecasting techniques have caught more attention, and also provides indispensable information in decision-making process. In this paper, a new forecasting technique, named DNA forecasting, is developed. This may be of use to a nonlinear time series forecasting. The methods combined the mathematical, computational, and biological sciences. In the empirical study, we demonstrated a novel approach to forecast the exchange rates through DNA. The mean absolute forecasting accuracy method is defined and used in evaluating the performance of linguistic forecasting. The comparison with ARIMA model is also illustrated. [ABSTRACT FROM AUTHOR]

Content-addressability is a fundamental feature of human memory underlying many associative information retrieval tasks. In contrast to location-based memory devices, content-addressable memories require complex interactions between memory elements, which makes conventional computation paradigms difficult. Here we present a molecular computational model of content-addressable information storage and retrieval which makes use of the massive interaction capability of DNA molecules in a reaction chamber. This model is based on the "hypernetwork" architecture which is an undirected hypergraph of weighted edges. We describe the theoretical basis of the hypernetwork model of associative memory and its realization in DNA-based computing. A molecular algorithm is derived for automatic storage of data into the hypernetwork, and its performance is examined on an image data set. In particular, we study the effect of the hyperedge cardinality and error tolerance on the associative recall performance. Our simulation results demonstrate that short DNA strands in a vast number can be effective in some pattern information processing tasks whose implementation is within reach of current DNA nanotechnology. [ABSTRACT FROM AUTHOR]

Simulations are needed to predict various parameters for chemical reactions and error propagation in microfluidic networks. This paper studies the impact of the order of microreactors implementing a fluidic network on the error in solutions for Boolean expressions. Additionally, we present a computer program that augments the software toolkit introduced in our previous work. The program is useful for simulating microfluidics; we present an example from DNA computing. It monitors the concentration of every molecule throughout the fluidic network and assists in predicting how the layout of the network contributes to the error in the DNA computation. [ABSTRACT FROM AUTHOR]

Predicting the behavior of DNA molecules in vitro is one of the most fundamental issues on DNA computing, but is also known to be quite difficult. Shiozaki et al. proposed a probabilistic model that can simulate many features of biochemical experiments in terms of the reaction rate [7], although there are several differences between the biochemical experiments and the computational simulations on the model. In this paper, we extend the model to support base pairs construction among k DNA sequences, which plays an essential role in realizing branch migrations. The simulation results have much more similarities to the biochemical experiments results than ones on the previous model, which implies that the analysis of the model may give some insight about the reaction rate. Through the analysis, we conclude this paper by giving a guideline for designing DNA sequences that can quickly react. [ABSTRACT FROM AUTHOR]

We developed a computer-software with graphic interfaces for generating de novo DNA sequences of various DNA motifs for DNA nanotechnology research. The software is free of charge for academic and non-profit organizations. [ABSTRACT FROM AUTHOR]

Understanding the structure of viruses is an important first step in terms of many applications in virology, including the protein engineering of containers to enable more effective drug delivery. In particular, the viral capsids, i.e. the protective shells on the exterior of viruses containing the important genetic code, play an important role in the context of gene therapy, where small amounts of therapeutic DNA is packaged into a capsid which then penetrates the cell membrane and delivers its payload. Cross-linking structures are particular additional covalent bonds that can occur in addition to the already present hydrophobic interactions and hydrogen bonds between the proteins. Their importance lies in the fact that they render the capsid particularly stable. Here we shall introduce a mathematical method to predict possible locations for these additional bonds of cross-linking. We will give examples of failed cases as well as of cases where cross-linking structures are possible. These results serve as a pointer for experimentalists as to which types of cross-linking structures may possibly be engineered and exploited in the framework of drug delivery. [ABSTRACT FROM AUTHOR]

In this paper, we propose a framework for a discrete event simulator for simulating the DNA based nano-robotical systems. We describe a physical model that captures the conformational changes of the solute molecules. We also present methods to simulate various chemical reactions due to the molecular collisions, including hybridization, dehybridization and strand displacement. The feasibility of such a framework is demonstrated by some preliminary results. [ABSTRACT FROM AUTHOR]

Winfree's pioneering work led the foundations in the area of error-reduction in algorithmic self-assembly[26], but the construction resulted in increase of the size of assembly. Reif et. al. contributed further in this area with compact error-resilient schemes [15] that maintained the original size of the assemblies, but required certain restrictions on the Boolean functions to be used in the algorithmic self-assembly. It is a critical challenge to improve these compact error resilient schemes to incorporate arbitrary Boolean functions, and to determine how far these prior results can be extended under different degrees of restrictions on the Boolean functions. In this work we present a considerably more complete theory of compact error-resilient schemes for algorithmic self-assembly in two and three dimensions. First we consider two-dimensional algorithmic self-assembly. We present an error correction scheme for reduction of errors from ε to ε2 for arbitrary Boolean functions in two dimensional algorithmic self-assembly. Then we characterize the class of Boolean functions for which the error reduction can be done from ε to ε3, and present an error correction scheme that achieves this reduction. Then we prove ultimate limits on certain classes of compact error resilient schemes: in particular we show that they can not provide reduction of errors from ε to ε4 is for any Boolean functions. Further, we develop the first provable compact error resilience schemes for three dimensional tiling self-assemblies. We also extend the work of Winfree on self-healing in two-dimensional self-assembly[25] to obtain a self-healing tile-set for three-dimensional self-assembly. [ABSTRACT FROM AUTHOR]

We study the times to grow structures within the tile self-assembly model proposed by Winfree, and the possible shapes that can be achieved during the self-assembly. Our earlier work was confined to the growth of rectangular structures, in which the border tiles are prefabricated. By varying the relative rates between the border-tile and rule-tile attachment, one can engineer interesting new shapes, which have been observed in the laboratory. We show that the results from an extension of our earlier stochastic models agree remarkably closely with experimental results. This is an important further demonstration of the validity and usefulness of our stochastic models, which have also been used successfully in studies of error correction in DNA self assembly. [ABSTRACT FROM AUTHOR]