Multicellular Logic Circuits, Part III: A Model

September 26, 2007

In Part I and Part II of this series, I discussed genetic algorithms and why we might want to create artificial machines that begin life as a single cell, and develop into networks of identical communicating cells. In this post, I want to begin describing a model that works along these lines.

The model is a highly stylized and simplified cartoon of biological multicellular organisms. It my attempt to make the simplest model possible that captures the essence of what is happening in biology. So understand that biology is more complicated than this model; but the goal is a model stripped down to those essential elements that cannot be taken away if one wants something that looks like life. Thus, the model is proposed in the spirit of the Ising model of magnets in statistical physics; the simplest model that captures the general behavior we are looking for.

The first question is what do we want our machine (or “circuit” or “network” or “organism”; I will use these terms interchangeably) to do? As is quite conventional in hardware design, I will presume the organism receives some input signals from the world, and it is supposed to produce some desired output signal, which depends on the inputs it has received at the current and previous times. Thus, the circuit should in general be capable of creating memories, that lets it store something about previous inputs.

model001.png

The organism begins its life as a single cell, and then has two phases in its life, a dynamic “embryonic” phase and a static “adult” phase. During the embryonic phase, the cells in the organism can undergo developmental events, primarily cell duplication, but also perhaps cell death or cell relocation, to sculpt out the final network of communicating cells. After the embryonic phase is complete (say after a fixed amount of time has passed, or some signal is generated by the circuit) the adult phase is entered. The network is static in structure during the adult phase. It is during the adult phase that the network can be tested to see whether it properly computes the desired input-output function. The figure above is a pictorial representation of the model that hopefully makes clear what I have in mind.

Each of the cells in the network will have an internal structure, defined primarily by “logic units” which send signals to each other. The computations performed by the organism will simply be the computations performed by the logic units inside of its cells. The details of what the logic units do, and how they are connected to each other, is specified by a “genome” or “program” for the organism.

Look at the figure below for a peek inside an individual cell in the model. Each cell will have an identical set of logic units, with identical connections between the logic units.

cell2002.png

The logic units compute an output according to some fixed function of their inputs. They transmit that output after some delay, which is also part of their fixed function. The output of one logic unit will be the input of another; they send “signals” to each other.

These signals are of various types (see the above figure). The first type of signal, called a “factor signal,” will always go from a logic unit to another logic unit in the same cell. The second type of signal, called an “inter-cellular signal,” will always go from a logic unit to a logic unit in a different cell. The third type of signal, called a “developmental output signal,” will not actually go to another logic unit, but will be a signal to the cell development apparatus to perform some important development event, such as duplication or programmed cell death. Finally, the fourth type of signal, called a “developmental input signal,” will be used by the cell development apparatus to signal that some type of cell development event has occurred, and will serve as an input to logic units.

Remember that initial cell (the “fertilized egg”) will need to have a set of logic units that enable it to automatically create the adult network, so it must effectively contain the instructions for development as well as for the adult circuit. It might seem hard to imagine that this can work, but it can. In the next post in this series, I will discuss in more detail the process of development in this model, and then we will be in position to look at some interesting multicellular circuits that I have designed.

If you don’t want to wait, you can visit this page to find a PDF and a PowerPoint version of a talk I gave on the subject at a conference in Santa Fe in May 2007, although unfortunately, it might be hard to decipher without my explanation…

Magic the Gathering: Lorwyn Prerelease

September 25, 2007

If your interest in Magic the Gathering has been piqued by one or another of the previous posts here, you might want to know that this coming week-end, September 29 and 30, is the perfect time to attend your first Magic tournament, because a new expansion, named Lorywn, is having its “prerelease.” A prerelease is a kind of opening day for the new expansion, when the cards are seen and played with for the first time (although they won’t be legal for other tournaments until the official release two weeks later.)

Prereleases are much more informal than ordinary tournaments, and beginners are very welcome (not that they aren’t at other tournaments). In the ones around Boston, typically 200 players will be there. You can arrive at any time on Saturday or Sunday, as new tournaments are started as players arrive. Your wait will be shorter if you arrive early on Saturday though.

