#  Cellular memory enhances bacterial chemotactic navigation in rugged
environments

Adam Gosztolai<EMAIL_ADDRESS>Current address: Brain Mind Institute
and Interfaculty Institute of Bioengineering, École Polytéchnique Fédérale de
Lausanne, Lausanne, Switzerland Department of Mathematics, Imperial College
London, SW7 2AZ, London, United Kingdom  Mauricio Barahona
<EMAIL_ADDRESS>Department of Mathematics, Imperial College London,
SW7 2AZ, London, United Kingdom

(August 27, 2024)

###### Abstract

The response of microbes to external signals is mediated by biochemical
networks with intrinsic time scales. These time scales give rise to a memory
that impacts cellular behaviour. Here we study theoretically the role of
cellular memory in Escherichia coli chemotaxis. Using an agent-based model, we
show that cells with memory navigating rugged chemoattractant landscapes can
enhance their drift speed by extracting information from environmental
correlations. Maximal advantage is achieved when the memory is comparable to
the time scale of fluctuations as perceived during swimming. We derive an
analytical approximation for the drift velocity in rugged landscapes that
explains the enhanced velocity, and recovers standard Keller-Segel gradient-
sensing results in the limits when memory and fluctuation time scales are well
separated. Our numerics also show that cellular memory can induce bet-hedging
at the population level resulting in long-lived multi-modal distributions in
heterogeneous landscapes.

## Introduction

The natural habitat of many microbes is shaped by inherent micro-scale
ruggedness arising from random spatial inhomogeneities due to porous or
particulate matter Blackburn  _et al._ (1998); Ngom  _et al._ (2011); Hol  _et
al._ (2016)) or to filamentous structures resulting from turbulent advection
in the medium Muñoz-García  _et al._ (2010); Stocker (2012). Microbes
typically navigate such rugged attractant landscapes in search of nutrients
and stimulants in a process called chemotaxis. Chemotaxis is mediated and
governed by specialised biochemical pathways that sense changes in stimulant
concentration, transduce those signals, and induce subsequent adjustments to
the locomotion of the cell Porter  _et al._ (2011). Such pathways have
characteristic dynamic responses with intrinsic time scales, which are used by
cells to resolve changes in chemoattractant concentrations, i.e., to perform
local gradient-sensing Macnab and Koshland (1972); Berg (1993). In addition,
the dynamic response of the biochemical circuits can filter out the high
frequencies of noisy signals, to enhance gradient-sensing Block  _et al._
(1982); Andrews  _et al._ (2006); Aquino  _et al._ (2014).

The time scales of such responses can also be viewed as the basis for a
cellular memory, over which signals are processed. Indeed, microbes sample
continuously their chemical environment along their swimming trajectory, and
recent work has shown that the biochemical memory can be dynamically tuned
Shah  _et al._ (2000) from seconds to minutes Krembel  _et al._ (2015) in
response to environmental statistics. Hence, in addition to evaluating the
stimulant gradient, cells could extract informative features of the
heterogeneous environment from the fluctuations they perceive as they swim.

We study the effects of cellular memory in the context of Escherichia coli (E.
coli) chemotaxis, a model system for the navigation of microbes Stocker
(2012), worms Pierce-Shimomura  _et al._ (1999), and eukaryotes Polin  _et
al._ (2009), as well as an inspiration for the motion of swarm robots Taylor-
King  _et al._ (2015); Ebbens and Howse (2010) and random search algorithms
Viswanathan  _et al._ (1999). E. coli chemotaxis entails a run-and-tumble
strategy: runs (i.e., stretches of linear motion at constant velocity)
interrupted by tumbles (i.e., random stops with reorientation onto a random
direction). To generate a drift towards high chemoattractant concentrations,
cells reduce their tumbling rate upon sensing a favourable gradient, thus
lengthening the up-gradient runs Berg and Brown (1972).

The tumble rate is regulated by a chemotactic pathway with a bi-lobed temporal
response with a characteristic time scale $\gamma$, which we denote the
cellular memory. Input signals are convolved with this temporal response, with
the effect that recent samples are weighed positively whereas signals in the
past are given a negative weighting Segall  _et al._ (1986). It has been shown
that this response yields an estimate of the local temporal gradient Block
_et al._ (1982); Berg (1993).

The capability of cells to compute local gradients is the basis for several
coarse-grained models (drift-diffusion equations). The classic example is the
linear Keller-Segel (KS) model Keller and Segel (1970); Othmer and Hillen
(2000), which describes the behaviour of a population of cells whose mean
velocity aligns instantaneously with the local gradient. The KS model
successfully reproduces a variety of chemotactic phenomena, including
experimentally observed distributions under shallow attractant gradients
Menolascina  _et al._ (2017). Yet the presence of fluctuations may lead to an
incorrect assessment of the underlying gradient if using only instantaneous
information. Indeed, KS fails to recapitulate situations when cells do not
have time to adapt to large fluctuations, both in experiments Zhu  _et al._
(2012) and in agent-based simulations Xue (2015); Dufour  _et al._ (2014);
Long  _et al._ (2017). These shortcomings suggest the need to consider
additional time scales that play a role in chemotactic transient responses
Gosztolai  _et al._ (2019), and, specifically, the intrinsic memory of the
chemotactic pathway processing incoming stimuli Tu  _et al._ (2008); Lambert
and Kussell (2014).

Here, we study how bacteria use their cellular memory as they swim across a
rugged chemoattractant landscape to extract spatio-temporal information from
the perceived signal to improve their chemotactic navigation. To shed light on
the role of memory, we carry out simulations of an agent-based (AB) model
containing an input-output response function of the E. coli chemotactic
pathway Aminzare and Sontag (2013); Becker  _et al._ (2015); Jiang  _et al._
(2010) and compare its predictions to the KS model, which is based on
memoryless local gradient alignment. The KS agrees well with the AB numerics
for constant gradients, yet it underestimates the drift velocity of the
population when the ambient concentration has spatial correlations, consistent
with cells taking advantage of correlations in addition to local gradients.

Motivated by these numerical findings, we derive an analytical formula for the
drift velocity in terms of the cellular memory and the length scale of the
spatial correlations of the attractant landscape. Our model predicts the
numerical results and recovers KS in various limits, thus elucidating the
conditions in which cellular memory provides a chemotactic advantage over
memoryless local gradient-sensing. We also show that our results are
consistent with optimal information coding by the chemotaxis pathway
Clausznitzer  _et al._ (2014); Becker  _et al._ (2015), yet cells are band-
limited by their tumbling rate. Our work thus extends the gradient-sensing
viewpoint in chemotaxis, and provides insight into the role of memory in
navigating heterogeneous landscapes.

## Results

## Gradient-sensing as the classical viewpoint of chemotaxis

Figure 1: Setup of the agent-based model and simulation framework. a Cells
navigate a chemoattractant landscape $S(x)$ using a run and tumble strategy
with characteristic scales and variables as represented in the picture
($\ell_{0}$, $\lambda_{0}^{-1}$ and $v_{0}$ are the typical run length, run
time and ballistic run speed respectively). The simulations are run in a long
domain of length $\widetilde{L}\gg\ell_{0}$ over long times
$\widetilde{T}\gg\lambda_{0}^{-1}$. b The swimming cell senses the attractant
concentration along its trajectory $x(t)$ and modulates its tumbling rate
$\lambda(S(x(t)))$ by the chemotaxis transduction pathway with response given
by Eq. (1). The dynamic response of the pathway is mediated by the response
kernel $K(t)$ (Eq. (2)). c The shape of the bi-lobed kernel $K(t)$ normalised
by its amplitude $K_{\text{max}}$ against time.

