A sheet that routes itself

At the scale of a molecule there is no sheet. There is a single strand of DNA about seven thousand bases long, a few hundred short strands designed to bind to particular stretches of it, and a shape that emerges when the mixture is warmed and cooled.

The technique is called DNA origami and the name is borrowed rather than earned. Nothing about it is a crease pattern: no flat sheet, no mountain and valley, nothing that folds flat. But there is a design problem, it is geometric, and it turns out to have an obstruction this site has met before in a completely different setting.

What the design problem actually is #

The abstraction used here is the standard one and it is worth stating plainly, along with how much it throws away.

The target shape is a set of cells on a square lattice, each cell one double helix seen end-on. Two helices that are lattice neighbours can be joined by a crossover — a place where the strand leaves one helix and continues in the next. So the shape becomes a graph, and threading a single strand through every part of it becomes the problem of finding a path that visits every cell exactly once.

That is a Hamiltonian path, and if the strand has to return to its start it is a Hamiltonian cycle.

What the abstraction discards is substantial: real crossovers can only occur where the helical twist brings the two backbones close, so their positions are quantised along each helix; the lattice may be honeycomb rather than square; and the staples have their own routing problem sitting on top of the scaffold’s. None of that is modelled and the essay does not pretend otherwise.

The obstruction, which costs one pass #

Colour each cell by the parity of the sum of its coordinates. Every neighbour of a black cell is white and every neighbour of a white cell is black — a square lattice is bipartite, which is a fact about the lattice and not about any particular shape.

A path alternates colours by construction. So a path through n cells uses the two colours alternately, and the counts can differ by at most one. A cycle, which has to close, cannot differ at all.

That is a complete refusal for any shape whose colours are unbalanced, and it costs one pass over the cells. No search, no backtracking, no exponential anything: count two numbers and compare.

Where this site has seen this argument before #

The resemblance to Maekawa’s condition is close enough to be worth spelling out, because both are the same kind of reasoning applied to different objects.

Maekawa’s theorem says that at any flat-foldable vertex the number of mountains and valleys differs by exactly two. The reason is a winding argument: walking around the vertex in the folded state, the direction of travel reverses at every crease, and getting back to where the walk started forces a count.

The parity argument here says that walking along the scaffold, the colour changes at every step, and covering every cell forces a count.

Both are cheap, necessary, and blind. Neither looks at anything except a count. Neither can be beaten by a cleverer arrangement, because the counting holds whatever the arrangement is. And neither is remotely sufficient, which is the next section and the more important half.

Balanced and still impossible #

The condition refuses shapes and it does not certify them, and there is a witness for that in the sweep.

A plus with arms of length two has nine cells coloured five to four. The counts are as balanced as an odd number allows, the parity test raises no objection, and there is still no route — because the centre cell is a cut vertex of degree four, a path passes through any cell at most once, and passing through the centre once can serve at most two of the four arms.

The generator’s assertion is one-directional for this reason. It requires that no shape the count refuses can be routed — a contradiction would mean one of the two computations is wrong — and it separately requires that at least one shape in a sweep is balanced and unroutable, so the figure cannot quietly become an argument that the cheap test is sufficient.

Which shapes the count refuses, exactly #

The sweep shows the parity condition refusing some shapes and permitting others, and for the two families in it the boundary can be written down rather than discovered.

Rectangles. An $m \times n$ block has its colours balanced when $mn$ is even and off by one when $mn$ is odd. Off by one is what a path allows, so every rectangle passes the count for a path, and only the even-area ones pass it for a cycle. That is why the eight-by-five block in the figure can be routed as a closed cycle — forty cells, twenty and twenty — and a three-by-three cannot.

Pluses. A plus with arms of length $a$ has one centre cell and four at each distance from it. Cells at even distance take the centre’s colour and cells at odd distance the other, so the counts are $1 + 4\lfloor a/2 \rfloor$ against $4\lceil a/2 \rceil$. At $a = 1$ that is one against four — off by three, and refused. At $a = 2$ it is five against four, off by one, and permitted. At $a = 3$ it is five against eight, refused again.