You can choose to play in a “sealed deck” tournament, where you construct your deck from a pool of cards given to you, or you can play with a pre-constructed “theme” deck. If you’ve never played before at all, the theme deck option is a pretty good choice, and will also leave you with a deck that can be your starting point for constructed tournaments.

For all the details, you should go the this Lorwyn Pre-release primer page from the official Magic web-site, and this Prerelease schedule.

If you’re going, whether or not you’ve had Magic experience, you might want to check out the rules about “Planeswalkers,” a new card type being added in Lorwyn.

And if you want to know what all the cards in the Lorwyn set will be before you get there, there are spoilers available at MTG Salvation (some players love these spoilers, others hate the idea of them.)

If you can’t make it this weekend, there are also Release tournaments in a couple weeks (October 12-14), although those tournaments are on a much smaller scale.

World Chess Championship 2007

September 24, 2007

Click on picture above to expand

The World Chess Championship is being held now in Mexico City. It began on September 12, and is scheduled to finish on September 30. Unlike some of the World Championships of the past, this one is a tournament between eight players rather than a match between two. The eight players are Vladimir Kramnik (the current world champion), Viswanathan Anand (the world’s highest rated player), Levon Aronian, Alexander Morozevich, Peter Leko, Boris Gelfand, Peter Svidler and Alexander Grischuk.

In the picture above Kramnik (to the right) is playing Anand (to the left), while Gelfand (between the players) and Grischuk (behind Anand) observe. All of these players play at a fantastically high level (the general level of human chess players has steadily improved with time), but sadly fewer people pay attention now that computers play even better.

The only one of these grandmasters that I’ve personally played against is Peter Svidler, in the 1995 New York Open. I was doing very well in that tournament, and had a chance to win a large prize, but then I played Svidler with the Black pieces, and he crushed me. The memory is actually not so bad, because it was very interesting to play him and to talk to him afterwards (he was 19, but it was already clear that he could potentially challenge for the world championship), and I nevertheless achieved a norm for my international master title in that tournament.

The World Championship tournament is a double-round robin, so it will last 14 rounds. After nine rounds, Anand leads with a record of 6-3, followed by Gelfand with 5-4, Leko, Grischuk, and Kramnik with 4.5-4.5, Aronian and Morozevich with 4-5, and Svidler with 3.5-5.5. Today Kramnik plays Anand with the White pieces; he’ll need to win to have much chance of catching him. But even if Kramnik does not win, he’s guaranteed a match against the world champion in 2008.

(UPDATE: Anand held Kramnik to a hard-fought draw in round 10, and then followed up with a win against Morozevich in round 11, so with three rounds to go, he holds a substantial 1.5 point lead over Gelfand, and looks likely to become the next World Champion.)

(UPDATE 2: Anand has won the world championship, with Kramnik and Gelfand tying for second place. The cross-table of the results is below):

WCh Mexico City MEX (MEX), 13-29 ix 2007               cat. XXI (2752)
----------------------------------------------------------------------
                                     1  2  3  4  5  6  7  8 
----------------------------------------------------------------------
1 Anand, Viswanathan     g IND 2792 ** == == == 1= =1 1= 1=  9.0  2848
2 Kramnik, Vladimir      g RUS 2769 == ** == =1 == 10 =1 ==  8.0  2799
3 Gelfand, Boris         g ISR 2733 == == ** == == 1= 11 =0  8.0  2804
4 Leko, Peter            g HUN 2751 == =0 == ** == =1 0= =1  7.0  2751
5 Svidler, Peter         g RUS 2735 0= == == == ** 0= == =1  6.5  2725
6 Morozevich, Alexander  g RUS 2758 =0 01 0= =0 1= ** == 01  6.0  2700
7 Aronian, Levon         g ARM 2750 0= =0 00 1= == == ** =1  6.0  2702
8 Grischuk, Alexander    g RUS 2726 0= == =1 =0 =0 10 =0 **  5.5  2675
----------------------------------------------------------------------

