Robustness of optimal intermittent search strategies in one, two, and three dimensions

Learning how to find targets in the micro-world: the case of intermittent active Brownian particles

Finding the best strategy to minimize the time needed to find a given target is a crucial task both in nature and in reaching decisive technological advances. By considering learning agents able to switch their dynamics between standard and active Brownian motion, here we focus on developing effective target-search behavioral policies for microswimmers navigating a homogeneous environment and searching for targets of unknown position. We exploit projective simulation, a reinforcement learning algorithm, to acquire an efficient stochastic policy represented by the probability of switching the phase, i.e. the navigation mode, in response to the type and the duration of the current phase. Our findings reveal that the target-search efficiency increases with the particle's self-propulsion during the active phase and that, while the optimal duration of the passive case decreases monotonically with the activity, the optimal duration of the active phase displays a non-monotonic behavior.

First-passage process in degree space for the time-dependent Erdős-Rényi and Watts-Strogatz models

In this work, we investigate the temporal evolution of the degree of a given vertex in a network by mapping the dynamics into a random walk problem in degree space. We analyze when the degree approximates a preestablished value through a parallel with the first-passage problem of random walks. The method is illustrated on the time-dependent versions of the Erdős-Rényi and Watts-Strogatz models, which were originally formulated as static networks. We have succeeded in obtaining an analytic form for the first and the second moments of the first-passage time and showing how they depend on the size of the network. The dominant contribution for large networks with N vertices indicates that these quantities scale on the ratio N/p, where p is the linking probability.

Gaussian process and Lévy walk under stochastic noninstantaneous resetting and stochastic rest

A stochastic process with movement, return, and rest phases is considered in this paper. For the movement phase, the particles move following the dynamics of the Gaussian process or the ballistic type of Lévy walk, and the time of each movement is random. For the return phase, the particles will move back to the origin with a constant velocity or acceleration or under the action of a harmonic force after each movement, so that this phase can also be treated as a noninstantaneous resetting. After each return, a rest with a random time at the origin follows. The asymptotic behaviors of the mean-squared displacements with different kinds of movement dynamics, returning, and random resting time are discussed. The stationary distributions are also considered when the process is localized. In addition, the mean first passage time is considered when the dynamic of the movement phase is Brownian motion.

Persistence-Speed Coupling Enhances the Search Efficiency of Migrating Immune Cells

Migration of immune cells within the human body allows them to fulfill their main function of detecting pathogens. We present experimental evidence showing the optimality of the search strategy of these cells, which is of crucial importance to achieve an efficient immune response. We find that the speed and directional persistence of migrating dendritic cells in our in vitro experiments are highly correlated, which enables them to reduce their search time. We introduce theoretically a new class of random search optimization problems by minimizing the mean first-passage time (MFPT) with respect to the strength of the coupling between influential parameters. We derive an analytical expression for the MFPT in a confined geometry and verify that the correlated motion enhances the search efficiency if the mean persistence length is sufficiently shorter than the confinement size. Our correlated search optimization approach provides an efficient searching recipe and predictive power in a broad range of correlated stochastic processes.

Chemokinetic Scattering, Trapping, and Avoidance of Active Brownian Particles

We present a theory of chemokinetic search agents that regulate directional fluctuations according to distance from a target. A dynamic scattering effect reduces the probability to penetrate regions with high fluctuations and thus reduces search success for agents that respond instantaneously to positional cues. In contrast, agents with internal states that initially suppress chemokinesis can exploit scattering to increase their probability to find the target. Using matched asymptotics between the case of diffusive and ballistic search, we obtain analytic results beyond Fox colored noise approximation.

eGFRD in all dimensions