So a plus is refused by the count exactly when its arm length is odd, and passes it whenever the arm length is even.

Which is the whole of what the count can do to a plus #

That characterisation makes the essay’s witness less of a coincidence and more of a rule.

Half the pluses are caught by the count, for a reason that is arithmetic and costs one pass. The other half are not caught by it at all — and none of them is routable either, because the centre is a single cell whose removal leaves four separate arms, and a path can enter and leave at most two of them.

So the two tests divide the family cleanly between them. The odd-armed pluses fail the colour count; the even-armed ones fail a connectivity count; and no plus of any size has a route. That is a complete answer for one family obtained without any search, and it is a better demonstration of what the cheap tests are worth than the single witness the sweep supplies — a witness shows that a gap exists, and a characterisation says exactly what fills it.

It also says what a search is genuinely needed for. Neither of the two counting arguments has anything to say about a shape whose colours balance and whose removal of any one cell leaves it in one or two pieces — and that describes almost every shape a designer would actually draw, which is why the exhaustive search is a verification device rather than a curiosity.

Running the sweep #

Both computations are run over a family of shapes rather than over the ones chosen for the figures, which is the difference between a demonstration and a check.

The two never contradict each other across the sweep, which is the strongest statement available: the parity condition is genuinely necessary, established by a search that shares no code with it.

The one-directional nature of the agreement is what makes it useful. A cheap test that sometimes says yes when the answer is no is a filter. A cheap test that sometimes says no when the answer is yes is a bug, and the sweep is what would find one.

The designer’s route, and where it fails #

There is a second way to produce a route, which is how designs are actually drawn: a raster, running along one row, up, and back along the next.

That gap is worth noticing because it runs the opposite way from the parity one. Parity is a cheap test that refuses more than it should not; the raster is a cheap construction that succeeds less often than it could. Between them they bracket the real answer, and the exhaustive search is what sits in the middle.

For rectangles the two agree, which is why rectangles are what almost every worked example uses and why the abstraction survives contact with practice.

The other constraint, which is a number from a virus #

There is a bound on how large a shape can be, and it is unlike any other bound on this site because it is not geometric at all.

The scaffold is a fixed molecule. Most designs use the genome of the M13 bacteriophage, which is 7,249 bases long, and that length was not chosen by anybody for this purpose. So the shape’s total demand — the number of helices times the length of each — has to fit inside a number that comes from a virus.

The arithmetic has a consequence worth stating: doubling a shape’s linear size quadruples its demand, so the reachable sizes run out quickly. A rectangle of forty helices at sixty-four bases each uses thirty-five percent of the scaffold; doubling both dimensions would need well over the whole of it.

That is an unusual kind of constraint to meet on this site, and it is worth dwelling on why. Every other bound in this field is geometric or material — a curvature that a metric forces, a radius a hinge cannot go below, a thickness that fills a container. This one is a supply limit: a fixed quantity of a particular molecule, whose length is a fact about a bacteriophage’s genome and has no relationship to anything anybody wants to build.

Designs get past it by using several scaffolds, or a longer one, or by assembling small units into larger structures — and each of those turns a single routing problem into a set of routing problems plus an assembly problem, which is a different and harder thing. The bud’s container is the nearest analogue elsewhere in this field: a constraint that comes from outside the object and that no amount of cleverness about the object removes.

Why the exhaustive search is affordable at all #

Finding a Hamiltonian path is one of the standard hard problems, so it is worth saying why an exhaustive search is being run here rather than avoided.

The honest answer is that the shapes are small. At a few dozen cells a depth-first search with two prunings finishes immediately, and the prunings are what make it immediate: a step that disconnects the unvisited cells cannot be completed, and a cell with too few unvisited neighbours must be an endpoint. Both are cheap and both cut enormous subtrees.

