Scientific Summary

Search processes are ubiquitous among physical, chemical, and biological systems. Representative examples include diffusion-limited encounter of molecules involved in a chemical reaction; the dynamical or stochastic search for a global minimum in a complex energy landscape, relevant to systems such as glasses, protein (folding), and others; oil recovery from mature reservoirs; proteins searching for their specific target sites on DNA in gene regulation; transition rates of mechanochemical cycles of molecular motors; animal foraging; survival at the edge of extinction due to low availability of energetic resources; automated search of registers in high-capacity databases, search engines (e.g., "crawlers") that explore the internet, and even pizza delivery in a jammed traffic system of a medium- size town. In this way, the subject is interesting, challenging and inherently multidisciplinary, and has very recently become an important scientific area of investigation.

The search for a desired target may depend on a variety of conditions. Targets may be sparse, hidden, difficult to detect even when found. The targets may be mobile or immobile, they may try to avoid searchers, there may be one target or many. They may have a finite life-time and vanish before they are detected. Searchers may search "blindly", detecting the target only upon encounter, or may perceive distant targets and adjust their motion accordingly. They may have no memory of previously visited areas, or they may avoid such areas. The searchers may act individually or in swarms, optimizing their search efficiency by exchanging information. Finally, the "efficiency" of a search may be judged by a variety of measures, including the time to reach a target or targets, the number of encounters of searchers and targets per unit time, or the exploration range of space per unit time. In general, for each specific situation different search strategies may be appropriate. The quest for optimal strategies has motivated a great deal of work in the past and currently represents one of the most rapidly growing fields of research.

Although the applications are diverse, the underlying physical mechanisms are often the same. Moreover, the inherent complexity of the problem, the abundance of ideas and methods found in this interdisciplinary, innovative field of research is studied in many areas of physics. In particular, the concepts and methods of statistical mechanics are particularly useful to the study of random search. On the one hand, it centers on how to find the global or local maxima of search efficiency functions with incomplete information. This is, naturally, related to the long tradition in physics of using different conceptual and mathematical tools to optimize relevant quantities, e.g., energy, entropy, and action. Such ideas and approaches are very important to solve computationally complex problems involving optimizations in very high dimensional energy landscapes, e.g., in protein folding. On the other hand, random search can also be studied from the perspectives of diffusion and transport properties, stochastic processes, Lévy walks and flights, complex systems and fractal geometry. Some important questions in random search, especially in the case of discrete landscapes, are also associated with graph theory, random lattices, and complex networks.

The highly innovative character of the subject stems from a cross-fertilization of approaches, ideas and fruitful synergies between condensed matter and statistical physics, quantitative biology and mathematics. In particular, analyzing the data gathered by biologists on the trajectories of lizards, fish, or birds searching for food, one introduces random search strategies, based either on Lévy-type or on intermittent random motion, (in which slow search phases alternate with fast relocations), which explore most of the available space within a minimal time, with minimal oversampling and having the best chances of success. As one important outcome, one may introduce more efficient computer algorithms for the search for global minima in nonconvex (multiple extrema) energy landscapes by simulated annealing. It appears that a random search with Lévy-type jump-length distributions allows for a faster cooling scheme, and hence, for a considerable reduction of computer time, than standard algorithms (Boltzmann machine) based on a nearest-neighbor exploration. An observation that in reality a protein finds a specific binding site on a DNA 103 times faster than it is predicted by conventional chemical kinetics, prompted a very deep understanding of the role of non-specific parts of the DNA. Being inert with respect to the reaction, they act as very efficient antennae reducing the overall search time, essentially in the same way as cell bound glycoproteins, extending in the extracellular medium, enhance the efficiency of chemoreception by capturing the ligands and facilitating their transport to the cell bound receptors. Indeed, finding the target in a finite amount of time is of fundamental importance for many biological processes in the cell, in particular for protein diffusion along DNA. In vivo biological cells are characterized by a high degree of molecular crowding and under some conditions, by an inhomogeneous environment, affecting not only the way proteins and biological molecular motors carrying them move, but perhaps even the internal functioning of the molecular motor and its efficiency. For this the stochastic aspects of thermodynamics of such systems are of particular interest for the experimentalists, due to the recent advance in the technologies of manipulating systems at nano and micro scales.

The aim of our workshop is to bring together leading scientists working in this field to exploit and to advance the synergies between the communities working in condensed matter and statistical physics, quantitative biology and mathematics. We will exchange recent theoretical and experimental advances in the understanding of various search processes ranging from the ones taking place in living cells up to the search of animals for food. Also, some recent work points towards the existence of relations between some (intermittent) search strategies and Brownian motors, an aspect that we want to further explore.

The workshop presumes a wide participation from across Europe, as well as scientists from USA and Israel. Some participating groups have already either well-established or incipient collaborations. Our post-workshop aim is to enlarge the scale of existing collaborations. The workshop will also be attended by young, post-graduate and post-doctoral researchers. This workshop will provide a good opportunity to present their work and ample time to exchange ideas with the leaders in the field, which might be very helpful in their further carrier.

Updated at: 2012-03-09 10:05:43