A corridor has two mouths

A DNA origami is folded by routing one long strand of DNA, the scaffold, through every helix of a bundle exactly once — the design problem a sheet that routes itself set out — and then pinning it in place with hundreds of short staples. Deciding whether a given arrangement of helices admits such a route is the problem of finding a path through a graph that visits every vertex once — hard in general, and hard even on grids — so the practical question is which cheap tests refuse shapes that cannot be routed, before anybody searches. The method is Paul Rothemund’s, published in 2006 for flat shapes; the honeycomb lattice of helices, on which a bundle becomes three-dimensional, was introduced by Shawn Douglas and colleagues in 2009.

Every cheap test misses a shape set the problem up as a staircase. Each cheap test is necessary and never sufficient, so for every set of them there is a smallest shape they all pass and no route reaches, and a census of every connected shape finds it. A test that only knows one lattice added a fifth test, read off the square lattice’s smallest survivor, and found it refusing all thirty-two of the square’s eleven-helix survivors and none of the honeycomb’s six at sixteen. It ended on that honeycomb shape: the only object in these essays with no cheap refusal at all.

It has one. The argument that refuses it is about corridors, and it is the first test in the list read off a honeycomb shape.

Why every earlier test needed the ends #

The tests already in the list share a habit. The colour count says a route alternates colours, so the colours must nearly balance; the ends test says a route has two ends, so at most two helices may have only one neighbour; the cut tests say removing one or two helices must not leave too many pieces. Those three know nothing about where the route ends. The next three — the steps the ends force, the colour of each forced end, and the piece a cut fences off — are strong precisely because they reason from the ends: a helix with one neighbour must be an end, its neighbour is then its first step, and a chain of consequences follows.

The honeycomb survivor defeats that chain. It has one helix with one neighbour and fifteen helices whose roles the ends cannot fix. With a single end known, the forcing has one step to take and then stops; thirteen of the sixteen helices have two neighbours, and a two-neighbour helix forces nothing until both ends are placed. So the tests that reason from ends reason about one end, and one end says very little.

What the shape has instead is structure that does not depend on the ends at all. Its helices with two neighbours come in chains, and the chains meet at three helices with three neighbours each.

A corridor, and what a route must do with it #

Call a helix with any number of neighbours other than two a junction, and a maximal chain of two-neighbour helices between junctions a corridor. A corridor has two mouths, one at each end, where it meets a junction.

A route visits every helix, so it must pass through every corridor’s helices. Inside a corridor there is nowhere to turn: each helix has exactly the two neighbours the corridor gives it. So the route either runs the length of the corridor, in at one mouth and out at the other, or it has an end inside the corridor — it comes in at one mouth, runs along, and stops just short of the other. The only other possibility spends both of the route’s ends on one corridor, leaving by one mouth and coming back by the other; and a route that entered from neither mouth would never reach the corridor’s helices.

A route passes through each junction once, leaving by a different neighbour from the one it arrived by — two of the junction’s neighbours used, or one if the route ends at the junction. A junction with three corridors attached therefore uses two of them, and the third must be entered only from its far mouth: which is possible only if an end of the route lies inside it.

That gives the count. At each junction with three neighbours or more, take its compulsory mouths — corridors with a helix inside, and the link to any helix with a single neighbour, which that helix needs — and count how many exceed two. Each excess mouth needs an end of the route inside the corridor behind it, and each end can do that for one corridor. A route has two ends, and every helix with a single neighbour already spends one. If the excess summed over the junctions is more than the ends left free, no route exists.

Three junctions and one end #

The honeycomb survivor reads immediately. Its three junctions each meet three compulsory mouths: two corridors and the pendant link at the bottom junction; three corridors at each of the top two. Each has an excess of one, so the route needs three ends inside corridors. One end is spent at the helix with a single neighbour, which must be an end. One end is left, and three are needed. The shape is refused without a search.

