Weeknote #11 (w/e 25/7/10)

This week we finally submitted our paper on engineered oscillations in bacterial populations. This is something I've been working on with a colleague in Madrid, Angel Goni-Moreno, since he visited us in Manchester last year (in truth, he's been doing most of the work, although any delays have been entirely due to me).

In physics, an oscillator is a system that produces a regular, periodic "output". Familiar examples include a pendulum or a vibrating string. Linking several oscillators together in some way gives rise to synchrony -- for example, heart cells repeatedly firing in unison, or millions of fireflies blinking on and off, seemingly as one.

Oscillators are fundamental to biology, but they are also of interest to engineers, since they form the basis for counting (and synchronisation). Synthetic biology combines both disciplines, so the construction of oscillators within living cells is one of the main topics of interest in the field right now. However, until recently, most work has been restricted to single cells. In our paper, we have shown, in theory, how to engineer oscillations within populations of cells, using the "client-server" model familiar to computer scientists.

Update: the preprint version of the paper is here.

While writing the final draft, I was reminded of my brief contact with one of the founders of the field of theoretical biology. I first met Brian Goodwin in 2004, when I was still at the University of Exeter. He, along with Susan Blackmore, very kindly agreed to speak at the launch of a network I'd set up to encourage the study of complexity theory within the University. Best known in the broader community for his work on the evolution of complexity, Goodwin laid the foundations for recent research in synthetic biology with his seminal 1965 work on negative feedback. His later work focussed on the notion of a science of qualities (on which he spoke at our meeting), and when I first met him he was already formally retired, although still very active at Schumacher College, just down the road in Dartington. We also spent time chatting a year later, while we were both giving lectures at a summer school in Montpellier. I was struck most of all by his gentle nature and generosity of spirit, and we had the chance to discuss in greater depth the topics he'd touched on in his lecture.

Brian died just over a year ago; I first found out about his death while looking up references to give to my current Ph.D. student, who is now applying some of his ideas to the field of architecture. He had a great effect on me, and will continue to influence generations of students to come.

Weeknote #10 (w/e 18/7/10)

Into weeknote double figures, but nothing much to report, as we've been on holiday at the Suffolk coast.

Normal service will resume next Monday.

Weeknote #9 (w/e 11/7/10)

Only one thing of significance to report since my last weeknote; the acceptance of a fun little conference paper on solving a puzzle game that has, so far, escaped the attention of the algorithms community.

The Zen Puzzle Garden is a one-player puzzle game, involving a monk raking a traditional Japanese rock garden. The aim is to find a series of moves that allow the monk to rake all of the available sand, whilst negotiating rocks, pushing statues and collecting leaves - all without getting stuck in a dead-end.

While the problem is easy to describe, it's related to puzzles like Sokoban, which are actually very difficult to solve automatically (ie. with a computer program), in the general case. Jack Coldridge, who graduated from MMU a year ago, worked on this problem with me for his final-year dissertation, and we then developed it further into a full paper. The title, Genetic algorithms and the art of Zen is a play on David Goldberg's 1989 paper Zen and the art of genetic algorithms, which itself references Robert Pirsig's famous book.

Problems such as Sokoban are difficult because there are, potentially, a vast number of possible solutions to consider (where a solution is a path through the garden, in this example). Most solutions will be incorrect or "illegal", and the problem is to find the "needles in the haystack" (that is, the correct solutions). These so-called NP-hard problems are the most "interesting" problems in combinatorial mathematics, because they're the most challenging. The practical significance of such problems lies in the fact that they are related to "real world" problems of great importance, such as scheduling, packing and routeing. For a nice review of hard puzzle games, see this paper (PDF).

Several methods have been applied to the solution of such problems, including "traditional" algorithms, which use a "tree-based" approach to searching the space of possible solutions, as well as biologically-inspired algorithms. In the paper, we used a genetic algorithm to "evolve" paths through the garden. We start with a set of random paths, and see how well they solve the problem. Some will be "less bad" than others, so we keep them and use them to "breed" the next generation of solutions. Gradually, the power of natural selection (combined with a sprinkling of mutation) forces the population towards better and better solutions.

We found that our method was capable of finding the optimal (ie. shortest) solutions in the vast majority of cases, and it required far less processing power than another standard algorithm. Importantly, we have highlighted a new problem for the AI/puzzle community to get its teeth into.

The paper has been accepted for presentation at the IEEE Fifth International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA), to be held in Liverpool, on 8-10 September 2010.

Weeknote #8 (w/e 4/7/10)

To Paris, for the regular board meeting of our European Union BACTOCOM project. We launched the project with a workshop in Manchester, and partners take turns to organize subsequent meetings. We'll be in Santander in October, and then Berlin next year. Whilst browsing in the Abbey Bookshop in St. Michel, I noticed a copy of Genesis Machines, and had Justine record the fact that it was still on sale, in a proper shop. The subsequent scene ensured that I was brought to the attention of Brian, the proprietor, who kindly asked me to sign the last remaining copy in stock (i.e., the single copy they ordered three years ago).

Prior to leaving for Paris, we had quite a busy week; in addition to finishing off and submitting a research council proposal, we're now heavily into the preparations for our contributions to the Manchester Science Festival. So far, we have a couple of workshops lined up (I don't want to spoil the surprise until the details are confirmed), plus a public debate on the scientific, technological and ethical implications of synthetic biology and so-called artificial life. Watch this space for more details nearer the time.

On a personal note, I was delighted to receive confirmation of my promotion to a Readership. Most of my family members were quite baffled by this antiquated term, until I explained that it's the academic rank below Professor (in the UK), and is awarded on the basis of research.