A Novel Bio-Sensor Based on DNA Strand Displacement

DNA strand displacement technology performs well in sensing and programming DNA segments. In this work, we construct DNA molecular systems based on DNA strand displacement performing computation of logic gates. Specifically, a class of so-called “DNA neurons” are achieved, in which a “smart” way inspired by biological neurons encoding information is developed to encode and deliver information using DNA molecules. The “DNA neuron” is bistable, that is, it can sense DNA molecules as input signals, and release “negative” or “positive” signals DNA molecules. We design intelligent DNA molecular systems that are constructed by cascading some particularly organized “DNA neurons”, which could perform logic computation, including AND, OR, XOR logic gates, automatically. Both simulation results using visual DSD (DNA strand displacement) software and experimental results are obtained, which shows that the proposed systems can detect DNA signals with high sensitivity and accretion; moreover, the systems can process input signals automatically with complex nonlinear logic. The method proposed in this work may provide a new way to construct a sensitive molecular signal detection system with neurons spiking behavior in vitro, and can be used to develop intelligent molecular processing systems in vivo.     

Coherent information structure in complex computation

We have recently presented a framework for the information dynamics of distributed computation that locally identifies the component operations of information storage, transfer, and modification. We have observed that while these component operations exist to some extent in all types of computation, complex computation is distinguished in having coherent structure in its local information dynamics profiles. In this article, we conjecture that coherent information structure is a defining feature of complex computation, particularly in biological systems or artificially evolved computation that solves human-understandable tasks. We present a methodology for studying coherent information structure, consisting of state-space diagrams of the local information dynamics and a measure of structure in these diagrams. The methodology identifies both clear and "hidden" coherent structure in complex computation, most notably reconciling conflicting interpretations of the complexity of the Elementary Cellular Automata rule 22.     

Implementing an OR-NOT (ORN) logic gate with components of the SOS regulatory network of Escherichia coli

Whether biological or electronic, man-engineered computation is based on logic circuits assembled with binary gates that are interconnected to perform Boolean operations. We report here the rewiring of the SOS system of Escherichia in a fashion that makes the output of both the recA and lexA promoters to faithfully follow the pattern of a binary composite OR-NOT gate (ORN) in which the inputs are DNA damage (e.g. nalidixic acid addition) and IPTG as an exogenous signal. Unlike other non-natural gates whose implementation requires changes in genes and promoters of the genome of the host cells, this ORN was brought about by the sole addition of wild-type bacteria with a plasmid encoding a module for LacI(q)-dependent expression of lexA. Specifically, we demonstrate that the interplay between native, chromosomally-encoded components of the SOS system and the extra parts engineered in such a plasmid made the desired performance to happen without any modification of the core DNA-damage response network. It is thus possible to artificially interface autonomous cell networks with a predetermined logic by means of Boolean gates built with regulatory elements already functioning in the recipient organism.     

Comparing machine-independent versus machine-specific parallelization of a software platform for biological sequence comparison

A platform program that performs biological sequence comparisonprovides a case study to compare the relative advantages ofa machine–independent approach to parallel computationversus a machine-specific approach. The program consists oftwo routines: (i) PSCANLIB, which compares a single biologicalsequence against a database of sequences, and (ii) PCOMPLJB,which compares a database of sequences against another databaseof sequences, or against itself. The program was first parallelizedto run on the Intel Hypercube parallel computer using nativeHypercube commands to coordinate the parallel computation. Theparallelization logic of the program was then translated intoa machine–independent parallel programming language, Linda.Tliese two approaches to parallelization are contrasted in termsof: (i) the expressive power of the logic that coordinates theparallel computation, (ii) the portability of the machine–independentversion to other parallel machines and (Hi) the relative efficiencyof the two versions of the program. In the benchmark tests reported,the benefits of the machine–independent approach wereachieved with only a modest sacrifice in efficiency.     

Towards computing with proteins

