LITMIR.BIZ

Скачать книгу

Nanjing, 211189, China

3.1 From Theory to DNA Implementations

One of the critical challenges of Moore's law is the physical limits of transistor scaling. To this end, alternative non‐silicon substitutes have been researched, among which are quantum computing, spintronic computing, and DNA computing.

      Computing using DNA materials has been studied in the last few decades. Different from traditional silicon‐based computing, DNA computing is inherently massively parallel, molecular scale, and well suited for complex computing. The theoretical analysis of such computing usually builds on an abstraction model of DNA reactions, chemical reaction networks (CRNs) [1–5]. Based on such a model, there are mapping methods that can directly translate programmed CRNs to experimentally implementable DNA reactions [6,7]. Also, to enable the construction of more complex systems, compilers have also been developed [8,9]. Apart from that, some researchers also tried to establish instruction sets based on DNA reactions [10]. Overall, researchers are constructing DNA computing systems in a manner similar to constructing early computers, and more progress in this area can be expected in the near future.

CRNs have been proven a type of effective computation tool for DNA computing [1–5]. Stochastic chemical reaction networks (SCRNs) can well model the interactions among a small number of molecules [11] and are Turing‐universal [1]. The relation between the SCRN model and the conventional concepts in computer science has already been established by [2]. For both time/space bounded and unbounded computations, SCRNs are capable of simulating Turing machines with time complexity under an asymptotic upper bound and error probability under an upper bound hence are Turing‐universal. Figure 3.1 shows the simulation of a register machine as an example [1]. SCRNs are also able to stably compute functions under an asymptotic upper bound of time if and only if the functions have semilinear graphs [3]. Chemical reaction computer, defined as a CRN with initial settings, is thus a powerful computation tool. Regarding the computation correctness issues, an error correction method in the construction of CRN simulation of register machines has been proposed [4]. This validates that Turing‐universal probability 1 computation (the probability of producing a correct answer is 1 as time approaches infinity) can be implemented in CRNs. A more recent work [5] addresses the composability problem in continuous CRNs. A method to construct composable CRNs is proposed to replace the error‐prone direct cascade of different CRNs.

Figure 3.1 The simulation of a register machine. (a) Simulation of bounded register machine. (b) Clock module used to simulate the Turing machine.

      Source: From Soloveichik et al. [1]. Reproduced with the permission of Springer Nature.

With such powerful computing abilities, CRNs have the potential to build complex functional computing systems. However, it is difficult to rely on manual design when building large biocomputing systems; hence there are attempts to build corresponding compilers [8,9]. Like compilers of modern programming languages, these tools can synthesize CRNs based on a higher‐level abstraction of algorithms. Syntax of hardware description language like Verilog HDL may be used [12], where users can utilize the previously defined modules to construct their systems in a manner similar to digital hardware design. There are also attempts to synthesize CRNs from more software‐like descriptions. One critical technique is to map control flows like linear flow, branch statement, and loop statement to CRNs [9]. Another recently proposed tool [8] integrates basic arithmetic operations like additions and subtractions and is able to compile codes written in the high‐level description language called CRN++. There are some simulation results of such synthesized CRNs, showing that CRNs can well perform computation as intended. Besides synthesizing CRNs from manually written codes, by formulating the problem of CRN design (including design of reactions and related parameters) as a satisfiability modulo theory (SMT) problem and solving this problem by existing mathematical toolkits, CRNs that satisfy user specifications can be directly synthesized [13] (Figure 3.2). Apart from CRN compilers, Thubagere et al. [14] targets the compilation of lower‐level DNA reactions. Using DNA sequences generated by the compiler, DNA circuits can be conveniently built. Since the construction of the compiler takes synthesis error into account, the experimental process can also be simplified.

Figure 3.2 State graph with state transition implemented by CRNs.

      Source: Adapted from Murphy et al. [13].

To show the capability of DNA materials to establish computers, many researchers begin with building Turing machines. Apart from the aforementioned simulations of Turing machines in Figure 3.1 [1], there is a universal molecular Turing machine based on site‐directed mutagenesis [15]. Qian et al. employ a “history‐free” method to implement CRNs, based on which the authors implement irreversible and reversible stack machines [16]. Besides the attempts to build Turing machines, some researchers start from the design of DNA strand displacement reactions and propose instruction sets for DNA computers. The work called SIMD||DNA (Single Instruction Multiple Data DNA) [10] leverages the cascade of DNA strand displacement reactions. By introducing a set of binary encoding rules that utilize different arrangements of upper DNA strands of DNA complexes to represent “1” and “0,” data can be stored in DNA “registers” (multistranded complexes). When adding auxiliary single DNA strands that equal to executing instructions, the upper single DNA strands can be attached/displaced/detached from the DNA complexes, hence changing the encoded data stored in DNA “registers.” An example of Rule 110 Automata is shown in Figure 3.3.

Figure 3.3 Implementation of Rule 110 Automata. Two different arrangements of upper single DNA strands within each cell (slices of DNA complex separated by dashed lines) represent “1” and “0,” respectively. When executing an instruction, some specific DNA strands are added to the system to initiate the attachment, detachment, and displacement of upper DNA strands. The combination of such instructions changes the state of related cells, resulting in state transitions of the automata after the execution of all instructions.

      Source: Modified from Wang et al. [10].

With the computing power of CRNs, one critical issue is how to implement such formal reactions in the real world using DNA reactions. Soloveichik et al. propose a DNA reaction substrate in [6], based on which theoretically designed reactions with less than three reactants can be readily mapped to DNA strand displacement reactions. The kinetic features of original formal reactions are approximately retained, as proved by mass action kinetic analysis. For bimolecular reactions, Qian et al. propose a design of DNA strand displacement reactions [16] to map such formal reactions. The model can address both reversible and irreversible formal reactions; unimolecular reactions and reactions with higher orders can be similarly constructed. Experimental work [7], which shows that bimolecular reactions

Скачать книгу