Biochemical reactions often occur at low copy numbers but at once in crowded and diverse environments. Space and stochasticity therefore play an essential role in biochemical networks. Spatial-stochastic simulations have become a prominent tool for understanding how stochasticity at the microscopic level influences the macroscopic behavior of such systems. While particle-based models guarantee the level of detail necessary to accurately describe the microscopic dynamics at very low copy numbers, the algorithms used to simulate them typically imply trade-offs between computational efficiency and biochemical accuracy. eGFRD (enhanced Green's Function Reaction Dynamics) is an exact algorithm that evades such trade-offs by partitioning the N-particle system into M ≤ N analytically tractable one- and two-particle systems; the analytical solutions (Green's functions) then are used to implement an event-driven particle-based scheme that allows particles to make large jumps in time and space while retaining access to their state variables at arbitrary simulation times. Here we present "eGFRD2," a new eGFRD version that implements the principle of eGFRD in all dimensions, thus enabling efficient particle-based simulation of biochemical reaction-diffusion processes in the 3D cytoplasm, on 2D planes representing membranes, and on 1D elongated cylinders representative of, e.g., cytoskeletal tracks or DNA; in 1D, it also incorporates convective motion used to model active transport. We find that, for low particle densities, eGFRD2 is up to 6 orders of magnitude faster than conventional Brownian dynamics. We exemplify the capabilities of eGFRD2 by simulating an idealized model of Pom1 gradient formation, which involves 3D diffusion, active transport on microtubules, and autophosphorylation on the membrane, confirming recent experimental and theoretical results on this system to hold under genuinely stochastic conditions.

Spatial Cytoskeleton Organization Supports Targeted Intracellular Transport

The efficiency of intracellular cargo transport from specific sources to target locations is strongly dependent upon molecular motor-assisted motion along the cytoskeleton. Radial transport along microtubules and lateral transport along the filaments of the actin cortex underneath the cell membrane are characteristic for cells with a centrosome. The interplay between the specific cytoskeleton organization and the motor performance results in a spatially inhomogeneous intermittent search strategy. To analyze the efficiency of such intracellular search strategies, we formulate a random velocity model with intermittent arrest states. We evaluate efficiency in terms of mean first passage times for three different, frequently encountered intracellular transport tasks: 1) the narrow escape problem, which emerges during cargo transport to a synapse or other specific region of the cell membrane; 2) the reaction problem, which considers the binding time of two particles within the cell; and 3) the reaction-escape problem, which arises when cargo must be released at a synapse only after pairing with another particle. Our results indicate that cells are able to realize efficient search strategies for various intracellular transport tasks economically through a spatial cytoskeleton organization that involves only a narrow actin cortex rather than a cell body filled with randomly oriented actin filaments.

Model of chromosomal loci dynamics in bacteria as fractional diffusion with intermittent transport

The short-time dynamics of bacterial chromosomal loci is a mixture of subdiffusive and active motion, in the form of rapid relocations with near-ballistic dynamics. While previous work has shown that such rapid motions are ubiquitous, we still have little grasp on their physical nature, and no positive model is available that describes them. Here, we propose a minimal theoretical model for loci movements as a fractional Brownian motion subject to a constant but intermittent driving force, and compare simulations and analytical calculations to data from high-resolution dynamic tracking in E. coli. This analysis yields the characteristic time scales for intermittency. Finally, we discuss the possible shortcomings of this model, and show that an increase in the effective local noise felt by the chromosome associates to the active relocations.

Turing mechanism for homeostatic control of synaptic density during C. elegans growth

We propose a mechanism for the homeostatic control of synapses along the ventral cord of Caenorhabditis elegans during development, based on a form of Turing pattern formation on a growing domain. C. elegans is an important animal model for understanding cellular mechanisms underlying learning and memory. Our mathematical model consists of two interacting chemical species, where one is passively diffusing and the other is actively trafficked by molecular motors, which switch between forward and backward moving states (bidirectional transport). This differs significantly from the standard mechanism for Turing pattern formation based on the interaction between fast and slow diffusing species. We derive evolution equations for the chemical concentrations on a slowly growing one-dimensional domain, and use numerical simulations to demonstrate the insertion of new concentration peaks as the length increases. Taking the passive component to be the protein kinase CaMKII and the active component to be the glutamate receptor GLR-1, we interpret the concentration peaks as sites of new synapses along the length of C. elegans, and thus show how the density of synaptic sites can be maintained.

Numerical analysis of homogeneous and inhomogeneous intermittent search strategies

