Understanding Turing Machine through DNA Computation-2

Following our last expedition of  Turing Machine, let us now see it apply to DNA computing. The information in the DNA is represented using the four-character genetic alphabet- A [adenine], G [guanine], C [cytosine], and T [thymine]. These four are known as bases and are linked through deoxyribose. This connection between the bases follows a direction such that the lock-and-key principle is achieved - 

(A)(T) and (C)(G)

This means Adenine (A) pairs with Thymine (T), and Cytosine (C) pairs with Guanine (G). These bases make DNA a computational medium.

Drawing the analogy from traditional computers to DNA computing, we see that while the former process formation sequentially, DNA computing allows for parallelism, the ability to perform many computations simultaneously by leveraging the vast number of DNA molecules. This significantly speeds up the process. DNA computing uses biochemical reactions and DNA molecules instead of silicon-based computing like conventional computers. The analogy between the two is outlined below-

Traditional Computing	DNA Computing
Bits (0s and 1s)	DNA bases (A, T, G, C)
Circuits	DNA Strands
Logic gates (AND, OR, NOT)	Biochemical operations (Enzymes and hybridization reactions)
Memory (RAM)	DNA storage

 

DNA computing follows stochastic processing. When DNA molecules are added to a test tube to obtain a desirable set(s) of output(s), they naturally combine in various ways without further intervention in the tube and present potential solutions. There are two properties of DNA computing- molecular algorithms and parallel processing. 

i.               Molecular Algorithm

DNA computing relies on the use of nucleic acids (DNA and RNA) to perform molecular computing, i.e., carrying out operations at a molecular scale, which in turn allows for massive parallelism.  

Molecular algorithms occur from molecular operations. Some of these are listed below, along with the algorithm they induce. These operations do not follow a step-by-step occurrence; they all happen at once.

Molecular Operation	Algorithmic equivalent	Description
Hybridization	Pattern matching	Base pairing between complementary strands (A–T, C–G)
Ligation	Concatenation	Enzyme ligase merges DNA strands, creating new sequences
Strand Displacement	Memory overwrite	Replace one strand with another
Enzyme cutting	Conditional branching	Cuts the DNA at specific sequences
Gel electrophoresis	Sorting or selection	Separates DNA by size

 

ii.              Parallel Processing

Parallelism is a term that refers to utilising multiple processing units simultaneously executing tasks to speed up the process. DNA computing naturally follows this property, making it a suitable choice to solve problems involving numerous potential results.

Parallel processing is done when DNA strands start to interact through natural chemical processes (molecular operations). These interactions provide all possible combinations to our problem. We add a biological filter (like adding enzymes) that omits the incorrect combinations and keeps the ones that meet the criteria of the problem. The last DNA strand remaining (survived all the filters) is the final solution to our problem.

Example:

Say we want to find out whether a person is infected with a certain virus or not. The virus is known to leave 3 specific DNA markers in the patient’s cells:

Marker A, Marker B, and Marker C.

We know the virus is present if all three markers are present. An ‘AND’ logic gate would help in this scenario.

-       We create sensors (synthetic DNA strands) that bind to all three markers.

-       We then add a sample of the person’s DNA to these strands. If the markers are present, the probes will hybridize (bind) to them.

-       The DNA-based AND gate will produce a visual indication for a positive result (like a visible color change) if all three strands bind successfully.

-       If one or more markers are missing, nothing happens, i.e., the result is negative.

iii.            Self-Replication

Self-replication means that DNA can make exact copies of itself using enzymes and basic building blocks (nucleotide bases). This process occurs naturally in all living beings. This process begins when the DNA strand starts to unwind with the help of an enzyme called helicase. Consequently, the double helix is broken into two single strands. The free-floating nucleotides match up with the now exposed bases on the strands to synthesize new sequences in the presence of DNA polymerase (an enzyme that helps attach new bases, forming two identical DNA molecules from the original one).

1.The Adleman’s Experiment (1994), conducted by Dr. Leonard M. Adleman, was the first DNA computing experiment. Its goal was to find a route through the network of cities (1-7) associated with disposable roads. The problem shows that routes must start and end in a particular city and only visit all cities once. (This is also known as the Hamiltonian Path issue.)

A directed graph G with designated vertices vstart and vend is said to have a Hamiltonian path if and only if there exists a sequence of compatible directed edges e1; e2; ...; ez (i.e., a directed path) that begins at vstart, ends at vend, and enters every other vertex exactly once. The following (nondeterministic) algorithm solves the problem: 

