Skip to main content
Be Bitwise

DNA Computing Principles

DNA & Molecular Computing · Frontiers track

10 min read

In this module

Computing with Molecules

Last lesson treated DNA as inert ink — letters in a four-character alphabet you write to and read from. But DNA can also react. The same Watson-Crick rules that make it a stable archive also make its reactions programmable, and with the right design those reactions become logic gates, full circuits, and even algorithms.

This isn't a path to a faster laptop. DNA computing plays a different game: trillions of molecules reacting at once in a millilitre of buffer, sweeping enormous solution spaces in parallel. Each individual reaction is glacial by silicon standards — seconds to minutes — but for certain problem shapes the parallelism overwhelms the per-step latency.

Adleman's Experiment: The Birth of DNA Computing

The field traces back to a single experiment in 1994. Leonard Adleman, at USC, used DNA molecules to solve the Hamiltonian path problem — find a route through a graph that hits every node exactly once.

The Setup

Adleman encoded a 7-node directed graph as follows:

  1. Each node in the graph was represented by a unique 20-base DNA sequence
  2. Each edge was represented by a 20-base DNA sequence whose first 10 bases complemented the second half of the source node and whose last 10 bases complemented the first half of the destination node
  3. All node and edge DNA strands were mixed together in a test tube

Watson-Crick base pairing did the rest of the work. Edge strands snapped onto compatible node strands, growing into longer chains that physically encoded paths through the graph. With trillions of molecules sloshing around, every possible path was generated at once.

The Filtering Process

To find the Hamiltonian path among all the generated paths, Adleman applied a series of biochemical filtering steps:

  1. Length selection: Use gel electrophoresis to keep only paths of the correct length (those visiting exactly 7 nodes)
  2. Start/end filtering: Use PCR with primers for the start and end nodes, so only paths starting at the designated start node and ending at the designated end node get amplified
  3. Node verification: For each node, use affinity purification (probe strands for that node on magnetic beads) to keep only paths that contain that node's sequence. Repeat for all 7 nodes.

After all those steps, the only strands left in the tube were correct Hamiltonian paths. Sequence them and the answer fell out.

