# The role of tumbling frequency and persistence
in optimal run-and-tumble chemotaxis

Julius B. Kirkegaard and Raymond E. Goldstein  Department of Applied
Mathematics and Theoretical Physics, Centre for Mathematical Sciences,
University of Cambridge, Wilberforce Road, Cambridge CB3 0WA, United Kingdom

###### Abstract

One of simplest examples of navigation found in nature is run-and-tumble
chemotaxis. Tumbles reorient cells randomly, and cells can drift toward
attractants or away from repellents by biasing the frequency of these events.
The post-tumble swimming directions are typically correlated with those prior,
as measured by the variance of the reorientation angle distribution. This
variance can range from large, in the case of bacteria, to so small that
tumble events are imperceptible, as observed in choanoflagellates. This raises
the question of optimality: why is such a range of persistence observed in
nature? Here we study persistent run-and-tumble dynamics, focusing first on
the optimisation of the linearised chemotactic response within the two-
dimensional parameter space of tumble frequency and angular persistence.
Although an optimal persistence does exist for a given tumble frequency, in
the full parameter space there is a continuum of optimal solutions.
Introducing finite tumble times that depend on the persistence can change this
picture, illuminating one possible method for selecting tumble persistence
based on species-specific reorientation dynamics. Moving beyond linear theory
we find that optimal chemotactic strengths exist, and that these maximise
reaction when swimming in a wrong direction, but have little or no reaction
when swimming with even the slightest projection along the chemoattractant
gradient.

##  I Introduction

Chemotaxis, the ability to navigate concentration fields of chemicals, is a
ubiquitous feature of the microscopic world. Performed by uni- and
multicellular organisms alike, it represents one of the simplest forms of
navigation. Within this simplicity, various strategies exist. For instance,
certain spermatozoa measure chemoattractant gradients by swimming in helical
trajectories and bias the helical axis to move directly towards the
chemoattractant (Friedrich and Juicher,, 2007; Jikeli et al.,, 2015). Green
algae can swim towards light-intense regions by measuring light source
directions as they rotate around their own swimming axis (Yoshimura and
Kamiya,, 2001; Drescher et al.,, 2010), but also bias their navigation by
switching between synchronous and anti-synchronous beating of their flagella
(Polin et al.,, 2009). The slime mould D. discoideum is large enough to
measure directly the spatial concentration gradients in cAMP, along which it
navigates (Bonner and Savage,, 1947). The epitome of chemotaxis is perhaps the
run-and-tumble of certain peritrichously flagellated bacteria such as E. coli
(Berg and Brown,, 1972).

Run-and-tumble motion is comprised of approximately straight lines (runs)
interrupted by reorientation events (tumbles), as shown in Fig. 1. For
example, in peritrichous bacteria, the helical flagella rotate counter-
clockwise and form a coherent bundle during swimming. A tumble is induced when
(some of) the flagella reverse their rotational direction and the bundle is
disrupted (Fig. 1a). This creates a large, transient, reorientation.
Navigation along a gradient of chemoattractant becomes possible if the
frequency of tumbling is biased in response to the chemoattractant
distribution. This is a type of stochastic navigation in the sense that the
organisms that perform it do not swim directly in the desired direction, but
rather in a random direction and later decide whether such a turn was correct.

The tumbling frequency is modulated through measurements of the variation in
concentration of chemoattractants, illustrated by the background of Fig. 2. In
an idealised scenario, the reorienting tumbles result in unbiased new
directions, uniformly chosen from the unit sphere, but this is not typically
the case. Instead, a persistence with the previous direction is present (Berg
and Brown,, 1972). In fact, for some species, the individual reorientations
are so small that they are hardly observable. This is the case in colonies of
choanoflagellates (Kirkegaard et al., 2016a, ), within which the flagella beat
independently (Kirkegaard et al., 2016b, ) and a reorientation event may
simply arise from slight modulation of the beating of a single flagellum (Fig.
1b). These smaller tumbles, or directionally persistent tumbles, add up to a
smoother swimming while still allowing navigation. Fig. 2 shows two
realisations of run-and-tumble swimming. In blue is the case of full-
reorientation tumbles and in red is very persistent tumbles occurring with
higher frequency. Over long time-scales both of these swimmers perform random
walks biased in the direction of the chemoattractant signal.

Figure 1: Run-and-tumble. (a) Swimming and tumbling of a peritrichous
bacterium. During swimming the flagella rotate counter-clockwise and form a
bundle resulting in a run. Clockwise rotation one or more of the flagella
breaks the bundle and results in a tumble that reorients the cell. (b)
Choanoflagellate colony reorientation event. Each cell’s flagellum beats
independently of the others. A change in the beating dynamics of one cell
(green flagellum) can cause a small reorientation of the colony as a whole.

A strong theoretical understanding of chemotaxis exists (Tindall et al.,
2008a, ; Tindall et al., 2008b, ), including the filtering of chemoattractant
signals to which the cells react (Segall et al.,, 1986; Celani and
Vergassola,, 2010), the fundamental limits of measurement accuracy of such
signals (Mora and Wingreen,, 2010) and the limits they impose on navigation
(Hein et al.,, 2016). Theories of chemotaxis are typically developed in the
weak-chemotaxis limit (Celani and Vergassola,, 2010; Locsei,, 2007; Locsei and
Pedley,, 2009; Reneaux and Gopalakrishnan,, 2010; Mortimer et al.,, 2011), the
linear theory of which provides accurate explanations of many experimental
observations. Theory (Locsei,, 2007) and simulation (Nicolau et al.,, 2009) of
chemotactic bacteria have also showed that for otherwise equal chemotactic
parameters, directional persistence of tumbles, as observed in experiments,
can lead to enhanced chemotaxis.

This raises a more general question: could the effect of changing one
parameter, such as directional persistence, be compensated by simultaneously
changing another? Here, we address this question of global optimality, and
examine effects that lead to the existence of optima. For example, in
linearised theories, the drift velocities for large chemotactic strength and
for steep gradients can become unbounded, and thus the evaluation of one
effect is done at fixed chemotactic response. But microorganisms do not have
the restrictions that come with choosing theories that are analytically
tractable. In real systems, the drift velocity will be limited (trivially) due
to the finite swimming speed of the organisms and (more importantly) by
uncertainties of measurements in noisy environments combined with diffusion.
Throughout this study we optimise for the performance of a single organism,
neglecting population effects (Peaudecerf and Goldstein,, 2015).

##  II Model

The model of chemotaxis used here assumes that organisms determine
concentration gradients by comparing their concentration measurements at
different times as they move through the medium, rather than detecting
gradients over their own body, as is possible for organisms considerably
larger than bacteria (Berg and Purcell,, 1977). To be precise, we assume that
as a cell swims it measures only the local chemoattractant concentration
$c({\boldsymbol{x}},t)$ at its present position ${\boldsymbol{x}}$. Moreover,
in this section the concentration is taken to be linear in position,
$c({\boldsymbol{x}})=c_{0}+\alpha\,x$, allowing the notation
$c(t)=c({\boldsymbol{x}}(t))$ for a given trajectory ${\boldsymbol{x}}(t)$.
Cells are thought to store the history of these measurements, and use this to
bias their tumbling frequency $\lambda$. In the present model, this is
embodied by the relationship $\lambda=\lambda_{0}\,\lfloor 1+q\rfloor$, where
$\lfloor\cdot\rfloor=\max(0,\,\cdot)$. Here, $q$ is the biaser, determined by
a linear convolution of $c$,

$q(t)=\int_{0}^{\infty}c(t-t^{\prime})\,\kappa(t^{\prime})\,\mathrm{d}t^{\prime}.$
(1)

We take the kernel to be one studied previously and which corresponds well to
experimental measurements (Segall et al.,, 1986; Celani and Vergassola,,
2010),

