Priority Encoder Based on DNA Strand Displacement

I.   Introduction

Non-traditional computers are a booming field of research, and bio-computers have developed rapidly in recent years. In 1994, Dr. Adleman of the University of Southern California pioneered the usage of DNA to solve computing problems [1]. The research solved a classic combinatorial optimization problem, the Hamiltonian path problem, and opened a new chapter for DNA molecular computing. DNA computing completes operations by controlling biochemical reactions between DNA molecules, and uses the unique properties of biological components such as DNA, RNA, and enzymes to perform information encoding, storage, and calculation operations [2]–[5]. Compared with traditional computers, bio-computers have the characteristics of strong parallel processing capability, fast calculation speed, and low energy consumption. Therefore, they have received widespread attention from scientists. In more than 20 years of development, a number of remarkable results have been achieved [6]–[10].

DNA strand displacement technology, one of the foundations of DNA molecular calculation [11], is widely used due to its advantages of strong operability and predictable products. A critical feature of DNA strand displacement technology is the scalability [12]. The output of one reaction can be used as the input of the next reaction, so that a large-scale chemical reaction network can be realized.

The realization of various molecular gate circuits based on molecular logic computing units is an important application scenario of DNA strand displacement technology [13]–[15]. The scalability reduced the complexity of circuit design and provided the possibility to realize large-scale circuits with various complex functions. Many researchers have proposed different models of molecular logic gate structures. Seelig et al. designed various digital logic circuits for the first time using DNA strand displacement [16]. Frezza et al. used DNA strand displacement technology and fluorescence labelling technology to construct AND, OR, and NOR gates, and on this basis, implemented XOR logic through cascading multiple logic gates [17]. Zhang et al. implemented the YES gate, AND gate, and OR gate with single-chain input and output [18]. Qian et al. proposed the “seesaw” gate structure based on a toehold exchange mechanism and implemented different logic gate operations, and used these logic gates for complex circuits of large-scale DNA logic gate cascades opening up the research of complex DNA molecular logic circuits [19].

DNA strand displacement technology has great development potential and application prospects in many fields. However, nowadays, most of the circuits that use DNA strand displacement technology to implement logical negation require the use of two-track notation, which causes the number of DNA strands to increase exponentially. In this study, a single-track molecular NAND gate was designed based on a step function molecular logic gate, and the correctness of the NAND gate was successfully verified in experiments. Furthermore, a 4-wire-2-wire priority encoder based on DNA molecules was realized by cascading multiple molecular NAND gates. The feasibility and accuracy of the proposed priority encoder are simulated and verified using Visual DSD software [20]. The simulation experimental results provide a basis for explorations of the realization of the logic coding function of information based on the cascading of complex DNA molecular circuit.

II.   Priority Encoder Logic Circuit

A logic circuit uses binary numbers 0 and 1 to represent high and low levels for the transmission and processing of discrete signals. Encoding is the process of compiling a specific logic signal into a set of binary codes. The logic circuit that can realize an encoding function is called an encoder. The priority encoder works on producing output according to the priority of the input signal. The input signal with the highest priority will be output, and any signals with lower priority will be ignored, which often used to control interrupt requests when processing the highest priority requests. This work designed a 4-input 2-output molecule priority encoder, and the truth table is shown in Table 1.

Table  1.  Truth table of 4-wire-2-wire priority encoder

$A$	$B$	$C$	$D$	$L_0$	$L_1$
1	$X$	$X$	$X$	1	1
0	1	$X$	$X$	1	0
0	0	1	$X$	0	1
0	0	0	$X$	0	0

 | Show Table

DownLoad: CSV

Assuming that the priority order of the input signals is $A$, $B$, $C$, and $D$. When the circuit has simultaneous input signals, the output is a high-priority code: 1 means high level, 0 means low level, and $X$ means any level. Use $L_0$$L_1$ to represent the output signal. $L_0$$L_1 = 00$ means either no input or input signal $D$, $L_0$$L_1 = 01$ means $C$ input, $L_0$$L_1 = 10$ means $B$ input, and $L_0 L_1 = 11$ means $A$ input. Its expression is:

As shown in Figure 1, a 4-wire-2-wire priority encoder logic circuit is designed according to (1) and (2), in which $A$, $B$, $C$, and $D$ represent the input signal, and $L_0$ and $L_1$ represent the output signal.

Figure  1.  4-wire-2-wire priority encoder logic circuit.

DownLoad: Full-Size Img PowerPoint

III.   Priority Encoder Molecular Logic Model

1   DNA strand displacement

DNA strand displacement technology occupies an important position in bio-molecular computing. DNA strand displacement involves a branch migration and strand displacement reaction based on toehold adjustment. Following the rules of fulcrum isolation and fulcrum exchange proposed by Yurke et al. [21], [22], through the reaction between the DNA single strand and partially complementary double strand, a single strand in the original double strand is replaced, thereby forming a new DNA double-strand chain. It is a spontaneous dynamic reaction process. The reaction process is shown in Figure 2.

Figure  2.  Schematic diagram of the principle of DNA strand displacement.

DownLoad: Full-Size Img PowerPoint

The directed line segment represents the DNA strand, 1, 2, and 3 represent domains with different sequences on the DNA strand, domain 2 and domain 2* represent complementary DNA sequences, and domain 2 only reacts with its complementary domain 2*. The double-stranded $X$ was present in the solution before the start of the reaction, and the branch domain 3* of $X$ was exposed. When the single-chain $A$ input is input, the single-chain branch domain 3 and the double-chain branch domain 3* are combined, and the reaction starts. According to the fulcrum isolation and fulcrum exchange rules, the domain 2 of the input chain $A$ migrates towards the upper domain 2 of the double-strand $X$. After the migration, the DNA sequence 1, 2 on the double-strand $X$ is replaced, and the final DNA sequence 1, 2 forms the output chain $B$, the remaining part of the input chain $A$ and the double-strand $X$ form a double-strand $Y$, and the reaction ends.

2   Molecular NAND gate design

In the design of the molecular NAND gate, Mulawka et al. [23] proposed a method to realize the NAND gate through the restriction nuclease FokI. The main drawback of this method is that the logic gate will be destroyed at the end of the calculation process. Ruiz-Perez et al. [24] proposed a logic system based on the gate of DNAzyme, but the implementation process of this method is complicated, and whether it can be applied in large-scale circuits remains to be verified. And based on the NAND gate of the seesaw gate, dual-track logic is generally used to distinguish the input signals. The dual-rail logic means that instead of using a single signal chain to represent logic 1 and logic 0, a pair of signal chains are used to represent logic 1 and logic 0 respectively. Each logic gate is composed of a pair of AND gates and OR gates, which greatly increases the number of logic gates. We designed a NAND gate based on a high-sensitivity precise DNA strand displacement logic gate proposed by Chen et al. [25]. The input signal of the NAND gate is a low signal when the signal chain concentration is about 0.1 nM, and a high signal when the signal chain concentration is about 0.9 nM. It can directly form NAND gate logic, and successfully construct a 4-wire-2-wire priority encoder by cascading the NAND gate. The NAND gate structure is shown in Figure 3.

Figure  3.  Molecular NAND logic structure.

DownLoad: Full-Size Img PowerPoint

The process of implementing the molecular reaction of NAND gate is shown in Figure 4. The input chain signals $A$ and $B$ first generate signal chains $T_1$ and $T_2$ after single molecule reaction [26]: $A\to T_1 + T_2$ and $B\to T_1 + T_2$. $T_1$ and $T_2$ will pass through two step function gates and then get the output signal $Y$. The step function gate consists of threshold chain, gate chain and fuel chain. A step function gate with a threshold of 0.15 will produce $Y$ of 0.9 nM, and a step function gate with a threshold of 1.5 will produce 0.8 nM $Y'$, this reaction is similar to the reaction that forms $Y$ (Figure 4(a)). If there is no input signal, the values of $A$ and $B$ are 0, then the two step functions will not be generating $Y$ of 0.9 nM, and the output signal $Y$ has a value of 0.9 nM, indicating a high-level signal. If $A$ and $B$ include a low-level signal and a high-level signal, then the values of $T_1$ and $T_2$ are 0.1 nM + 0.9 nM = 1.0 nM. At this concentration, the step function with a threshold value of 0.15 nM will be activated, generating $Y$ of 0.9 nM, so the value of the output signal $Y$ is 0.9 nM, indicating the high-level signal. If both $A$ and $B$ are high-level signals, the values of $T_1$ and $T_2$ are 0.9 nM + 0.9 nM = 1.8 nM. At this concentration, both step functions will be activated. The step function with a threshold value of 1.5 nM produces $Y'$ of 0.8 nM, and the step function with a threshold value of 0.15 produces $Y$ of 0.9 nM. $Y$ and $Y'$ will be annihilated in pairs, as shown in Figure 4(b), and finally only the output chain $Y$ with a concentration of 0.1 nM will be left, indicating a low signal.