It is worth following one attempt by hand, because it shows the count’s arithmetic as a route running out of room. The shape’s four corridors hold four, three, four and one helices: one of four joins the bottom junction to the upper left, one of three runs across the top from the upper left to the upper right, one of four returns from the upper right to the bottom, and a single helix makes a short corridor between the two upper junctions. The route must start at the pendant helix under the bottom junction, since that helix has one neighbour. From the bottom junction it takes one of its two long corridors — say the left — and arrives at the upper-left junction, which it may pass through once. It leaves by the top corridor or by the single-helix one, arrives at the upper right, and leaves that junction by whichever of those two it did not take — and arrives back at the upper left, which it has already used. The only way out is to stop, and the right-hand long corridor has not been entered. Choosing differently at any junction moves the unentered corridor but never removes it: three junctions each shut out one corridor, and the route has one end to spend on them.

The count is sound in the plain sense: it refuses only shapes that cannot be routed. It was checked the way every test in the list is checked, against the exhaustive search on every shape of the census that passes the colour, ends and cut tests — 59,726 honeycomb shapes to sixteen helices, out of 3,898,510 counted, and 72,881 square ones to twelve, out of 691,268 — and it refused not one shape that has a route.

The count is tight, and it is cheap #

The count is not merely sound; on the simplest shape it can speak about, it is exactly right. Take two junctions joined by three corridors, a shape like the Greek letter theta, with no helix of a single neighbour. Each junction has three compulsory mouths and an excess of one, so the route needs two ends inside corridors, and it has two. The count passes it — and it should, because a route exists: start just inside the first corridor near one junction, run it to the other junction, cross by the second corridor, and run the third almost back to where the route began. Two junctions of three are the most a route with two free ends can afford, and the theta spends both.

That gives a corollary a designer can use by eye. Call a junction isolated if it has three neighbours and every one of them sits in a corridor or is a single-neighbour helix. A shape with more isolated junctions than the route has free ends cannot be routed — at most two in a shape with no single-neighbour helix, at most one in a shape with one. The honeycomb survivor has three isolated junctions and one single-neighbour helix, and fails the corollary twice over. On the honeycomb lattice, where no helix can have more than three neighbours, isolated junctions are common: every junction in a thin shape is one.

It is also the cheapest test in the list after the colour count, and cheapness matters for the reason two ceilings gave: a designer growing a shape one helix at a time wants to know at each step whether the next helix has made it unroutable. It reads each helix’s neighbours once, counts the ones with two neighbours at every junction, and adds; the cost grows with the number of helices and nothing else. The piece test, by comparison, tries a cut at every helix and counts colours on the fenced-off stretch, and the exhaustive search on the survivor visits 818 partial routes before it gives up. The last shape to fall was the cheapest to refuse.

All six survivors at sixteen are placements of the one shape, so the count refuses all six. And the census now runs out of honeycomb shapes before it runs out of tests.

With the corridor count added, no honeycomb shape of sixteen helices or fewer passes every cheap test and has no route. Each of those claims rests on an exhaustive search that found nothing, which is the kind of claim whose cost the order that proves nothing exists showed depends on the order a search takes, though its answer does not; the search here is the one every earlier census used. The staircase on that lattice has climbed past the census: the smallest honeycomb shape that every test lets through and no route reaches is somewhere beyond sixteen helices, and finding it means counting the seventeen-helix shapes, of which there are about three times as many again.

The same census reads more clearly as a climb. Drawn size by size, each test’s survivors sit on the floor until the first shape gets past it, and then rise: the colour, ends and cut tests let their first unroutable shape through at twelve helices, the forced steps at fifteen, the end colours and the piece test at sixteen.

Counted to sixteen, the corridor count’s curve never leaves the floor. Every other curve has left it by then, and the one question the figure cannot answer is the one the next size would: where the last curve takes its step.

The square lattice, where the test was not read #

The last essay’s lesson was that a test inherits the lattice of the shape it was read off: the piece test, found on a square shape, refused every square survivor at eleven helices and no honeycomb one. The corridor count was read off a honeycomb shape, and the fair question is what it does on the square lattice.

The square lattice’s smallest survivors, after the piece test, are twelve placements of two shapes at twelve helices. The corridor count refuses one shape and not the other. The first has four junctions whose excess sums to two, with one end free, so it is refused in all eight of its placements. The second has five junctions, but most of its links run junction to junction with no helix between them, and a direct link between two junctions is not compulsory — a route may simply not use it. Its excess is one, one end is free, and it passes.