To learn more about the tournament, you might start with Macauley’s rather artistic coverage of the first game between Kramnik and Anand in round 3. More videos of this type head are at macauley.blip.tv. You might also head over to the excellent chess web-site The Week in Chess for news and annotated game scores, and the ChessVibes blog for many on-the-scene videos (often including instructive post-game interviews with the players) and the games in an easy-to-use Java player (I already pointed to some remarkable videos from earlier this year at ChessVibes in a previous post.) But perhaps the most interesting coverage of the World Championship tournament for intermediate or stronger chess players is by the Internet Chess Club, which has a team of strong grandmasters presenting annotated game videos.

Talking about Probabilistic Robotics

September 23, 2007

Sebastian Thrun is a professor of computer science and electrical engineering at Stanford, and director of the Stanford Artificial Intelligence Laboratory. He was the leader of Stanford’s team which won the $2 million first prize in the 2005 DARPA Grand Challenge, which was a race of driver-less robotic cars across the desert, and also leads Stanford’s entry into the 2007 DARPA Urban Challenge.

One of the ingredients in the Stanford team’s win was their use of “probabilistic robotics,” which is an approach based on the recognition that all sensor readings and models of the world are inherently subject to uncertainty and noise. Thrun, together with Wolfram Burgard and Dieter Fox have written the definitive text on probabilistic robotics, which will be a standard for years to come. If you are seriously interested in robotics, you should read this book. (The introductory first chapter, which clearly explains the basic ideas of probabilistic robotics is available as a download here.)

The Laboratory of Intelligent Systems at the Swiss École Polytechnique Fédérale de Lausanne (EPFL) hosts the superb “Talking Robots” web-site, which consists of a series of podcast interviews with leading robotics researchers. I noticed that the latest interview is with Thrun, and liked it quite a bit; it is well worth downloading to your iPod or computer.

You can watch Thrun speaking about the DARPA Grand Challenge at this Google TechTalk.

WordPress.com

September 21, 2007

When I tell my friends about this blog, they often want to know more about how it’s constructed. So I thought I’d talk a bit about the wordpress.com software that I use, and some tips I can pass on after seven weeks of using it.

First of all, it’s important to distinguish between wordpress.org and wordpress.com. WordPress.org is an open-source project for the wordpress blogging software; you can download it, and then set it up on your own web-server (it typically costs $7/month to set things up with a web-hosting company) and you’ll have full control over everything in your blog. WordPress.com is an easier alternative; they’ll host your web-site for you for free, but you don’t get absolutely complete control over what you can do. You can learn more details about the differences here.

I chose to use wordpress.com, because their features were basically what I wanted, but I wanted to use my own domain name (nerdwisdom.com) instead of the default nerdwisdom.wordpress.com. That extra feature costs $15/year; for that price, wordpress.com pays for your registration and handles redirection transparently. I recommend this option, because it means that if you ever want to change the way you do things later (e.g. switch to wordpress.org or some other service, which is not so hard because wordpress.com lets you “export” you entire blog as an XML file) you won’t have to change the url for your blog.

A nice bonus that happened when I paid for this option was that wordpress.com walked me through the process of setting up a Google Apps account for nerdwisdom.com. This is quite nice; I actively use Google’s Page Creator application, and there are other useful features and applications including Gmail accounts with the nerdwisdom.com domain.

Building your blog on wordpress.com is done through a web browser; you won’t need to download anything, and you can work on multiple computers with multiple operating systems. I recommend that you use the Firefox browser, it is better supported than the others. You write up your posts using an editor that can display either a WYSIWYG interface or your HTML code; it’s pretty easy to use if you have any experience with HTML, and I’d guess it’s not too bad even without any such experience. WordPress.com comes with a whole lot of different “themes” for changing the look of your blog, but I’m pretty happy with the default theme.

You can buy some “upgrades” with wordpress.com that give you some more control over your stylesheet and let you store more than 50 MB of data. At the rate I’m going, I’ll need to spend $20/year for the extra storage once I’ve done this for a couple years.