Figure  4.  NAND gate molecular circuit. (a) Step gate function; (b) Annihilation reaction.

DownLoad: Full-Size Img PowerPoint

3   Experiment and result analysis

Firstly, we run computer simulations, using Visual DSD software to design and simulate DNA strand displacement experiments. This experiment used the default sequence provided by the software, in which the base length of the fulcrum domain is 6, base length of the non-branch domain is 20, normal phase binding rate of the fulcrum is 0.003 nM⁻¹s⁻¹, and reverse binding rate is 1.3 s⁻¹. As shown in Figure 5(a), input parameters are adjusted respectively, and it can be seen that the simulation results meet the expected logic.

Figure  5.  Experimental results of molecular NAND circuit. (a) Computer simulation results under different input combinations; (b) Molecular NAND circuit fluorescence readout results under different inputs; (c) Results of agarose gel electrophoresis imaging under UV light.

DownLoad: Full-Size Img PowerPoint

Then during experiment, mix quenching chain and fluorescent chain in Tris-EDTA buffer with 12.5 mM MgCl₂ at a molar ratio of 1.15:1, each step function gate fuel chain $F_1$ and $F_2$ is 200 nM, annihilation link A concentration is 300 nM, and output gate is 0.9 nM and 0.8 nM. The experiment was performed in Tris-acetate-EDTA buffer containing 12.5 mM Mg²⁺ at 20 ℃. Detect the fluorescence kinetics of each sample well every 20 s, and capture the curve of fluorescence intensity changing with time in about 30 min. The trajectory blank is a baseline, which is a blank control group without input chain but only logic gates added. In order to read the logical result, use the fluorescence intensities of 300000 and 600000 as thresholds. Signals with a fluorescence intensity of 300000 or less are considered to be low by default, and signals with a fluorescence intensity of 600000 or more are considered to be high by default. As shown in Figure 5(b), when the input $A$, $B$ is low signal, the output fluorescence intensity is high signal; when the input $A$, $B$ is high signal and the other is low signal, the output fluorescence intensity is high signal; when the input $A$, $B$ is both high signal, the output fluorescence intensity is low signal, which meets the expected result. As supported by Figure 5(c), the results of 3% agarose gel electrophoresis imaging showed that the visible light band between 100 bp and 250 bp markers proved that $S_2$ was produced, and the annihilation reaction of $Y$ and $Y'$ occurred.

4   Molecular model of the priority encoder

The molecular logic gate model of the 4-wire-2-wire priority encoder, which places the molecular logic circuit diagram within the traditional circuit, is illustrated in Figure 6.

Figure  6.  Molecular logic gate model of 4-wire-2-wire priority encoder.

DownLoad: Full-Size Img PowerPoint

In the model of Figure 6, molecular NAND gates replace NAND gates in a traditional logic circuit. The priority encoder is obtained by cascading multiple molecular NAND gates. The input signal chain is $A$, $B$, $C$, and $D$, and the output signal chain is $L_1$ and $L_0$. The input signal chains $A$ and $B$ undergo a single-molecule reaction to generate two signal chains of the same concentration. The corresponding output signals $\mathrm{YA}$ and $\mathrm{YB}$ are obtained through NAND gate 1 and NAND gate 2, respectively. $\mathrm{YA}$ and $\mathrm{YB}$ generate intermediate chains $\mathrm{YA}_1$, $\mathrm{YA}_2$, $\mathrm{YB}_1$, and $\mathrm{YB}_2$ through a single-molecule reaction.

