Two ceilings

A sheet that routes itself established what a DNA origami is and what goes wrong first. One long strand is held against itself by a few hundred short ones; there is no sheet and no crease; what has to be designed is a route, a path visiting every helix of the target shape exactly once. And the first thing that goes wrong is a counting argument this site already knew under another name — colour the helices like a chequerboard, a route alternates colours, so the two counts can differ by at most one — the same parity argument that decides a two-colouring of a crease pattern.

That rung also showed the count is not sufficient: a plus with arms of two has nine helices coloured five to four, the count raises no objection, and there is still no route.

What neither rung asked is how far any of this gets before something else stops it. A strand is a physical object of a fixed length — one viral genome, seven thousand two hundred and forty-nine bases — and a design cannot have more helices than it can thread. So there are two ceilings, they have nothing to do with each other, and which one a shape meets first is worth measuring.

The arithmetic ceiling #

The strand is 7,249 bases. A helix in these designs is about sixty-four bases long. So a design can thread at most a hundred and thirteen helices, and that number is the same for every shape ever proposed: it is division.

It is also a hard edge rather than a slope. A hundred and thirteen helices fit; a hundred and fourteen do not, and there is no partial credit — a strand that runs out has produced nothing, not a slightly incomplete object.

Two of the five families reach it.

A single row of helices reaches 113 and uses 99.8 per cent of the strand. An L with equal arms reaches 113 as well, for the same reason: both are long thin shapes with nothing to waste.

A square block stops at ten by ten, which is a hundred helices and 88 per cent of the strand — because eleven by eleven is a hundred and twenty-one and does not fit. The twelve per cent left over is not slack a designer can spend; it is the granularity of a shape that only comes in square numbers.

The combinatorial ceiling #

The other two families never get near it.

A plus — a centre with four arms — is refused at every size. The smallest, with arms of one, has five helices coloured one to four, and the colour count refuses it outright: a route alternates colours and cannot visit four of one colour with one of the other in between. A plus with arms of two has nine helices coloured five to four, which the count permits, and has no route — the centre 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.

A comb of teeth is routable with one tooth and refused with two, at eight helices.

So these shapes are stopped at five and eight, against a strand that could thread a hundred and thirteen. A factor of twenty, and it has nothing to do with how much strand there is: a strand ten times longer would change nothing.

The three verdicts, and the one that matters #

Every shape gets one of four words, and the fourth is the one this rung is about.

Disconnected — the shape is in pieces, and no strand crosses a gap. Reported separately because it is not a fact about routing.

Refused — the colour count refuses it, and the exhaustive search agrees. Four of the twelve catalogue shapes.

Routed — the count permits it and the search finds a route. Six of the twelve.

Permitted — the count permits it and there is no route. Two of the twelve: the plus with arms of two, and a T.

Those two are the whole content of “necessary but not sufficient”, and having them in the catalogue is what stops the cheap test from looking like the whole answer. A catalogue with only the first three verdicts in it would be a demonstration that the count works.

The direction matters as much as the count. No shape the colour count refuses has a route — checked by handing every refused shape to the search anyway, which is the only way a necessary condition gets tested against the thing it is necessary for. The count never forbids something buildable; it merely permits things that are not.

The second ceiling has a cheap test too #

The catalogue treats the two shapes that pass the colour count and have no route as findable only by exhaustive search, and the argument the essay gives for the plus is already a general criterion in disguise.

That argument is: the centre is a single cell whose removal leaves four separate arms, a route visits each arm in one unbroken run, and a route has two ends — so it can enter and leave at most two arms and the other two are stranded.

Written generally: remove any set of cells and count the pieces left. If a set of $s$ cells leaves more than $s + 1$ pieces, there is no route. A path crosses between pieces only by passing through a removed cell, each removed cell affords one crossing, and the two ends of the path afford one piece each. That is the classical necessary condition for a Hamiltonian path and it needs no search.

Run it on the two shapes the colour count let through. The plus with arms of two: remove the single centre cell and four arms fall apart — four pieces from one cell, against a permitted two. Refused. The T: remove the junction and three pieces fall apart — again more than two. Refused.

Both of the catalogue’s permitted verdicts are caught by it, and caught by removing a single cell, which costs one flood fill per cell and finishes instantly on a hundred-cell shape.

Which sharpens the design rule #

The closing advice — count the branch points — is nearly right and the criterion says exactly how nearly.

A branch point on its own is harmless. A square block is full of cells with three and four neighbours and routes perfectly well, because removing any one of them leaves the rest in one piece. What matters is not the degree but whether removing a cell disconnects the shape into three or more parts.

So the rule is: look for a cell whose removal cuts the shape into three or more pieces, or a small group of cells whose removal cuts it into more pieces than the group has members plus one. A shape with such a cell has no route at any size, and a shape without one has passed a second necessary condition on top of the colour count.

That leaves the honest position intact and moves the line. The colour count is one cheap necessary condition, the cut condition is a second, and together they catch every unroutable shape in this catalogue — which does not mean they catch every unroutable shape. Deciding a Hamiltonian path is hard in general, so there will be shapes both tests permit and no route reaches, and the catalogue simply does not contain one yet. Finding the smallest such shape is a better use of an exhaustive search than re-deciding the two cases a flood fill settles.

Which ceiling a shape meets is a property of the shape #

Put the two together and the design statement is short.

A shape whose helices form a long thin region, or a compact block, is limited by chemistry: it can be scaled up until the strand runs out, and then a longer strand would help.

A shape with a branch point of degree three or more is limited by combinatorics: it fails at whatever size it first has that branch point, and no strand helps at all.