$\kappa(t)=\frac{\beta\gamma^{2}}{\alpha\,v}e^{-\gamma
t}\left[\frac{\left(\gamma\,t\right)^{2}}{2}-\gamma\,t\right],$ (2)

where $v$ is the swimming speed and $\gamma$ is the memory time scale of past
measurements. The normalisation is chosen such that $\max|q|=\beta$ in the
absence of noise, and hence $\beta$ solely specifies the chemotactic strength.
The kernel satisfies $\int k(t)\,\mathrm{d}t=0$ which gives perfect adaptation
to any background chemoattractant concentration. This criteria arises
naturally from maximising the minimum chemotactic efficiency over all
chemoattractant profiles (Celani and Vergassola,, 2010). In particular, this
is an important feature that will not arise from maximising drift velocity
alone and which we thus impose a priori here.

Figure 2: Run-and-tumble trajectories. Both simulated trajectories drift to
the right, starting from the origin. Full tumbles are shown in blue
($k=0,\,\lambda_{0}=0.1$) and persistent but frequent tumbles in red
($k=10,\,\lambda_{0}=2.0$). Circles indicate tumbles. Shared parameters:
$D_{r}=0.1,\,\beta=1/2,\,\gamma=1.$

We consider cells swimming in two dimensions in an instantaneous direction
$\theta(t)$ with velocity $v$, and discuss the three-dimensional case in
Appendix D. This direction is modulated by both rotational diffusion as
$\mathrm{d}\theta=\sqrt{2D_{r}}\,\mathrm{d}W$, where $W$ is a standard Wiener
process, and by tumbles, the size of which are chosen from a von-Mises
distribution with parameter $k$,
$p(\Delta\theta)=\exp(k\cos(\Delta\theta))/2\pi I_{0}(k)$, where $I_{n}$ are
the modified Bessel functions of the first kind. Thus $k$ specifies the
persistence of the tumbles, $k=0$ corresponding to full tumbles.

##  III Measurement Time-scale

If the time $1/\lambda_{0}$ between tumbles is too long compared to the
rotational diffusion time $1/D_{r}$, the trajectories will be reoriented by
rotational diffusion and the organism will have lost the ability to bias its
motion in any useful way. Thus, the biasing of tumbles must outcompete
rotational diffusion and we expect $\lambda_{0}\gtrsim D_{r}$. In the absence
of measurement noise, and if the organism can make instantaneous measurements
($\gamma\rightarrow\infty$), increasing the chemotactic strength will
monotonically increase the chemotactic drift, and in the limit
$\beta\rightarrow\infty$ chemotaxis becomes perfect, despite the hindering
effects of rotational diffusion. But, we emphasise that this is only possible
in the absence of measurement noise. Here, in contrast, we are interested in
the noise-limited situation, and with noise comes another time scale, that
over which accurate measurements can be made (see Appendix F for a simple
lattice calculation illustrating this point).

To illuminate this situation we perform simulations in which cells are placed
in a constant gradient (linear increase) of discrete chemoattractants. In a
periodic $2L\times 2L$ box, $N$ molecules are placed, decreasing linearly in
concentration from $x=0$. This is achieved by choosing each molecule’s
position as $x=L\sqrt{|U_{1}|}\,\text{sign}(U_{1}),\,y=LU_{2}$, where $U_{i}$
is uniformly distributed on $[-1,1]$. $c(t)$ is then defined to be the number
of molecules within a cell’s area. This can be evaluated efficiently by
storing the molecules in a $k$-D tree, allowing for fast simulations with
billions of molecules.

Figure 3: Chemotactic efficiency as a function of $\gamma$. Each curve
corresponds to different concentration levels; at the lowest concentration
(blue data) each cell senses on average $n\sim 1.5$ molecules, while at the
highest (red), $n\sim 2000$ are sensed. Shaded background indicates standard
error of the simulations. Inset shows optimal $\gamma$ as a function of $n$
for $\lambda_{0}\in\\{0.1,1.0,5.0\\}$. $D_{r}=0.1,\,\gamma=1$.

For the purposes of the present discussion, we define the chemotactic
efficiency proportional to the average value of the concentration experienced
by the organism in steady state

$\eta\propto\langle
c\rangle=\int\\!c({\boldsymbol{x}})P({\boldsymbol{x}})\,\mathrm{d}{\boldsymbol{x}},$
(3)

where $P({\boldsymbol{x}})$ is the steady-state probability distribution. The
normalisation is chosen such that $\eta=1$ corresponds to perfect chemotaxis.

Fig. 3 shows $\eta$ as function of the measurement rate $\gamma$ for various
molecular concentrations. The curves clearly reveal the existence of an
optimal $\gamma$ for each choice of the (average) number of molecules sensed.
Choosing $\gamma$ too low means slow reaction, but with $\gamma$ too high the
organism does not have time to make an accurate measurement before previous
information is forgotten. Varying the chemoattractant concentration (but not
the gradient) shifts the optimal $\gamma$. At higher concentrations, the
measurement noise is lower (Mora and Wingreen,, 2010), and thus less time is
needed to make an accurate measurement. The inset of Fig. 3 shows how the
optimal $\gamma$ varies with the concentration, and further shows that, within
the resolution of our simulations, this optimum is independent of the base
tumbling frequency $\lambda_{0}$. This independence means that we can fix
$\gamma$ to its optimal value without specifying the value of $\lambda_{0}$.

In this noise-dominated regime, $\gamma$ is thus set by the chemoattractant
concentration. If cells are kept in a chemostat with fixed concentration and
gradient, as is the case considered here, the optimal $\gamma$ is thus
indicative of the underlying noise levels. In the following sections we fix
$\gamma$, thus implicitly defining the noise levels. The goal then becomes to
find the optimal choice of the remaining parameters for a given $\gamma$. Our
approach ignores spatial variations in noise, but conclusions made are
confirmed by checking them against the full simulation setup used in this
section.

##  IV Tumbling Frequency & Persistence

In earlier theoretical work, persistence of tumbles has been shown to enhance
the chemotactic drift velocity (Locsei,, 2007; Nicolau et al.,, 2009).
Possible rationalizations for this effect include the idea of information
relevance; for persistent tumbles, the gradient information (stored in $q$,
Eq. 1) remains more relevant than for full tumbles, where a completely random
direction is chosen. It has also been shown that an optimum base tumbling
frequency $\lambda_{0}$ exists (Celani and Vergassola,, 2010). Intuitively, in
the low-noise limit, this optimum should be set by the rotational diffusion
constant $D_{r}$, in order to dominate rotational diffusion but not hinder
drift. Intuitively, one expects that introducing persistence, which results in
smaller angular deflections from tumbles, would shift the optimal tumble
frequency to higher values. So while it is clear that persistence can increase
the chemotactic drift for a given base tumble frequency, it is not clear what
the effect is if variations in $\lambda_{0}$ are also allowed.

To study this, we simulated cells performing chemotaxis in a constant gradient
for various persistence parameters $k$, while varying $\lambda_{0}$. The
results shown in Fig. 4 confirm the intuition outlined above; for large base
tumbling frequency $\lambda_{0}$, increasing the persistence $k$ leads to
increased chemotactic drift, as previously found. However, for low values of
$\lambda_{0}$ the opposite effect is found. There is thus a trade-off between
frequency and persistence of tumbles.

To gain further insight we study the relevant Fokker-Planck equation. As shown
previously (Celani and Vergassola,, 2010), the dynamics of the biaser $q$ can
be made Markovian by introducing three internal variables (moments of $c$)

$m_{j}=\int_{-\infty}^{t}e^{-\gamma(t-t^{\prime})}(t-t^{\prime})^{j}c(t^{\prime})\,\mathrm{d}t^{\prime},$
(4)

