The Cell That Solves Bellman’s Equation

A Sudden Feast

A colony of E. coli has been living on thin food. Then, in an instant, the food gets five times better. Every bacterium in the dish now faces the same decision, and it faces it with every protein it makes: build ribosomes, the machines that make proteins, or build enzymes, the machines that turn food into the raw material ribosomes need.

Get it wrong in one direction and the ribosomes sit idle, starved of raw material. Get it wrong in the other and raw material piles up with nothing to use it. The right mix changes as the cell grows, and the cell has to find it with no brain, no plan and no idea how long the feast will last.

**Figure 1.** A petri dish of bacteria on a laboratory bench. Each colony is solving the same allocation problem, one protein at a time.

Two Machines and One Budget

In 2016 Nils Giordano, Hidde de Jong and their colleagues at Inria and Grenoble wrote the problem down in its simplest honest form. Two numbers describe the cell: $p$, its stock of raw material, and $r$, the share of its protein that is ribosomes. One number is the cell’s to choose: $\alpha$, the share of each new protein it makes as ribosomes rather than enzymes. $E$ is how good the food is. Writing a dot over a quantity for its rate of change in time, so that $\dot p = dp/dt$, and measuring in the right units:

$$\begin{aligned} \dot p &= E\,(1-r) \;-\; (1+p)\,\mu \\[4pt] \dot r &= \mu\,(\alpha – r) \\[4pt] \mu &= \frac{r\,p}{K + p}, \qquad K = 0.003 \end{aligned}$$

$(1)$

The first line is the raw material: made by the enzymes, used up and diluted by growth. The second is the ribosomes: made at the share $\alpha$, diluted by growth. The third is the growth itself: ribosomes times how well fed they are.

Enzymes, the share $1-r$ of the cell, turn food into raw material; growth dilutes everything, which is where the extra terms come from.

Hold the food fixed and ask for the steady mix that grows fastest, and the model gives back a law biologists have measured since the 1950s: richer food, more ribosomes. On poor food the best cell makes a third of its new protein as ribosomes and doubles every 36 minutes; on good food, half, doubling every 24 minutes; on rich food, two thirds, doubling every 18.

Bellman’s Question

A steady state is the easy part. The feast is the hard part. The food has just changed, the cell is still built for the old one, and what it wants is to make as much of itself as possible over the next few hours. Its growth adds up in logarithms, so the goal is

$$\max_{\alpha(\cdot)} \int_0^T \mu\,dt \;=\; \max\; \log \frac{\text{biomass}(T)}{\text{biomass}(0)} .$$

$(2)$

This is exactly the kind of question Richard Bellman built dynamic programming for in the 1950s. Let $V(p, r, t)$ be the most extra growth still obtainable from where the cell stands, with $t$ units of time left. Then $V$ satisfies Bellman’s equation:

$$-\frac{\partial V}{\partial t} \;=\; \max_{\alpha\in[0,1]} \Big[\, \mu \;+\; \frac{\partial V}{\partial p}\,\underbrace{\big(E\,(1-r) – (1+p)\,\mu\big)}_{\dot p} \;+\; \frac{\partial V}{\partial r}\,\underbrace{\mu\,(\alpha – r)}_{\dot r} \Big] .$$

$(3)$

In words: the growth you get now, plus what the change in raw material ($\dot p$) is worth, plus what the change in ribosomes ($\dot r$) is worth, with the best choice of $\alpha$.

Look at where $\alpha$ appears: once, multiplied by $\mu\,\partial V/\partial r$. The thing to maximise is a straight line in $\alpha$, and a straight line on an interval is always largest at one end. So the optimal choice is never a compromise:

$$\alpha^{*} \;=\; \begin{cases} 1 & \text{if } \partial V/\partial r > 0 \text{: one more ribosome is worth something,} \\ 0 & \text{if } \partial V/\partial r < 0 \text{: it is not.} \end{cases}$$

$(4)$

All ribosomes, or none. The whole decision collapses onto one curve in the plane of raw material and ribosomes, the curve where $\partial V/\partial r = 0$, where one more ribosome is worth exactly nothing. Below it, build ribosomes flat out. Above it, build enzymes flat out. And near the new best steady state, the optimal cell does something stranger still: it crosses the curve back and forth faster and faster, an infinite number of switches in a finite time, a behaviour control theorists call chattering. Giordano and colleagues showed that if the optimum settles on the curve, it must arrive this way.

The Race

I solved Bellman’s equation for this cell numerically, once, on a grid across the whole plane, and then raced five cells from the same starting point after the food improved:

optimal: follows Bellman’s switching curve;
on–off: switches ribosome making fully on when ribosomes are scarce for the raw material it has, fully off when they are plentiful;
precursor-only: sets its ribosome share from its stock of raw material alone;
nutrient-only: jumps at once to the best steady mix for the new food and stays there;
no reaction: keeps the mix that was best for the old food.