A classical setup for chemotaxis is represented schematically in Fig. 1a.
Cells swim following a run-and-tumble motion: ballistic motion (‘runs’) at
constant velocity $v_{0}$, interrupted by random re-orientations (‘tumbles’)
occurring at random times governed by a Poisson process with rate $\lambda(t)$
Othmer  _et al._ (1988). As cells swim along their trajectory $x(t)$ (taken
here to be one-dimensional for simplicity), they are exposed to an attractant
concentration $S(x(t))$. Assuming initial adaptation to the ambient attractant
concentration, the cells modulate their Poisson tumbling rate according to Tu
_et al._ (2008); de Gennes (2004):

$\displaystyle\lambda(t)=1-\Lambda(t)$ (1)
$\displaystyle\text{with}\quad\Lambda(t)=\int_{-\infty}^{t}K(t-u)S(x(u))du\,.$

This represents the dynamics of the chemotaxis signal transduction,
illustrated on Fig. 1b. Throughout, we use variables non-dimensionalised with
respect to the characteristic length and time scales:

$x=\frac{\widetilde{x}}{\ell_{0}},\enskip
t=\lambda_{0}\widetilde{t},\enskip\lambda=\frac{\widetilde{\lambda}}{\lambda_{0}},\enskip
S=\frac{\widetilde{S}}{S_{\text{tot}}},$

where $S_{\text{tot}}$ is the total attractant concentration,
$\lambda_{0}=1\,s^{-1}$ is the basal tumbling rate, and
$\ell_{0}=v_{0}/\lambda_{0}=10\,\mu m$ is the average run length Berg and
Brown (1972).

In Eq. (1), $K(t)$ is the chemotactic memory kernel, measured through impulse
response experiments Segall  _et al._ (1986), which has a bi-lobed shape for
some attractants in E. coli Clark and Grant (2005); Celani and Vergassola
(2010) (Fig. 1c). A typical form for $K(t)$ is given by:

$K(t)=\frac{\beta}{\gamma}e^{-t/\gamma}\left(\frac{t}{\gamma}-\frac{t^{2}}{2\gamma^{2}}\right),$
(2)

where $\beta$ is a dimensionless signal gain, and
$\gamma=\lambda_{0}\widetilde{\gamma}$ is the cellular memory, a
(dimensionless) relaxation time, as seen by the fact that the crossing point
of the bi-lobed response is $t=2\gamma$ (Fig. 1c). Note that the amplitude of
the response kernel is
$K_{\text{max}}=(\sqrt{2}-1)e^{\sqrt{2}-2}\beta/\gamma$. Hence an increase in
memory decreases the overall response. The kernel in Eq. (2) can be understood
as a linear filter with three states (Supplementary Note 1), with a topology
that achieves perfect adaptation Yi  _et al._ (2000); Ma  _et al._ (2009),
since $\int_{0}^{\infty}K(t)dt=0$. Our setup differs from an alternative model
Dufour  _et al._ (2014) based on the dynamics of the CheY protein regulating
the tumbling rate, which typically leads to a one-state linear filter obtained
through linearisation. In Supplementary Note 2, we show that this alternative
model can be equivalently written in the form of Eq. (1) but with a kernel
$K(t)=\beta(\delta(t)-(1/\gamma)e^{-t/\gamma})$ with a singularity at $t=0$
and a single decaying exponential, instead of the bi-lobed kernel (Eq. (2)).

At long time scales involving many runs and tumbles ($t\gg 1$), the swimming
behaviour may be approximated by a drift-diffusion process Rousset and Samaey
(2013); Othmer and Hillen (2000); Xue (2015). In this regime, the time
evolution of the population density of cells $\rho(x,t)$ from an initial state
$\rho(x,0)$ is described by a Fokker-Planck partial differential equation:

$\frac{\partial\rho}{\partial t}-\frac{1}{2}\frac{\partial^{2}\rho}{\partial
x^{2}}+\frac{\partial}{\partial x}(\rho v)=0,$ (3)

where $v(x,t)=\widetilde{v}(x,t)/v_{0}$ is the drift velocity of the cells,
and the diffusion coefficient $D=\ell_{0}^{2}\lambda_{0}$ drops out as part of
the non-dimensionalisation. Equivalently, $\rho(x,t)$ is the probability of
finding a cell at $x$ after time $t$ from a starting position $x_{0}$ drawn
from $\rho(x,0)$.

Typically, derivations in the literature Rousset and Samaey (2013); Erban and
Othmer (2004); Othmer  _et al._ (1988) consider the regime of long memory
(compared to the average run) and shallow perceived gradient (i.e., the
attractant does not vary appreciably over the memory):

$1\ll\gamma\ll\left(\beta\frac{\partial S}{\partial x}\right)^{-1}.$ (4)

Under these assumptions, the drift velocity $v(x,t)$ can be shown de Gennes
(2004) to align with the local gradient (see Supplementary Note 3):

$v(x,t)=\chi\frac{\partial S}{\partial x}=:v_{\text{KS}}(x),$ (5)

where the chemotactic response coefficient $\chi$ follows from the kinematics
and the memory kernel (Eq. (2)):

$\chi=\frac{2\beta\gamma}{(1+2\gamma)^{3}}\,.$ (6)

Eq. (3), together with Eqs. (5) and (6), defines the classic linear Keller-
Segel (KS) equation for the time evolution of the population density under a
landscape $S(x)$. We denote the solution to this equation as
$\rho_{\text{KS}}(x,t;\,S)$.

However, the KS model is actually valid under the weaker condition Xue (2015)

$|\Lambda|\ll 1\quad\textit{(small response)},$ (7)

i.e., the tumbling response remains close to the adapted value. It can be
shown that time scale separation (Eq. (4)) implies small response (Eq. (7)),
but the converse is not necessarily true. Hence KS can still be valid in the
realistic situation when Eq. (4) breaks down because the cellular memory is
commensurate with environmental fluctuations Becker  _et al._ (2015); Aquino
_et al._ (2014); Andrews  _et al._ (2006), as long as Eq. (7) holds. Below, we
consider a broad span of memory values (from the well separated to the
commensurate) but always in the small response regime so that the KS model is
valid.

## Chemotaxis of cells with memory studied using agent-based numerics

We consider cells with memory swimming in a rugged environment with spatial
correlations, leading to a temporally fluctuating input perceived along their
trajectories. To study the effect of memory, we performed agent-based (AB)
simulations of run-and-tumble motion as in Refs. Aminzare and Sontag (2013);
Becker  _et al._ (2015) coupled to a cellular response (Eqs. (1)–(2)) with
memory (see Supplementary Note 1 for details).

Our rugged landscape is a simple linear attractant concentration profile with
additive spatial noise (Becker  _et al._ , 2015):

$S_{\eta}(x)=\alpha\,x+\eta(x),$ (8)

where $\eta(x)$ is a random spatial variable described by the stochastic
harmonic oscillator Langevin equation:

$\displaystyle\frac{d}{dx}\eta(x)$ $\displaystyle=\theta(x)$ (9)
$\displaystyle m\frac{d}{dx}\theta(x)$
$\displaystyle=-\frac{1}{\mu}\eta(x)-\theta(x)+\sigma_{\eta}\sqrt{\frac{2}{\mu}}\,\xi(x).$

Here $\xi(x)$ is a unit white noise, and

$\alpha=\frac{\ell_{0}}{S_{\text{tot}}}\,\widetilde{\alpha},\enskip\sigma_{\eta}=\frac{\widetilde{\sigma}_{\eta}}{S_{\text{tot}}},\enskip
m=\frac{\widetilde{m}}{\ell_{0}},\enskip\mu=\frac{\widetilde{\mu}}{\ell_{0}}$

are non-dimensionalised parameters corresponding to: attractant gradient,
noise variance, inertia, and spatial correlation length, respectively. This
random landscape has two desirable properties. First, $S_{\eta}(x)$ with $m>0$
is continuous and differentiable, so that

$\left\langle\frac{\partial S_{\eta}}{\partial
x}\right\rangle_{\xi}=\alpha+\left\langle\frac{\partial\eta}{\partial
x}\right\rangle_{\xi}=\alpha,$ (10)