The five families sort cleanly into those two, and nothing sits between them. That is the useful shape of the answer: a designer looking at a target does not need to compute anything to know which ceiling they are approaching. Count the branch points.

What a route actually is #

The object being searched for is a Hamiltonian path in the graph whose vertices are the helices and whose edges join helices that lie side by side. That is the thing the strand does: it runs the length of one helix, crosses over, runs the length of the next, and must eventually have run every one exactly once.

Two consequences worth stating.

A route cannot cross a gap. If the shape is in two pieces, no strand joins them, and the measurement reports that as disconnected rather than as a shape with no route — because those are different facts and only one of them is about routing.

And the search does not look at the colouring. That is deliberate: the colour count is a separate computation, and the two are required to agree in the direction that matters. Every shape the count refuses is handed to the exhaustive search anyway and the search has to agree. It does, on every shape tried.

The staples, and why they are not a third ceiling #

There is a third quantity a designer counts and it turns out not to bind.

The short strands — the staples — are what hold the long one against itself, and there are about two per helix. A hundred-helix design needs roughly two hundred of them, each about thirty-two bases, and each has to be synthesised separately.

That is an expense and a logistical problem and it is not a ceiling: nothing stops a design having four hundred staples except the cost of ordering them. So the count is reported beside the other two and is not treated as a limit, which is the honest arrangement — a limit is a thing that makes a design impossible, and this one makes it tedious.

Worth noting for scale: the largest design here needs about two hundred distinct short strands, which is why these things are made in laboratories with plate robots rather than at benches. The word folding is doing two jobs and this is one of the places the jobs come apart.

Where the numbers come from and what they assume #

Three inputs, all stated rather than derived, because none of them is geometry.

7,249 bases is the M13 bacteriophage genome, which is what the field uses and has used since the method was introduced. A different scaffold changes every number in the first ceiling proportionally and none of the second.

Sixty-four bases to a helix is a design convention rather than a fact about DNA: it is a length that leaves room for crossovers at sensible intervals. Halving it doubles the helix count and does not move the routing.

And a helix is adjacent to the helices beside it in a square lattice. Honeycomb lattices are also used and give a different adjacency graph — which would change the routing results and not the arithmetic, and is the obvious next measurement.

So the two ceilings depend on different inputs, and neither of them is a property of DNA as a molecule. That is the sense in which this rung belongs to folding rather than to chemistry: what is being counted is a path in a graph, and every number survives with the biology replaced by anything that has to be threaded.

What the search costs, and where it stops #

The Hamiltonian search is exhaustive with two prunings, and both are what make a hundred-cell shape affordable.

Connectivity of what remains: a step that cuts the unvisited cells into two pieces cannot be completed, and checking costs a flood fill. A degree count: an unvisited cell with fewer than two unvisited-or-endpoint neighbours must be an endpoint, and two of those is already one too many.

The sweep also arranges never to run the search past the arithmetic ceiling. A shape is checked for fit first, and if it does not fit there is nothing to route — so the search is only ever asked about shapes of at most a hundred and thirteen cells, which is where the prunings still hold.

That ordering is the reason the whole measurement takes a fraction of a second rather than not terminating, and it is worth writing down because the obvious ordering — route first, then check the budget — would not have finished.

The shape of the two limits together #

The two ceilings are not merely different numbers; they are different kinds of limit, and a designer meets them differently.

The strand’s limit is continuous in the target. A shape one helix too big can be made one helix smaller and it works. There is always a nearby buildable design, and the question is only how much has to be given up.

The routing’s limit is discontinuous. A plus with arms of two is unroutable and a plus with arms of one is unroutable and a plus with arms of three is unroutable — there is no nearby plus that works, because what fails is a feature of the shape rather than its size. Shrinking does not help and growing does not help.

That difference is why the first is described as a budget and the second as an obstruction. A budget is spent; an obstruction is either there or not. And this subject has met the same pair before under other names: an allowance that scales against a condition that either holds or does not, which is the shape of nearly every difficulty here.

Where the first ceiling actually sits #

The hundred and thirteen is a division and it is worth checking against what gets built, because a limit nobody reaches is not a limit.

The classical rectangular designs are around two hundred nanometres on a side, which at the helix pitch used here is a block of roughly a hundred helices — which is exactly the ceiling this arithmetic gives. So the first limit is not theoretical: it is the size published designs actually are, and the reason they are that size.

That agreement is the check that the inputs are the right inputs. A scaffold length and a helix length are both conventions rather than facts about the molecule, and a pair of conventions that predicted a limit ten times larger than what is built would be the wrong pair.

It also says something about the second ceiling. A field whose designs sit at the first limit is a field that has already excluded the shapes stopped by the second, because those never got as far as being built — which is why the routing obstruction is not something a reader will have encountered in a picture of a finished object.

What a designer does about the second ceiling #

The first ceiling is answered by a longer strand or a smaller shape. The second is not answered at all, and what the field does instead is worth naming.

Change the target. A plus is unroutable and a plus with a thickened middle may not be, because filling in the four cells diagonally adjacent to the centre gives the route somewhere to turn. That is a change to the object being built, which is sometimes acceptable and sometimes the whole point of the design. It is the same move a designer makes when a molecule refuses a polygon: the difficulty moves backwards to whoever chose the shape.

Or use more than one strand. Everything above assumes a single scaffold, which is the classical method. Multi-scaffold designs exist, and they turn a Hamiltonian path problem into a path cover problem — which is a different question with different obstructions, and it dissolves the plus’s difficulty immediately.

Neither of those is a way round the ceiling. They are ways of asking a different question, and being clear about which question is being asked is the whole content of a constraint like this — the same discipline the vertex conditions need.