At the sizes a real design reaches — hundreds of helices — that search is not available, and this is the same situation the flat-folding problem is in. The general question is hard, the instances that arise in practice are highly structured, and the structure is what makes them tractable. A rectangle’s route is not found by search; it is written down.

So the search here is a verification device rather than a design tool. It exists so that the parity test has something independent to be checked against, and its inability to scale is not a problem for that job.

There is also a lesson in which of the two computations is the one that scales. The cheap necessary condition works at any size, and the complete answer does not — which is exactly the arrangement the flat-folding theorems have, where four local conditions run in linear time and the global question is NP-hard. A field that has a cheap filter and an expensive oracle should expect to spend its life using the filter.

The search that found its own bug #

The search has one property worth recording because it nearly produced a confident wrong answer.

An early version fixed the starting cell at the first one in the list, which is correct for a Hamiltonian cycle — a cycle contains every cell, so any cell will do — and wrong for a path. It reported that an L of six helices has no route, which is false: the route runs down the long arm and up the short one, and it starts at either tip and at neither corner.

The symptom is the dangerous kind. A negative result looks like a finding, it agrees with the general reputation of the problem as hard, and it would have made the parity test look far better than it is by handing it agreement it had not earned. It was caught by trying a shape whose answer was obvious by inspection rather than the shape the figure wanted.

The general habit that catches it is worth naming: when a search returns nothing, test it on an instance whose answer is known independently, and prefer the instance that is easy rather than the one that is interesting.

What is genuinely different about folding at this scale #

Three things, and each removes something this site normally relies on.

There is no sequence. A crease pattern is folded in an order, and restricting which orders are available changes what is reachable. A DNA origami structure has no folding order at all; the strands find each other and the shape is whatever the mixture settles into. That difference is the next rung.

There is no sheet. The object being folded is one-dimensional, and its shape comes from which parts of it are held next to which other parts. Nothing about a metric, a curvature or a developable surface applies.

And there is no folder. The nearest thing on this site is a sheet that folds itself, where the actuation is in the material — and even there a sheet has a pattern of creases that somebody put in it. Here the design is entirely in the sequence.

What the picture cannot show #

The routes drawn are paths on a lattice diagram. They are not the molecule, they are not to scale in either dimension, and the circles are not helices.

Most consequentially, the diagram has no length in it. A real crossover has to land where the helical twist brings two backbones adjacent, which happens at a fixed spacing along the helix, so the positions available for a crossover are quantised and a route that is fine in the diagram can be unbuildable in the molecule. The abstraction knows nothing about that.

The staple strands are also absent. They are the majority of the design work in practice — several hundred sequences, each binding two or three stretches of scaffold — and the figure reports only how many would be needed at a stated length.

The idealisation, named #

A square lattice with four neighbours, unit-length helices, crossovers anywhere, and a scaffold that is a featureless string of the right length.

Real designs frequently use a honeycomb lattice, where each helix has three neighbours rather than four. That changes the parity argument’s form — a honeycomb lattice is also bipartite, so a version of the counting survives — and it changes which shapes are reachable, because a degree-three lattice has fewer routes available at every cell.

And the scaffold is not featureless. It has a sequence, that sequence determines where staples can bind, and a route that is geometrically fine can require a staple whose sequence binds somewhere else as well. Nothing here models sequence at all, which means the design problem solved on this page is the easy half of the real one.

Where this ladder goes next #

The routing problem is solved and the shape assembles. What has not been asked is whether “folding” is the right word for what happened, and the next rung says it is not.

The comparison it makes is a counting one. A sheet with k creases has two-to-the-k assignments and a computable fraction of them fold flat, filtered by four conditions checked one vertex at a time. A chain of k joints has an exponentially growing configuration space and no local test whatsoever. Both are exponential and that is not the difference; the difference is that one of them has a filter and the other does not.