Random search processes for targets that are inhomogeneously distributed in a search domain require spatially inhomogeneous search strategies to find the target as fast as possible. Here, we compare systematically the efficiency of homogeneous and inhomogeneous strategies for intermittent search, which alternates stochastically between slow, diffusive motion in which the target can be detected and fast ballistic motion during which targets cannot be detected. We analyze the mean first-passage time of homogeneous and inhomogeneous strategies for three paradigmatic search problems: (1) the narrow escape problem, i.e., the searcher looks for a small area on the boundary of the search domain, (2) reaction kinetics, i.e., the detection of an immobile target in the interior of a search domain, and (3) the reaction-escape problem, i.e., the searcher first needs to find a mobile target before it can escape through a narrow area on the boundary. Using families of inhomogeneous strategies, partially motivated by the organization of the cytoskeleton in cells with a centrosome, we show that they are almost always more efficient than homogeneous strategies.

Optimality of Spatially Inhomogeneous Search Strategies

We consider random search processes alternating stochastically between diffusion and ballistic motion, in which the distribution function of ballistic motion directions varies from point to point in space. The specific space dependence of the directional distribution together with the switching rates between the two modes of motion establishes a spatially inhomogeneous search strategy. We show that the mean first passage times for several standard search problems-narrow escape, reaction partner finding, reaction escape-can be minimized with a directional distribution that is reminiscent of the spatial organization of the cytoskeleton filaments of cells with a centrosome: radial ballistic transport from the center to the periphery and back, and ballistic transport in random directions within a concentric shell of thickness Δ_{opt} along the domain boundary. The results suggest that living cells realize efficient search strategies for various intracellular transport problems economically through a spatial cytoskeleton organization that involves radial microtubules in the central region and only a narrow actin cortex rather than a cell body filled with randomly oriented actin filaments.

Langevin equation with fluctuating diffusivity: A two-state model

Recently, anomalous subdiffusion, aging, and scatter of the diffusion coefficient have been reported in many single-particle-tracking experiments, though the origins of these behaviors are still elusive. Here, as a model to describe such phenomena, we investigate a Langevin equation with diffusivity fluctuating between a fast and a slow state. Namely, the diffusivity follows a dichotomous stochastic process. We assume that the sojourn time distributions of these two states are given by power laws. It is shown that, for a nonequilibrium ensemble, the ensemble-averaged mean-square displacement (MSD) shows transient subdiffusion. In contrast, the time-averaged MSD shows normal diffusion, but an effective diffusion coefficient transiently shows aging behavior. The propagator is non-Gaussian for short time and converges to a Gaussian distribution in a long-time limit; this convergence to Gaussian is extremely slow for some parameter values. For equilibrium ensembles, both ensemble-averaged and time-averaged MSDs show only normal diffusion and thus we cannot detect any traces of the fluctuating diffusivity with these MSDs. Therefore, as an alternative approach to characterizing the fluctuating diffusivity, the relative standard deviation (RSD) of the time-averaged MSD is utilized and it is shown that the RSD exhibits slow relaxation as a signature of the long-time correlation in the fluctuating diffusivity. Furthermore, it is shown that the RSD is related to a non-Gaussian parameter of the propagator. To obtain these theoretical results, we develop a two-state renewal theory as an analytical tool.

Optimization and universality of Brownian search in a basic model of quenched heterogeneous media

The kinetics of a variety of transport-controlled processes can be reduced to the problem of determining the mean time needed to arrive at a given location for the first time, the so-called mean first-passage time (MFPT) problem. The occurrence of occasional large jumps or intermittent patterns combining various types of motion are known to outperform the standard random walk with respect to the MFPT, by reducing oversampling of space. Here we show that a regular but spatially heterogeneous random walk can significantly and universally enhance the search in any spatial dimension. In a generic minimal model we consider a spherically symmetric system comprising two concentric regions with piecewise constant diffusivity. The MFPT is analyzed under the constraint of conserved average dynamics, that is, the spatially averaged diffusivity is kept constant. Our analytical calculations and extensive numerical simulations demonstrate the existence of an optimal heterogeneity minimizing the MFPT to the target. We prove that the MFPT for a random walk is completely dominated by what we term direct trajectories towards the target and reveal a remarkable universality of the spatially heterogeneous search with respect to target size and system dimensionality. In contrast to intermittent strategies, which are most profitable in low spatial dimensions, the spatially inhomogeneous search performs best in higher dimensions. Discussing our results alongside recent experiments on single-particle tracking in living cells, we argue that the observed spatial heterogeneity may be beneficial for cellular signaling processes.

