Intermittent search strategies

This review examines intermittent target search strategies, which combine phases of slow motion, allowing the searcher to detect the target, and phases of fast motion during which targets cannot be detected. It is first shown that intermittent search strategies are actually widely observed at various scales. At the macroscopic scale, this is, for example, the case of animals looking for food; at the microscopic scale, intermittent transport patterns are involved in a reaction pathway of DNA-binding proteins as well as in intracellular transport. Second, generic stochastic models are introduced, which show that intermittent strategies are efficient strategies that enable the minimization of search time. This suggests that the intrinsic efficiency of intermittent search strategies could justify their frequent observation in nature. Last, beyond these modeling aspects, it is proposed that intermittent strategies could also be used in a broader context to design and accelerate search processes.

Figure 1

Intermittent reaction paths illustrated by an everyday-life example of a search problem. The searcher looks for a target. The searcher alternates fast relocation phases, which are not reactive as they do not allow for target detection, and slow reactive phases, which permit target detection.

Figure 2

Examples of patterns for systematic exploration of space.

Figure 3

Example of Lévy walks, with $\mu =1.5$ (not present on the zoom), $\mu =2$, and $\mu =3$. The total path length is the same for the three examples.

Figure 4

Basic model for intermittent search.

Figure 5

Log-log plot of experimental data (129; 102; 21) of saltatory search behaviors and their linear regression. Here $f_i=1/{\tau }_i$.

Figure 6

Two models of intermittent search: The searcher alternates slow reactive phases (regime 1) of mean duration ${\tau }_1$ and fast nonreactive ballistic phases (regime 2) of mean duration ${\tau }_2$.

Figure 7

Comparison between a Lévy walk and a composite random walk: They are not easy to distinguish at short time scales.

Figure 8

Artistic view of a DNA-protein interaction, which combines one-dimensional sliding phases and three-dimensional relocation phases. From Virginie Denis, Pour la Science 352, February 2007.

Figure 9

A model of intermittent transport for DNA-protein interactions.

Figure 10

Mean first-passage time of a DNA-binding protein to its target site, renormalized by the mean first-passage time by diffusion alone ($T_{\mathrm{diff}}$), as a function of ${\tau }_1/{\tau }_2$. $T_{\mathrm{diff}}/{\tau }_2=1$ (dash-dotted line), $T_{\mathrm{diff}}/{\tau }_2=10$ (dashed line), $T_{\mathrm{diff}}/{\tau }_2=100$ (dotted line), and $T_{\mathrm{diff}}/{\tau }_2=1000$ (solid line). For a small DNA length $\ell$ (and therefore small $T_{\mathrm{diff}}$) (dash-dotted line), the reaction constant depends monotonically on ${\tau }_1$ and intermittent reaction paths are inefficient. For larger values of $\ell$ (other curves), the reaction rate can be optimized as a function of ${\tau }_1$. Here we averaged over the initial position of the target.

Figure 11

Sliding is often represented by diffusion with perfect reactivity on the target. The two main directions shown for a more realistic description of the 1D phase: On the one hand, the sliding is not necessarily diffusive, and on the other hand, the 1D phase could be, in fact, a combination of two phases, one fast, but with low recognition, and another slow (or immobile), but with high recognition of the target.

Figure 12

Description of 3D excursions. Jumps are 3D excursions whose starting and ending points on the DNA sequence are uncorrelated. In practice, for confined DNA conformations as in a cellular medium, jumps have a span (measured along the DNA contour) larger than the density-density correlation length ${\xi }_c$ of DNA. Conversely, hops are 3D excursions whose starting and ending points on the DNA sequence are correlated, or equivalently 3D excursions whose relocation length is smaller than the correlation length ${\xi }_c$.

Figure 13

Facilitated diffusion of a protein on DNA. Left: Schematic definition of sliding, hopping, and jumping. Hops are 3D excursions whose starting and ending points on the DNA sequence are correlated, or equivalently 3D excursions whose relocation length is smaller than the typical distance between DNA segments. In the case of confined DNA, this distance is estimated by the DNA density-density correlation length ${\xi }_c$. Right: Model parameters.