There are a few important restrictions with wordpress.com. Probably the most important is that you may not run advertisements (wordpress.com says this may change in the future). If you want to run ads you probably want to either use Google’s blogger.com service or wordpress.org or maybe typepad.com. You can also run advertisements on wordpress.com (and get other benefits) if you are a “VIP” blog, but to get that service you need to pay $300/month and have in the neighborhood of 15,000+ page-views/day, which is a lot.

I experimented just a little with blogger.com, and it seemed quite clunky to me in comparison with wordpress.com, but maybe that was just because I was already used to wordpress.com. My impression from what I have read is that wordpress.com is the more powerful system. I don’t have any experience with typepad.com at all. Apparently, blogger.com and typepad.com were the first entries into this field, but wordpress.com has now surpassed typepad.com in popularity, and is the second most used blogging software, and gaining on blogger.com.

Another restriction of wordpress.com is that it will not host Javascript widgets or Java applets. I wanted to put up a Java applet for my post on simulating the Ising model in NetLogo, so I put it on a page hosted by Google Pages instead, and just linked to the page.

One nice feature of wordpress.com is that they will put your posts on their front page if they think that they are high quality. I have no idea what algorithm they’re using to make that decision, but my posts are showing up pretty often, which drives some extra traffic my way. Speaking of traffic, you can access pages which give you a lot of information about how much traffic you’re getting and where it’s coming from.

Another nice thing about wordpress.com is their FAQs and forums. I use the FAQs a lot; nearly every time I have had a question, it’s been answered there.

Now a couple of tips for people already using wordpress.com. I found that Windows and Mac OS X browsers were using different fonts for my pages (the Mac OS X fonts were smaller than I liked), but you can fix this by using the HTML code “<font size=”2”> …. </font> in all your posts. I am also a big fan of the text widgets that let you put all sorts of things in your side-bars, because you can include HTML code.

You should also make sure to turn off the very annoying Snap preview feature, which is on by default.

If you’re interested, it’s easy as pie to set up an account and give it a whirl. I’m happy with the choice I made.

Artificial Intelligence: A Modern Approach

September 20, 2007

images.jpeg

“Artificial Intelligence: A Modern Approach,” by Stuart Russell (professor of computer science at UC Berkeley) and Peter Norvig (head of research at Google) is the best-known and most-used textbook about artificial intelligence, and for good reason; it’s a great book! The first edition of this book was my guide to the field when I was switching over from physics research to computer science.

I feel almost embarrassed to recommend it, because I suspect nearly everybody interested in AI already knows about it. So I’m going to tell you about a couple related resources that are maybe not as well-known.

First, there is the online code repository to the algorithms in the book, in Java, Python, and Lisp. Many of the algorithms are useful beyond AI, so you may find for example that the search or optimization algorithm that you are interested in has already been written for you. I personally have used the Python code, and it’s really model code from which you can learn good programming style.

Second, if you haven’t ever visited Peter Norvig’s web-site, you really should. I particularly recommend his essays “Teach Yourself Programming in Ten Years,” “Solving Every Sudoku Puzzle,” and “The Gettysburg Powerpoint Presentation.”

Cynthia Kenyon’s Long-lived Worms

September 19, 2007

Professor Cynthia Kenyon is a pioneering researcher in the biology of aging. A couple years ago, she presented a Harvey Lecture at Rockefeller University on her work; that lecture was similar to the one I heard her give at last year’s Woods Hole summer school course on aging. I think that it’s worth highlighting some of the things she has to say.

“We began our studies in the early 1990s. At that time, and for years before, many people assumed that aging was a haphazard process, not subject to regulation. Our tissues just break down, and we die. But the more I thought about it, the more I started to question this view. A mouse lives two years, whereas a bat can live 30 years or more. A rat lives three years; a squirrel, 25. These animals differ by their genes, so there must be genes that affect aging. Also, nothing in biology seems to “just happen”; everything seems to be regulated, often in quite an extraordinary way.