$\mathrm{YA}_1$ and $\mathrm{YB}_1$ generate the final output signal chain $L_0$ through NAND gate 3. $\mathrm{YB}_2$ and input chain $C$ react with NAND gate 4 to generate intermediate chain $\mathrm{YC}$. The intermediate chain $\mathrm{YC}$ and the intermediate chain $\mathrm{YA}_2$ react with NAND gate 5 to form the final output chain $L_1$. In the logic circuit, although the input signal chain $D$ has no effect on the output result, the input signal chain $D$ is retained to ensure the logic integrity of the molecular circuit. In summary, the input chains $A$, $B$, $C$, and $D$ generate the corresponding output signal chain after passing through multiple NAND gates.

The results of the simulation experiment of the 4-wire-2-wire priority encoder using Visual DSD are shown in Figure 7. The same default sequence as described in Section III was used. 0.1 nM represents the low-level signal, and 0.9 nM represents the high-level signal.

Figure  7.  Simulation results of all input group. (a) Input = 1000; (b) Input = 0100; (c) Input = 0010; (d) Input = 0001.

DownLoad: Full-Size Img PowerPoint

In the graphs of Figure 7, blue curve represents $L_0$ and the yellow one represents $L_1$. Figure 7(a) is the time-varying curve of the concentration of the output signals $L_0$ and $L_1$ when the input signal $ABCD$ is 1000. After the reaction started, the concentration of $L_0$ and $L_1$ increased rapidly and reached a steady state after about 5000 s. The concentration is 0.9 nM, which represented the output signal 11. Figure 7(b) shows the concentration curves of the output signals $L_0$ and $L_1$ when the input signal $ABCD$ is 0100. After the reaction started, the concentration of $L_0$ quickly rose to 0.9 nM and stabilized. The concentration of $L_1$ first increased rapidly, and then due to the existence of annihilation reaction, the concentration began to decrease, and stabilized after 6000 s, the final concentration was 0.1 nM.

Figure 7(c) shows the concentration of the output signals $L_0$ and $L_1$ over time when the input signal $ABCD$ is 0010. The concentration of $L_0$ first increases, then the annihilation reaction occurs, and then begins to decrease, and stabilizes after about 6000 s. The steady-state concentration of $L_0$ is 0.1 nM. The concentration of $L_1$ directly increases to 0.9 nM and stabilizes. The final concentration of $L_1$ and $L_0$ represents the output signal 01. The final outputs signal represents 10. Figure 7(d) shows the time-varying concentration of the output signals $L_0$ and $L_1$ when the input signal $ABCD$ is 0001. After the input chain is input, the concentration of $L_0$ and $L_1$ increases rapidly, and then due to the annihilation reaction, the concentration of $L_0$ and $L_1$ begins to decrease. After about 6000 s, the concentration of $L_0$ and $L_1$ stabilizes at 0.1 nM, which represents the output signal 00. The simulation results show that the output signals in all cases are in line with the expected results, indicating that the molecular model can realize the function of the 4-wire-2-wire priority encoder, proving the feasibility and accuracy of the molecular circuit model, and constructs more complex circuits for the subsequent the structural model is explored.

IV.   Conclusions

In summary, based on the DNA strand displacement reaction, this study constructed a NAND gate molecular logic operation device using DNA molecular step function logic gates. A 4-wire-2-wire DNA molecular priority encoder was constructed by cascading multiple molecular NAND gates that can achieve the cascade reaction between corresponding molecular logic gates to finally realize the function of the priority encoder. The experimental results show the correctness of the monorail molecule NAND gate. The feasibility of the 4-wire-2-wire priority encoder and the accuracy of the molecular reaction were verified by Visual DSD software simulation. Experimental and simulation results show that the molecular priority encoder constructed in this research has the characteristics of simple logic circuit and accurate results. The results of the whole cascade reaction system show that the cascade circuit proposed in this paper has great potential in applying large-scale molecular logic calculation circuits. Since the reaction sequence is controlled by adjusting the concentration of DNA strands. Leakage is possible in this system.

In future research, we will use this logic circuit to build more complex structural models and achieve more powerful functions. The single-track molecular NAND gate and the 4-wire-2-wire priority encoder implemented in this paper have made a useful exploration for the development of logic circuits based on DNA strand displacement.