First passages in bounded domains: when is the mean first passage time meaningful?

We study the first passage statistics to adsorbing boundaries of a Brownian motion in bounded two-dimensional domains of different shapes and configurations of the adsorbing and reflecting boundaries. From extensive numerical analysis we obtain the probability P(ω) distribution of the random variable ω=τ(1)/(τ(1)+τ(2)), which is a measure for how similar the first passage times τ(1) and τ(2) are of two independent realizations of a Brownian walk starting at the same location. We construct a chart for each domain, determining whether P(ω) represents a unimodal, bell-shaped form, or a bimodal, M-shaped behavior. While in the former case the mean first passage time (MFPT) is a valid characteristic of the first passage behavior, in the latter case it is an insufficient measure for the process. Strikingly we find a distinct turnover between the two modes of P(ω), characteristic for the domain shape and the respective location of absorbing and reflective boundaries. Our results demonstrate that large fluctuations of the first passage times may occur frequently in two-dimensional domains, rendering quite vague the general use of the MFPT as a robust measure of the actual behavior even in bounded domains, in which all moments of the first passage distribution exist.

Filling of a Poisson trap by a population of random intermittent searchers

We extend the continuum theory of random intermittent search processes to the case of N independent searchers looking to deliver cargo to a single hidden target located somewhere on a semi-infinite track. Each searcher randomly switches between a stationary state and either a leftward or rightward constant velocity state. We assume that all of the particles start at one end of the track and realize sample trajectories independently generated from the same underlying stochastic process. The hidden target is treated as a partially absorbing trap in which a particle can only detect the target and deliver its cargo if it is stationary and within range of the target; the particle is removed from the system after delivering its cargo. As a further generalization of previous models, we assume that up to n successive particles can find the target and deliver its cargo. Assuming that the rate of target detection scales as 1/N, we show that there exists a well-defined mean-field limit N→∞, in which the stochastic model reduces to a deterministic system of linear reaction-hyperbolic equations for the concentrations of particles in each of the internal states. These equations decouple from the stochastic process associated with filling the target with cargo. The latter can be modeled as a Poisson process in which the time-dependent rate of filling λ(t) depends on the concentration of stationary particles within the target domain. Hence, we refer to the target as a Poisson trap. We analyze the efficiency of filling the Poisson trap with n particles in terms of the waiting time density f(n)(t). The latter is determined by the integrated Poisson rate μ(t)=∫(0)(t)λ(s)ds, which in turn depends on the solution to the reaction-hyperbolic equations. We obtain an approximate solution for the particle concentrations by reducing the system of reaction-hyperbolic equations to a scalar advection-diffusion equation using a quasisteady-state analysis. We compare our analytical results for the mean-field model with Monte Carlo simulations for finite N. We thus determine how the mean first passage time (MFPT) for filling the target depends on N and n.

Optimizing persistent random searches

We consider a minimal model of persistent random searcher with a short range memory. We calculate exactly for such a searcher the mean first-passage time to a target in a bounded domain and find that it admits a nontrivial minimum as function of the persistence length. This reveals an optimal search strategy which differs markedly from the simple ballistic motion obtained in the case of Poisson distributed targets. Our results show that the distribution of targets plays a crucial role in the random search problem. In particular, in the biologically relevant cases of either a single target or regular patterns of targets, we find that, in strong contrast to repeated statements in the literature, persistent random walks with exponential distribution of excursion lengths can minimize the search time, and in that sense perform better than any Levy walk.

Optimal intermittence in search strategies under speed-selective target detection

