IEEE Circuits and Systems Magazine - Q1 2021 - 29

in the two strands is " 1 " , the ith bit of the DNA strand in
tube Td is set (line 5). Strands are re-combined in tube
Ta in line 7.
Algorithm 2 applies the ADD operation over the nbit operands represented by strands in source tubes
Ts1 and Ts2 , and the sum is deposited into the destination tube Td . Although the addition algorithm is
supported by binary arithmetic, we present it to illustrate how arithmetic is implemented in biological
substrates. The auxiliary tubes Tnc and Tc are used
to register the absence or existence of the carry bit,
respectively. By pouring the contents of tubes Ts1 and
Ts2 into the auxiliary tube Tnc, it is considered that the
initial carry-in is equal to " 0 " (line 1). For the Least Significant Bit (LSB), strands in the Tnc tube (line 3) are
separated according to the value of this bit in tubes
B [1] and B [0] (line 4). If neither B [1] and B [0] are empty,
this means that the LSBs have different values (line 5).
Since carry-in is not considered, the LSB of the DNA
strand in tube Td is set (line 6). No carry-out is generated; thus, both strands are placed back in the Tnc tube
(line 7). On the other hand, if both LSBs take the value 1
((line 9), the sum bit is " 0 " , and we only have to put
both strands in the Tc (line 10) to signal that a carryin exists for the next bit. For the last condition in line 11,
both LSBs are " 0 " , and we only have to return both
strands to Tnc (line 12). The second half of Algorithm 2,
from line 15, is similar to the first but for the case
where a carry-in exists, which means tube Tnc is empty
and tube Tc contains the input strands. All this processing is iteratively repeated from the LSB to the Most
Significant Bit (MSB) (line 2).
Current DNA computational systems are constrained
by their poor integration capability, complex device
structures or limited computational functions. However,
the ability to build efficient DNA logic gates and cascade
circuits based on polymerase-mediated strand displacement synthesis has been shown [112]. The pillars are a
single-rail AND gate built with three strands and a singlerail OR gate built with two strands. Dual-rail DNA logic
Algorithm 1.
AND(Ts1, Ts2, n:in; Td:out).
Require: Pour blank strand of n bits (0f0 ) into Td
Ensure: bit_stream_in_Td =bit_stream_in_Ts1 /bit_stream_in_Ts2
1: Combine(Ta, Ts1, Ts2 ) {Ta : auxiliary Tube}
2: for all bit 0 # i 1 n do
3: Separate(Ta, i, B [1], B [0] )
4: if B [0] is empty then
5:
Set(Td , i )
6: end if
7: Combine(Ta, B [1], B [0] )
8: end for
FIRST QUARTER 2021

gates were built by parallelizing a single-rail AND gate
and a single-rail OR gate to construct a logical expression. The NOT gate, fundamental to the construction
of general logic systems, is difficult to build but can be
achieved by reversing the definition of the strands
and constructing a single-rail AND gate and a single-rail
OR gate [112].
A DNA ALU, with four 1-bit functions (FA, AND, OR
and NAND) and the decoding and controlling logic,
was constructed [112]. It was built with 16 equivalent
logic gates and consists of 27 DNA species and 74 DNA
strands. After purifying the strands with PolyAcrylamide Gel Electrophoresis (PAGE), the logic gates and
circuits are tested, and the results are visualized with
the real-time Polymerase Chain Reaction (PCR); PAGE
can also be followed by gel imaging. The results in
[112] show that it is possible to integrate components
to implement DNA computer systems. Leakage is the
main challenge, especially when the size scales up. The
limited purity of commercial chemosynthetic strands
and DNA components is the primary source of leakage.

Algorithm 2.
ADD(Ts1, Ts2, n:in; Td:out).
Require: Pour blank strand of n bits (0 f 0 ) into Td
Ensure: bit_stream_in_Td =bit_stream_in_Ts1 + bit_stream_in_Ts2
1: Combine(Tnc , Ts1, Ts2 ) {Tnc : No-carry auxiliary Tube}
2: for bits i = 0 to n - 1 do
3: if Tnc is not empty then
4:
Separate(Tnc , i, B [1], B [0] )
5:
if neither B [0] nor B [1] is empty then
6:
Set(Td , i ) {bits in position i have different values}
7:
Combine(Tnc , Ts1, Ts2 )
8:
else
9:
if B [0] is empty then
10:
Combine(Tc , Ts1, Ts2 ) {Tc: (with-)carry auxiliary Tube}
11:
else
12:
Combine(Tnc , Ts1, Ts2 ) {bits in position i are both 0}
13:
end if
14:
end if
15: else
16:
Separate(Tc , i, B [1], B [0] )
17:
if neither B [0] nor B [1] is empty then
18:
Combine(Tnc , Ts1, Ts2 ){bits in position i have
different values}
19:
else
20:
if B [0] is empty then
21:
Set(Td , i ) {bits in position i are both 1}
22:
Combine(Tc , Ts1, Ts2 )
23:
else
24:
Set(Td , i ) {bits in position i both 0}
25:
Combine(Tnc , Ts1, Ts2 ) {bits in position i are both 0}
26:
end if
27:
end if
28: end if
29: end for
IEEE CIRCUITS AND SYSTEMS MAGAZINE

29
IEEE Circuits and Systems Magazine - Q1 2021

Table of Contents for the Digital Edition of IEEE Circuits and Systems Magazine - Q1 2021
