Cell Automata: Simple rules that generate complicated patterns

& Also other kinds of theories about generation of geometric patterns in embryos

Simple signaling rules often can generate complicated geometric patterns, and sometimes computers are the only practical way to find out what patterns can be produced by what rules.

A good way to start is with some of the simplest possible rules by which the behavior of any kind of unit can control each other's properties. The biological meaning of the units could be molecules, or cells, or something else. As part of the Manhattan Project (that developed atomic bombs), "cellular automata" were invented as a very abstract means to study pattern generation. To many students, cellular automata seem at first to be unrealistically simple and non-biological. But give them a chance, you might become addicted to them.

A "Cell Automata" program that runs on PCs is included on my web pages, down below the listings of "courses" [link]. Just click on it, and it will run on your computer. This program is written in Java by Andy Wheeler, who took this course a few years ago. It is a re-write of a program that I wrote in Pascal for Macintosh computers. The Mac version is available on some of the web pages for the course "Biology 166" (which has now been given a new number, like all courses).

Before trying them, you should first click where is says "Cell Automata instructions", which produces a diagram what you see when you run the actual program, including the menus that control the running of the program.

Cell automata use a field like a checker-board, in which numerical values are assigned to spatial positions and then repeatedly re-calculated based on the values of each location's neighboring positions according to a set of rules. Each square being assigned a value of either one (="filled") or zero (="blank"). You start out with an initial pattern of some squares filled and other squares empty, and you have a set of rules for calculating the next "generation". For historical reasons, the set of rules that has been studied most is the one in which any square that has two filled neighbors will stay the same in the next generation as it is now; and any square that has 3 filled neighbors will become filled (whether it was filled in the current generation, or not); but any square that has 0 filled neighbors, or 1, or 4, 5, 6, 7 or 8 filled neighbors will become blank, whether or not it is now filled. This set of rules is called the "Game of Life", and before desktop computers became available, many billions of dollars worth of mainframe computer time was used testing effects of this "Game of Life". It was invented by a Cambridge mathematician (John Conway), and popularized by Martin Gardner in his monthly article in "Scientific American" magazine (back when it was still a good magazine!) Many shareware programs are available on line for this particular cell automaton. rules (3->filled; 2->same; any other number->empty)

On this program for this course, the pull-down menu allows you to chose this set of rules with one click. The plan was to have maybe 10 alternative sets of rules, each of which has some interesting consequences, on this pull down menu. But the column of menus on the left allow you to set 4 alternative consequences for each of nine possible numbers of neighbors (i.e. no filled neighbors, one filled neighbor, two filled neighbors, etc. up to eight filled neighbors). Can you calculate the total number of alternative sets of rules? Hint: it is either 4 to the ninth power, or nine to the fourth power. There are almost a quarter of a million different combinations; so when you find a set of rules that produces some nice effect, then I advise you to write down the rules, because otherwise you may never find them again (or you would need many hours of testing).
The program also has pull down menus to produce a random distribution of filled and blank squares, and lets you decide what fraction should be filled. 50% is the default condition. You can also create gradients of % of filled cells.

Other cellular automata are used in computer simulations of chemical reactions, gas flow ("lattice gases"), neutron chain reactions and who knows what else.

Dozens of books and thousands of research papers have been written about cellular automata. There are many variant forms: you can have hexagonal and triangular neighborhoods as well as square ones, you can decide to count only the 4 orthogonal neighbors (above, below, left, right) and omit the diagonal ones; or you can also count positions some distance away; for example, I wrote a Mac program that counts 24 neighbors for each square. In addition, the number of different alternative values that each "cell" can be more than 2 (filled or empty); they can have values of 0, 1, 2, 3 etc. Furthermore, the recalculation rules can be based on something other than simply adding up filled neighbors. Computers are good at this sort of thing. If the numerical value of each square tends to approximate the average value of its immediate neighbors, then the result will be a simulation of ordinary diffusion. If the calculation of new generations is based on the ratio of near neighbors to far neighbors (with near ones stimulating and far ones inhibiting), then the system's behavior will generate patterns like those of reaction diffusion systems (such as those of Turing) that will be discussed below. You can simulate propagated changes, like nerve impulses, or waves of calcium permeability in fertilized oocytes, by means of the following combination of rules (that your particular PC computer program does not allow you to run. Here are these rules: each square can have a value of either 0 or 1 or 2 or 3; any square having a value of 1 will always become a 2 in the next generation; any 2 will become a 3; and any 3 will become a 0; but any 0 that is next to a 1 will itself become a 1 in the next generation. Can you see what the net behavior will be? Can you see why it will "simulate" propagation of nerve impulses? (What corresponds to the refractory period?) It can also simulate forest fires!