Five bacteria after the same improvement in food. Left: inside the cell, raw material against ribosome share; the amber curve is Bellman's switching curve, the teal dashed curve is the rule the on–off cell follows, and the star is the new best steady state. Right: each cell's biomass as a share of the best possible, and the ribosome share each one chooses over time. It opens on the finished race; press play to watch it run. The buttons change the food and how much better it gets; click a name to hide it. Below the plots: the model and Bellman's equation.

The obvious strategy is the worst sensible one. The nutrient-only cell, which sets the ideal mix for the new food at once, ends with 52% of the biomass the optimal cell makes, because its existing machinery is still wrong: raw material floods in faster than its too-few ribosomes can use it. The precursor-only cell does much better, 94%. And the on–off cell, which just switches ribosome making fully on or fully off, reaches 98%, and it chatters exactly as the optimum does. The 98% and 94% are the figures Giordano and colleagues reported; the numerical solution of Bellman’s equation reproduces them.

Left: at steady state, the best share of protein made as ribosomes against the growth it buys; the three points are poor, good and rich food. Right: biomass after five and a half hours, as a percentage of Bellman's optimum, when the food improves two, five or ten times. The bigger the change, the… — **Figure 2.** Left: at steady state, the best share of protein made as ribosomes against the growth it buys; the three points are poor, good and rich food. Right: biomass after five and a half hours, as a percentage of Bellman’s optimum, when the food improves two, five or ten times. The bigger the change, the more it pays to switch rather than to aim.

The Magic Spot

The on–off cell is not an invention. In 1969 Michael Cashel and Jonathan Gallant found two unexpected spots on the chromatograms of starving E. coli, which they nicknamed “magic spot”. The molecule, ppGpp, turned out to be the cell’s alarm: when ribosomes run short of raw material, it accumulates and shuts down the making of new ribosomes. In the 2016 paper’s words, it “senses a discrepancy between the concentrations of precursors and ribosomes, and adjusts ribosome synthesis in an on-off fashion”: the structure of the strategy that came within two per cent of the optimum.

**Figure 3.** A banquet laid out in an empty hall. The question for the cell is not whether to eat, but what to build first.

So does the bacterium solve Bellman’s equation? It computes nothing. It has no value function and no grid. What it has is a switch, shaped by billions of generations in which food came and went without warning, and the switch sits almost exactly where the equation says it should. The equation does not describe what the cell calculates. It describes what evolution kept.

The Colony Is a Game

One cell in an endless supply of food is only the beginning. Real bacteria share their food. What one cell eats, its neighbours do not, so the best allocation for each cell depends on what all the others do, and what they do depends on what is best for them. Each cell has its own Bellman equation, and the equations are coupled through the food they share.

That structure has a name: a mean-field game, the mathematics Jean-Michel Lasry and Pierre-Louis Lions, and independently Minyi Huang, Roland Malhamé and Peter Caines, introduced in 2006 for large crowds of players who each respond to the crowd as a whole. A colony of bacteria competing for sugar is such a crowd. Whether its equilibrium, the allocation that no single cell would change given all the others, is the one that ppGpp implements is, as far as I know, an open question.

**Figure 4.** A lighthouse beam on a dark sea. All or nothing is not a crude answer; for a choice that enters linearly, it is the optimal one.

A lighthouse does not dim its beam to suit the weather. It is on or off. The bacterium’s ribosome switch works the same way, and not because it is primitive: when a choice enters the rules of a problem as a straight line, Bellman’s equation says the best answer is always at an end. The cell found that out before anyone wrote the equation down.

Sources

N. Giordano, F. Mairet, J.-L. Gouzé, J. Geiselmann and H. de Jong, “Dynamical allocation of cellular resources as an optimal control problem: novel insights into microbial growth strategies”, PLOS Computational Biology 12 (2016) e1004802.
M. Cashel and J. Gallant, “Two compounds implicated in the function of the RC gene of Escherichia coli”, Nature 221 (1969) 838–841.
M. Schaechter, O. Maaløe and N. O. Kjeldgaard, “Dependency on medium and temperature of cell size and chemical composition during balanced growth of Salmonella typhimurium”, Journal of General Microbiology 19 (1958) 592–606.
R. Bellman, Dynamic Programming (1957).
J.-M. Lasry and P.-L. Lions, “Mean field games”, Japanese Journal of Mathematics 2 (2007) 229–260.
M. Huang, R. P. Malhamé and P. E. Caines, “Large population stochastic dynamic games: closed-loop McKean–Vlasov systems and the Nash certainty equivalence principle”, Communications in Information and Systems 6 (2006) 221–252.

The Bellman solution and every percentage in the text are computed by the scripts archived with this post, from a solution saved once.

Interested in applying these ideas to your work? Get in touch.