where $\langle\cdot\rangle_{\xi}$ denotes averaging over independent
realisations of $\eta(x)$. Second, Eq. (9) is a regularised spatial Ornstein-
Uhlenbeck (OU) process (Supplementary Figure 1): as $m\to 0$, $\eta$ converges
to an OU process $\eta^{0}(x)$ which has exponential correlations with
characteristic length $\mu$:

$\langle\eta^{0}(x)\eta^{0}(x^{\prime})\rangle_{\xi}=\sigma_{\eta}^{2}e^{-|x-x^{\prime}|/\mu}=:C_{\eta}(|x-x^{\prime}|).$
(11)

The OU limit is used below to facilitate our analytical calculations.

## Chemotaxis in constant shallow gradients

We first consider the landscape with zero ruggedness:

$S_{0}=\alpha\,x,$ (12)

which corresponds to $\sigma_{\eta}=0$ or, alternatively, to the limit
$\mu\to\infty$, when the correlation length diverges. In this case, it has
been shown Erban and Othmer (2004); Othmer and Hillen (2000) that the
condition

$\beta\alpha\ll 1\quad\textit{(shallow perceived gradient)}$ (13)

guarantees that the small response condition (Eq. (7)) also holds. Hence we
expect the AB numerics to be well described by the KS equation.

To test this prediction, we used the AB model to simulate $N=10^{5}$
independently generated cell trajectories
$\\{x_{\text{AB}}(t;\,S_{0});\;t\in(0,T)\\}$, where $T=4\times 10^{3}$ (Fig.
2a), from which we obtain population snapshots,
$\rho_{\text{AB}}(x,t;\,S_{0})$. All the simulations were run in the regime of
small $\beta\alpha$. In Fig. 2b, we show that the statistics of the AB
simulations are well captured by the continuum KS solution:

$\displaystyle\rho_{\text{AB}}(x,t;\,S_{0})\approx\rho_{\text{KS}}(x,t;\,S_{0}).$

We also compared the drift velocity of the KS solution to the average velocity
of AB cells (computed over the long simulation time $T$):

$\displaystyle
v_{\text{AB}}(S_{0}):=\left\langle\frac{x_{\text{AB}}(T;S_{0})-x_{\text{AB}}(0;S_{0})}{T}\right\rangle_{\text{AB}}$
(14) $\displaystyle v_{\text{KS}}(x;S_{0})=\chi\frac{\partial S_{0}}{\partial
x}=\chi\,\alpha,$

where $\langle\cdot\rangle_{\text{AB}}$ denotes averaging over the ensemble of
AB cells. Fig. 2c shows that the average velocity of the AB population matches
the drift velocity of the KS model for varying memory $\gamma$.

Maximising Eq. (6) shows that the drift velocity $v_{\text{KS}}$ achieves a
maximum at an optimal memory:

$v_{\text{KS}}^{\,\ast}:=\max_{\gamma}v_{\text{KS}}(S_{0})\quad\text{at
$\gamma_{\text{KS}}^{\ast}=1/4$},$ (15)

Hence a cell with optimal memory $\gamma_{\text{KS}}^{\ast}$ has a kernel
$K(t)$ with a zero crossing at $t=1/2$, i.e., halfway through the expected
length of a run (see Fig. 1c). KS thus predicts that the drift speed is
maximal when the gradient is measured along a single run, when the cell can
take an unbiased measurement while moving in a straight line. For the zero-
ruggedness landscape, our AB simulations (Fig. 2c) also display a maximum in
the average velocity of the population when the cells have memory
$\gamma=\gamma_{\text{KS}}^{\ast}$.

Fig. 2d confirms that the simulations are in the regime of small response (Eq.
(7)) where KS holds. As $\beta\alpha$ is increased, and the small response
condition (Eq. (7)) is violated, the correspondence between the AB and KS
solutions gradually breaks (see Supplementary Figure 2).

Figure 2:  Comparison of agent-based numerics and Keller-Segel approximation
in shallow gradients. The AB model is used to produce $N=10^{5}$ cell
trajectories over $T=4\times 10^{3}$ ($\Delta x=5\times 10^{-5}$, $\Delta
t=5\times 10^{-3}$) with perceived gradient $\beta\alpha=0.1$,
$\beta\sigma_{\eta}=0$. The KS model is integrated numerically using a first-
order in time, second-order in space forward-Euler scheme ($\Delta x=10^{-4}$,
$\Delta t=1$). a Sample trajectories of the AB model ($\gamma=0.5$) in the
deterministic landscape $S_{0}(x)$. b The evolution of the population density
of the AB model ($\rho_{\text{AB}}(x,t;\,S_{0})$, histogram) is well captured
by the evolution of the KS equation ($\rho_{\text{KS}}(x,t;\,S_{0})$, Eq. (3),
dashed line, $\gamma=0.5$). The solid blue line indicates the average velocity
$v_{\text{AB}}$, which is indistinguishable from the KS drift $v_{\text{KS}}$.
The densities are normalised to unit mass. c The drift velocity from the AB
model ($v_{\text{AB}}$, circles) is well predicted by the KS drift velocity
($v_{\text{KS}}$, dashed line). Both velocities are normalised by the maximal
KS drift velocity $v_{\text{KS}}^{*}$, which is reached at a memory of
$\gamma_{\text{KS}}^{*}=1/4$, shown by the dotted line. d The maximum tumbling
response $\max|\Lambda|$ (circles) stays well below unity, showing that the
small response condition is met for all the simulations. The blue band
indicates the standard deviation of the simulations.

## Chemotaxis in rugged, correlated landscapes

The kernel $K(t)$ with intrinsic memory $\gamma$ has been shown to filter
high-frequency input noise Aquino  _et al._ (2014); Becker  _et al._ (2015).
However, cells could also use this memory to their advantage as they process
the correlated fluctuations that they encounter as they traverse a rugged
landscape.

To test this idea, we carried out AB simulations of cells with memory
navigating the spatially correlated landscape (Eq. (8)) and compared it to the
predicted KS behaviour. To ensure that the differences between AB and KS are a
direct consequence of the correlated spatial fluctuations, all our simulations
are run in the small response regime (Eq. (7)) where KS holds, while keeping a
large signal-to-noise ratio (Supplementary Note 4):

$\displaystyle\alpha\gg\sigma_{\eta}\quad\textit{(large signal-to-noise
ratio)},$ (16)

Fig. 3 shows that the AB cell population travels faster than predicted by KS
going up the gradient of the rugged landscape. Fig. 3a presents simulated AB
trajectories for a particular realisation of the landscape $S_{\eta}(x)$, and
Fig. 3b compares the time evolution of the KS solution
$\langle\rho_{\text{KS}}(x,t;\,S_{\eta})\rangle_{\xi}$ to the empirical
distribution from the AB numerics
$\langle\rho_{\text{AB}}(x,t;\,S_{\eta})\rangle_{\xi}$, both averaged over
$10^{2}$ independent realisations of the landscape $S_{\eta}(x)$. Our numerics
show that the AB distribution propagates faster: $\langle
v_{\text{AB}}(S_{\eta})\rangle_{\xi}>v_{\text{KS}}$, i.e., the average cell
velocity of the AB simulations (defined in Eq. (14)) averaged over
realisations of the landscape (blue solid line) is larger than the
corresponding KS drift velocity (dashed line).

We have examined this enhanced chemotaxis as a function of the length scale of
the landscape. We show in Fig. 3c that for correlation lengths around the run
length ($\mu\approx 1$), the KS drift velocity $v_{\text{KS}}$ underestimates
the average velocity $\langle v_{\text{AB}}(S_{\eta})\rangle_{\xi}$ of cells
with memory $\gamma\geq\gamma_{\text{KS}}^{\ast}=1/4$.

As expected, the average velocity of the AB cells is well approximated by the
KS solution in the limits of both vanishingly small and infinitely large
correlation length:

$||\langle v_{\text{AB}}(S_{\eta})\rangle_{\xi}-v_{\text{KS}}||\to
0\quad\text{as}\quad\mu\to\\{0,\,\infty\\},$ (17)

which correspond to an uncorrelated landscape or a zero-ruggedness constant
gradient, respectively. Also expected, Eq. (17) holds in the memoryless limit
$\gamma\to 0$. In this limit, the kernel $K(t)$ computes the temporal
derivative of the signal (see Supplementary Note 1), and the tumble rate (Eq.
(1)) is $\lambda(t)\simeq 1-\beta dS/dt$, so that the drift velocity is given
by Eq. (5) (see Sect. 2.3 in Ref. Rousset and Samaey (2013)). This result is
consistent with fast adaptation dynamics approaching gradient-sensing Aminzare
and Sontag (2013); Rousset and Samaey (2013).

Note that the system is in the small response regime (Eq. (7)) where KS is
applicable (compare Fig. 3d with Fig. 2d). Yet, our AB numerics show that
cells with memory can drift faster than predicted by mere gradient sensing
(KS) when navigating environments with spatially correlated fluctuations, thus
indicating a role for cellular memory in using spatial information beyond
local gradients.

Figure 3:  Comparison of agent-based simulations and analytic predictions in
rugged landscapes $S_{\eta}$. The AB model is used to produce $N=10^{4}$ cell
trajectories over $T=4\times 10^{3}$ ($\Delta x=5\times 10^{-5}$, $\Delta
t=5\times 10^{-3}$) in $10^{2}$ realisations of $S_{\eta}(x)$ with perceived
gradient $\beta\alpha=0.05$, $\beta\sigma_{\eta}=10^{-3}$. The KS model is
integrated numerically using a first-order in time, second-order in space
forward-Euler scheme ($\Delta x=10^{-4}$, $\Delta t=1$). a Sample trajectories
of the AB model ($\gamma=0.5$) in the rugged landscape ($\mu=1$). Note that
the ensemble average drift of the AB cells (solid blue line) is faster than
the KS drift (dashed black line). b The evolution of the population density of
the KS model ($\langle\rho_{\text{KS}}(x,t;\,S_{\eta})\rangle_{\xi}$, Eq. (3),
dashed black line, $\gamma=0.5$, $m=5\times 10^{-3}$) generally fails to
capture the evolution of the AB population
($\langle\rho_{\text{AB}}(x,t;\,S_{\eta})\rangle_{\xi}$, histogram). The
densities are normalised to unit mass. c The average drift velocity of the AB
model ($\langle v_{\text{AB}}(S_{\eta})\rangle_{\xi}$, circles) as a function
of the memory $\gamma$ is well described by our approximation ($V_{\mu}$, Eq.
(23), red solid line) for all values of $\mu$, but in general not well
captured by the KS drift ($v_{\text{KS}}$, Eq. (5), black dashed line). The AB
drift is averaged over realisations of the rugged landscape and both
velocities are normalised by the maximal KS drift $v_{\text{KS}}^{*}$ in the
deterministic landscape. d The average maximum response amplitude $|\Lambda|$
from the AB simulations at different values of $\mu$ (different symbols in the
figure) remains much smaller than unity for all combinations of $\gamma$ and
$\mu$ (as in Fig. 2d), indicating that the KS model still holds in the rugged
landscape. Yet, as panels b, c show, it does not capture the drift velocity.
The blue bands indicate the standard deviation of the simulations.

## Derivation of drift speed in rugged landscapes

To capture the numerically observed enhancement of AB chemotaxis in rugged
landscapes, we extend de Gennes’ analytical derivation of the drift velocity
to incorporate the interaction of memory with the landscape fluctuations. To
facilitate our analysis, in the rest of this section we work in the OU limit
of the landscape, i.e., $m\to 0$ in Eq. (9).

Consider a population of cells navigating the rugged landscape $S_{\eta}(x)$.
Under chemotaxis, the average duration of runs up the gradient $\left\langle
t^{+}\right\rangle_{\text{AB}}$ is larger than the duration of runs down the
gradient $\left\langle t^{-}\right\rangle_{\text{AB}}$. Following de Gennes de
Gennes (2004), it can be shown that the (non-dimensionalised) average velocity
of the cells is:

$\displaystyle v_{\text{AB}}(S_{\eta})$ $\displaystyle=\frac{\left\langle
t^{+}\right\rangle_{\text{AB}}-\left\langle
t^{-}\right\rangle_{\text{AB}}}{\left\langle
t^{+}\right\rangle_{\text{AB}}+\left\langle
t^{-}\right\rangle_{\text{AB}}}=\left\langle
t^{+}\right\rangle_{\text{AB}}-1,$ (18)

where we use the fact that $\left\langle
t^{+}\right\rangle_{\text{AB}}+\left\langle t^{-}\right\rangle_{\text{AB}}=2$,
i.e., the sum of the average duration of one up-hill and one down-hill run is
equal to two runs. Equation (18) just states that the average cell velocity is
the excess duration of the average up-gradient run beyond the duration of an
average run.

Using the ergodicity of the run-and-tumble process, the expectation over AB
trajectories becomes a time integral:

$\displaystyle\langle t^{+}\rangle_{\text{AB}}$
$\displaystyle=\int_{0}^{\infty}s\,p(s\,|\,x(t))\,ds=\int_{0}^{\infty}e^{-\int_{0}^{s}\lambda(t)dt}\,ds,$
(19)

where $p(s\,|\,x(t))=\lambda(s)\exp(-\int_{0}^{s}\lambda(t)dt)$ is the
conditional probability density of Poisson tumble times given the path $x(t)$.
In the small response regime (Eq. (7)), we can expand the exponential to
second order to obtain

$\displaystyle\langle t^{+}\rangle_{\text{AB}}$ $\displaystyle\simeq
1+\int_{0}^{\infty}e^{-s}\left[\int_{0}^{s}\Lambda(t)dt+\frac{1}{2}\left(\int_{0}^{s}\Lambda(t)dt\right)^{2}\right]ds.$

We now depart from de Gennes’ derivation and consider the cell velocity (Eq.
(18)) averaged over realisations of the landscape $S_{\eta}$:

$\displaystyle\langle v_{\text{AB}}(S_{\eta})\rangle_{\xi}\simeq$
$\displaystyle\int_{0}^{\infty}e^{-s}\left\langle\int_{0}^{s}\Lambda(t)dt\right\rangle_{\xi}ds$
$\displaystyle+$
$\displaystyle\frac{1}{2}\int_{0}^{\infty}e^{-s}\left\langle\left(\int_{0}^{s}\Lambda(t)dt\right)^{2}\right\rangle_{\xi}ds,$
(20)

where the first term does not depend on the spatial noise:

$\displaystyle\left\langle\int_{0}^{s}\Lambda(t)dt\right\rangle_{\xi}$
$\displaystyle=\int_{0}^{s}\int_{0}^{\infty}K(u)\left\langle
S_{\eta}(x(t-u))\right\rangle_{\xi}dudt$
$\displaystyle=\int_{0}^{s}\int_{0}^{\infty}K(u)S_{0}(x(t-u))dudt,$ (21)

and the second term contains the effect of the spatial correlations as a
result of the overlap between the memory kernel and the spatial covariance
(Eq. (11)):

$\displaystyle\left\langle\left(\int_{0}^{s}\Lambda(t)dt\right)^{2}\right\rangle_{\xi}=\left(\int_{0}^{s}\int_{0}^{\infty}K(u)S_{0}(x(t-u))dudt\right)^{2}$
$\displaystyle+\int_{0}^{\infty}K(w)\int_{w}^{s}\int_{w-\widehat{t}}^{0}\left(\int_{0}^{\infty}K(u)\,C_{\eta}(x(\tau-u))\,du\right)d\tau
d\widehat{t}\,dw.$ (22)