Cellular automata can also be one-dimensional (i.e. along a line, usually with sequential generations being represented below each other down the page), two-dimensional (like the game of life) or 3-dimensional (with neighbors above and below the plane of the page).

The two examples above were obviously initiated at single "filled" squares. But what if the initial pattern contained some kind of random mixture of filled and empty squares? Here is an example:

Which of the sets of rules does the cellular automaton above seem to be obeying?
In what way is the initial pattern non-random?
The color patterns on several species of cone shells happens to have very much this particular pattern.
What do you conclude from this? What might be the explanation? Are there alternatives?
The major guru of cellular automata these days, especially one-dimensional cellular automata is a British whiz kid named Stephen Wolfram (who is also the author/owner/president of Mathematica, a set of expensive software for doing calculus and other higher math). Primarily based on one-dimensional cell automata, Wolfram wrote an enormous long book titled "A New Kind of Science", which he claims is the most important breakthrough in all of science since Newton! If you experiment with different sets of rules, you find hundreds or even thousands of different behaviors, but these fall into a few main patterns including
a) homogeneity
b) patterns with internal self-similarity, analogous to fractals
c) chaos.

One of my favorite facts about cellular automata is that if the rules are these:
Fill if you have an odd number of neighbors; Empty if you have an even number (or zero neighbors).The result is to duplicate the original pattern infinite numbers of times!!
In fact, this is only a special case of a more general theorem which is that if the rules are of this form: Fill if sum of neighbors modulo any prime number; otherwise become empty.
(the "fill if odd, empty if even" rule above is the special case where the prime number is 2)
Rules of this class will multiply duplicate any initial pattern, for 1, 2 or 3 dimensional automata, and for any definition of what is a neighborhood.
Don't panic. You will not be tested on anything but the basic idea "what are cellular automata", and what are some of the kinds of phenomena that they can simulate.

Developing embryos often contain concentration gradients of certain chemicals, or sometimes gradients of metabolic rates. Gradients of adhesion molecules and receptors in the brain and retina have been mentioned, and so have gradients of the concentrations of hox gene proteins (which are a class of transcription factor).

Almost all biologists assume that diffusion gradients are the most likely cause of gradients. However, one lesson that we can learn from cell automata is that gradients can be generated in other ways. Imagine a class full of students, all of whom always sit in the same chairs in a given class. Also imagine that these students are very fashion-conscious, for example regarding hair length. They therefore want to cut their own hair to whatever length the students around them have. Lastly, also imagine that a student who sits in the front row has really long hair, and somebody in the back row is in ROTC or something, and has a "crew cut" (Imitating the hair cuts of the Prussian soldiers in the Franco-Prussian War of 1870! Hardly anybody realizes that's why the US military requires short hair.)

Over time, a gradient of hair length would develop, with longer hair in the front, and crew cuts in the back. A believer in "positional information" would believe either that the hair must be diffusing from front to back, or (more likely) that some "morphogen" chemical must be diffusing from front to back, that stimulates growth of hair in proportion to the local concentrations of this diffusing chemical signal. After all, what else could it be!

Transcription factor proteins are too large to diffuse through plasma membranes, from cell to cell. Therefore, most embryologists assume that concentration gradients of these proteins must result from diffusion gradients of some smaller molecule, that is probably hydrophobic, such as retinoic acid. The same beliefs are held about concentration gradients of cell surface proteins.

In fact, it is quite possible that concentration gradients may be controlled by diffusion gradients. The point is that isn't the only possibility. Some kind of molecular conformism (like the imaginary students with the different hair lengths) gives us a whole range of alternative possible mechanisms.



back to syllabus

back to index page