which obey a coupled system of differential equations
$\partial_{t}m_{j}=c(t)\delta_{j0}-\gamma m_{j}+jm_{j-1}$. It follows that our
system can be fully described by a Fokker-Planck equation for a distribution
function $P(x,\theta,\\{m_{j}\\},t)$

$\displaystyle\frac{\partial P}{\partial t}+v\cos\theta\,\frac{\partial
P}{\partial x}=$
$\displaystyle\,\,D_{r}\frac{\partial^{2}P}{\partial\theta^{2}}+\lambda_{0}\lfloor
1+q(t)\rfloor\left[\int\,\frac{e^{k\cos(\theta-\theta^{\prime})}}{2\pi
I_{0}(k)}P(\theta^{\prime})\,\mathrm{d}\theta^{\prime}-P\right]$ (5)
$\displaystyle-\sum_{j}\partial_{m_{j}}[\delta_{j,0}\,c(x)\,+jm_{j-1}-\gamma
m_{j}]\,P,$

where

$q(t)=\frac{\beta\gamma^{2}}{\alpha\,v}\left(\frac{1}{2}\gamma^{2}m_{2}-\gamma
m_{1}\right)~{}.$ (6)

Figure 4: Drift efficiency as a function of tumble frequency. Data from direct
simulation of full model are shown for $k=0$ (blue), $k=3$ (red), and $k=6$
(green). Each data point is the result of 10,000 simulations and shaded
background indicates standard error, with $D_{r}=0.1,\,\beta=1/2,\,\gamma=1$.
Linearised theory is indicated by dashed lines.

We begin by solving this system for small $\beta$. Later we will argue that
our conclusions remain qualitatively correct also for large $\beta$. In steady
state, we find (Appendix A)

$\langle\cos\theta\rangle=\frac{\beta\gamma^{3}\lambda_{k}}{2(D_{r}+\lambda_{k})(D_{r}+\gamma+\lambda_{k})^{3}}+\mathcal{O}(\beta^{2}),$
(7)

where $\lambda_{k}=\lambda_{0}\left[1-I_{1}(k)/I_{0}(k)\right]$. Note that the
only place $\lambda_{0}$ enters is through the quantity $\lambda_{k}$, which
has the optimal value

$\lambda_{k}^{*}=\frac{1}{3}\left(\sqrt{4D_{r}^{2}+3\gamma
D_{r}}-D_{r}\right)~{}.$ (8)

From this fact, we conclude that the trade-off between tumbling frequency and
tumble persistence is perfectly balanced; changes in $k$ can be precisely
compensated by changes in $\lambda_{0}$.

Fig. 4 shows how this small-$\beta$ result accurately matches the full
numerical results even for $\beta=1/2$. So while persistence can lead to
enhanced chemotaxis, we find that this has nothing inherently to do with the
persistence of the tumbles themselves, as the same increase can be achieved
simply by lowering the base tumbling frequency.

With constant $\lambda_{0}$, letting $k\rightarrow\infty$ results in
negligible drift. For large $k$, $\left[1-I_{1}(k)/I_{0}(k)\right]^{-1}\sim
2k$. Thus we see that a continuous version of run-and-tumble (Kirkegaard et
al., 2016a, ) emerges in the limit $k\rightarrow\infty$ if $\lambda_{0}$ is
scaled linearly with $k$, and we conclude that such a strategy is equally
optimal to any other persistence of tumbles with the correct choice of tumble
frequency. These results arise because we allow $\lambda_{0}$ to be chosen
independently of $\gamma$. Without persistence, chemotaxis is optimised for
$\lambda_{0}$ and $\gamma$ of similar order. For cells with large persistence,
however, optimisation leads to $\lambda_{0}$ much larger than $\gamma$.

The expansion $P(\theta,\cdots)=a_{0}(\cdots)+a_{1}(\cdots)\cos\theta$
captures the steady state distribution well, and the form of $\lambda_{k}$ can
only change if higher order Fourier modes become important. This is not case
even in the high $\beta$ regime, and so these conclusions are also valid
there. Second order effects such as small dependencies of the optimal $\gamma$
on $\lambda_{0}$ and $k$ could also perturb the result of perfect trade-off
between tumble frequency and persistence. Furthermore, although we only
considered the steady state here, the conclusions apply to the transient
behaviour of the system. Our conclusions also hold in three dimensions as
demonstrated in Appendix D.

Real bacteria are observed to have an angular distribution of tumbles with a
non-zero mode (Berg and Brown,, 1972). To model this, we consider the
reorientation distribution
$g(\theta,\theta^{\prime})=\sum_{\pm}e^{k\cos(\pm\mu+\theta-\theta^{\prime})}/\penalty
04\pi I_{0}(k)$. This results in the substitution
$I_{1}(k)/I_{0}(k)\rightarrow I_{1}(k)/I_{0}(k)\cos\mu$ in Eq. (7) (see
Appendix B), leaving unchanged our conclusions. If the turns are biased in one
direction (e.g. turning more clockwise than counter-clockwise), such that
$g(\theta,\theta^{\prime})=e^{k\cos(\mu+\theta-\theta^{\prime})}/2\pi
I_{0}(k)$, the efficiency can surpass that of unbiased cells. In this case the
optimum strategy involves cells that continuously rotate, modulating their
rotation speed as they swim (Appendix C). While this is interesting behaviour,
such a bias is a 2D phenomenon, although a related optimality may exist in 3D.

The fact that no single persistence value is globally preferable fits well
with the experimental variations seen between biological species. The question
still remains, however, if there are other effects that could induce a
preferred tumble persistence. So far we have assumed the tumbles to be
instantaneous. Including a finite tumble time can change the conclusions. In
particular, since the optimal tumbling frequency for persistent tumbles is
large, adding a constant time for each tumble results in large amounts of time
in which no chemotactic progress is made, hence disfavouring persistence, On
the other hand, one would expect a persistent tumble to take less time than a
full tumble. The average tumble time $\langle\tau\rangle$ should depend on the
average angle turned. The precise form of this dependence will change with
reorientation method. If the tumbling rotation is ballistic, the mean
reorientation time should be proportional to the mean angle turned. If, on the
other hand, the cell relies on a diffusive method (which includes simply not
swimming), the reorientation time will be proportional to the mean of the
squared angle. We parametrise this with the exponent $\alpha$, with $\alpha=1$
for ballistic reorientations and $\alpha=2$ for diffusive and a mixture for
values in-between. The mean tumbling time is thus

$\langle\tau\rangle=\frac{\tau_{0}}{\pi
I_{0}(k)}\int_{0}^{\pi}\\!\delta^{\alpha}e^{k\cos\delta}\,\mathrm{d}\delta.$
(9)

The insets of Fig. 5 show trajectories for ballistic diffusive and
intermediate exponents. For small chemotactic strength it is easy to
incorporate this effect. The fraction of time spent swimming will be
$1/(1+\langle\tau\rangle\lambda_{0})$, so we find

$\langle\cos\theta\rangle\rightarrow\frac{1}{1+\langle\tau\rangle\lambda_{0}}\frac{\beta\gamma^{3}\lambda_{k}}{2(D_{r}+\lambda_{k})(D_{r}+\gamma+\lambda_{k})^{3}}.$
(10)

Crucially, $\lambda_{0}$ now appears alone, and we thus expect a global
optimum to appear. Fig. 5 shows $\langle\cos\theta\rangle$ evaluated for
various exponents. For ballistic ($\alpha=1$) we find that full tumbles
($k=0$) are optimal. For diffusive $\alpha=2$, the continuous dynamics
($k\rightarrow\infty$) become optimal. In-between, as shown in Fig. 5b, a
finite $k$ optimum appears. A finite non-zero persistence also appears for
diffusive scaling with an added constant, i.e. for Eq. (9) plus a constant.

