The DNA and Natural Algorithms Group:

The Xgrow Simulator

Summary:

This simulator, written in C for the X Windows environment, has been used to build our intutions about how algorithmic self-assembly may occur. We have used it, in particular, to explore issues of error rates ("Simulations..." and "Proofreading...") and to help understand experimental results ("One Dimensional Boundaries..."). Xgrow is currently pre-beta -- we fully expect it to have bugs as well as butterflies. Use at your own risk! If the results are important to you, perform careful control experiments.

What it does:

Xgrow implements the "abstract Tile Assembly Model" (aTAM) and the "kinetic Tile Assembly Model" (kTAM) described in the above papers. These models consider a single crystal (refered to as a "flake" in the context of Xgrow) that is growing in a solution environment by accretion of individual monomer tiles, one at a time. In the kTAM, single tiles can also fall off. To define a simulation, you must give Xgrow (a) a file containing definitions for all the tile type you will be using, i.e. what bond types are presented on the N, E, S, and W sides of each tile, and how strong are those bonds; (b) the parameter Gmc, exponentially dictating the concentration of the tiles and thus the on-rate for tile accretion; and (c) the parameter Gse, giving the strength of a "unit" bond and thus exponentially dictating the off-rate. Depending on the parameters, a tile set may simply not grow (off-rates are too high), grow slowly and well (just the right balance), or grow fast and uncontrollably (on-rates are too high). See the papers for more details, or ask me questions.

The basic aTAM and kTAM models assume that monomer tiles are present at a fixed concentration throughout the assembly. In cases where there are sufficiently many crystals forming that the monomer concentration is significantly depleted, this assumption fails. Correctly treating the depletion of resources shared by a distribution of crystal forms is a complex issues, and so Xgrow currently contains a hack: the user specifies that the flake being simulated is representative of some typical concentration [flake]=exp(-Gfc) of crystals, and thus every time a monomer accretes to the flake, [flake] is subtracted from the concentration of the monomer in solution. This leads to a balance developing, which sets a stable size for the crystal.

Xgrow can simulate many flakes simultaneously. This is really only interesting in the case described above, where the growth of crystals depletes the concentration of monomers. Although Xgrow's treatment of this case is a hack, nonetheless, one can see genuine effects such as winner-take-all (the first crystal to nucleate grows, depletes the monomer tile concentration, and thereby increases the critical nucleus size, making it harder for other crystals to nucleate -- so they don't) and Ostwald ripening (many crystals have nucleated; over time, the larger ones get larger and the smaller ones get smaller, because larger crystals have a higher number of bonds formed per tile -- a surface-to-volume effect).

Xgrow's main feature is that it is (usually) fast. All possible events in the Markov process (of which there could be S*S*N*F for F flakes built from N tile types in an S x S field) are stored in a quad-tree for logarithmic-time selection of the next event.

How to use it:

Xgrow has a confusing array of options, toggle switches, and doodads. You can "heat" and "cool" the reaction in real-time by changing Gse. You can view either the tile types (by color) or whether they have a mismatch with their neighbor ("err"). With the mouse, you can puncture a hole in the flake -- which can be fun!

In the case of multiple flakes, you can view a sample of them chosen at random to get some visual sense of the distribution. A button allows you to move from one flake to the next, or to jump to the largest one. You can save a flake, and load it back in later (using the command-line).

It's important to know that Xgrow keeps track of a special tile, called the seed. At the start of a simulation, this is just the first tile. Usually, the seed is fixed to be the same throughout time -- in this case, Xgrow will never allow that tile to dissociate. Alternatively, you can ask the seed to "wander" -- in which case, if the seed tile is chosen to dissociate, a neighboring tile is designated the seed. As you might infer from the name, the seed designation wanders around from tile to tile.

Another important feature is whether the flake can fission. To have a set of strictly reversible reactions in the model, the fact that only monomers can associate implies that only monomers can leave. This means that a flake which consists of two lobes, held together by a single tile with weak bonds to its two neighbors, cannot fall apart. If the linking tile were chosen to dissociate, the flake would be disconnected after the tile is gone -- and the reverse reaction (association of two large flakes) is not in the kTAM. So by default, such moves are not allowed. However, you can set the "fission" option, which allows these actions (at the cost of no longer being a well-defined reversible model -- i.e. it no longer satisfies detailed balance). Note, however, that for the two-lobed flake to break, the critical tile must dissociate by breaking all boths to both lobes, and thus the rate is much slower than the more realistic assumption (not implemented by xgrow) that breaking bonds to just one lobe would be sufficient for the flake to fall apart. (Recall that dissociation rates decrease exponentially with the number of bonds that must be broken.) Even more extreme, you can set the "chunk_fission" option, which allows pairs of tiles and even 2x2 blocks of tiles to dissociate together, if they are weakly bonded to the rest of the flake.

Xgrow is all best learned by poking around and by example, so we've included several. Try them all. See below.

Sample tile sets:

Several example tile files and commands to run simulations are included with the source code. For additional examples, see the supplementary materials for the above-mentioned papers.

Download and installation instructions:

All you need is four files: xgrow.c, grow.c, grow.h, and makecc.

Run the shell script makecc, after making sure the library and include paths are correct for your system, and there you have it: xgrow.

Try a few command-line examples from example-runs using the tile sets provided in tilesets. Run "xgrow --" to see help on the command-line parameters.

Xgrow is known to compile under Red Hat Linux 8 and under Mac OSX.

The following Xgrow releases are available, but you probably just want the most recent one: Sep 15, 2006 (tar file). Jun 3, 2004 (directory). April 9, 2004 (directory); Nov 17, 2003 (directory).

Please send questions and bug reports to winfree@caltech.edu. Until I have time to prepare complete documentation, this web page will be updated with information primarily in response to your queries. If you modify these files, either to add features or incorporate them into your own programs, please let me know!