My experience as a developmental biologist sharpened my thoughts about aging. People were once very skeptical about looking for developmental genes. Treating frog embryos with acid can produce a second head, and inhibiting pyrimidine synthesis in flies produces small wings, so many people thought that genes affecting development would also affect things like the Krebs cycle, or pH. They were wrong. There is a dedicated regulatory circuitry for pattern formation. In addition, many people thought that developmental mechanisms would differ completely in different kinds of animals, but again they were wrong. In fact, the degree of evolutionary conservation is striking. So it seemed to me that something as fundamental as aging might also be subject to regulation. Maybe there would be a molecular longevity “dial,” like a thermostat, that is universal but set to run at different rates in different kinds of animals. The dial would be turned up in mice (which age quickly) and down in bats (which age slowly). I wrote extensively about this in the 1990’s (Kenyon, 1996, 1997), suggesting, for example, that aging might be regulated by something like the heterochronic genes of C. elegans, which control the timing of developmental events.”

kenyon001.jpg

Click on figure to expand

“Since we obtained such a long lifespan when we killed the gonads of daf-2 mutants, we wondered what would happen if we reduced daf-2 activity even more in these animals. Using a stronger daf-2 allele would run the risk of triggering dauer formation, but we found that we could dodge dauer formation if we subjected long-lived daf-2(e1368) mutants to daf-2 RNAi soon after hatching. When we did this, and killed the gonads as well, the animals lived six times as long as normal (Fig. 2.16). Incredibly, the animals remained healthy and vigorous for a very long time. In fact, when Nuno Arantes-Oliveira, the graduate student doing this work, showed two 144-day-old animals, still moving around, to other lab members and asked them to guess the age of the animals, they reckoned five days! [For a movie of these two spunky animals, see Arantes-Oliveira et al. (2003).] It is remarkable that with just a few minor changes, it is possible to produce such an enormous lifespan extension (the equivalent of 500 years in humans) with no obvious effect on the vitality of the animals.”

“If we really could live longer, remaining youthful and disease-free, why haven’t scientists been working on this already? First, as I said, they didn’t think it was possible, since aging was thought to be unruly and random. Second, and even more important, we haven’t had any role models to emulate, primates that shoot rockets to the moon, go to the opera, and live for 300 years. If we did, we might already know how to stay young and live much longer than we do. We invented airplanes because we could see birds could fly. Now that we know that animals can live longer than they do, perhaps soon we will learn how to extend our own youthfulness and lifespan. It may not be that difficult. Since there are short-lived and long-lived insects, birds, and mammals, longevity must have evolved not just once but many times. Maybe the path to increased longevity is in us already, in the form of a network of genes and proteins, waiting to be nudged in just the right way.”

I recommend you read the whole thing–it’s quite readable, and the scientific results are breathtaking.

And if you’re interested, here is a video from earlier this year with Charlie Rose interviewing a panel of biologists about the remarkable progress that has been made in aging research recently. Members of the panel include Kenyon and Lenny Guarente, another leader in the field whose book I previously reviewed.

Multicellular Logic Circuits, Part II: Cells

September 18, 2007

In my post “Multicellular Logic Circuits, Part I: Evolution,” I discussed evolution and genetic algorithms; I want to continue that discussion here.

There are two salient facts of biology that are completely inescapable. The first is that all organisms are shaped by the process of evolution. The second is that all organisms are constructed from cells.

Furthermore, all complex multicellular organisms begin life as a single cell, and undergo a process of development through cell division to mature into an adult. And no matter how different any two organisms may be on the gross macroscopic level that we are used to, inside their cells the chemical processes of life are fundamentally very similar.

080534635x.jpg 0815340729.jpg

Thus it is no accident that the titles of the two leading textbooks in molecular biology are The Molecular Biology of the Gene by Watson, et. al. and The Molecular Biology of the Cell by Alberts et. al. [These are both great books. This link to the first chapter of MBOC is an excellent entry point into modern biology. And if you are serious about learning biology, I also strongly recommend the companion Molecular Biology of the Cell: A Problems Approach, by Wilson and Hunt, which will force you to think more actively about the material.]

It therefore seems reasonable that if we want to construct artificial systems that achieve the performance of natural ones, we should consider artificially evolving a system constructed from cells.

Although there are typically many different cell types in a mature multi-cellular organism, all the different cells of the organism, with the exception of sperm and egg cells, share an identical genetic specification in their DNA. The different behavior of cells with identical genetic specifications is the result of the cells having different histories and being subjected to different environments.