Figure 5: Drift efficiency $\langle\cos\theta\rangle$ with finite tumbling
time. Panels correspond to different tumble time exponents: (a) $\alpha=1.0$,
(b) $1.7$, and (c) $2.0$. Colour scale shows the top 20% range of drift
velocities. Insets show examples of reorientation trajectories for with
exponent $\alpha$, the angle on the circle indicating the orientation and the
radial distance indicating time. Common parameters:
$D_{r}=0.1,\,\beta=1/2,\,\gamma=1,\,\tau_{0}=1$.

##  V Chemotactic Strength

We now ask whether optimality exists for the chemotactic strength parameter
$\beta$. Of course, in models linearised in $\beta$ no such optimality can
appear, and we must seek a different approach. Averaging over many numerical
realisations of the model would allow these effects to be captured, but a
large number of realisations is needed to gain accurate statistics, rendering
parameter space exploration hard. Hence, we begin this section by gaining
intuition through a more tractable model, which gives a good qualitative
understanding of the problem.

The crucial insight for this simplified model is that in a constant gradient
there is nothing to distinguish one value of the position variable $x$ from
another. In our full model, the biaser $q(t)$ relaxes to $-\beta$ times the
cell’s estimate of $\cos\theta$ on a time scale $\sim\gamma$. Such a behaviour
can be modelled by the Langevin equation

$\displaystyle\mathrm{d}q=-\frac{\gamma}{4}\,(q+\beta\cos\theta)\,\mathrm{d}t+\beta\sqrt{2\sigma}\,\mathrm{d}W~{},$
(11)

where the prefactor of $1/4$ is chosen so that the effective relaxation time
matches that of the kernel $\kappa$ used in the full model, and we have
introduced a noise term (such a noise term plays no role in the linearised
system). We can specify this system fully through a Fokker-Planck equation for
$P(\theta,q,t)$

$\frac{\partial\hskip 0.50003ptP}{\partial
t}=\frac{\gamma}{4}\frac{\partial}{\partial
q}(q+\beta\cos\theta)\,P+\sigma\beta^{2}\,\frac{\partial^{2}P}{\partial
q^{2}}+D_{r}\frac{\partial^{2}P}{\partial\theta^{2}}+\lambda_{0}\lfloor
1+q\rfloor\left[\int\,\frac{e^{k\cos(\theta-\theta^{\prime})}}{2\pi
I_{0}(k)}P(\theta^{\prime})\,\mathrm{d}\theta^{\prime}-P\right].$ (12)

The optimal behaviour of the original system is well-captured by this reduced
model (Appendix E). Crucially, equation (12) is simple enough to be solved
numerically using a hybrid spectral-finite difference method. Again we find
that for all parameters the same efficiency can be obtained for any $k$ by a
simple rescaling of $\lambda_{0}$. We thus set $k=0$ in the remainder of this
section without loss of generality.

Figure 6: Drift efficiency as a function of chemotactic strength. (a)
Variations in $\beta$ and $\lambda_{0}$ reveal a maximum as
$\beta\rightarrow\infty$, $\lambda_{0}\rightarrow 0$. Dashed curve is
analytical approximation to optimum region. (b) Chemotactic drift with
modulation of the form $\tilde{\beta}\lfloor q\rfloor$. Curves vary from
$\sigma=0.15$ (red) to $\sigma=1.0$ (blue). (c) Full particle simulations with
average molecules sensed by cells varying from 0.5 (blue) to 3 (red). Common
parameters: $D_{r}=0.1,\,\beta=1/2,\,\gamma=1$.

Fig. 6a shows the resulting chemotactic drift under variation of the
chemotaxis strength $\beta$ and the base tumbling frequency $\lambda_{0}$. For
a given $\lambda_{0}$, an optimal chemotactic strength does indeed exist.
Choosing the chemotactic strength too high, evidently, also results in too
many tumbles. Fig. 6a also shows, however, that under variations of both
$\beta$ and $\lambda_{0}$, the optimal is found for $\beta\rightarrow\infty$.
For large $\beta$ the optimum lies on a straight line (power law) relating
$\beta$ to $\lambda_{0}$.

To understand what sets the optimal chemotactic strength, we seek an
analytical approach, but since there is no perturbative small parameter we
examine instead a Fourier-Hermite expansion of the form

$p(\theta,q)=\sum_{n=0}^{N}\sum_{m=0}^{M}a_{nm}\cos(n\theta)\,H_{m}(q/\zeta)\,e^{-q^{2}/\zeta^{2}},$
(13)

where $H_{m}$ are the Hermite polynomials. The choice of this expansion arises
from the fact that $q$ resembles an Ornstein-Uhlenbeck process, the solution
of which is Gaussian, with a scale $\zeta$, which, for a true Ornstein-
Uhlenbeck process would be $\sim\sqrt{4\sigma/\gamma}$. Presently,
$\cos\theta$ also contributes to variations in $q$, and so
$\zeta\sim\sqrt{1+4\sigma/\gamma}$. Here, we truncate at $N=M=1$, which, while
yielding numerically inaccurate results nevertheless reveals the key dynamics.
Higher-order terms can easily be calculated, but the expressions become
lengthy. Exploiting orthogonality, the steady state coefficients
$\\{a_{nm}\\}=(a_{00},a_{10},a_{01},a_{11})$ are found as the null space of

