Sunday, September 27, 2009

Algorithmic Botany

Plants have proven to be fertile ground for modeling morphogenesis. Much of the pioneering work was carried by a professor of Computer Science at the University of Calgary named Przemyslaw Prusinkiewicz, and his many students and collaborators. Early in his career, Prusinkiewicz, who usually goes by the more English-friendly nickname Shemeck, teamed up with the Hungarian botanist Aristide Lindenmayer, who had invented the class of grammars known as L-systems to serve as a systematic language for describing plant shapes. If your only association with the concept of grammar relates to conjugating verbs, you should know that for linguists, and later for computer scientists, grammars are powerful, formal, quasi-mathematical systems for describing transformations of symbolic structures. In the 1950's the linguist Noam Chomsky had described a hierarchy of grammars of increasing complexity which he used to analyze the organization of sentences in human languages. If you think back to your grammar lessons, you will recall that sentence structures are represented by tree diagrams. Lindenmayer's insight was that grammars could describe the tree-structure of, well, trees, as well as bushes and other plants. A grammar works by applying rules that rewrite parts of a sentence. A simple rule for building a tree might be fork a branch. If you start with a single vertical branch (i.e., a trunk), and apply this rule to it, you will create a trunk with two branches -- a Y shape. If you now apply the rule to the branches you will have a trunk with two internal limbs, each carrying two branches. If you keep going, you will make a tree of progressively greater complexity.

Shemeck's innovation was to marry L-systems to computer graphics, which allowed computers to generate plant shapes. Here's an example, showing the computer-generated plant image, and below the symbolic representation of the grammar that it is based on.  Shemeck early computer graphic work was published in a book, the Algorithmic Beauty of Plants, that is a classic in the field of e-morphogenetics: perhaps its only coffee-table book to date. The book is now freely available in electronic form at Algorithmic Botany, the web site for Shemeck's lab, along with more recent images and publications. The web-site also has Quick-Time animations that show the temporal behavior of these models. Although at first the focus of the work was primarily on producing realistic plant graphics without much concern for biological realism, over time more biology was layered on: for example, plant hormones emmited in one part of the plant and sensed in another to trigger flowering. The modeling was mostly at the level of structural elements like leaves and branches, as opposed to cells or genes. However chapter 7 describes some explorations in the application of L-system graphics to 2 and 3-dimensional systems of cells; some examples are show below.

Others have gone on to apply L-systems for science and art, see for example Laurens Lapre's gallery; the sample below is called an airhorse. He has a program called LParser for experimenting with L-systems; it generates VRML output so you can zoom, pan, rotate, etc.

Saturday, September 5, 2009

Questions of Selection and Complexity

I am exercising droit de bloggeur and responding to Bob's comment on my last post in the blog itself, since my response overran Blogger's length limit on responses.

Hi Bob.  Thanks for the comment, and for tip on Andy Goldsworthy. I was not familiar with his work, but Google pulled some interesting U-tube clips and other material.

I read two questions in your comments -- not sure if they are same ones you intended... One is the intensity of morphogenetic selection pressures, and whether much morphogenetic variation could be selectively neutral. That put me in mind of an interview on NPR's Fresh Air the other day with Douglas Emlen, an animal behavior biologist who studies dung beetles.
 (Tangent: could he be related to Professor Steve Emlen whom I learned animal behavior from at Cornell as an undergraduate, a generation earlier?) He describes the intricate morphology of the weapons that the male dung beetles are adorned with, which they use to lock each other out of the tunnels that provide access to both food (i.e., dung) and females deeper in the tunnels. These horn or antler-like appendages vary tremendously in form from one variety of dung beetle to the next. The temptation is to dismiss these variations as arbitrary and selectively neutral, but as Emlen has delved deeper into the subject, so to speak, he has discovered complex tradeoffs between investment in different aspects of the weapons and other body parts, given that the beetle has only so much material to work with in building a body. I think the answer to the question of selective pressure on morphology, like so much else in biology, needs to be answered on a case by case basis, and with due respect for the complexity of Nature's decisions. Note also that it is very hard to prove experimentally that a design decision has no selective effect; you would have to alter it without causing any disadvantageous side-effects, and show that the manipulation had no effect on reproductive success over multiple generations: not a simple experiment to conduct.

The other question I took from your comments is whether the processes generating morphogenetic variation are simple or complicated. I think that is partly in the eye of the beholder, or the programmer. There is a large literature on computational models of pattern formation, going back to Turing's pioneering work on reaction/diffusion equations. I suspect one reason there has been a lot of work on these systems is that they are easy to program. Dividing cells in 2 or 3 dimensions are more challenging in terms of both the geometry and physics involved. Whether the processes are more complex from the standpoint of the cell's program is less clear. The cell gets its geometry and physics for free, provided by the world, whereas the programmer has to put these into the model, and that takes considerable work. Given an appropriate simulator that took care of that stuff, are the rules for generating, say, a tabby cat's fur pattern, a zebra's stripes or a leopard's spots more or less complicated than the rules for generating spiral cleavage or gastrulation in an embryo, or the variation in shapes of teeth or bones?
This depends in part on how you choose to define and measure complexity. One simple metric, as I alluded to in an earlier post, is the number of tunable parameters in your model. Reaction / diffusion systems will have parameters controlling the rates of production, diffusion, and destruction of 2 or 3 morphogens, so perhaps on the order of a dozen parameters.  To specify the difference in shape between a canine tooth and a molar probably requires at least that many. For a whole set of teeth, there are probably hundreds of parameters; for a whole skeleton, probably closer to a thousand, even allowing for the fact that ribs resemble other ribs, vertebrae are similar to other verterbrae (though there are differences within and between cervical, thoracic, lumbar, etc.), a left femur is a mirror-image of a right femur, etc., all of which reduce the number of independent parameters. Given that current estimates of the total number of genes in the human genome are in the 20-30 thousand range (though this number has been notoriously unstable and also difficult to interpret), if we naively map "parameters" to "genes" (very naive) then the skeletal shape would seem to require a good fraction of the total parameters, whereas coat color would require only a small bit. For example in butterflies a single gene is responsible for significant variation in patterning.
(Source article)

So I think it may be possible to give a quantitative answer to your question about the relative complexity of shape variation and surface patterns, and the answer is likely to be that, even after discounting the complexity of modeling geometry and physics, surface patterns are the icing on the cake, but the cake recipe is a good deal more complicated than the icing. However I agree that the genetic changes underlying differences between species in pattern or form could be equally small, with a single gene change having dramatic effects on either. I hope to discuss that issue more in future posts.