Can proteins be used as computational devices to address difficult computational problems? In recent years there has been much interest in biological computing, that is, building a general purpose computer from biological molecules. Most of the current efforts are based on DNA because of its ability to self‐hybridize. The exquisite selectivity and specificity of complex protein‐based networks motivated us to suggest that similar principles can be used to devise biological systems that will be able to directly implement any logical circuit as a parallel asynchronous computation. Such devices, powered by ATP molecules, would be able to perform, for medical applications, digital computation with natural interface to biological input conditions. We discuss how to design protein molecules that would serve as the basic computational element by functioning as a NAND logical gate, utilizing DNA tags for recognition, and phosphorylation and exonuclease reactions for information processing. A solution of these elements could carry out effective computation. Finally, the model and its robustness to errors were tested in a computer simulation. Proteins 2006. © 2006 Wiley‐Liss, Inc.     

Genetic algorithms and parallel processing in maximum-likelihood phylogeny inference

We investigated the usefulness of a parallel genetic algorithm for phylogenetic inference under the maximum-likelihood (ML) optimality criterion. Parallelization was accomplished by assigning each "individual" in the genetic algorithm "population" to a separate processor so that the number of processors used was equal to the size of the evolving population (plus one additional processor for the control of operations). The genetic algorithm incorporated branch-length and topological mutation, recombination, selection on the ML score, and (in some cases) migration and recombination among subpopulations. We tested this parallel genetic algorithm with large (228 taxa) data sets of both empirically observed DNA sequence data (for angiosperms) as well as simulated DNA sequence data. For both observed and simulated data, search-time improvement was nearly linear with respect to the number of processors, so the parallelization strategy appears to be highly effective at improving computation time for large phylogenetic problems using the genetic algorithm. We also explored various ways of optimizing and tuning the parameters of the genetic algorithm. Under the conditions of our analyses, we did not find the best-known solution using the genetic algorithm approach before terminating each run. We discuss some possible limitations of the current implementation of this genetic algorithm as well as of avenues for its future improvement.     

Modular implementation of dynamic algorithm switching in parallel simulations

We present a modular approach to implementing dynamic algorithm switching for parallel scientific software. By using a compositional framework based on function call interception techniques, our proposed method transparently integrates algorithm switching code with a given program without directly modifying the original code structure. Through fine-grained control of algorithmic behavior of an application at the level of functions, our approach supports design and implementation of application-specific switching scenarios in a modular way. Our approach encourages algorithm switching to dynamically perform at the loop end of a parallel simulation, where cooperating processes in concurrent execution typically synchronize and intermediate computation results are consistent. In this way, newly added switching operations do not cause race conditions that may produce unreliable computation results in parallel simulations. By applying our method to a real-world scientific application and adapting its algorithmic behavior to the properties of input problems, we demonstrate the applicability and effectiveness of our approach to constructing efficient parallel simulations.     

A sticker-based model for DNA computation.

We introduce a new model of molecular computation that we call the sticker model. Like many previous proposals it makes use of DNA strands as the physical substrate in which information is represented and of separation by hybridization as a central mechanism. However, unlike previous models, the stickers model has a random access memory that requires no strand extension and uses no enzymes; also (at least in theory), its materials are reusable. The paper describes computation under the stickers model and discusses possible means for physically implementing each operation. Finally, we go on to propose a specific machine architecture for implementing the stickers model as a microprocessor-controlled parallel robotic workstation. In the course of this development a number of previous general concerns about molecular computation (Smith, 1996; Hartmanis, 1995; Linial et al., 1995) are addressed. First, it is clear that general-purpose algorithms can be implemented by DNA-based computers, potentially solving a wide class of search problems. Second, we find that there are challenging problems, for which only modest volumes of DNA should suffice. Third, we demonstrate that the formation and breaking of covalent bonds is not intrinsic to DNA-based computation. Fourth, we show that a single essential biotechnology, sequence-specific separation, suffices for constructing a general-purpose molecular computer. Concerns about errors in this separation operation and means to reduce them are addressed elsewhere (Karp et al., 1995; Roweis and Winfree, 1999). Despite these encouraging theoretical advances, we emphasize that substantial engineering challenges remain at almost all stages and that the ultimate success or failure of DNA computing will certainly depend on whether these challenges can be met in laboratory investigations.     

DNA implementation of addition in which the input strands are separate from the operator strands

