From DNA to algorithms

From DNA to algorithms


Self-assembling DNA programmed by applying theoretical computer science to molecular engineering

Through the incorporation of computer science into molecular engineering, computer scientists from UC Davis and the California Institute of Technology developed DNA that can algorithmically self-assemble. Using a DNA set tile containing 355 single-stranded tiles, the scientists were able to construct 21 circuits that can execute algorithms ranging from obtaining an unbiased choice from a random biased source to stimulating cellular automata, according to a Nature article titled “Diverse and robust molecular algorithms using reprogrammable DNA self-assembly.”

“I hope that molecular engineers will understand that the best way to understand how to get their molecules to automatically do what they want is to program them, which is where computer science comes in,” said David Doty, an assistant professor of computer science at UC Davis. “At its core computer science is not about electronic computers. It’s about automation […] how to design automatic processes that just work — we call them algorithms — without any need for people to come in and direct things by hand.”

The initial idea for this research came from Erik Winfree, a professor of computer science, computation and neural systems and bioengineering at the California Institute of Technology, who published a paper titled “The program-size complexity of self-assembled squares” that incorporated ideas on how to make these molecules perform computation from his Ph.D. thesis.

“I have long been fascinated by the conceptual connections between the mathematics of geometrical tilings, the fundamental principles of theoretical computer science, the exquisite forms of crystals and minerals, the complexity of biological self-assembly processes and the elegant formalisms of statistical mechanics,” Winfree said. “All those threads come together here.”

Doty, who had originally been studying Algorithmic Information Theory at Iowa State University as a graduate student, was captivated by the notion that this theory could be implemented to create actual self-assembling DNA molecules which can form nanoscale structures. Doty began working on theoretical problems in the field before joining Winfree’s lab. Damien Woods, a professor at Hamilton Institute of Maynooth University, joined Winfree’s lab after Winfree’s arguments intrigued him. Although both researchers were unfamiliar with laboratory work, instead coming from a theoretical computer science background, the two worked together to implement the theory into actual experiments.

Woods identified a major step in their research to be functionalizing an error reduction technique called “2×2 proofreading,” which allows the creation of more complex systems. Once this technique could be implemented, they were able to design the DNA system to fully exploit proofreading.

“When we purchased our molecules and started our experiments, we knew of only three or four circuits (programs) that we could implement in the lab,” Woods said. “But because our DNA system was reprogrammable, we spent subsequent days, weeks and months figuring out a total of 21 circuits to implement experimentally. Programming at the lab bench. A wonderful experience.”

Doty explained that a large portion of the project was devoted to determining how to unzip the DNA in order to demonstrate that their experiment had worked. After working roughly six months to develop a method to unzip the DNA, the problem resurrected and forced the researchers to come up with new ideas.  

“You take years to do an experiment, and you think the first few months will be spent knocking out the boring mundane stuff just to get the system up and running, and the next several years doing cool things with it,” Doty said. “In reality it’s the reverse: the majority of the time on the project is boring mundane stuff, mostly focused on figuring out what doesn’t work by trying things over and over again and recording that they don’t work.”

Woods stated he was pleased with the range of algorithms implemented through the experiments and the mathematically proven theoretical results from their self-assembling DNA. According to Doty, although they concentrated on DNA because there are already synthesizing methods in place and the molecule is fairly predictable, the double helix structure and the negatively charged characteristic of the molecule made some of the procedures difficult. Doty stated that their research could serve as a stepping stone to learning the general principles of automated molecule engineering. The researchers have the opportunity to move from title growth causing the execution of an algorithm, as in their recently published paper, to exploring how algorithms can direct this growth, essentially turning around the arrow of causation. This could lead to 3D printing without a printer and growing an object controlled by algorithms.

“We are still in the early stages of exploring this jungle of ideas,” Winfree said. “Now that we’ve cut a trail to one lovely waterfall, so everyone can go there, I imagine that we’ll rest for a few days at our base camp to renew our energies and then pick up our machetes again and start hacking away at the underbrush to explore in a new direction, and see what we’ll find.”

Written by: Michelle Wong ––

Leave a Comment