More specifically, the behavior of a biological cell is controlled by complex genetic regulatory mechanisms that determine which genes are transcribed into messenger RNA and then translated into proteins. One very important regulatory mechanism is provided by the proteins called “transcription factors” that bind to DNA regulatory regions upstream of the protein coding regions of genes, and participate in the promotion or inhibition of the transcription of DNA into RNA. The different histories of two cells might lead to one having a large concentration of a particular transcription factor, and the other having a low concentration, and thus the two cells would express different genes, even though they had identical DNA.

Another important mechanism that controls the differential development of different types of cells in a multi-cellular organism is the biochemical signaling sent between cells. Signals such as hormones have the effect of directing a cell down a particular developmental pathway.

In general, the transcription factors, hormones, and multitude of other control mechanisms used in biological cells are organized into a network which can be represented as a “circuit” where the state of the system is characterized by the concentrations of the different biochemical ingredients. In fact, biologists are now using wiring diagrams to help summarize biological circuits; see for example, the “Biotapestry editor” developed by Eric Davidson’s lab at Caltech.

books.jpeg books2.jpeg

[I strongly recommend Davidson’s recent book The Regulatory Genome: Gene Regulatory Networks in Development and Evolution for an exciting introduction to the burgeoning “evo-devo” field; if you don’t have any background in biology, you may prefer The Coiled Spring, by Ethan Bier for a somewhat more popular account.]

Turning to the problem of designing artifical systems, a natural question is what theoretical advantages exist, from the point of view of designing with evolution, to using an identical genetic specification for all the cells in a multi-cellular organism.

One potential advantage is that relatively small changes to the genetic specification of the organism can concurrently alter the behavior of many different kinds of cells at many different times during the development of the organism. Therefore, if there is the possibility of an advantageous change to the circuitry controlling a cell, then it can be found once and used many times instead of needing to find the same advantageous mutation repeatedly for each of the cells in the organism.

Another related potential advantage is that a highly complicated organism can be specified in a relatively compact way. If each of the trillions of cells in a complex organism like a human had to be separately specified, then the overall amount of information required to describe the human genome would be multiplied more than a trillion-fold. Clearly, it is much more efficient to re-use the identical circuitry in many different types of cells.

In other words, biology uses a strategy of specifying a complex multi-cellular organism by just specifying a single cell–all the other cells in the mature organism are grown organically out of the developmental process. This seems like a strategy worth imitating.

On the other hand, the constraint that each cell in an organism should share an identical genetic specification clearly causes complications from the point of view of design. For example, it is important that genes that are designed to function in one type of cell at one point in development not cause problems for different type of cell at a different point in development. Clearly, good design of the control logic that turns genes on and off is essential to the proper functioning of a multi-cellular organism.

In the next post in this series, I will turn to the construction of a concrete model for multi-cellular circuits that tries to capture, as simply as possible, the essence of what is happening in biology. 

Mindbusters for Magic the Gathering

September 16, 2007

Today we have a guest article from my son Adam, about a variant of Magic the Gathering that we enjoy playing. I wrote a post introducing Magic and other trading card games previously, so if you know nothing about them, you might want to read that first. Adam’s article is definitely addressed to the advanced Magic player.

There are a few problems with Magic that this variant addresses: in particular the luck of the draw and the expense of buying packs. This variant is essentially a no-luck version which just requires two packs of cards. This type of variant can also be used for other trading card games.

If you’re interested in other variants to games like chess, go, bridge, etc., or perhaps in learning how to design your own variants or games, I highly recommend R. Wayne Schmittberger’s “New Rules for Classic Games.”

And if you’re interested in adding some Magic-like luck to the no-luck game of Chess, rather than eliminating the luck from Magic to make it more like Chess, you should read this post.

Read about the “Mindbusters” variant of Magic the Gathering.

(One comment for those who try to follow the article without much Magic experience: “milling” is the strategy of trying to run your opponents out of cards to draw: if you can’t draw a card when you’re supposed to, you lose the game.)