$\displaystyle\left(\begin{array}[]{cccc}0&0&0&0\\\
0&-\frac{\gamma}{4}&-\frac{\gamma}{8\zeta}&0\\\
0&0&\frac{\lambda_{0}}{2}\,\text{erfc}(\frac{1}{\zeta\beta})-\frac{\lambda_{0}\zeta\beta}{2\sqrt{\pi}}\exp(\frac{-1}{\zeta^{2}\beta^{2}})-\lambda_{0}-D_{r}&-\frac{1}{2}\lambda_{0}\zeta\beta(1+\text{erc}(\frac{1}{\zeta\beta}))\\\
\frac{-\gamma}{4\beta}&0&-\frac{1}{4}\lambda_{0}\zeta\beta(1+\text{erf}(\frac{1}{\zeta\beta}))&\frac{1}{2}\lambda_{0}\,\text{erfc}(\frac{1}{\zeta\beta})-\lambda_{0}(1+\frac{\zeta\beta}{\sqrt{\pi}}\exp(\frac{-1}{\zeta^{2}\beta^{2}})\end{array}\right),$
(18)

whence $\langle\cos\theta\rangle=a_{10}/(2\,a_{00})$. Optimising this for
$\lambda_{0}$ we obtain the dashed white curve in Fig. 6a. In the limit
$\beta\rightarrow\infty$ this has the form

$\lambda_{0}\sim\frac{D_{r}(D_{r}+\gamma/4)}{\sqrt{1+4\sigma/\gamma}}\,\frac{1}{\beta}.$
(19)

Although the expansion does not quite capture the location of the optimum, the
correct scaling is obtained. The global optimum is found at
$\beta\rightarrow\infty$ and we learn that $\lambda_{0}\beta$ tends to a
finite value in that limit. In detail, the optimisation tries to diminish the
base tumbling contribution in the expression $\lambda_{0}\lfloor 1+q\rfloor$
and the optimum is found in limit where $\lambda_{0}\lfloor
1+q\rfloor\rightarrow\lambda_{0}\lfloor q\rfloor$. Explicitly making this
substitution in Eq. (12) and defining $\tilde{\beta}=\lambda_{0}\beta$, we
obtain a system that has a finite optimal value of chemotactic strength. This
is shown in Fig. 6 for various noise strengths $\sigma$. To verify our
conclusions based on this model we turn to the full simulation. Exactly as in
the simplified model, we find optimum behaviour after making the substitution
$\lambda_{0}\lfloor 1+q\rfloor\rightarrow\lambda_{0}\lfloor q\rfloor$. This is
shown in Fig. 6c for various levels of chemoattractant concentrations,
confirming our conclusions.

It is perhaps surprising that the optimum is found in this limit, since no
modulation of tumbling frequency then can occur if $q<0$, which is the case
when the cell swims just slightly in the correct direction, and thus in the
limit of no noise, the angular distribution will be governed simply by
rotational diffusion on $\theta\in[-\pi/2,\pi/2]$. In this optimal limit, the
cells have minimised the time they spend swimming in any wrong direction,
which, evidently, even though it leads to no active modulation for $q<0$, is
also the optimum for the total chemotactic drift. For stochastic taxis to
work, the modulation must necessarily be a monotonically increasing function
of $q$. Strong reaction when swimming in the wrong direction ($q>0$) is thus
typically coupled will smaller reaction when swimming in the correct direction
($q<0$). Our results show, at least for the presently chosen form of
modulation, that with this trade-off the best choice is to react very strongly
when swimming in the wrong direction, even though this reduces the
effectiveness of chemotaxis while swimming in the right direction.

##  VI Conclusions

In this study we have taken an approach to understanding run-and-tumble
chemotaxis based on global parameter optimisation. For the specific system
studied here, cells in constant gradients, we have focused on the base
tumbling frequency $\lambda_{0}$, tumbling persistence $k$, and chemotactic
strength $\beta$ as key parameters. Varying any one parameter alone, there is
a unique value that optimises the chemotactic drift, but when all parameters
are free there is a higher-dimensional optimal locus.

In particular, the trade-off in optimality between the base tumbling frequency
and tumble persistence is “perfect” in the sense that any increase, say, in
persistence can be countered by an increase in base tumble frequency. After a
persistent tumble, it would seem that the current value of $q$ would stay more
relevant than for a full tumble, indicating that persistence could lead to
enhanced chemotaxis. The intuition behind this argument is based on comparing
a single full tumble to a single persistent tumble, but a more appropriate
comparison would be to a series of persistent tumbles. And as evident by our
calculations, comparing in this way the argument of preservation of
information leads to similar behaviour for all persistence parameters. One
might also argue for the opposite: after a full tumble (or a series of
persistent tumbles) there is a high risk that the new direction is wrong.
Therefore, one could argue that keeping $q$ large is a desirable strategy,
since it increases the probability of correcting the tumble quickly. Our
results show that both of these arguments are incorrect. Although one could
imagine a model in which $q$ is explicitly altered after each tumble, say
$q\rightarrow a\,q$, the study of this variant would require relaxing the
assumption of fixed $\gamma$ in order to find global optima.

Introducing a finite tumble time moves the model away from the perfect trade-
offs described above. We have shown that an optimum persistence emerges that
depends on the manner in which the tumble time depends on reorientation angle.
For ballistic tumbles, zero persistence is optimal, while continuous tumbling
is optimal for diffusive tumbles. A finite persistence emerges for exponents
in-between, i.e. for tumbles that are superdiffusive, but not ballistic. Such
a tumble could simply be a mixture of ballistic and diffusive reorientations
that when taken together have a super-diffusive behaviour. Diffusive tumbles
are easy to generate: a cell can do so by simply not swimming, and more
generally by wiggling its flagella in random directions. Ballistic tumbles
require directed motion of the flagella (even though the actual direction is
chosen randomly). Actual tumbles might be a combination of a fixed tumble time
plus a diffusive scaling, which would favour a finite tumble persistence (non-
zero and non-infinite). One could furthermore imagine minimising tumble times
by maintaining a finite swimming speed during tumbles, e.g. via polymorphic
transformations of the flagella (Goldstein et al.,, 2000).

In addition to studying the weak chemotaxis limit, we have also investigated
the effects of strong chemotaxis. While this is, naturally, dependent on the
precise functional form chosen for the biasing of tumbles, we have shown that
optima in chemotactic strength can also emerge. Through an analytical
approximation we found that the form $\lambda_{0}\lfloor 1+q\rfloor$ has an
optimal value of $\beta$ for constant $\lambda_{0}$. Allowing for variations
in $\lambda_{0}$ the optimum shifts to $\beta\rightarrow\infty$, and instead
$\tilde{\beta}=\beta\lambda_{0}$ as $\beta\rightarrow\infty$ has an optimal
value. This naturally leads to the question of the optimal form of the
modulation. Preliminary results have shown that other simple choices, e.g.
$\lambda_{0}\,e^{q}$, do not perform better than the form studied here. In
general such problems can be considered partially observable Markov decision
processes, and a potential optimal functional form could be found by methods
such as reinforcement learning. Results from such analysis, however, will
probably be strongly dependent on the model setup, and a form that optimises
for drift in constant gradients will not necessarily do well in other
gradients.

Comparing to experimental systems, our result that persistence does not have a
unique optimum when allowing for variations in base tumble frequency fits well
with the variation that exists between species. The chemotactic strength
result that the optimum is found as $\lambda_{0}\rightarrow 0$ is a special
outcome of maximising the drift velocity in a constant gradient. In more
complex domains, the cells will need to react also to spatial variations
(Appendix E) and thus need a finite $\lambda_{0}$ and smaller $\beta$.
Maximising the minimum chemotactic efficiency over many chemoattractant
profiles reveals the experimental values associated with the kernel $\kappa$
and base tumbling frequency (Celani and Vergassola,, 2010). A linear approach
cannot, however, reveal an optimal chemotactic strength. An interesting
question for future research is thus: can maximising the minimum chemotactic
efficiency over suitably chosen noise models reveal an optimal finite
chemotactic strength? While difficult to tackle analytically, numerical
methods may be able to answer such questions.

## Acknowledgments

It is a pleasure to dedicate this work to the memory of John Blake, whose
impact on the mathematics of microorganism locomotion was so profound. This
work was supported in part by the EPSRC and St. John’s College, Cambridge
(JBK), and by an Established Career Fellowship from the EPSRC (REG).

##  Appendix A Linearised drift

To find the drift $\langle\cos\theta\rangle$ linearised in $\beta$, we
multiply

$\displaystyle\frac{\partial P}{\partial t}+v\cos\theta\,\frac{\partial
P}{\partial x}=$
$\displaystyle\,D_{r}\frac{\partial^{2}P}{\partial\theta^{2}}+\lambda_{0}\lfloor
1+q(t)\rfloor\left[\int\,\frac{e^{k\cos(\theta-\theta^{\prime})}}{2\pi
I_{0}(k)}P(\theta^{\prime})\,\mathrm{d}\theta^{\prime}-P\right]$ (20)
$\displaystyle-\sum_{j}\partial_{m_{j}}[\delta_{j,0}\,c(x)\,+jm_{j-1}-\gamma
m_{j}]\,P,$

by $\cos\theta$, whereafter integration yields

$\partial_{t}\langle\cos\theta\rangle=-D_{r}\langle\cos\theta\rangle-\lambda_{0}\left(1-\frac{I_{1}(k)}{I_{0}(k)}\right)\left(\langle\cos\theta\rangle+\langle
q\cos\theta\rangle\right),$ (21)

using

$\int e^{k\cos(\theta-\theta^{\prime})}\cos\theta\,\mathrm{d}\theta=2\pi
I_{1}(k)\cos\theta^{\prime}.$ (22)

Since $q(t)=\frac{\beta\gamma^{2}}{\alpha\,v}(\gamma^{2}m_{2}/2-\gamma m_{1})$
we continue, neglecting quadratic terms

$\displaystyle\partial_{t}\langle m_{0}\cos\theta\rangle$
$\displaystyle=-(D_{r}+\lambda_{k}+\gamma)\langle
m_{0}\cos\theta\rangle+\alpha\langle x\cos\theta\rangle,$ (23)
$\displaystyle\partial_{t}\langle m_{1}\cos\theta\rangle$
$\displaystyle=-(D_{r}+\lambda_{k}+\gamma)\langle
m_{1}\cos\theta\rangle+\langle m_{0}\cos\theta\rangle,$ (24)
$\displaystyle\partial_{t}\langle m_{2}\cos\theta\rangle$
$\displaystyle=-(D_{r}+\lambda_{k}+\gamma)\langle
m_{2}\cos\theta\rangle+2\langle m_{1}\cos\theta\rangle,$ (25)
$\displaystyle\partial_{t}\langle x\cos\theta\rangle$
$\displaystyle=\frac{v}{2}-(D_{r}+\lambda_{k})\langle x\cos\theta\rangle.$
(26)

Solving these equations for the steady state, one finds the result of the main
text.

##  Appendix B Linearised with mean tumble angle

The reorientation distribution is now

$g_{k}(\theta,\theta^{\prime})=\frac{1}{4\pi
I_{0}(k)}\left(e^{k\cos(\theta-\theta^{\prime}-\mu)}+e^{k\cos(\theta-\theta^{\prime}+\mu)}\right)$
(27)

such that

$\partial_{t}\langle\cos\theta\rangle=-D_{r}\langle\cos\theta\rangle-\lambda_{0}\left(1-\frac{I_{1}(k)}{I_{0}(k)}\cos\mu\right)\left(\langle\cos\theta\rangle+\langle
q\cos\theta\rangle\right),$ (28)

where we used that $\cos\mu$ is an even function and $\sin\mu$ odd. So having
a finite $\mu$ corresponds to changing the persistence. At precisely
$\mu=\pm\pi/2$, persistence no longer changes the behaviour.

##  Appendix C Linearised with mean tumble angle — biased direction

Here we take

$g_{k}(\theta,\theta^{\prime})=\frac{1}{2\pi
I_{0}(k)}e^{k\cos(\theta-\theta^{\prime}-\mu)}.$ (29)

We now have

$\displaystyle\partial_{t}\langle\cos\theta\rangle=$ $\displaystyle-
D_{r}\langle\cos\theta\rangle-\lambda_{0}\left(1-\frac{I_{1}(k)}{I_{0}(k)}\cos\mu\right)\left(\langle\cos\theta\rangle+\langle
q\cos\theta\rangle\right)$
$\displaystyle-\lambda_{0}\frac{I_{1}(k)}{I_{0}(k)}\sin\mu\left(\langle\sin\theta\rangle+\langle
q\sin\theta\rangle\right).$ (30)

And then

$\displaystyle\partial_{t}\langle m_{0}\cos\theta\rangle$
$\displaystyle=-D_{r}\langle
m_{0}\cos\theta\rangle-\lambda_{0}\left(1-\frac{I_{1}(k)}{I_{0}(k)}\cos\mu\right)\langle
m_{0}\cos\theta\rangle$
$\displaystyle\quad-\lambda_{0}\frac{I_{1}(k)}{I_{0}(k)}\sin\mu\langle
m_{0}\sin\theta\rangle+\alpha\langle x\cos\theta\rangle-\gamma\langle
m_{0}\cos\theta\rangle,$ (31) $\displaystyle\partial_{t}\langle
m_{1}\cos\theta\rangle$ $\displaystyle=-D_{r}\langle
m_{1}\cos\theta\rangle-\lambda_{0}\left(1-\frac{I_{1}(k)}{I_{0}(k)}\cos\mu\right)\langle
m_{1}\cos\theta\rangle$
$\displaystyle\quad-\lambda_{0}\frac{I_{1}(k)}{I_{0}(k)}\sin\mu\langle
m_{1}\sin\theta\rangle+\langle m_{0}\cos\theta\rangle-\gamma\langle
m_{0}\cos\theta\rangle,$ (32) $\displaystyle\partial_{t}\langle
m_{2}\cos\theta\rangle$ $\displaystyle=-D_{r}\langle
m_{2}\cos\theta\rangle-\lambda_{0}\left(1-\frac{I_{1}(k)}{I_{0}(k)}\cos\mu\right)\langle
m_{2}\cos\theta\rangle$
$\displaystyle\quad-\lambda_{0}\frac{I_{1}(k)}{I_{0}(k)}\sin\mu\langle
m_{2}\sin\theta\rangle+2\langle m_{1}\cos\theta\rangle-\gamma\langle
m_{2}\cos\theta\rangle,$ (33) $\displaystyle\partial_{t}\langle
x\cos\theta\rangle$ $\displaystyle=\frac{v}{2}-D_{r}\langle
x\cos\theta\rangle-\lambda_{0}\left(1-\frac{I_{1}(k)}{I_{0}(k)}\cos\mu\right)\langle
x\cos\theta\rangle$
$\displaystyle\quad-\lambda_{0}\frac{I_{1}(k)}{I_{0}(k)}\sin\mu\langle
x\sin\theta\rangle$ (34)

and similarly for the $\sin\theta$ terms, except no $v/2$ term appears in the
equation for $\partial_{t}\langle x\sin\theta\rangle$.

This can be solved for the steady solution of $\langle\cos\theta\rangle$, but
the expression is quite lengthy. Analysing it, we find that the optimum is
found for $k\rightarrow\infty$. Taking this limit we find

$\displaystyle\langle\cos\theta\rangle\rightarrow$
$\displaystyle\beta\gamma^{3}\lambda_{0}\bigg{[}\lambda_{0}^{2}(\cos(2\mu)(3(\gamma+D_{r}+\lambda_{0})(\gamma+2(D_{r}+\lambda_{0}))+\lambda_{0}(3\gamma+4(D_{r}+\lambda_{0})))$
(35)
$\displaystyle+\lambda_{0}(\cos(3\mu)(-3\gamma-4D_{r}-5\lambda_{0})+\lambda_{0}\cos(4\mu)))-\cos\mu(\gamma+D_{r}+\lambda_{0})\big{(}\lambda_{0}^{2}(10\gamma+17D_{r})$
$\displaystyle+\lambda_{0}(\gamma+D_{r})(2\gamma+7D_{r})+D_{r}(\gamma+D_{r})^{2}+11\lambda_{0}^{3}\big{)}+(\gamma+D_{r}+\lambda_{0})^{2}((D_{r}+\lambda_{0})(\gamma+D_{r}+\lambda_{0})$
$\displaystyle+\lambda_{0}(\gamma+4(D_{r}+\lambda_{0})))\bigg{]}\bigg{/}\bigg{[}2\big{(}-2\lambda_{0}(D_{r}+\lambda_{0})\cos\mu+(D_{r}+\lambda_{0})^{2}+\lambda_{0}^{2}\big{)}$
$\displaystyle\big{(}-2\lambda_{0}\cos\mu(\gamma+D_{r}+\lambda_{0})+(\gamma+D_{r}+\lambda_{0})^{2}+\lambda_{0}^{2}\big{)}^{3}\bigg{]}.$

The optimum is found at $\mu\rightarrow 0$, $\lambda_{0}\rightarrow\infty$,
keeping $\lambda_{0}\mu$ constant. The motion is thus continuously rotating
cells, where the rotation speed is modulated by the chemoattractants.

##  Appendix D Persistence in 3D

The linearised calculation is very similar in 3D. Defining $p$ as a unit
vector in the swimming direction, we can write the Fokker-Planck equation with
von-Mises tumbles as

$\displaystyle\frac{\partial P(t,x,p,m)}{\partial t}+v\,p_{x}\,\frac{\partial
P}{\partial x}=$ $\displaystyle\,D_{r}\nabla_{p}^{2}P+\lambda_{0}\lfloor
1+q(t)\rfloor\left[\int\,\frac{k\,e^{k\,p\cdot p^{\prime}}}{4\pi\sinh
k}P(p^{\prime})\,\mathrm{d}\Omega^{\prime}-P\right]$ (36)
$\displaystyle-\sum_{j}\partial_{m_{j}}[\delta_{j,0}\,c(x)\,+jm_{j-1}-\gamma
m_{j}]\,P,$

where $\nabla_{p}^{2}$ is the angular Laplacian.

This leads to

$\partial_{t}\langle p_{x}\rangle=-2D_{r}\langle
p_{x}\rangle-\lambda_{0}\left[1+\frac{1}{k}-\frac{1}{\tanh
k}\right]\left(\langle p_{x}\rangle+\langle q\,p_{x}\rangle\right),$ (37)

showing an only slightly altered persistence modification to $\lambda_{k}$
compared to 2D, and thus leading to similar conclusions as in 2D.

##  Appendix E Simplified effective model

Fig. 7 shows the performance of the simplified model of Eq. (12) compared to
the simulations shown in Fig. 4.

Figure 7: Similar to Fig. 4, but with theoretical curves (dashed) obtained
from the analysis of Eq. (12).

##  Appendix F Run-and-tumble in discrete 1D

In this section we study run-and-tumble in one spatial dimension. Such
simplifications have proven to yield much insight in the case of no noise
(Rivero et al.,, 1989). For the present purpose we will consider the case of a
very noisy signal. To simplify further we put the cells and chemoattractants
on an equilateral grid. We assume that each measurement carries the same error
$\sigma$. In reality, the measurement of a concentration $c$ has an error
$\propto\sqrt{c}$, but such effects are expected to be second order. Thus at
each grid position $i$, the cell measures a concentration
$c_{i}\sim\mathcal{N}(c({\boldsymbol{x}}_{i}),\sigma^{2})$, where
$c({\boldsymbol{x}}_{i})$ is the time-average of the signal at that position.

In particular, a cell will swim $n$ lattice points and calculate
$Q=\sum_{j}k_{j}c_{i(j)}$, where $k_{j}$ is some kernel, reminiscent of the
continuous kernel used in the main text. In the simplest model, if $Q>0$ the
cell will keep going in the same direction, but turn if $Q<0$. We begin by
determining the optimal $\\{k_{j}\\}$.

###  F.1 Optimal kernel

We determine $\\{k_{j}\\}$ in such a way that $Q$ makes the best estimate of a
constant gradient. Thus we consider $c_{i}=\mathcal{N}(c_{0}+\alpha
i),\,\sigma^{2})$. Then $Q=\sum k_{j}c_{j}$ is an unbiased estimator of
$\alpha$ if