Here $\tau=t-\widehat{t}+w$ represents the delay between the input
$\eta^{0}(x(t-\tau))$ and the output $\Lambda(t)$, and the limits of
integration reflect causality.

Collating Eqs. (19)–(22) and integrating, we obtain our approximation of the
drift velocity in rugged landscapes:

$\langle v_{\text{AB}}(S_{\eta})\rangle_{\xi}\simeq v_{\text{KS}}+\Delta
v_{\mu}=:V_{\mu},\\\ $ (23)

where Eq. (Derivation of drift speed in rugged landscapes) gives rise de
Gennes (2004) to the KS drift velocity (Eq. (5)):

$\displaystyle v_{\text{KS}}=\beta\alpha\,\frac{2\gamma}{(1+2\gamma)^{3}},$
(24)

and Eq. (22) leads to the correction due to spatial correlations:

$\displaystyle\Delta v_{\mu}$
$\displaystyle=\frac{\beta^{2}\sigma_{\eta}^{2}}{2}\frac{\gamma^{2}\mu\left[2\gamma^{3}(1+\mu)+(1+\gamma)^{3}\mu^{2}+6\gamma^{2}\mu-2\mu^{2}\right]}{(1+\gamma)^{6}(1+\mu)(\gamma+\mu)^{3}}$
(25)

For further details, see Supplementary Note 5.

Our approximation $V_{\mu}$ recovers the KS drift velocity in different
limits: for deterministic and uncorrelated landscapes ($\Delta v_{\mu}\to
0\text{ as }\mu\to\\{0,\,\infty\\}$); in the zero and infinite memory limits
($\Delta v_{\mu}\to 0\text{ as }\gamma\to\\{0,\,\infty\\}$); as well as in the
limit of vanishing gradient ($V_{\mu}\to v_{\text{KS}}\text{ as }\alpha\to
0$), since (Eq. (16)) is required to derive $\Delta v_{\mu}$.

Figure 4:  Dependence of the maximal drift velocity and the optimal memory on
the environmental correlation length. a The maximum drift velocity from the
agent-based (AB) numerics at various correlation lengths of the landscape
(circles) is well predicted by our approximation (solid line). This maximum,
achieved in rugged gradients, exceeds the corresponding deterministic Keller-
Segel (KS) drift for all $\mu$, and approaches the KS prediction in the white
noise ($\mu\to 0$) and constant gradient ($\mu\to\infty$) limits. The drift
velocities are normalised with respect to the maximum attainable KS drift in
deterministic landscapes. The error bars indicate the standard deviation of
drift velocity fluctuations across realisations of the rugged landscape at the
optimal memory $\gamma^{*}_{\mu}$ corresponding to this drift speed. b The
optimal memory against the correlation length shows that the memory at which
the drift velocity is maximised is always larger in AB cells than the optimal
KS value: $\gamma^{*}_{\mu}/\gamma_{\text{KS}}^{*}\geq 1$. The longest optimal
memory for a given correlation length occurs for $\mu=1$ (dotted line), which
equals the expected run length. Thus, the tumble rate limits the length scale
of perceivable fluctuations.

## The effect of memory on the drift speed

Our approximation (Eq. (23)) makes explicit the fact that cells use both the
local gradient (through $v_{\text{KS}}$) and the spatial correlations (through
$\Delta v_{\mu}$) to navigate rugged landscapes. Fig. 3c shows that, in
contrast to the KS drift, our $V_{\mu}$ predicts the enhanced cell velocity in
the AB simulations, $\langle v_{\text{AB}}(S_{\eta})\rangle_{\xi}$, and its
dependence on the landscape length scale $\mu$ for a broad range of memory,
$\gamma$.

Fig. 4 compares the predicted maximal velocity and the optimal memory at which
it is achieved,

$V_{\mu}^{\,\ast}=\max_{\gamma}V_{\mu}\quad\text{attained at
$\gamma_{\mu}^{\ast}$}$ (26)

with the numerical simulations. As expected, we recover the KS behaviour in
both limits of deterministic ($\mu\to\infty$) and uncorrelated ($\mu\to 0$)
landscapes, when there is no advantage in using memory to use the statistical
correlations of the environment. The optimal memory $\gamma_{\mu}^{\ast}$ thus
emerges as a balance between filtering and tumbling: for
$\gamma>\gamma_{\mu}^{\ast}$, cells improve their noise filtering Becker  _et
al._ (2015) but lose orientation due to the larger number of tumbles taken
account in their history; on the other hand, for $\gamma<\gamma_{\mu}^{\ast}$,
cells are less likely to tumble, but filtering of environmental noise becomes
suboptimal. Our results in Fig. 4a show that the velocity of cells with
optimal memory is always larger than the gradient-sensing KS drift velocity
(i.e., $V_{\mu}^{\,\ast}(\mu)\geq v_{\text{KS}}^{\,\ast},\enskip\forall\mu$),
with the largest improvement at $\mu\simeq 1/2$, the point where the length
scale of the environmental correlations are on the order of one half of a run
length. As seen in Fig. 4b, the corresponding optimal memory is also always
larger than the KS memory:
$\gamma_{\mu}^{\ast}\geq\gamma^{\ast}_{\text{KS}}=1/4$. Our calculations show
that it is advantageous to increase the memory when the correlations are of
the same order as the length of the run ($\mu=1$); yet for correlations longer
than one run ($\mu\geq 1$), the presence of random tumblings erode this
advantage and the optimal memory returns to the KS value..

This behaviour is consistent with models of tethered cells receiving noisy
temporal stimuli Becker  _et al._ (2015). In particular, the mutual
information between input and output with a delay $\tau$ is maximised when
maximising the correlation

$\displaystyle R_{\eta\Lambda}(\tau)$
$\displaystyle:=\frac{\langle\eta^{0}(t-\tau)\Lambda(t)\rangle_{\xi}}{\sigma_{\eta}\sigma_{\Lambda}}=\frac{1}{\sigma_{\eta}\sigma_{\Lambda}}\int_{0}^{\infty}K(u)R_{\eta}(\tau-u)\,du\,,$
(27)

which is a normalised version of the integral in brackets in the second term
of Eq. (22). It was shown Becker  _et al._ (2015); Tostevin and ten Wolde
(2009) that Eq. (27) is maximised for a memory corresponding to optimal
filtering, and, consistently, our results reflect the importance of noise
filtering. For navigation, however, the optimality of filtering is not the
only criterion, and it needs to be balanced with the random tumbling time
scale which imposes a threshold on the bandwidth of correlations that are
useful to improve drift speed.

## The effect of memory on the heterogeneity of the population

Thus far, we have shown that our approximation predicts well the effect of
memory on enhancing the cell velocity in rugged landscapes, although, as seen
in Fig. 3c, it overpredicts the velocity of AB cells with short memory
($\gamma<\gamma^{*}_{\text{KS}}=1/4$) navigating mildly rugged landscapes
($0.05<\mu<0.5$). The origin of this discrepancy is in the fact that cellular
memory has an effect not only on the average cell velocity but also on the
heterogeneity of the distribution of AB cells, an effect that is not captured
by our approximation in Eq. (23).

To characterise this behaviour further, we carry out additional numerical
computations. Intuitively, we expect that cells with short memories will be
more sensitive to local irregularities, and hence more prone to becoming
disoriented in rugged landscapes. At the population level, this could lead to
the appearance of subpopulations of propagating agents. On the other hand,
cells with long memory will average their responses over extended patches of
the landscape, thus being less sensitive to local fluctuations of the
landscape and maintaining the unimodality of the distribution.

A numerical illustration of this behaviour is presented in Fig. 5a, where we
show the long-term AB numerics of two population of cells (one with long
memories, another with short memories) starting from an initial Gaussian
distribution and navigating a rugged landscape $S_{\eta}$. In the KS model, it
is known that a Gaussian population remains Gaussian for all times Carrillo
and Toscani (1998). Indeed, our AB numerics show that when cells have
relatively long memories ($\gamma=1$), the population does remain unimodal.
However, the population of cells with short memories ($\gamma=0.05$) goes from
being Gaussian to multimodal (i.e., with separate subpopulations), as time
elapses. This behaviour is persistent over long times.

