As you might have guessed, the mere fact that I asked this question means that the answer is ‘yes’. And there is also precedent, as people have made computers out of other things: Conway’s Game of Life, redstone in Minecraft, marbles, and, my personal favorite, Magic the Gathering. We’ve basically established that nerds, given time and resources, will build a computer out of almost anything, so why should DNA be the exception?
Before we delve into the different nanocontraptions scientists have made, we should define what a computer is in general. For the purposes of this piece, a computer is any device that can handle (usually numerical) information and do some operations on it.
One very special case is the so-called Turing machine. It is the most commonly used model of a general purpose computer. A Turing machine works on a long tape divided into cells for different symbols. The machine can move left and right on the tape, read, write, and erase the symbol on the tape. It also has an internal state, usually labeled by some number. A program for this machine consists of a set of instructions in the form of “if you’re in state 1, and the number on the tape you read is 2, write 1 in place of it, move 1 cell to the right, and change your state to 2”. With a proper set of such instructions you can do any thing a computer can do.
The beginnings of DNA computing were a bit more humble than that. In 1994 Leonard Adleman published a paper in Nature describing the use of DNA to solve a so-called Hamiltonian path problem.
The problem: Given a graph such as above, where the numbered circles may represent cities, and the arrows represent roads (either one-way or two-way), find a way to go from city no. 0 to city no. 6, that goes through all the other cities, but only once. It may not even be possible for all road networks imaginable, but knowing it’s not is also a valid answer. Doing so by going by all possible routes one by one takes a lot of time, especially as the number of cities grows, so traditional computers have a hard time solving it. The trick? Not doing it one by one, but in parallel.
Adleman came up with the ingenious idea of representing each of the cities by a 20-nucleotide sequence. If the graph included a 2->3 link, he would make a single stranded DNA molecule including the 3' end of the sequence number 2, and the 5' end of the sequence number 3. He would also create single stranded DNA molecules complementary to the city sequences, that would, through hybridization (G nucleotides pairing up with C, and A pairing up with T to create a double-stranded DNA molecule), link together the strands representing say, road 2->3 and road 3->4 , as shown in Figure 3, below:
All the strands representing a given problem together would be then incubated: the mixed strands representing edges of the graph, and the complimentary strands for the cities (except for the endpoint cities 0 and 6, which weren’t given the complimentary strand, their road strand was just the whole 20-nucleotide city sequence to which nothing could bind from the undesired side). They would be then ligated together, giving long, double-stranded DNA representing random paths. These molecules would be selected for length by gel electrophoresis, for having the proper cities at ends via PCR, and for having all the cities in between via single stranded probes with magnetic beads attached. Thus, through molecular biology Adleman could sort out the molecules corresponding to the Hamiltonian paths.
All well and good, but this DNA computer solved only a very particular problem, and it was far from being a general-purpose machine like the one on which I’m writing this text. Which is why the idea was developed further.
Benenson et al. published 2 papers, first one in 2001, and the other in 2003, which described a more advanced kind of a machine. This one could read a DNA sequence with a sticky end, containing 5 bp sequences labelled ‘a’ and ‘b’ in some arbitrary order, separated by 3 bp spacers, and could answer questions like “Are there 2 ‘a’ sequences in a row?” or “Is there at least 1 ‘b’ sequence?”
This computer consisted of 8 different “software” pieces of DNA, each containing a recognition site for the FokI restriction enzyme, and a 4-nucleotide sticky end, separated by either no, 1, or 2 base pairs from the recognition sequence. The sticky end is 4 nucleotides long, and the ‘a’ and ‘b’ sequences are 5 nucleotides long. This means, that whether the overhanging strand contains the first, or the last nucleotide of the sequence determines whether the machine is in a state S0, or S1. As you can see, we are getting closer to the Turing machine: we have a tape with the input (the DNA molecule), the machine can read it (albeit only one symbol at a time, and in one direction), and the machine has something corresponding to internal states (even if they’re encoded in the state of the input molecule).
The researchers put in a mix of the software fragments along with the input DNA and the restriction enzyme in a tube. If the sticky end of the input molecule matched the sticky end of the software molecule, they would bind together. Now the main difference between the computer presented in 2001 and in 2003 is that the latter did not need a ligation step after this annealing. We will come back to this issue later. Afterwards, the restriction enzyme would make a cut in the input DNA, creating an overhang from the nucleotides of the next symbol. Depending on the separation between the sticky end and the FokI recognition site of the software molecule, the cuts in DNA could be shifted by one nucleotide, allowing for transitions between internal states. So for example the software molecule in Figure 4 labeled T6 would bind to ‘a’ in state S1, and make nicks in such a place, that the next symbol would also be in S1.
Now what happened was that if the machine had the appropriate software fragments to bind the next symbol, and the next, until the end then the last sticky end would be a special terminator sequence. It could then be fused with a DNA molecule that served as an output detector, and amplified by PCR, and the input would be deemed as accepted. The detector for the S0 state would have a different length than the detector for S1, giving the experimenters data on the final state of the machine. If at some point the machine couldn’t find an adequate partner to the input (e.g. it would not have a software molecule able to bind ‘b’ in the S0 state), or it ended in a final state undesirable to the experimenters, it would be deemed unaccepted by this program. An example computation is shown below:
See for yourself, that if you put in a sequence with an odd number of a’s into program A1 you would end up in the unaccepted final state S1.
I mentioned that I would come back to the absence of the ligation step in the second paper. Ligation is a reaction that requires energy from ATP to be performed. It also makes the software molecules single-use, as after ligation they are basically useless. Another interesting consequence of it is that the computer seems to be powered simply by the degradation of the input molecule, which can be viewed as an entropically favorable scrambling of the input information. It’s as if you would read a book by eating it page by page, deriving sustenance for an all-day studying session from it (DO NOT DO IT AT HOME, OR ANYWHERE ELSE).
But that still isn’t the end of the story. Recent years have brought us very close to building a general-purpose computer out of DNA. A 2013 paper in Nature Nanotechnology by Chen et al. showed the possibility of creating programmable computational networks based on single DNA strands displacing each other from bigger DNA complexes. Those network are now programmable and can serve as a basis for creating analog computers simulating regulatory networks in cells.
When it comes to binary computing, in 2019, Eshra et al. published a paper showing an implementation of multi-use DNA logic gates, such as the OR gate (if at least one input is 1, the output is 1), which are reusable. They are also based on the strand exchange mechanism, containing hairpin DNA (DNA strands that have complementary fragments on the same molecule). These systems can perform binary operations more similar to our computers, and show that there is still a lot to discover in the field.
All the research I told you about shows, that DNA-based computing might become a quite viable way of solving some problems. When I first heard the term “bioinformatics” that’s what I expected to see, using biology-inspired systems to do computation. Well, we are getting closer to this version of bioinformatics. DNA computing, while not being able to work fast on a single thread, has the advantage of being compact, allowing for non-deterministic computation, and the ability to run many operations in parallel. It can be applied to a wide range of problems, as described in a paper by Tagore et al. At the end, we are left with but one question: Will it run Doom?
References:
Churchill, A., Biderman, S., & Herrick, A. (2019). Magic: The gathering is Turing complete. arXiv preprint arXiv:1904.09828.
Adleman, L. M. (1994). Molecular computation of solutions to combinatorial problems. Science, 266(5187), 1021–1024. https://doi.org/10.1126/SCIENCE.7973651
Benenson, Y., Paz-Elizur, T., Adar, R. et al. (2001). Programmable and autonomous computing machine made of biomolecules. Nature 414, 430–434 . https://doi.org/10.1038/35106533
Benenson, Y., Adar, R., Paz-Elizur, T., Livneh, Z., & Shapiro, E. (2003). DNA molecule provides a computing machine with both data and fuel. Proceedings of the National Academy of Sciences, 100(5), 2191–2196. https://doi.org/10.1073/PNAS.0535624100
Chen, Y.-J., Dalchau, N., Srinivas, N., Phillips, A., Cardelli, L., Soloveichik, D., & Seelig, G. (2013). Programmable chemical controllers made from DNA. Nature Nanotechnology 2013 8:10, 8(10), 755–762. https://doi.org/10.1038/nnano.2013.189
Shah, S., Wee, J., Song, T., Ceze, L., Strauss, K., Chen, Y.-J., & Reif, J. (2020). Using Strand Displacing Polymerase To Program Chemical Reaction Networks. Journal of the American Chemical Society, 142(21), 9587–9593. https://doi.org/10.1021/JACS.0C02240
Eshra, A., Shah, S., Song, T., & Reif, J. (2019). Renewable DNA hairpin-based logic circuits. IEEE Transactions on Nanotechnology, 18, 252–259. https://doi.org/10.1109/TNANO.2019.2896189
Tagore, S., Bhattacharya, S., Islam, A., & Islam, L. (2010). DNA Computation: Applications and Perspectives. Journal of Proteomics & Bioinformatics, 3, 234–243. https://doi.org/10.4172/jpb.1000145