A DNA representation of Boolean logic for which the input strands are separate from the operator strands is described and used to construct a two-bit DNA adder. The successful operation of the adder for several test inputs demonstrates that digital molecular computation with a complexity of order 30 gates is feasible.     

On the reduction of errors in DNA computation.

In this paper, we discuss techniques for reducing errors in DNA computation. We investigate several methods for achieving acceptable overall error rates for a computation using basic operations that are error prone. We analyze a single essential biotechnology, sequence-specific separation, and show that separation errors theoretically can be reduced to tolerable levels by invoking a tradeoff between time, space, and error rates at the level of algorithm design. These tradeoffs do not depend upon improvement of the underlying biotechnology which implements the separation step. We outline several specific ways in which error reduction can be done and present numerical calculations of their performance.     

Optimizing MPI collective communication by orthogonal structures

MPI collective communication operations to distribute or gather data are used for many parallel applications from scientific computing, but they may lead to scalability problems since their execution times increase with the number of participating processors. In this article, we show how the execution time of collective communication operations can be improved significantly by an internal restructuring based on orthogonal processor structures with two or more levels. The execution time of operations like MPI_Bcast() or MPI_Allgather() can be reduced by 40% and 70% on a dual Xeon cluster and a Beowulf cluster with single-processor nodes. But also on a Cray T3E a significant performance improvement can be obtained by a careful selection of the processor structure. The use of these optimized communication operations can reduce the execution time of data parallel implementations of complex application programs significantly without requiring any other change of the computation and communication structure. We present runtime functions for the modeling of two-phase realizations and verify that these runtime functions can predict the execution time both for communication operations in isolation and in the context of application programs.     

DNA计算机的研究和展望

DNA计算机是计算机科学和分子生物学互相结合、互相渗透而产生的新兴交叉研究领域.目前已取得较大进展.DNA计算机是以编码的DNA序列为运算对象,通过分子生物学的运算操作以解决复杂的数学难题.DNA计算机的重要特点是信息容量的巨量性和密集性,和处理操作的高度并行性,通过强力搜索策略迅速得出正确的答案,从而使其运算速度大大超过常规计算机的计算速度.介绍了DNA计算机的近期进展和工作原理及其分子生物学的运算操作过程.并对DNA计算机的未来发展前景及在生物信息学中的意义,进行了分析和讨论.     

Fluorescence for biological logic gates

Biological logic gates are smart probes able to respond to biological conditions in behaviors similar to computer logic gates, and they pose a promising challenge for modern medicine. Researchers are creating many kinds of smart nanostructures that can respond to various biological parameters such as pH, ion presence, and enzyme activity. Each of these conditions alone might be interesting in a biological sense, but their interactions are what define specific disease conditions. Researchers over the past few decades have developed a plethora of stimuli‐responsive nanodevices, from activatable fluorescent probes to DNA origami nanomachines, many explicitly defining logic operations. Whereas many smart configurations have been explored, in this review we focus on logic operations actuated through fluorescent signals. We discuss the applicability of fluorescence as a means of logic gate implementation, and consider the use of both fluorescence intensity as well as fluorescence lifetime.     

Ultrasensitive DNA detection by cycle isothermal amplification based on nicking endonuclease and its application to logic gates

In recent years, an intense interest has grown in the DNA logic gates having high potential for computation at literally the “nano-size” level. A limitation of traditional DNA logic gates is that each target strand hybridizes with only a single copy of the probe. This 1:1 hybridization radio limits the gain of the approach and thus its sensitivity. The exponential amplification of nucleic acids has become a core technology in medical diagnostics and has been widely used for the construction of DNA sensor, DNA nanomachine and DNA sequencing. It would be of great interest to develop DNA-based logic systems with exponential amplification for the output signal. In the present study, a series of three-input DNA logic gates with the cycle isothermal amplification based on nicking endonuclease (NEase) are designed. Very low concentrations of the analytes were sufficient to initiate an autocatalytic cascade, achieving a significant improvement of the detection limit, 100-fold improvement compared to the non-autocatalytic system. This was achieved by engineering a simple and flexible biological circuit designed to initiate a cascade of events to detect and amplify a specific DNA sequence. This procedure has the potential to greatly simplify the logic operation because amplification can be performed in “one-pot”.     