$\langle Q\rangle=\sum k_{j}\langle c_{j}\rangle=\sum k_{j}(c_{0}+\alpha
j)=c_{0}\sum k_{j}+\alpha\sum k_{j}j=\alpha,$ (38)

so we must require $\sum k_{j}=0$ and $\sum k_{j}j=1$. The variance becomes

$\text{Var}Q=\langle Q^{2}\rangle-\langle Q\rangle^{2}=\sigma^{2}\sum
k_{j}^{2}.$ (39)

Writing $Q=\sum k_{i}c_{i}$, minimising the variance subject to the unbiased
estimation yields

$k_{i}=\frac{6(2i-n_{1}-n_{2})}{(n_{2}-n_{1}+2)(n_{2}-n_{1}+1)(n_{2}-n1)}$
(40)

for a measurement on $[n_{1},n_{2}]$. Thus

$k_{j}=\frac{6(2j-n)}{(n+2)(n+1)n},$ (41)

where $n=n_{2}-n_{1}$. Assuming a Gaussian distribution we thus have

$Q\sim\mathcal{N}\\!\left(\alpha,\sigma^{2}\sum
k_{j}^{2}\right)=\mathcal{N}\\!\left(\alpha,\frac{12\sigma^{2}}{(n+2)(n+1)n}\right)\equiv\mathcal{N}(\alpha,\sigma_{n}^{2}).$
(42)