The surviving square shape shows what the count cannot see. Its centre helix has four neighbours and every one of them is a junction, so every link at the centre is optional as far as the count is concerned; the count charges nothing there. The route’s difficulty is real — the exhaustive search finds none — but it is a difficulty about which of the optional links to use, and the count only reads links that are not optional.

So the square staircase does not move. The smallest square shape no test refuses stays at twelve helices; it is one shape instead of two. The honeycomb staircase moves past the census. The lesson of the last essay holds in reverse: a test read off a honeycomb witness clears the honeycomb and only thins the square.

Why corridors are a honeycomb’s shape #

The asymmetry has a reason in the lattices themselves. A helix on the honeycomb lattice has at most three neighbours, so in any shape most helices have two or three, and a shape is a network of corridors joined at junctions of three — exactly the structure the count reads. A helix on the square lattice has up to four neighbours, and a compact square shape has many junctions linked directly, with no corridor between them. Direct links between junctions are what the count cannot charge, and the square lattice makes them freely.

That fits the other things the honeycomb has shown in these essays. The lattice the pitch prefers is the honeycomb because a double helix faces three neighbours a third of a turn apart every seven bases; a row the route cannot leave found honeycomb blocks refused along a single row of helices with too few neighbours. Both are consequences of three neighbours rather than four. The corridor count is a third: on a lattice of degree three, the shape of a shape is its corridors.

What the count assumes, and what it cannot show #

A route is a path, not a loop. Some scaffolds are circular and a designer may want a closed route through the bundle. The count adapts — a closed route has no ends, so no excess can be absorbed at all, and every junction must have exactly two compulsory mouths — and the version here is for the open route the census has always counted.

Helices are vertices and neighbours are edges. A helix can be crossed to its neighbour only where its backbone faces that neighbour, which the crossover period prices; the graph here assumes every pair of neighbours has at least one crossover available, as every census in this series has.

The count is necessary and far from sufficient. It refuses a shape when its junctions need too many ends; it says nothing about a shape whose trouble is elsewhere, as the surviving square shape shows. And like every test in the list it was found by looking at one shape, so its power is concentrated on shapes that look like that one.

And the census stops at sixteen honeycomb helices. The next honeycomb survivor exists — every finite list of cheap tests has one, since routing is hard — and it is larger than sixteen helices. Nothing here says how much larger.

A route is a spanning structure, and corridors are its skeleton #

The surprising connection is with the other half of this subject, the half with paper in it. The crane census found nearly every failing cutting of a slit grid failing at one crane — a local fact about a global property — and the argument here is the same shape: a global property, the existence of a route, refused by counting something at each junction. Both are statements that a spanning structure has to pass through narrow places in a limited number of ways, and both become cheap exactly where the narrow places are easy to find.

In a routing problem the narrow places are corridors: a corridor admits the route in only two ways, through or into a dead end, so a graph with many corridors has few routes and a count of dead ends is a count of how many it can afford. The route’s two ends are a budget, and the corridors spend it.

Still open: the seventeen-helix honeycomb, and the optional links #

The honeycomb census needs one more size to find the next survivor, and seventeen helices means about seven million shapes, a count of minutes rather than seconds. Whether the next honeycomb survivor is a shape the corridor count nearly refuses — one with two junctions of excess against one free end, say, which would be a near miss — or a shape of an entirely different kind, would say whether the count has cleared a whole family or only its smallest member.

The square survivor points at the other direction. Its difficulty is in the optional links between junctions, and the count ignores them. A refinement that charges a junction for the optional links a route could use there — a junction of four whose neighbours are all junctions still has to be passed through once, using two of its four links, and the choice constrains its neighbours — would be the first test in the list that reasons about choices rather than about compulsions, and it would be the natural test to read off the square lattice’s twelve-helix shape.

Sideways from here, the corridor structure is a clean input for the question the chequerboard count has asked from the start: which necessary conditions exist that nobody has written down. A corridor’s length has a colour count of its own, and a corridor of odd length between two junctions of the same colour is a constraint the count here does not use.

The habit worth carrying is about what a test is built on. When every test in a list reasons from the same piece of information, look for a shape where that information is missing. Every test after the first three reasoned from the route’s ends; the shape that beat them all was the one with only one end to reason from, and the test that refused it was the one that did not need ends at all.