Random search theory has been previously explored for both continuous and intermittent scanning modes with full target detection capacity. Here we present a new class of random search problems in which a single searcher performs flights of random velocities, the detection probability when it passes over a target location being conditioned to the searcher speed. As a result, target detection involves an N-passage process for which the mean search time is here analytically obtained through a renewal approximation. We apply the idea of speed-selective detection to random animal foraging since a fast movement is known to significantly degrade perception abilities in many animals. We show that speed-selective detection naturally introduces an optimal level of behavioral intermittence in order to solve the compromise between fast relocations and target detection capability.

Quasi-steady-state analysis of two-dimensional random intermittent search processes

We use perturbation methods to analyze a two-dimensional random intermittent search process, in which a searcher alternates between a diffusive search phase and a ballistic movement phase whose velocity direction is random. A hidden target is introduced within a rectangular domain with reflecting boundaries. If the searcher moves within range of the target and is in the search phase, it has a chance of detecting the target. A quasi-steady-state analysis is applied to the corresponding Chapman-Kolmogorov equation. This generates a reduced Fokker-Planck description of the search process involving a nonzero drift term and an anisotropic diffusion tensor. In the case of a uniform direction distribution, for which there is zero drift, and isotropic diffusion, we use the method of matched asymptotics to compute the mean first passage time (MFPT) to the target, under the assumption that the detection range of the target is much smaller than the size of the domain. We show that an optimal search strategy exists, consistent with previous studies of intermittent search in a radially symmetric domain that were based on a decoupling or moment closure approximation. We also show how the decoupling approximation can break down in the case of biased search processes. Finally, we analyze the MFPT in the case of anisotropic diffusion and find that anisotropy can be useful when the searcher starts from a fixed location.

Diffusion with stochastic resetting

We study simple diffusion where a particle stochastically resets to its initial position at a constant rate r. A finite resetting rate leads to a nonequilibrium stationary state with non-Gaussian fluctuations for the particle position. We also show that the mean time to find a stationary target by a diffusive searcher is finite and has a minimum value at an optimal resetting rate r*. Resetting also alters fundamentally the late time decay of the survival probability of a stationary target when there are multiple searchers: while the typical survival probability decays exponentially with time, the average decays as a power law with an exponent depending continuously on the density of searchers.

Intermittent pathways towards a dynamical target

In this paper, we investigate the quest for a single target, which remains fixed in a lattice, by a set of independent walkers. The target exhibits fluctuating behavior between a trap and an ordinary site of the lattice, whereas the walkers perform an intermittent kind of search strategy. Our searchers carry out their movements in one of two states, between which they switch randomly. One of these states (the exploratory phase) is a symmetric nearest-neighbor random walk and the other state (the relocating phase) is a symmetric next-nearest-neighbor random walk. By using the multistate continuous-time random-walk approach we are able to show that for dynamical targets, the intermittent strategy (despite the simplicity of the kinetics chosen for searching) improves detection, in comparison to displacements in a single state. We have obtained analytic results, which can be numerically evaluated, for the survival probability and for the lifetime of the target. Thus, we have studied the dependence of these quantities both in terms of the transition probability that describes the dynamics of the target and in terms of the parameter that characterizes the walkers' intermittency. In addition to our analytical approach, we have implemented Monte Carlo simulations, finding excellent agreement between the theoretical-numerical results and simulations.

Narrow escape for a stochastically gated Brownian ligand

Molecular activation in cellular microdomains is usually characterized by a forward binding rate, which is the reciprocal of the arrival time of a ligand to a key target. Upon chemical interactions or conformational changes, a Brownian ligand may randomly switch between different states, and when target activation is possible in a specific state only, switching can significantly alter the activation process. The main goal of this paper is to study the mean time for a switching ligand to activate a small substrate, modelled as the time to exit a microdomain through a small absorbing window on the surface. We present the equations for the mean sojourn times the ligand spends in each state, and study the escape process with switching between two states in dimension one and three. When the ligand can exit in only one of the two states, we find that switching always decreases its sojourn time in the state where it can exit. Moreover, the fastest exit is obtained when the ligand diffuses most of the time in the state with the maximal diffusion coefficient, although this may imply that it spends most of the time 'hidden' in the state where it cannot exit. We discuss the physical mechanisms responsible for this apparent paradox. In dimension three we confirm our results with Brownian simulations. Finally, we suggest possible applications in cellular biology.