Figure 14

Transport options for vesicles inside cells.

Figure 15

Vesicle transport in the bulk (three dimensions).

Figure 16

Optimization of the reaction rate for intermittent active transport. Gain of reactivity due to active transport in three dimensions as a function of ${\tau }_2$ for different values of the ratio $b/a$ (logarithmic scale). The analytical form (the mean detection time with diffusion alone divided by the mean detection time with intermittence) (plain lines) is plotted against numerical simulations (symbols) for the following values of the parameters (arbitrary units): $a=1$ ($\square$), $a=5$ ($\star$), $a=7$ ($\circ$), $a=10$ ($+$), $a=14$ ($\times$), $a=20$ ($\diamond$), with ${\tau }_1=6$, $V=1$, and $D=1$. $G_{3d}$ presents a maximum only for $a>a_c\simeq 4$.

Figure 17

Planar structures such as membranes and lamellipodia ($d=2$).

Figure 18

Optimization of the reaction rate for intermittent active transport. Gain of reactivity due to active transport $G_{2d}$ in two dimensions as a function of ${\tau }_1$ or ${\tau }_2$ (logarithmic scale). The analytical form [the mean detection time with diffusion alone divided by the mean detection time with intermittence (b50)] (plain lines) is plotted against numerical simulations (symbols) for the following values of the parameters (arbitrary units): $a=20$, $b=2000$ ($\star$); $a=10$, $b=1000$ ($\square$); $a=10$, $b=100$ ($+$); $a=2.5$, $b=250$ ($\circ$); with $V=1$ and $D=1$. These curves represent standard cellular conditions (as discussed in the text).

Figure 19

Tubular structures in cells, such as axons and dendrites ($d=1$).

Figure 20

Optimization of the reaction rate for intermittent active transport. Gain of reactivity due to active transport $G_{1d}$ in one dimension as a function of ${\tau }_1$ or ${\tau }_2$ (logarithmic scale). The analytical form [the mean detection time with diffusion alone divided by the mean detection time with intermittence (b23)] is plotted against the exact solution (symbols), for the following values of the parameters (arbitrary units): $D=1,V=1$ for all curves and $a=10,b={10}^4$ ($+$); $a=10,b={10}^3$ ($\circ$); $a=2.5,b={10}^3$ ($\square$). Standard cellular conditions (as discussed in the text) correspond to $\circ$ and $+$ curves.

Figure 21

The three different descriptions of phase 1 (the phase with detection), here represented in two dimensions.

Figure 22

Examples of target distributions.

Figure 23

Validity of the approximations. Mean first-passage time to the target, renormalized by the mean first-passage time without intermittence. Small-ballistic-displacements approximation (48) (dashed line). Large-ballistic-displacements approximation (47) (dotted line). Intermediary approximation (49) (line). Numerical simulations (symbols). $D=1$, $V=1$, $L={10}^3$.

Figure 24

$\ln ({\tau }_2^{\mathrm{opt}})$ as a function of $\ln ({\tau }_1)$. Small-${\tau }_1$ analytical prediction (53) (dashed line). Large-${\tau }_1$ analytical prediction (50) (solid line). Numerical values (symbols), for $L=10$ ($\square$), $L={10}^3$ ($+$), and $L={10}^5$ ($\circ$). $D=1$, $V=1$.

Figure 25

$\ln (G)$ as a function of $\ln ({\tau }_1)$ (${\tau }_2$ taken optimal). Small-${\tau }_1$ analytical prediction (55) (dotted line). Large-${\tau }_1$ analytical prediction (52) (solid line). Numerical simulations (points). $L={10}^1$ ($\square$), $L={10}^3$ ($+$), and $L={10}^5$ ($\circ$). $D=1$, $V=1$.

Figure 26

