The apparatus shown in the diagram consists of a series of chambers that rearrange the nucleotides in a short DNA fragment. Your goal is to find the shortest path that not only leads you to the finish, but also produces the desired DNA fragment from the one given at the start. Conceptually, the DNA fragment acts like a “token” that affects where you can move in the puzzle. At the same time, where you move in the puzzle affects this token.
The tubes connecting the chambers allow fragments to pass only if they contain specific DNA sequences. For example, a tube labeled <CT> would allow fragments CTG or GCT to pass, but not TCG. (This is how the token affects where you can move.)
The spherical chambers contain enzymes that specifically move the first nucleotide to a different position in the fragment. For example, the above label indicates that the enzyme in this chamber moves the first nucleotide into the second position; it would take the fragment CTG and produce TCG. (This is how where you move affects the token.) Remember, the shaded squares represent positions within the fragment, not particular nucleotide bases.
The chambers are designed so that the enzyme always works in the direction indicated by the arrow, no matter how you enter or exit the chamber. (In other words, the enzymes never work in reverse.) The chambers also ensure that enzymes eject the DNA fragment once the rearrangement has occurred. The only way a fragment can undergo another rearrangement by a given enzyme is by leaving and re-entering the chamber. One way to repeatedly apply an enzyme would be to move back and forth between either the start or finish chamber, as these chambers contain no enzymes and thus do not rearrange the fragment.
Here is the example puzzle again (with the transposition chambers labeled):
Notice that, in this apparatus, each chamber is connected to every other chamber. The tube connecting Y to Z passes underneath the tube connecting the start and the finish.
With the fragment GTA inserted at the start, we can move down to chamber Y (since the fragment contains GT) or over to chamber Z (since the fragment contains TA). However, we cannot move to the finish chamber, since the fragment does not contain AG.
So how can we obtain the fragment ATG? One way is to apply the transposition Z, then Y. Applying Z yields TAG, which means we cannot move directly to chamber Y (since the connecting tube requires the sequence TG). But we can still get there by moving back to the start (TA), down to the finish (AG), and then over to Y (TA).
But now we have a problem. We can't get to the finish with the fragment ATG, since the tube connecting chamber Y and the finish requires TA, which we no longer have in our fragment. We also cannot go the roundabout way via the start chamber, since the fragment doesn't have GT (or AG) either. The only place we can go from here is up to chamber Z, but this rearranges the fragment again!
There is a way to recover from this, but there is also a quicker way. Instead of starting by going over to chamber Z, let's instead go down to chamber Y. This produces the fragment TGA. If we can apply Z twice in a row, we can get ATG. It turns out that we can do this by jumping between Z and the finish.
From Y, we move up to Z (TG), which produces GAT. We can move to the finish (AT) and back up to Z (AT again) to get ATG. Since AT is still in the sequence, we can again move to the finish, and we're done!
Below is the entire problem space for the puzzle (in other words, all of the possible moves that can be made). The solution path is highlighted in blue. Tubes that cannot be traversed are grayed out with an X. Because of the cyclical nature of the transpositions, the problem space has many loops. These are indicated by the dashed lines connecting certain states lower in the tree with the same states higher in the tree. (Be sure to always go up the dotted lines, not down!)
Note that our original attempt to solve this example puzzle is the branch on the left. Following this branch (down to Y:TGA) eventually leads to a loop back up the right-hand solution branch. Another loop leads back to the starting position and fragment, indicating that you should start over.
As we saw in the example puzzle, it may be necessary to move back and forth between two chambers. While it may not seem like you are physically making progress towards the finish, you may be arranging the genetic fragment in just the right way to enable your march towards the finish.
There are many possible ways that one could attempt to solve these puzzles. One alternative to the "go around until I get stuck" method is trying to determine which series of transpositions give you the desired genetic fragment, and then looking for that series in the puzzle. One can also try and work backwards, although this may produce paths through the problem space that aren't accessible when going forward.