###  F.2 Chemotaxis in a constant gradient

The probability that $Q<0$ after a swim of $n$ lattice points follows a
geometric distribution with parameter

$q=\frac{1}{\sqrt{2\pi\sigma^{2}}}\int_{-\infty}^{0}e^{-(x-\alpha)^{2}/2\sigma_{n}^{2}}\,\mathrm{d}x=\frac{1}{2}\,\text{erfc}\left(\frac{\alpha}{\sqrt{2\sigma_{n}^{2}}}\right).$
(43)

After a run left and right, the cell will have travelled on average

$\frac{n}{q}-\frac{n}{1-q},$ (44)

while in that time it could have travelled on average the distance

$\frac{n}{q}+\frac{n}{1-q}.$ (45)

The efficiency is thus $\eta=1-2q$, which is maximised for $q\rightarrow 0$,
corresponding to $n\rightarrow\infty$. This is in the absence of spatial
variations and diffusion effects.

###  F.3 Effective rotational diffusion

We now add the feature that after each jump the particle will flip either
because $Q<0$ or another process $R<0$, which has parameter $D_{r}$ for a
single jump. The probability $R<0$ after $n$ jumps will thus be
$r=1-(1-D_{r})^{n}$. Thus the probability of a turn after the $n$ jumps is
$\tilde{q}=q+r-qr$ when going right, and when going left
$\tilde{p}=(1-q)+r-(1-qr)$. Calculating the efficiency we thus find

$\eta=\frac{(1-2q)\,(1-D_{r})^{n}}{2-(1-D_{r})^{n}},$ (46)

where $q$ is defined as in Eq. (43). This defines an optimal $n$ as shown in
Fig. 8. The emergence of an optimal $n$ corresponds to the emergence of an
optimum $\gamma$ in the main text.

Figure 8: Efficiency $\eta$ as a function of $n$ as in Eq. (46). Noise varies
from $\sigma/\alpha=1$ (blue) to $\sigma/\alpha=10$ (red). $D_{r}=0.1$.

###  F.4 Chemotaxis in a spatially varying gradient

Spatial variation from linear concentration profiles can also affect the
optimal choice of $n$. Consider cells swimming in a gradient being held to a
fixed value $c_{0}>0$ at the origin. The diffusion equation allows for linear
steady state solutions. We thus consider 1D swimmers in

$c(x)=c_{0}-\alpha|x|.$ (47)

We again discretise space and allow the cells to choose an $n$, the number of
lattice points to swim before making a decision on whether to change
direction. This $n$ determines $\sigma_{n}$ and thus $q$. This also makes the
cells only visit sites that are multiples of $n$ and we thus reindex by that.
We further note that a state moving right at position $i$ is by symmetry the
same as moving left at site $-i$. We exploit this symmetry and consider only
$i\geq 0$. Our states are then called

$(i,\,s)\in\mathbb{N}_{0}\times\\{+,-\\}=\left\\{\begin{matrix}(0,+),&(0,-),&(1,+),&(1,-),&(2,+),&(2,-),&\cdots\end{matrix}\right\\}.$
(48)

Figure 9: Average $|x|$ for as a function of $n$, the number of jumps before
deciding to change direction, as described by Eq. (53). Chemotaxis is optimal
when $\langle|x|\rangle$ is minimised, since the chemoattractant concentration
decreases from $x=0$. Parameters as in Fig. 8.

The jumps form an infinite dimensional Markov chain with transition matrix