Input. A directed graph G with n vertices and designated vertices vstart and vend. 

Step 1. Generate random paths through the graph. 

Step 2. Keep only those paths that begin with vstart and end with vend. 

Step 3. Keep only those paths that enter precisely n vertices. 

Step 4. Keep only those paths that enter all the vertices of the graph at least once. 

Output. If any paths remain, output ‘‘YES’’; otherwise, output ‘‘NO.’’

It will be better to understand this by practicing the experiment. Consider the graph below:

Here, we can see that each node has its unique DNA sequence. Right now, we have not specified the path we want to find, so all possibilities among the three nodes are possible.

Say our desired path is  . This forms a directed graph.

To come up with a sequence that abides with our required path, we need the sequence for each of the two edges that combine the nodes. To do so, we understand the directionality of DNA strands (each DNA strand has a chemical orientation).

We follow these steps:

1.     Write the sequence at hand that reads from 5’ (five prime) to 3’ (three prime) according to the DNA orientation. This means it can only synthesize when used in 5’ to 3’ form. Consider the sequence 5’—ATGCCT—3’.

2.     Find the complement of the sequence, which is read in 3’ to 5’ form. The complement of the strand is 3’—TACGGA—5’.

3.     The reverse complement, i.e., write the complement in 5’ to 3’ form. The reverse complement is AGGCAT.

4.     Finally, we have a sequence that binds with our original sequence.

Coming back to our example, let us find the sequence of the edge that joins A and B. We take the last part of A’s sequence and the first part of B’s sequence and find and combine their complements.

Last part of A	First part of B	Reverse complement of A	Reverse complement of B	Combined strand
CGA	CGA	TCG	TCG	TCGTCG

So, .

Similarly, we find for .

Last part of B	First part of C	Reverse complement of B	Reverse complement of C	Combined strand
AGT	AAT	ACT	ATT	ACTATT

So, .

To get the collective strand representing , we combine the nodes with edges and eliminate the nucleotides that bind.

We keep the entire node A, the last part of  since the first part overlaps with the end of A, the last part of node B since the first part overlaps with , the last part of  since the first part overlaps with the end of B, and the last part of C since the first part overlaps with the end of  .

So, our final sequence is – ATCCGA TCG AGT ATT GCC

While working in practical conditions, this path would have appeared after DNA molecules would have ruled out other possibilities that did not include strands that followed   . For instance, if we want paths from A to C, the DNA molecules would operate such that they pull out strands starting with A’s sequence and keep the ones that end with C’s sequence.

We can claim that Adleman’s experiment used the property of DNA parallelism, i.e., processing multiple possibilities simultaneously.

2.     Turing Machine Implementation via DNA-

A DNA computation mimics the operations of a TM. DNA computing can simulate a TM by performing the same read, write, and move operations in a biological system. 

Components of Turing Machine	Equivalent Components of DNA Computing
Tape (memory storage)	DNA sequence (A, T, C, G strands)
Symbols (0, 1, blank)	Specific DNA sequences
Read/Write head	Enzymes (cut, copy, and modify DNA)
State Transitions	Chemical reactions
Computation process	DNA hybridization, ligation, and cleavage

Transition table of Turing Machine converting 0 to 1 and 1 to 0-

Current state	Reads symbol	Writes Symbol	Direction	Next state
q0 (start)	0	1	R	q1
q0	1	0	R	q1
q1	0	1	R	q1
q1	1	0	R	q1
q1	_	_	stops	qf (halt state)

 We can see the equivalent transition table of DNA Computing 

Current state	Reads Sequence	Writes Sequence	Direction	Next state
q0 (start)	AAC	GTT	R	q1
q0	GTT	ACC	R	q1
q1	AAC	GTT	R	q1
q1	GTT	AAC	R	q1
q1	_	_	stops	qf (halt state)

The motivation behind a DNA-based Turing machine is to show proof of principle that molecules can carry out symbolic computations. The Turing machine is the fundamental model of computation and gives DNA computing a formal theoretical foundation. A DNA-based TM forms the blueprint of how molecules follow logic. It allows us to run general logic without redesigning a new circuit for every task.

Example:

An application of a DNA-based Turing Machine is that of biological simulations (like protein synthesis in cells). Say we want to model gene repression via a repression protein on a Turing machine. Before we begin, let us define a basic logic we will follow:

Consider the gene that controls eye colour: OCA2. This gene depends on HERC2 mutation. When HERC2 is on, normal gene regulation occurs; otherwise, it does not.