Minimization of the mean search time for the static mode with infinite correlation ($p=1$). ${\alpha }^{\mathrm{opt}}$ as a function of $w$. Theoretical expression for small $w$ (dots), for intermediate $w$ (solid line), and for large $w$ (dashed lines). Optimization of the exact expression (with ${\tau }_2\to 0$ and ${\tau }_1=\alpha {\tau }_2$) (symbols). $b=100$ ($\square$), $b={10}^3$ ($+$), $b={10}^4$ ($\diamond$), and $b={10}^5$ ($\star$). $a=1$, $V=1$.

Figure 27

${\tau }^{\mathrm{opt}}$ as a function of $2(1-p)$. Theoretical value of ${\tau }_1^{\mathrm{opt}}$ (58) (dashed line) and theoretical value of ${\tau }_2^{\mathrm{opt}}$ (59) (solid lines), compared to the numerical minimization of the full exact mean search time, leading to ${\tau }_1^{\mathrm{opt}}$ (filled symbols) and ${\tau }_2^{\mathrm{opt}}$ (empty symbols). $a=0.01$, $b=1$ (△); $a=0.01$, $b=100$ (□); $a=1$, $b=100$ (◯); $a=1$, $b={10}^4$ (★); $a=100$, $b={10}^4$ (▽); $a=100$, $b={10}^6$ (◇). $k=1$, $V=1$.

Figure 28

Comparison between the search without ($\circ$) and with temporal memory ($\square$). Static mode in two dimensions. $t_m$ as a function of ${\tau }_2$. $k=1$, $V=1$, $b=113$, $a=10$, ${\tau }_1=2.6$.

Figure 29

$t_m$ as a function of ${\tau }_1$, with $\sigma$ at the theoretical minimum [numerical minimization of Eq. (62)]. Lines: analytical formula (62). $\times$: simulations without cutoff. $+$: simulations with cutoff at $L$. $D=1$, $V=1$. Left: $L={10}^4$, $\alpha =1.6$; $\alpha =1.5$; $\alpha =1.4$; $\alpha =1.3$; $\alpha =1.2$. Right: $L={10}^5$, $\alpha =1.6$; $\alpha =1.5$; $\alpha =1.4$; $\alpha =1.3$; $\alpha =1.2$.

Figure 30

Model used by 131, 132.

Figure 31

Model used by 144.

Figure 32

Model used by 139.

Figure 33

Model used by 42 and 128.

Figure 34

Model presented by 136.

Figure 35

Design of heterogeneous chemical reactions, with targets (disks) here fixed on a two-dimensional surface. The reactant either diffuses in the volume (thin lines) or diffuses on the surface (thick lines). The flow is represented by arrows.

Figure 36

Static mode in one dimension. Exact expression of $t_m$ (b13) (lines) compared to the approximation of $t_m$ (b14) (symbols), both rescaled by $t_m^{\mathrm{opt}}$. ${\tau }_1^{\mathrm{opt}}$ from (b15), ${\tau }_2^{\mathrm{opt}}$ from (b16). $V=1$, $k=1$. $b/a=10$ ($\square$), $b/a=100$ ($\circ$), and $b/a=1000$ ($+$).

Figure 37

Diffusive mode in one dimension. $t_m/t_{\mathrm{diff}}$, exact expression (line), and approximation in the regime of favorable intermittence and $b{D}^2/a^3{V}^2\gg 1$ (b23) (symbols). $a=1$, $b=100$ ($\circ$); $a=1$, $b={10}^4$ ($+$); $a=10$, $b={10}^5$ ($\square$). $D=1$, $V=1$. ${\tau }_1^{\mathrm{opt}}$ is from Eq. (b24), and ${\tau }_2^{\mathrm{opt}}$ is obtained from Eq. (b25).

Figure 38

Diffusive mode in one dimension. $t_m/t_{\mathrm{diff}}$, exact expression (line), and approximation in the regime of favorable intermittence and $b{D}^2/a^3{V}^2\ll 1$ (b28) (symbols). $a=10$, $b=100$ ($\circ$); $a=10$, $b=1000$ ($+$); $a=100$, $b={10}^4$ ($\square$). $D=1$, $V=1$. ${\tau }_1^{\mathrm{opt}}$ is from Eq. (b29), and ${\tau }_2^{\mathrm{opt}}$ is obtained from Eq. (b30).