$\mathbb{T}=\begin{pmatrix}{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&p&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&\cdots\\\
{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&q&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&\cdots\\\
p&q&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&p&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&\cdots\\\
q&p&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&q&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&\cdots\\\
{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&p&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&p&{\color[rgb]{0.81,0.81,0.81}0}&\cdots\\\
{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&q&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&q&{\color[rgb]{0.81,0.81,0.81}0}&\cdots\\\
{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&p&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&\cdots\\\
{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&q&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&\cdots\\\
{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&p&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&\cdots\\\
{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&q&{\color[rgb]{0.81,0.81,0.81}0}&{\color[rgb]{0.81,0.81,0.81}0}&\cdots\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots\end{pmatrix},$
(49)

where $p=1-q$. The steady state distribution is found by solving

${\bf p}=\mathbb{T}\,{\bf p}.$ (50)

To solve this infinite set of equations, we truncate in an appropriate manner
at $m$ equations and then let $m\rightarrow\infty$. We assume $m$ even and to
conserve probability, for finite $m$ set $\mathbb{T}_{m-1,m-1}=p$ and
$\mathbb{T}_{m,m-1}=q$. This leads to

$p_{i,s}=\frac{1}{A}\cdot\begin{cases}\frac{q^{k}}{p^{k-2}(1-2q+2q^{2})}&(0,+)\\\
\frac{q^{k+1}}{p^{k-1}(1-2q+2q^{2})}&(0,-)\\\ \frac{q^{k-i}}{p^{k-i}}&(i\geq
1,+)\\\ \frac{q^{k}}{p^{k-2}(1-2q+2q^{2})}&(1,-)\\\
\frac{q^{k-i+1}}{p^{k-i+1}}&(i\geq 2,-)\end{cases}$ (51)

where $k=m/2-2$ and $A$ is a normalisation constant determined by

$\displaystyle\sum_{i,s}\,p_{i,s}=1.$ (52)

After a long calculation we find (for $q>1/2$) in the limit
$m\rightarrow\infty$,

$\langle|x|\rangle=\frac{\Delta
x\,n}{2}\left(2-\frac{1}{q(n)}+\frac{1}{2q(n)-1}\right).$ (53)

Fig. 9 shows a minimum appearing for large noise. Thus we see that an optimal
measurement distance must also be balanced with potential spatial variations,
not just with rotational diffusion.

## References

  * Friedrich and Juicher, (2007) Friedrich, B. M. & Julicher, F.  Chemotaxis of sperm cells.  Proceedings of the National Academy of Sciences of the United States of America, 2007.
  * Jikeli et al., (2015) Jikeli, J. F., Alvarez, L., Friedrich, B. M. Wilson, L. G., Pascal, R., Colin, R., Pichlo, M., Rennhack, A.,Brenker, C. & Kaupp, U. B.  Sperm navigation along helical paths in 3D chemoattractant landscapes.  Nature communications, 6:7985, 2015.
  * Yoshimura and Kamiya, (2001) Yoshimura, K. & Kamiya, R.  The sensitivity of chlamydomonas photoreceptor is optimized for the frequency of cell body rotation.  Plant & cell physiology, 42(6):665–672, 2001.
  * Drescher et al., (2010) Drescher, K., Goldstein, R. E. & Tuval, I.  Fidelity of adaptive phototaxis.  Proceedings of the National Academy of Sciences of the United States of America, 107(25):11171–6, 2010.
  * Polin et al., (2009) Polin, M., Tuval, I., Drescher, K., Gollub, J. P. & Goldstein, R. E.  Chlamydomonas Swims With Two ‘Gears’ in a Eukaryotic Version of Run-and-Tumble Locomotion.  Science, 325 487-490, 2009.
  * Bonner and Savage, (1947) Bonner, J. T. & Savage, L.  Evidence for the formation of cell aggregates by chemotaxis in the development of the slime mold Dictyostelium discoideum.  Journal of Experimental Zoology, 106(1), 1947.
  * Berg and Brown, (1972) Berg, H. C. & Brown, D. A.  Chemotaxis in Escherichia coli analysed by three-dimensional tracking.  Nature, 1972.
  * (8) Kirkegaard, J. B., Bouillant, A., Marron, A. O., Leptos, K. C. & Goldstein, R. E.  Aerotaxis in the Closest Relatives of Animals.  eLife, e18109, 2016.
  * (9) Kirkegaard, J. B., Marron, A. O. & Goldstein, R. E.  Motility of Colonial Choanoflagellates and the Statistics of Aggregate Random Walkers.  Physical Review Letters, 116 038102, 2016.
  * (10) Tindall, M. J, Porter, S. L., Maini, P. K, Gaglia, G. & Armitage, J. P.  Overview of mathematical approaches used to model bacterial chemotaxis I: The single cell.  Bulletin of Mathematical Biology, 70(6):1525–1569, 2008.
  * (11) Tindall, M. J, Maini, P. K, Porter, S. L. & Armitage, J. P.  Overview of mathematical approaches used to model bacterial chemotaxis II: Bacterial populations.  Bulletin of Mathematical Biology, 70(6):1570–1607, 2008.
  * Segall et al., (1986) Segall, J. E., Block, S. M. & Berg, H. C.  Temporal comparisons in bacterial chemotaxis.  Proceedings of the National Academy of Sciences of the United States of America, 83(23):8987–8991, 1986.
  * Celani and Vergassola, (2010) Celani, A. & Vergassola, M.  Bacterial strategies for chemotaxis response.  Proceedings of the National Academy of Sciences, 107(4):1391–1396, 2010.
  * Mora and Wingreen, (2010) Mora, T. & Wingreen, N. S.  Limits of sensing temporal concentration changes by single cells.  Physical Review Letters, 104(24):1–4, 2010.
  * Hein et al., (2016) Hein, A. M., Brumley, D. R., Carrara, F., Stocker, R. & Levin, S. A.  Physical limits on bacterial navigation in dynamic environments.  Journal of the Royal Society, 13(114):20150844, 2016.
  * Locsei, (2007) Locsei, J. T.  Persistence of direction increases the drift velocity of run and tumble chemotaxis.  Journal of Mathematical Biology, 55(1):41–60, 2007.
  * Locsei and Pedley, (2009) Locsei, J. T. & Pedley, T. J.  Run and tumble chemotaxis in a shear flow: The effect of temporal comparisons, persistence, rotational diffusion & cell shape.  Bulletin of Mathematical Biology, 71(5):1089–1116, 2009.
  * Reneaux and Gopalakrishnan, (2010) Reneaux, M. & Gopalakrishnan, M.  Theoretical results for chemotactic response and drift of E. coli in a weak attractant gradient.  Journal of Theoretical Biology, 266(1):99–106, 2010.
  * Mortimer et al., (2011) Mortimer, D., Dayan, P., Burrage, K. & Goodhill, G. J.  Bayes-optimal chemotaxis.  Neural computation, 23(2):336–373, 2011.
  * Nicolau et al., (2009) Nicolau, D. V., Armitage, J. P. & Maini, P. K.  Directional persistence and the optimality of run-and-tumble chemotaxis.  Computational Biology and Chemistry, 33(4):269–274, 2009.
  * Peaudecerf and Goldstein, (2015) Peaudecerf, F. J. & Goldstein, R. E.  Feeding ducks, bacterial chemotaxis & the Gini index.  Phys. Rev. E, 92(022701), 2015.
  * Berg and Purcell, (1977) Berg, H. C. & Purcell, E. M.  Physics of Chemoreception  Biophysical Journal 20, 1977
  * Goldstein et al., (2000) Goldstein, R. E., Goriely, A., Huber, G. & Wolgemuth, C. W.  Bistable Helices.  Physical Review Letters, 84(7):1631–1634, 2000.
  * Rivero et al., (1989) Rivero, M. A., Tranquillo, R. T., Buettner, H. M. & Lauffenburger, D. A.  Transport models for chemotactic cell populations based on individual cell behavior.  Chemical Engineering Science, 44(12):2881–2897, 1989.