Current state	Read symbol	Write symbol	Move	Next state	Description
q0	HERC2_ON	HERC2_ON	R	q_checkOCA2	Check OCA2 regulation
q0	HERC2_OFF	HERC2_OFF	R	q_blockOCA2	Mutation blocks expression
q_checkOCA2	OCA2	OCA2	R	q_brown	Gene active
q_blockOCA2	OCA2	OCA2	R	q_blue	Gene repressed
q_brown	Eye_colour	BROWN	-	q_accept	O/p eye colour
q_blue	Eye_colour	BLUE	-	q_accept	o/p eye colour

 

Turing Machines have, to date, served to be foundational to the theory of computation. It has applications beyond the study of computation; it is profoundly used in bioinformatics. DNA computing simulates Turing Machines (TM) by using DNA strands to represent the tape, symbols, and states. Enzymes act as the read/write head, and biochemical reactions (like hybridization and ligation) simulate state transitions. Just as a Turing Machine processes symbols based on rules, DNA computing processes DNA sequences using base pairing rules (A-T, C-G). 

This allows DNA computing to solve complex problems through massive parallelism and high data storage capacity. By initiating this relationship with Turing machines, DNA computation allows us to approach various problems, including the Hamiltonian path problem. Overall, DNA computing follows the same logic as a Turing Machine, with biochemical reactions replacing the TM’s symbolic processing.

References

L. Kari, S. Seki, and P. Sosík, “DNA Computing — Foundations and Implications.” Handbook of Natural Computing, vol. 33, no. -, pp. 1073-1127, 2012, doi: 10.1007/978-3-540-92910-9_33.

L. De Mol, “Turing Machines,” in Stanford Encyclopedia of Philosophy, Metaphysics Research Lab, Stanford, 2024.

T. Kumar and S. Namasudra, Advances in Computers. vol. 129. Elsevier, 2023. T. Kumar and S. Namasudra, Advances in Computers. vol. 129. Elsevier, 2023.

S. Garg, Computing Handbook Set - Computer Science. vol. 1. Department of Computer Science, Duke University (Reif is also Adjunct, Technology (FCIT), King Abdulaziz University (KAU).

“DNA Computing Theory.” https://cs.stanford.edu/. https://cs.stanford.edu/people/eroberts/courses/soco/projects/2003-04/dna-computing/theory.htm#:~:text=In%20DNA%20computing%2C%20the%20DNA,and%20explained%20in%20the%20demo.

Rozen, D. E., McGrew, S., & Ellington, A. D. (1996). Molecular computing: Does DNA compute? Current Biology, 6(3), 254-257.

Unraveling the Potential of DNA Computing: A Revolutionary Leap .. medium.com. April 4, 2025. https://medium.com/@MakeComputerScienceGreatAgain/unraveling-the-potential-of-dna-computing-a-revolutionary-leap-in-information-processing-a887e155a268

van Nies, P., Westerlaken, I., Blanken, D. et al. Self-replication of DNA by its encoded proteins in liposome-based synthetic cells. Nat Commun 9, 1583 (2018).

Jonoska, N., & Winfree, E. (2023). Visions of DNA Nanotechnology at 40 for the Next 40. Springer Nature.

DNA and Molecular Computing | Department of Computer Science. cs.duke.com. April 4, 20

COMS 381, Summer 2005 Supplementary Handout 5. https://www.cs.cornell.edu/courses/cs381/2005su/Handouts/Nondet.pdf

Nondeterministic Turing Machines. https://courses.grainger.illinois.edu/cs374/sp2018/a/notes/models/09-nondeterminism.pdf

Kumar, T. (2023). Advances in Computers (Vol. 129). Science Direct.

How do we determine the overall outcome of a non-deterministic .. etica.org. April 4, 2025. https://eitca.org/cybersecurity/eitc-is-cctf-computational-complexity-theory-fundamentals/turing-machines/nondeterminism-in-turing-machines/examination-review-nondeterminism-in-turing-machines/how-do-we-determine-the-overall-outcome-of-a-non-deterministic-turing-machines-computation/

Issue 2 - Volume 17 - Nanotechnology - IOPscience. iopscience.iop.org. April 4, 2025. https://iopscience.iop.org/issue/0957-4484/17/2

Eghdami, H., & Darehmiraki, M. (2011). Application of DNA computing in graph theory. Artificial Intelligence Review, 38(3), 223-235. https://doi.org/10.1007/s10462-011-9247-5