To quantify the loss of unimodality, in Fig. 5b we compute the $L_{2}$
distance between the AB distribution $\rho_{AB}(x,t;\,S_{\eta})$ and its best
Gaussian fit $\mathcal{G}(x,t;S_{\eta})$ after a long simulation of $T=4\times
10^{3}$:

$\left\langle\mathcal{D}_{\mathcal{G}}(\rho_{\text{AB}},T)\right\rangle_{\xi}=\left\langle\left||\rho_{\text{AB}}(x,T;\,S_{\eta})-\mathcal{G}(x,T;\,S_{\eta})\right||_{L^{2}}\right\rangle_{\xi}\,.$
(28)

As discussed above, for a rugged landscape with length scale $\mu$, the AB
distribution becomes increasingly Gaussian for larger $\gamma$, converging to
a Gaussian distribution (Fig. 5b-c). For large $\gamma$, the standard
deviation becomes largely independent of the landscape length scale $\mu$
(Fig. 5c). This is consistent with the fact that randomness arises not from
the landscape but from tumbling, which is common to all cells, thus yielding
unimodal population distribution in this limit. When the memory is short, on
the other hand, cells use local information and their trajectories depend
strongly on the starting positions, leading to distributions far from
Gaussian. This dependence on the starting positions is reduced for cells with
longer memory, which perceive and average overlapping information of the
landscape.

These numerical results suggest that cellular memory could play a role not
only in optimising long-term drift velocity (Fig. 4a) but also in controlling
population level heterogeneity Frankel  _et al._ (2014). A trade-off between
both objectives could then allow a more extended exploration of heterogeneous
attractant landscapes by the cell population.

Figure 5: The cellular memory controls the population heterogeneity.  a
Snapshots of the agent-based population density $\rho_{AB}(x,T;\,S_{\eta})$ in
a rugged landscape $S_{\eta}$ ($\beta\sigma_{\eta}=10^{-3}$, $\mu=1$) measured
at $T=4\times 10^{3}$ for two values of the memory $\gamma$ (histogram) shown
with the best-fit Gaussian curves $\mathcal{G}(x,T;\,S_{\eta})$ (red line).
For short memories (where short depends on the correlation length $\mu$) the
population loses coherence. b As $\gamma$ increases, the population becomes
increasingly unimodal Gaussian. This is shown by
$\mathcal{D}_{\mathcal{G}}(\rho_{\text{AB}},\,T)$, the distance between the
population distribution and the best-fit Gaussian (Eq. (28)) averaged over
realisations of the landscape, decreasing to zero. c For large $\gamma$, the
standard deviation of $\mathcal{G}(x,T;\,S_{\eta})$ becomes independent of
$\mu$ and $\gamma$, indicating that randomness arises only from tumbling.

## Discussion

Chemotactic navigation relies on the processing of sensory information and its
efficient transduction by the cellular mechanisms that control locomotion.
Here we studied the run-and-tumble motion of E. coli and investigated the role
of the cellular memory inherently to the chemotactic response in determining
the ability of cells to navigate rugged chemoattractant landscapes. In
contrast to previous work, which focused on the deleterious effect of noise on
sensing and swimming Clausznitzer  _et al._ (2014); Aquino  _et al._ (2014),
our model explores how the correlations in the attractant, as encountered
through swimming, can be used to enhance chemotactic performance. To this end,
we considered an agent-based (AB) model of swimming cells with a history-
dependent tumble rate computed by each cell along its trajectory through a
signal-transduction model, and compared it to the classical Keller-Segel (KS)
model, in which cells instantaneously align their velocity to the
chemoattractant gradient independently of their history. Our results confirm
that the KS model accurately predicts the behaviour of the AB population when
navigating through constant, shallow chemoattractant gradients Aminzare and
Sontag (2013); Erban and Othmer (2004). However, when the chemoattractant
landscape has spatially correlated fluctuations superposed to the gradient, AB
cells with short-term memory can exhibit greater drift velocity than predicted
by mere gradient-alignment.

Building on our numerical observations from the AB model, we extended work by
de Gennes de Gennes (2004) to derive an analytical approximation of the drift
velocity that captures the ability of cells to use spatial correlations. The
validity of our derivation hinges upon the assumption that the tumbling rate
remains close to the adapted state Xue (2015). We show that this assumption,
which is less restrictive than the standard shallow gradient assumption Erban
and Othmer (2004); Othmer and Hillen (2000), is enough to constrain the
relationship between the time scales of internal response and perceived
stimulus. Specifically, our results hold for rugged environments in the large
signal-to-noise regime, even if the typical shallow gradient assumption breaks
down. Since our model only allows small tumble biases, the mechanism described
here can be fully attributed to the linear filtering of perceived stimuli, and
is therefore distinct from the non-linear response considered in previous work
Dufour  _et al._ (2014); Long  _et al._ (2017). Because our analytic
derivation of the drift velocity (Eq. (25)) links population dynamics to cell
level parameters, it can be used to guide the experimental design to define
parameter regimes where deviations from the Keller-Segel limit are expected.

Our analytical model predicts an enhancement of the drift velocity in rugged
environments across a range of correlation lengths and cellular memories
(Figs. 3–4). This result is consistent with cells with memory performing a
non-local optimisation Gosztolai  _et al._ (2019) beyond local gradient
alignment. Importantly, when the landscape fluctuations are negligibly small
or they occur on long spatial scales, our model recovers the KS model, so that
the best strategy is purely local optimisation, as shown by previous studies
Vergassola  _et al._ (2007); Celani and Vergassola (2010). Our findings are
consistent with our fundamental understanding of bacterial chemotaxis: we find
that cells relying only on instantaneous information tumble more often,
leading to decreased average run length and drift velocity. Hence there is an
ecological benefit for the cell to adjust their memory actively to match the
length scales in the environment Krembel  _et al._ (2015). We also show that
our findings are in agreement with optimal information coding by the
chemotactic pathway Clausznitzer  _et al._ (2014); Becker  _et al._ (2015) and
provide a link between previous results on memory and filtering in the time-
domain Becker  _et al._ (2015); Andrews  _et al._ (2006) to chemotactic
spatial navigation.

Our model overpredicts the drift velocity of AB cells with short memory
navigating mildly rugged landscapes (Fig. 3c). We showed that, in this regime,
suboptimal filtering due to short memory results in the segregation of the
bacterial population into long-lived multi-modal distributions (Fig. 5). This
numerical observation suggests another distinct role for cellular memory as a
means to tune how much the ruggedness of the landscape is reflected in the
heterogeneity of the population responses.

Micro-scale ruggedness in the landscape can have diverse origins. Ruggedness
can appear naturally as a result of random spatial inhomogeneities associated
with porous or particulate media, or due to degrading matter and secretions of
other organisms. Such processes generate gradient structures on scales smaller
or comparable to the mean run-length of bacteria Blackburn  _et al._ (1998);
Stocker (2012). In these environments, bacteria experience the spreading pulse
of chemoattractant as a ruggedness in dilute, shallow background gradients
Hein  _et al._ (2016); Blackburn  _et al._ (1998). There is evidence for this
effect in native E. coli environments: in soil, the length scales are
estimated to vary between $\sim 2\,\mu\text{m}-1\text{ mm}$ Ngom  _et al._
(2011); in the digestive tract, the chemical environment is also thought to
have fine-grained spatial structure Hol  _et al._ (2016). Furthermore, some
aquatic microbes also exhibit run-tumble motion, albeit at higher run speeds
of $\leavevmode\nobreak\ \sim 100\,\mu\text{m }\text{s}^{-1}$ and with longer
mean run lengths of $68–346\,\mu\text{m}$ Watteaux  _et al._ (2015). Studies
have found that the habitats of such microbes have inhomogeneities with length
scales of $\sim 10-1000\,\mu\text{m}$, commensurate with the run lengths of
bacteria. In addition, time-varying spatial ruggedness can also appear as a
result of advection (stirring) of the medium, which causes it to form a
network of thin, elongated filaments Stocker (2012); Muñoz-García  _et al._
(2010) on scales of around $200–1000\,\mu\text{m}$, again commensurate with
the run length of aquatic microbes.