A genetic code Boolean structure. II. The genetic information system as a Boolean information system

A Boolean structure of the genetic code where Boolean deductions have biological and physicochemical meanings was discussed in a previous paper. Now, from these Boolean deductions we propose to define the value of amino acid information in order to consider the genetic information system as a communication system and to introduce the semantic content of information ignored by the conventional information theory. In this proposal, the value of amino acid information is proportional to the molecular weight of amino acids with a proportional constant of about 1.96×10²⁵ bits per kg. In addition to this, for the experimental estimations of the minimum energy dissipation in genetic logic operations, we present two postulates: (1) the energy E _i (i = 1, 2, ..., 20) of amino acids in the messages conveyed by proteins is proportional to the value of information, and (2) amino acids are distributed according to their energy E _i so the amino acid population in proteins follows a Boltzmann distribution. Specifically, in the genetic message carried by the DNA from the genomes of living organisms, we found that the minimum energy dissipation in genetic logic operations was close to kTLn(2) joules per bit.     

Computation emerges from adaptive synchronization of networking neurons

The activity of networking neurons is largely characterized by the alternation of synchronous and asynchronous spiking sequences. One of the most relevant challenges that scientists are facing today is, then, relating that evidence with the fundamental mechanisms through which the brain computes and processes information, as well as with the arousal (or progress) of a number of neurological illnesses. In other words, the problem is how to associate an organized dynamics of interacting neural assemblies to a computational task. Here we show that computation can be seen as a feature emerging from the collective dynamics of an ensemble of networking neurons, which interact by means of adaptive dynamical connections. Namely, by associating logical states to synchronous neuron's dynamics, we show how the usual Boolean logics can be fully recovered, and a universal Turing machine can be constructed. Furthermore, we show that, besides the static binary gates, a wider class of logical operations can be efficiently constructed as the fundamental computational elements interact within an adaptive network, each operation being represented by a specific motif. Our approach qualitatively differs from the past attempts to encode information and compute with complex systems, where computation was instead the consequence of the application of control loops enforcing a desired state into the specific system's dynamics. Being the result of an emergent process, the computation mechanism here described is not limited to a binary Boolean logic, but it can involve a much larger number of states. As such, our results can enlighten new concepts for the understanding of the real computing processes taking place in the brain.     

The bounded complexity of DNA computing

This paper proposes a new approach to analyzing DNA-based algorithms in molecular computation. Such protocols are characterized abstractly by: encoding, tube operations and extraction. Implementation of these approaches involves encoding in a multiset of molecules that are assembled in a tube having a number of physical attributes. The physico-chemical state of a tube can be changed by a prescribed number of elementary operations. Based on realistic definitions of these elementary operations, we define complexity of a DNA-based algorithm using the physico-chemical property of each operation. We show that new algorithms for Hamiltonian path are about twice as efficient as Adleman's original one and that a recent algorithm for Max-Clique provides a similar increase in efficiency. Consequences of this approach to tube complexity and DNA computing are discussed.     

Demonstration of a universal surface DNA computer

A fundamental concept in computer science is that of the universal Turing machine, which is an abstract definition of a general purpose computer. A general purpose (universal) computer is defined as one which can compute anything that is computable. It has been shown that any computer which is able to simulate Boolean logic circuits of any complexity is such a general purpose computer. The field of DNA computing was founded in 1994 by Adleman's solution of a 7-bit instance of the Hamiltonian path problem. This work, as well as most of the subsequent experimental and theoretical investigations in the area, focused primarily upon the solution of NP-complete problems, which are a subset of the larger universal class of problems. In the present work a surface DNA computer capable of simulating Boolean logic circuits is demonstrated. This was done by constructing NOR and OR gates and combining them into a simple logic circuit. The NOR gate is one of the universal gates in Boolean logic, meaning that any other logic gate can be built from it alone. The circuit was solved using DNA-based operations, demonstrating the universal nature of this surface DNA computing model.