Seven nodes is already a lot of strands to track by hand, so here are the same filters on a smaller made-up graph (not Adleman's). It has five nodes, start 0, end 4, and exactly one Hamiltonian path:

A toy five-node graph. The only route through every node is 0 → 1 → 2 → 3 → 4.

Mix the strands and the tube fills with every walk those edges allow, including plenty that loop between 1 and 2. Each filter throws out a different kind of wrong answer:

One example casualty at each filter. Only the true Hamiltonian path survives all three.

The third casualty is the sneaky one. It has the right length and the right ends, and only the per-node check catches that it visits 2 twice and 3 never.

The Power of Molecular Parallelism

Adleman's experiment laid bare the core promise of DNA computing: a single tube can hold trillions of candidate solutions, and a single biochemical step acts on every one of them simultaneously. Seven nodes is small, sure. The problem is what happens for larger graphs, where the path count grows exponentially. So does the number of DNA molecules a test tube can hold — but only up to Avogadro's number. The unanswered question is whether molecular parallelism scales fast enough to keep up before the chemistry runs out of room.

Strand Displacement: The Foundation of DNA Logic

Adleman's experiment was brilliant; it was also bespoke. Every new problem demanded a fresh set of sequences and a custom biochemical protocol. The 2000s gave the field something more systematic: toehold-mediated strand displacement.

How Strand Displacement Works

Consider a short double-stranded DNA complex where one strand (the "incumbent") is partially bound to a longer strand, leaving a short single-stranded overhang called a toehold:

text
Toehold
↓
───┐
│══════════│ ← Incumbent strand (partially bound)
│══════════│══════│ ← Template strand (with exposed toehold)

A fuel strand complementary to the toehold latches on, kicking off branch migration: the fuel strand pries the incumbent off one base pair at a time, walking down the duplex until the incumbent floats free.

text
Step 1: Fuel strand binds to toehold
Step 2: Branch migration begins (fuel displaces incumbent)
Step 3: Incumbent strand fully displaced (released into solution)
───┐ ───────────┐
│══════════│ → │══════════════════│ ← Fuel strand now bound
│══════════│══════│ │ │══════│
+ released incumbent strand

The rate of this reaction is controlled by the toehold length:

  • No toehold: reaction essentially does not occur
  • Short toehold (3-4 bases): slow reaction
  • Long toehold (7+ bases): fast reaction

Tune the toehold and you tune the kinetics. That's the entire knob the designer turns.

DNA Logic Gates

Strand displacement gives you logic gates almost for free. An AND gate, for instance:

Inputs: Two DNA signal strands, X and Y Gate: A DNA complex that only releases its output strand when both X and Y have bound

The gate complex is designed with two toehold regions:

  1. Input X binds to the first toehold, partially displacing an intermediate strand
  2. This exposes a second toehold that input Y can bind to
  3. Input Y binds and completes the displacement, releasing the output strand

X without Y leaves the gate halfway through, output still trapped. Y without X has nowhere to bind because the second toehold hasn't been exposed yet. Only when both inputs show up does the output strand pop out. AND gate, in molecules.

Similarly:

  • OR gate: A complex that releases output when either input binds
  • NOT gate: A complex where the input strand displaces the output, preventing it from being available (more subtle to implement but achievable)
  • NAND/NOR: Built from combinations of the basic gates
DNA Gates Are Cascadable

The killer feature of strand-displacement gates is that the output is itself a DNA strand, which makes it a perfectly valid input to the next gate. Wire an AND output into an OR input, an OR into a NOT, and you have a circuit. With careful sequence design — keeping toeholds and stem regions orthogonal so the wrong strands don't react — you can stack layers and stack layers, the molecular analogue of building up a logic circuit from a stockpile of NAND gates.

DNA Circuits: Beyond Single Gates

Researchers have built increasingly complex DNA circuits using strand displacement:

Seesaw Gates

Seesaw gates are a scalable architecture for big DNA circuits. Every signal is dual-rail — the signal strand and its complement are both first-class citizens — and each gate acts as a weighted threshold element, firing only when the weighted input crosses the line.

Using seesaw gates, a Caltech group built a 130-strand circuit that computed integer square roots of 4-bit numbers. Trivial in silicon. The breakthrough was that multi-stage computation actually held together at all in solution.

Winner-Take-All Circuits

Winner-take-all DNA circuits exist too. Feed in multiple signals as DNA concentrations, and the circuit amplifies the strongest while squashing the rest. In computing terms: argmax in a test tube.

That trick is enough for molecular pattern classification. Hand the system a pattern of biomarker concentrations from a blood sample and the circuit fluoresces a colour-coded answer corresponding to its best guess.

DNA Neural Networks

In 2018 the Caltech group went further, building a DNA-based neural network that classified handwritten digits. Pixel intensities became concentrations of DNA signal strands. A cascade of strand displacement reactions did the weighted sums and threshold non-linearities. The output was a fluorescent signal naming the digit.

The network distinguished a handwritten 6 from a 7, and a few other tricky pairs, with no external power and a runtime of several hours. Compared to the nanoseconds a GPU spends, that is appallingly slow. The point was never the speed; it was that molecular-scale neural inference even ran.

DNA Walkers and Molecular Machines

DNA nanotechnology doesn't stop at static circuits. It also gives you molecular machines — constructs that physically move, ferry cargo, and do mechanical work down at the nanometre scale.

DNA Walkers

A DNA walker literally walks along a DNA track, binding then releasing from a series of foothold positions. Strand displacement powers the steps: each reaction unhooks the walker from the previous foothold while latching it onto the next.

DNA walkers can be programmed to:

  • Follow specific paths (choosing left or right at junctions based on instruction strands)
  • Carry molecular cargo from one location to another
  • Sort different types of cargo to different destinations

DNA Origami

DNA origami folds a single long strand into arbitrary 2D or 3D shapes by binding hundreds of short "staple" strands to specific regions, pinching the long strand into the target form. Think of it as papercraft for biology.

The technique resolves features down to about 6 nm, sharp enough to use the resulting structures as molecular pegboards for things like:

  • Organizing molecular components at precise positions
  • Creating nanoscale circuits where strand displacement reactions occur at defined locations
  • Building molecular robots and machines
text
DNA Origami: a long DNA strand folded into a smiley face
██████
██ ██
█ █
█ ■ ■ █ (not to scale - actual features ~100 nm)
█ █
█ ╲ ╱ █
██ ╲╱ ██
██████
Folded from ~7000 bases with ~200 staple strands

Chemical Reaction Networks

Step back from the strands and the abstraction underneath is a chemical reaction network (CRN) — a set of species plus the reactions that turn one set into another:

text
A + B → C + D (if species A and B meet, they produce C and D)
C → E (species C spontaneously converts to E)

CRNs have been formally proven Turing complete. Anything a digital computer can do, a chemical reaction network can do too, given enough patience. DNA strand displacement is the most practical recipe we have for implementing arbitrary CRNs:

  • Each chemical species is represented by a specific DNA strand
  • Each reaction is implemented as a strand displacement cascade
  • The concentrations of DNA species represent the variables of the computation
  • Reactions proceed according to mass-action kinetics (rate proportional to reactant concentrations)

In theory, then, DNA computing is general-purpose. In practice, molecular reactions are slow, noisy, and stubborn to scale up to the complexity needed for actual general-purpose work. The theory says yes, the wet lab says "good luck."

The next lesson zooms in on the problem domains where DNA's massive parallelism still beats electronics, awkward kinetics and all.