Our one-dimensional model allows us to gain analytical insights into the
relationship between memory and environmental fluctuations. In particular, we
find that the optimal memory is always smaller than the run length. Hence
cells are ‘blind’ to longer correlations in one dimension, a fact that is
consistent with short-term memory being typical of pre-adapted cells Segall
_et al._ (1986). In general, however, bacteria can optimise their adaptive
responses (and hence their memory) from seconds to minutes through receptor
methylation Krembel  _et al._ (2015), suggesting the relevance of longer-scale
memory-based sensing. This fact may be linked to the stronger directional
persistence of bacterial motion in two or three dimensions. With increased
directional persistence, we expect that cells can further improve their drift
speed by increasing their memory to exploit positive feedback from the
environment during up-gradient runs, i.e., by eliciting large tumble rate
reductions in comparison to small changes during down-gradient runs Tu  _et
al._ (2008); Dufour  _et al._ (2014); Long  _et al._ (2017). However,
understanding the interplay between memory and directional persistence would
be most relevant when studied in conjunction with an appropriate description
of 2D or 3D chemoattractant landscapes For instance, patchy landscapes, which
are frequently considered in the ecological theory Chang  _et al._ (2019), can
give rise to complex navigation strategies Hol  _et al._ (2016) aimed at
optimising the use of memory, swimming velocity and directional persistence.
Future theoretical work should therefore move from quantifying chemotactic
performance in terms of the drift speed in 1D landscapes towards studying
swimming in 2D and 3D heterogeneous landscapes using a generalised performance
measure, e.g., the amount of encountered attractant Gosztolai  _et al._
(2019).

Finally, although we have concentrated here on navigation in bacterial
chemotaxis, memory-based search strategies are also relevant in other
biological contexts for higher animals Gosztolai  _et al._ (2019). At a more
conceptual level, other search and exploration optimisation processes could
benefit from the consideration of agents with memory as a means to take
advantage of spatial correlations. For instance, processes of visual search
rely on specific neurons in the early visual cortex with a response function
commonly approximated by a bi-lobed function (c.f. Fig. 6 in Ref. Adelson and
Bergen (1985)). From this perspective, saccadic eye movements could be thought
of as a navigation over the image with bi-lobed neurons using their memory to
integrate the spatial correlations in the visual field as explored during the
visual search. Our work could also serve as inspiration for the development of
heuristic methods for optimisation problems over rugged landscapes, where
particles with memory could be used to complement gradient methods. Future
work would be needed to ascertain the significance of memory for optimisation
in high dimensions spaces and its effect in enhancing the efficiency of visual
search.

## Code availability

The code to carry out the simulations and analysis can be found at
github.com/barahona-research-group/Chemotaxis-In-Rugged-Landscapes under DOI:
10.5281/zenodo.3365951.

## Data availability

The data generated during the simulations is available with DOI:
10.14469/hpc/6522.

## Acknowledgements

We thank Philipp Thomas, José A. Carrillo and Julius B. Kirkegaard for
insightful comments. We thank Eduardo Sontag, on one hand, and Nils Becker and
Pieter Rein ten Wolde, on the other, for providing us with their agent-based
codes, which helped the development and validation of our models. AG
acknowledges funding through a PhD studentship under the BBSRC DTP at Imperial
College (BB/M011178/1). MB acknowledges funding from the EPSRC project
EP/N014529/1 supporting the EPSRC Centre for Mathematics of Precision
Healthcare.

## Author contributions

AG and MB designed the study. AG performed the numerical and analytical work
interacting closely with MB. AG and MB wrote the manuscript.

## Competing interests

The authors declare no competing interests.