Figure 39

Static mode in two dimensions. Simulations (symbols) and analytical approximation (b43) (lines). $k=1$, $V=1$, $b=56$; $a=10$ ($+$) (${\tau }_1^{\mathrm{opt}}=2.41$, ${\tau }_2^{\mathrm{opt}}=11.2$); $a=1$ ($\circ$) (${\tau }_1^{\mathrm{opt}}=0.969$, ${\tau }_2^{\mathrm{opt}}=1.88$); $a=0.1$ ($\square$) (${\tau }_1^{\mathrm{opt}}=0.348$, ${\tau }_2^{\mathrm{opt}}=0.242$). Left: mean search time $t_m$ as a function of ${\tau }_2/a$, with ${\tau }_1={\tau }_1^{\mathrm{opt}}$. Right: mean search time $t_m$ as a function of ${\tau }_1$, with ${\tau }_2={\tau }_2^{\mathrm{opt}}$.

Figure 40

Diffusive mode in two dimensions. Simulations (symbols) versus analytical approximate (b50) (line) of the search time, rescaled by the value in the absence of intermittence $t_{\mathrm{diff}}$ as a function of ${\tau }_2$ (left) and $\ln ({\tau }_1)=$ (right), for $D=1$, $V=1$, $b=226$. Left: $a=10$, ${\tau }_1=1.37$ ($\square$); $a=1$, ${\tau }_1=33.6$ ($\circ$); $a=0.1$, ${\tau }_1=213$ ($+$). Right: $a=10$, ${\tau }_2=15.9$ ($\square$); $a=1$, ${\tau }_2=13.7$ ($\circ$); $a=0.1$, ${\tau }_2=22$ ($+$).

Figure 41

Ballistic mode in two dimensions. $\ln (t_m)$ as a function of $\ln ({\tau }_2)$. Simulations (symbols), diffusive-diffusive approximation (b50) with (b65) (lines), ${\tau }_1\to 0$ limit (b66) (line), ${\tau }_1\to \infty$ (no intermittence) (b64) (dotted line). $b=30$, $a=1$, $V=1$. ${\tau }_1=0$ ($\star$), ${\tau }_1=0.17$ ($•$), ${\tau }_1=0.92$ ($\diamond$), ${\tau }_1=5.0$ ($\times$), ${\tau }_1=28$ ($\circ$), ${\tau }_1=150$ ($+$), ${\tau }_1=820$ ($\square$).

Figure 42

Static mode in three dimensions. $\ln (t_m)$ as a function of $\ln ({\tau }_2)$ for different values of ${\tau }_1$, $a$, and $b/a$. Comparison among simulations (symbols), analytical expression (line), and its asymptotics for $b\gg a$ obtained by 113 (small dots), and simple expression for $b\gg a$ and small $\alpha$ (b79) (dashed line). ${\tau }_1\simeq {\tau }_1^{\mathrm{opt}}\simeq 0.74\sqrt{aV/k}$ (b80) ($+$), ${\tau }_1=0.25\sqrt{aV/k}$ ($\circ$), ${\tau }_1=2.5\sqrt{aV/k}$ ($\square$). $V=1$, $k=1$.

Figure 43

Diffusive mode in three dimensions. $t_m/t_{\mathrm{diff}}$ as a function of ${\tau }_2$ for different values of the ratio $b/a$ (logarithmic scale). The full analytical form given in 113 (plain lines) is plotted against the simplified expression (b93) (dashed lines), the simplified expression with ${\tau }_1=0$ (dotted line), and numerical simulations (symbols) for the following values of the parameters (arbitrary units): $a=1$ ($\square$); $a=5$ ($\star$); $a=7$ ($\circ$); $a=10$ ($+$); $a=14$ ($\times$); $a=20$ ($\diamond$). ${\tau }_1=6$ everywhere except for the small dots, $V=1$, $D=1$. $t_m/t_{\mathrm{diff}}$ presents a minimum only for $a>a_c\simeq 4$.