The DNA and Natural Algorithms Group
The Xgrow Simulator
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 theoretically explore issues of error rates (e.g. "Simulations..." and "Proofreading..." and "...Nucleation..." ) and to help understand experimental results (e.g. "One Dimensional Boundaries..." and "...Sierpinski Triangles..." and "...Programmable Kinetic Barrier..." ). Xgrow is currently still 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.
- Renat Bekbolatov's Jgrow, written in 2003, which works in your web browser.
- Manish Gupta's group's Xtile program for performing tile set transformations, such as proofreading.
- Jack Lutz's group's suite of tile system simulators, generators, and transformers.
- Satoshi Murata's group's R-TAM model, with comparisons to real experiments.
- Other existing and potential users: Ashish Goel's group, Fabrizio Lombardi's group, Hao Yan's group, John Reif's group, Yuriy Brun, Pablo Moisset de Espanes, Robbie Schweller.
What Xgrow 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
The tinybox feature allows you to simulate a situation where there is a fixed volume and to follow all of the flakes in that volume (the volume should be tiny, as the name indicates, or the simulation would use up too much memory.) The syntax of this feature is
where v is the volume, in liters.
tinybox simulates the effects of tiny volume. When tinybox is set, the simulation then begins with 0 flakes. Flakes consisting of two tiles (which could be double tiles, for up to 4 squares) at a rate of k_f*2*num_free_tiles*num_free_tiles, where num_free_tiles is the number of free tiles in the box, given by [total concentration]*volume*A, where concentration is in Molar and volume in liters, and A is Avagadro's number. The factor of 2 is a combination of the number of orientations 2 tiles could attach (4), and the symmetry (which tile is left or right. ) Flakes are removed when they are reduced to a single tile.
Note that tinybox does not have a limit on the number of flakes, so care must be taken to not set the volume too large or xgrow will eat all the computer's memory. If tinybox is set too small, also, the box will contain fractional tiles (note the number of tiles in the rate of flake creation is not necessarily an integer), so weird things could happen then too. Tinybox will work with Gfc, which can be adjusted so that Gfc corresponds to a single tile. You can therefore use xgrow for an exact simulation (subject to the caveats above) of a very small volume. This example is a tinybox simulation that simulates the 4 wide zig zag ribbon tile set during a linear anneal zig-zag-4w.tiles. The tinybox option makes most sense for investigating nucleation, where the initiation and removal of flakes (and growth of a small number of flakes) is the behavior of interest . It doesn't simulate a large enough box to make it useful for other purposes in my opinion but that may change with increased computing power. It's also highly inefficient - an optimization that calculated the rate of 3 tile flakes and simulated that process directly would speed things up, but would be complex to implement.
Xgrow is all best learned by poking around and by example, so we've included several. Try them all. See below.
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.
Suppose you'd like to show Xgrow movies to someone, for example in a talk. There are three possibilites. (1) Run the program in real-time, and show it all happening with details subject to the gods of random numbers. (2) Use a program such as Snapz X Pro or Copernicus/iMovie to record Xgrow's window into a "canned" movie. (3) Xgrow can output movie frames in a format readable by MATLAB. Write a MATLAB script that pretties it up to be utterly gorgeous. Send us the script.
The most common error in Xgrow (as of 3/1/2009) is that if you ask for a window larger than your computer screen (e.g. "size" or "block" is too large) then Xgrow will crash with a "BadMatch" error. Sorry. Note that this should now be partially corrected.
The second most common error is that a tile file doesn't parse properly. Every now and again, our parse is ridiculously sensitive to spaces and things like that. Sorry.
Download and installation instructions:
To install, download the xgrow package and uncompress it. For most uses, it should be enough to do "make." This will produce an xgrow binary in the package directory.
Try a few command-line examples from example-runs and example-runs-talks 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, under Mac OSX and with Cygwin under Windows. Versions prior to March 1, 2011 may have problems compiling on 64-bit operating systems.
The following Xgrow releases are available, but you probably just want the most recent one:
- Feb 26, 2013 (tar.gz file).
- Nov 29, 2011 (tar.gz file).
- Mar 1, 2011 (tar.gz file).
- Mar 7, 2009 (tar.gz file).
- Sep 15, 2006 (tar.gz file).
- Jun 3, 2004 (directory).
- April 9, 2004 (directory);
- Nov 17, 2003 (directory).
In the latest release, there are a few options available:
- xgrow comes with a test module for adding new features. The testing module attempts to determine whether the current simulation obeys detailed balance. To compile xgrow with this feature, which requires glib and openssl, you can do make xgrow-test
- xgrow allows up to 2^16 tile and bond types. If you are using fewer than 256 of each and would like xgrow to run a bit faster, you can use the xgrow-small binary instead of the default.
Xgrow was written and is maintained by Erik Winfree, Rebecca Schulman, and Constantine Evans, with some contributions from Shaun Lee and Michael DeLorimier. Please send questions and bug reports to email@example.com. 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!