## References

  * Blackburn  _et al._ (1998) N. Blackburn, T. Fenchel, and J. Mitchell, “Microscale nutrient patches in planktonic habitats shown by chemotactic bacteria,” Science 282, 2254–2256 (1998).
  * Ngom  _et al._ (2011) N. F. Ngom, P. Garnier, O. Monga, and S. Peth, “Extraction of three-dimensional soil pore space from microtomography images using a geometrical approach,” Geoderma 163, 127–134 (2011).
  * Hol  _et al._ (2016) F. J. H. Hol, O. Rotem, E. Jurkevitch, C. Dekker, and D. A. Koster, “Bacterial predator–prey dynamics in microscale patchy landscapes,” Proc. R. Soc. B 283, 20152154–9 (2016).
  * Muñoz-García  _et al._ (2010) J. Muñoz-García, Z. Neufeld, and C. Torney, “Nutrient exposure of chemotactic organisms in small-scale turbulent flows,” New J. Phys. 12, 103043 (2010).
  * Stocker (2012) R. Stocker, “Marine microbes see a sea of gradients,” Science 338, 628–633 (2012).
  * Porter  _et al._ (2011) S. L. Porter, G. H. Wadhams, and J. P. Armitage, “Signal processing in complex chemotaxis pathways,” Nat. Rev. Microbiol. 9, 153 EP – (2011).
  * Macnab and Koshland (1972) R. M. Macnab and D. E. Koshland, “The gradient-sensing mechanism in bacterial chemotaxis,” Proc. Natl. Acad. Sci. USA 69, 2509–2512 (1972).
  * Berg (1993) H. C. Berg,  _Random Walks in Biology_ (Princeton University Press, Princeton, New Jersey, 1993).
  * Block  _et al._ (1982) S. M. Block, J. E. Segall, and H. C. Berg, “Impulse responses in bacterial chemotaxis,” Cell 31, 215–226 (1982).
  * Andrews  _et al._ (2006) B. W. Andrews, T.-M. Yi, and P. A. Iglesias, “Optimal noise filtering in the chemotactic response of Escherichia coli,” PLOS Comp. Biol. 2, 1–12 (2006).
  * Aquino  _et al._ (2014) G. Aquino, L. Tweedy, D. Heinrich, and R. G. Endres, “Memory improves precision of cell sensing in fluctuating environments,” Sci. Rep. 4, 2075–9 (2014).
  * Shah  _et al._ (2000) D. S. H. Shah, S. L. Porter, A. C. Martin, P. A. Hamblin, and J. P. Armitage, “Fine tuning bacterial chemotaxis: analysis of Rhodobacter sphaeroides behaviour under aerobic and anaerobic conditions by mutation of the major chemotaxis operons and cheY genes,” EMBO J. 19, 4601–4613 (2000).
  * Krembel  _et al._ (2015) A. Krembel, R. Colin, and V. Sourjik, “Importance of multiple methylation sites in Escherichia coli chemotaxis,” PLOS One 10, 1–15 (2015).
  * Pierce-Shimomura  _et al._ (1999) J. T. Pierce-Shimomura, T. M. Morse, and S. R. Lockery, “The fundamental role of pirouettes in Caenorhabditis elegans chemotaxis,” J. Neurosci. 19, 9557–9569 (1999).
  * Polin  _et al._ (2009) M. Polin, I. Tuval, K. Drescher, J. P. Gollub, and R. E. Goldstein, “Chlamydomonas swims with two “gears” in a eukaryotic version of run-and-tumble locomotion,” Science 325, 487–490 (2009).
  * Taylor-King  _et al._ (2015) J. P. Taylor-King, B. Franz, C. A. Yates, and R. Erban, “Mathematical modelling of turning delays in swarm robotics,” IMA J. Appl. Math. 80, 1454–1474 (2015).
  * Ebbens and Howse (2010) S. J. Ebbens and J. R. Howse, “In pursuit of propulsion at the nanoscale,” Soft Matter 6, 726–738 (2010).
  * Viswanathan  _et al._ (1999) G. M. Viswanathan, S. V. Buldyrev, S. Havlin, M. G. E. da Luz, E. P. Raposo, and H. E. Stanley, “Optimizing the success of random searches,” Nature 401, 911–914 (1999).
  * Berg and Brown (1972) H. C. Berg and D. A. Brown, “Chemotaxis in Escherichia coli analysed by three-dimensional tracking.” Nature 239, 500–504 (1972).
  * Segall  _et al._ (1986) J. E. Segall, S. M. Block, and H. C. Berg, “Temporal comparisons in bacterial chemotaxis,” Proc. Natl. Acad. Sci. USA 83, 8987–8991 (1986).
  * Keller and Segel (1970) E. F. Keller and L. A. Segel, “Initiation of slime mold aggregation viewed as an instability,” J. Theor. Biol. 26, 399 – 415 (1970).
  * Othmer and Hillen (2000) H. G. Othmer and T. Hillen, “The diffusion limit of transport equations derived from velocity-jump processes,” SIAM J. Appl. Math. 61, 751–775 (2000).
  * Menolascina  _et al._ (2017) F. Menolascina, R. Rusconi, V. I. Fernandez, S. Smriga, Z. Aminzare, E. D. Sontag, and R. Stocker, “Logarithmic sensing in Bacillus subtilis aerotaxis,” NPJ Syst. Biol. Appl. 3, 16036– (2017).
  * Zhu  _et al._ (2012) X. Zhu, G. Si, N. Deng, Q. Ouyang, T. Wu, Z. He, L. Jiang, C. Luo, and Y. Tu, “Frequency-dependent Escherichia coli chemotaxis behavior,” Phys. Rev. Lett. 108, 128101 (2012).
  * Xue (2015) C. Xue, “Macroscopic equations for bacterial chemotaxis: integration of detailed biochemistry of cell signaling.” J. Math. Biol. 70, 1–44 (2015).
  * Dufour  _et al._ (2014) Y. S. Dufour, Xiongfei Fu, Luis H.-N., and T. Emonet, “Limits of feedback control in bacterial chemotaxis,” PLOS Comp. Biol. 10, 1–11 (2014).
  * Long  _et al._ (2017) J. Long, S. W. Zucker, and T. Emonet, “Feedback between motion and sensation provides nonlinear boost in run-and-tumble navigation,” PLOS Comp. Biol. 13, 1–25 (2017).
  * Gosztolai  _et al._ (2019) A. Gosztolai, J. A. Carrillo, and M. Barahona, “Collective search with finite perception: transient dynamics and search efficiency,” Front. Phys. 6, 153 (2019).
  * Tu  _et al._ (2008) Y. Tu, T. S. Shimizu, and H. C. Berg, “Modeling the chemotactic response of Escherichia coli to time-varying stimuli.” Proc. Natl. Acad. Sci. USA 105, 14855–14860 (2008).
  * Lambert and Kussell (2014) G. Lambert and E. Kussell, “Memory and fitness optimization of bacteria under fluctuating environments,” PLOS Genet. 10, 1–10 (2014).
  * Aminzare and Sontag (2013) Z. Aminzare and E. D. Sontag, “Remarks on a population-level model of chemotaxis: advection-diffusion approximation and simulations,” Preprint at https://arxiv.org/abs/1302.2605 (2013).
  * Becker  _et al._ (2015) N. B. Becker, A. Mugler, and P. R. ten Wolde, “Optimal prediction by cellular signaling networks,” Phys. Rev. Lett. 115, 258103 (2015).
  * Jiang  _et al._ (2010) L. Jiang, Q. Ouyang, and Y. Tu, “Quantitative modeling of Escherichia coli chemotactic motion in environments varying in space and time,” PLOS Comp. Biol. 6, 1–12 (2010).
  * Clausznitzer  _et al._ (2014) D. Clausznitzer, G. Micali, S. Neumann, V. Sourjik, and R. G. Endres, “Predicting chemical environments of bacteria from receptor signaling,” PLOS Comp. Biol. 10, 1–14 (2014).
  * Othmer  _et al._ (1988) H. G. Othmer, S. R. Dunbar, and W. Alt, “Models of dispersal in biological systems,” J. Math. Biol. 26, 263–298 (1988).
  * de Gennes (2004) P. G. de Gennes, “Chemotaxis: the role of internal delays,” Eur. Biophys. J. 33, 691–693 (2004).
  * Clark and Grant (2005) D. A. Clark and L. C. Grant, “The bacterial chemotactic response reflects a compromise between transient and steady-state behavior,” Proc. Natl. Acad. Sci. USA 102, 9150–9155 (2005).
  * Celani and Vergassola (2010) A. Celani and M. Vergassola, “Bacterial strategies for chemotaxis response,” Proc. Natl. Acad. Sci. USA 107, 1391–1396 (2010).
  * Yi  _et al._ (2000) T-M Yi, Y. Huang, M. I. Simon, and J. Doyle, “Robust perfect adaptation in bacterial chemotaxis through integral feedback control,” Proc. Natl. Acad. Sci. USA 97, 4649–4653 (2000).
  * Ma  _et al._ (2009) W. Ma, A. Trusina, H. El-Samad, W. A. Lim, and C. Tang, “Defining Network Topologies that Can Achieve Biochemical Adaptation,” Cell 138, 760–773 (2009).
  * Rousset and Samaey (2013) M. Rousset and G. Samaey, “Individual-based models for bacterial chemotaxis in the diffusion asymptotics,” Math. Models Methods Appl. Sci. 23, 2005–2037 (2013).
  * Erban and Othmer (2004) R. Erban and H. Othmer, “From individual to collective behavior in bacterial chemotaxis,” SIAM J. Appl. Math 65, 361–391 (2004).
  * Tostevin and ten Wolde (2009) F. Tostevin and P. R. ten Wolde, “Mutual information between input and output trajectories of biochemical networks,” Phys. Rev. Lett. 102, 218101 (2009).
  * Carrillo and Toscani (1998) J. A. Carrillo and G. Toscani, “Exponential convergence toward equilibrium for homogeneous Fokker–Planck-type equations,” Math. Method. Appl. Sci. 21, 1269–1286 (1998).
  * Frankel  _et al._ (2014) N. W. Frankel, W. Pontius, Y. S. Dufour, J. Long, L. Hernandez-Nunez, and T. Emonet, “Adaptability of non-genetic diversity in bacterial chemotaxis,” eLife 3, e03526 (2014).
  * Vergassola  _et al._ (2007) M. Vergassola, E. Villermaux, and B. I. Shraiman, “’Infotaxis’ as a strategy for searching without gradients,” Nature 445, 406 EP – (2007).
  * Hein  _et al._ (2016) A. M. Hein, D. R. Brumley, F. Carrara, R. Stocker, and S. A. Levin, “Physical limits on bacterial navigation in dynamic environments,” J. R. Soc. Interface 13, 20150844–8 (2016).
  * Watteaux  _et al._ (2015) R. Watteaux, R. Stocker, and J. R. Taylor, “Sensitivity of the rate of nutrient uptake by chemotactic bacteria to physical and biological parameters in a turbulent environment,” J. Theor. Biol. 387, 120 – 135 (2015).
  * Chang  _et al._ (2019) W. K. Chang, D. VanInsberghe, and L. Kelly, “Towards a potential landscape framework of microbiome dynamics,” Preprint at https://biorxiv.org/content/early/2019/11/14/584201 (2019).
  * Adelson and Bergen (1985) E. H. Adelson and J. R. Bergen, “Spatiotemporal energy models for the perception of motion,” J. Opt. Soc. Am. A 2, 284–299 (1985).