Expectation propagation on the diluted Bayesian classifier.

Efficient feature selection from high-dimensional datasets is a very important challenge in many data-driven fields of science and engineering. We introduce a statistical mechanics inspired strategy that addresses the problem of sparse feature selection in the context of binary classification by leveraging a computational scheme known as expectation propagation (EP). The algorithm is used in order to train a continuous-weights perceptron learning a classification rule from a set of (possibly partly mislabeled) examples provided by a teacher perceptron with diluted continuous weights. We test the method in the Bayes optimal setting under a variety of conditions and compare it to other state-of-the-art algorithms based on message passing and on expectation maximization approximate inference schemes. Overall, our simulations show that EP is a robust and competitive algorithm in terms of variable selection properties, estimation accuracy, and computational complexity, especially when the student perceptron is trained from correlated patterns that prevent other iterative methods from converging. Furthermore, our numerical tests demonstrate that the algorithm is capable of learning online the unknown values of prior parameters, such as the dilution level of the weights of the teacher perceptron and the fraction of mislabeled examples, quite accurately. This is achieved by means of a simple maximum likelihood strategy that consists in minimizing the free energy associated with the EP algorithm.

Initial cell density encodes proliferative potential in cancer cell populations.

Individual cells exhibit specific proliferative responses to changes in microenvironmental conditions. Whether such potential is constrained by the cell density throughout the growth process is however unclear. Here, we identify a theoretical framework that captures how the information encoded in the initial density of cancer cell populations impacts their growth profile. By following the growth of hundreds of populations of cancer cells, we found that the time they need to adapt to the environment decreases as the initial cell density increases. Moreover, the population growth rate shows a maximum at intermediate initial densities. With the support of a mathematical model, we show that the observed interdependence of adaptation time and growth rate is significantly at odds both with standard logistic growth models and with the Monod-like function that governs the dependence of the growth rate on nutrient levels. Our results (i) uncover and quantify a previously unnoticed heterogeneity in the growth dynamics of cancer cell populations; (ii) unveil how population growth may be affected by single-cell adaptation times; (iii) contribute to our understanding of the clinically-observed dependence of the primary and metastatic tumor take rates on the initial density of implanted cancer cells.

Predicting Interacting Protein Pairs by Coevolutionary Paralog Matching.

Even if we know that two families of homologous proteins interact, we do not necessarily know, which specific proteins interact inside each species. The reason is that most families contain paralogs, i.e., more than one homologous sequence per species. We have developed a tool to predict interacting paralogs between the two protein families, which is based on the idea of inter-protein coevolution: our algorithm matches those members of the two protein families, which belong to the same species and collectively maximize the detectable coevolutionary signal. It is applicable even in cases, where simpler methods based, e.g., on genomic co-localization of genes coding for interacting proteins or orthology-based methods fail. In this method paper, we present an efficient implementation of this idea based on freely available software.

A multi-scale coevolutionary approach to predict interactions between protein domains.

Interacting proteins and protein domains coevolve on multiple scales, from their correlated presence across species, to correlations in amino-acid usage. Genomic databases provide rapidly growing data for variability in genomic protein content and in protein sequences, calling for computational predictions of unknown interactions. We first introduce the concept of direct phyletic couplings, based on global statistical models of phylogenetic profiles. They strongly increase the accuracy of predicting pairs of related protein domains beyond simpler correlation-based approaches like phylogenetic profiling (80% vs. 30-50% positives out of the 1000 highest-scoring pairs). Combined with the direct coupling analysis of inter-protein residue-residue coevolution, we provide multi-scale evidence for direct but unknown interaction between protein families. An in-depth discussion shows these to be biologically sensible and directly experimentally testable. Negative phyletic couplings highlight alternative solutions for the same functionality, including documented cases of convergent evolution. Thereby our work proves the strong potential of global statistical modeling approaches to genome-wide coevolutionary analysis, far beyond the established use for individual protein complexes and domain-domain interactions.

Exploration-exploitation tradeoffs dictate the optimal distributions of phenotypes for populations subject to fitness fluctuations.

We study a minimal model for the growth of a phenotypically heterogeneous population of cells subject to a fluctuating environment in which they can replicate (by exploiting available resources) and modify their phenotype within a given landscape (thereby exploring novel configurations). The model displays an exploration-exploitation trade-off whose specifics depend on the statistics of the environment. Most notably, the phenotypic distribution corresponding to maximum population fitness (i.e., growth rate) requires a nonzero exploration rate when the magnitude of environmental fluctuations changes randomly over time, while a purely exploitative strategy turns out to be optimal in two-state environments, independently of the statistics of switching times. We obtain analytical insight into the limiting cases of very fast and very slow exploration rates by directly linking population growth to the features of the environment.

Scaling description of non-local rheology.

The plastic flow of amorphous materials displays non-local effects, characterized by a cooperativity length scale ξ. We argue that these effects enter in the more general description of surface phenomena near critical points. Using this approach, we obtain a scaling relation between exponents that describe the strain rate profiles in shear driven and pressure driven flow, which we confirm both in numerical models and experimental data. We find empirically that the cooperative length follows closely the characteristic length previously extracted in homogenous bulk flows. This analysis shows that the often used mean field exponents fail to capture quantitatively the non-local effects. Our analysis also explains the unusually large finite size effects previously observed in pressure driven flows.

Localized growth and branching random walks with time correlations.

We generalize a model of growth over a disordered environment, to a large class of Ito processes. In particular, we study how the microscopic properties of the noise influence the macroscopic growth rate. The present model can account for growth processes in large dimensions and provides a bed to understand better the tradeoff between exploration and exploitation. An additional mapping to the Schrödinger equation readily provides a set of disorders for which this model can be solved exactly. This mean-field approach exhibits interesting features, such as a freezing transition and an optimal point of growth, which can be studied in detail, and gives yet another explanation for the occurrence of the Zipf law in complex, well-connected systems.

Simultaneous identification of specifically interacting paralogs and interprotein contacts by direct coupling analysis.

Understanding protein-protein interactions is central to our understanding of almost all complex biological processes. Computational tools exploiting rapidly growing genomic databases to characterize protein-protein interactions are urgently needed. Such methods should connect multiple scales from evolutionary conserved interactions between families of homologous proteins, over the identification of specifically interacting proteins in the case of multiple paralogs inside a species, down to the prediction of residues being in physical contact across interaction interfaces. Statistical inference methods detecting residue-residue coevolution have recently triggered considerable progress in using sequence data for quaternary protein structure prediction; they require, however, large joint alignments of homologous protein pairs known to interact. The generation of such alignments is a complex computational task on its own; application of coevolutionary modeling has, in turn, been restricted to proteins without paralogs, or to bacterial systems with the corresponding coding genes being colocalized in operons. Here we show that the direct coupling analysis of residue coevolution can be extended to connect the different scales, and simultaneously to match interacting paralogs, to identify interprotein residue-residue contacts and to discriminate interacting from noninteracting families in a multiprotein system. Our results extend the potential applications of coevolutionary analysis far beyond cases treatable so far.

Criticality in the Approach to Failure in Amorphous Solids.

Failure of amorphous solids is fundamental to various phenomena, including landslides and earthquakes. Recent experiments indicate that highly plastic regions form elongated structures that are especially apparent near the maximal shear stress Σmax where failure occurs. This observation suggested that Σmax acts as a critical point where the length scale of those structures diverges, possibly causing macroscopic transient shear bands. Here, we argue instead that the entire solid phase (Σ<Σmax) is critical, that plasticity always involves system-spanning events, and that their magnitude diverges at Σmax independently of the presence of shear bands. We relate the statistics and fractal properties of these rearrangements to an exponent θ that captures the stability of the material, which is observed to vary continuously with stress, and we confirm our predictions in elastoplastic models.

Ground-state statistics of directed polymers with heavy-tailed disorder.

In this mostly numerical study, we reconsider the statistical properties of the ground state of a directed polymer in a d=1+1 "hilly" disorder landscape, i.e., when the quenched disorder has power-law tails. When disorder is Gaussian, the polymer minimizes its total energy through a collective optimization, where the energy of each visited site only weakly contributes to the total. Conversely, a hilly landscape forces the polymer to distort and explore a larger portion of space to reach some particularly deep energy sites. As soon as the fifth moment of the disorder diverges, this mechanism radically changes the standard Kardar-Parisi-Zhang scaling behavior of the directed polymer, and new exponents prevail. After confirming again that the Flory argument accurately predicts these exponents in the tail-dominated phase, we investigate several other statistical features of the ground state that shed light on this unusual transition and on the accuracy of the Flory argument. We underline the theoretical challenge posed by this situation, which paradoxically becomes even more acute above the upper critical dimension.

Strong pinning of propagation fronts in adverse flow.

Reaction fronts evolving in a porous medium exhibit a rich dynamical behavior. In the presence of an adverse flow, experiments show that the front slows down and eventually gets pinned, displaying a particular sawtooth shape. Extensive numerical simulations of the hydrodynamic equations confirm the experimental observations. Here we propose a stylized model, predicting two possible outcomes of the experiments for large adverse flow: either the front develops a sawtooth shape or it acquires a complicated structure with islands and overhangs. A simple criterion allows one to distinguish between the two scenarios and its validity is reproduced by direct hydrodynamical simulations. Our model gives a better understanding of the transition and is relevant in a variety of domains, when the pinning regime is strong and only relies on a small number of sites.

Statistics of shocks in a toy model with heavy tails.

We study the energy minimization for a particle in a quadratic well in the presence of short-ranged heavy-tailed disorder, as a toy model for an elastic manifold. The discrete model is shown to be described in the scaling limit by a continuum Poisson process model which captures the three universality classes. This model is solved in general, and we give, in the present case (Frechet class), detailed results for the distribution of the minimum energy and position, and the distribution of the sizes of the shocks (i.e., switches in the ground state) which arise as the position of the well is varied. All these distributions are found to exhibit heavy tails with modified exponents. These results lead to an "exotic regime" in Burgers turbulence decaying from a heavy-tailed initial condition.

Explore or exploit? A generic model and an exactly solvable case.

Finding a good compromise between the exploitation of known resources and the exploration of unknown, but potentially more profitable choices, is a general problem, which arises in many different scientific disciplines. We propose a stylized model for these exploration-exploitation situations, including population or economic growth, portfolio optimization, evolutionary dynamics, or the problem of optimal pinning of vortices or dislocations in disordered materials. We find the exact growth rate of this model for treelike geometries and prove the existence of an optimal migration rate in this case. Numerical simulations in the one-dimensional case confirm the generic existence of an optimum.

Short-time growth of a Kardar-Parisi-Zhang interface with flat initial conditions.

The short-time behavior of the (1+1)-dimensional Kardar-Parisi-Zhang (KPZ) growth equation with a flat initial condition is obtained from the exact expressions for the moments of the partition function of a directed polymer with one end point free and the other fixed. From these expressions, the short-time expansions of the lowest cumulants of the KPZ height field are exactly derived. The results for these two classes of cumulants are checked in high-precision lattice numerical simulations. The short-time limit considered here is relevant for the study of the interface growth in the large-diffusivity or weak-noise limit and describes the universal crossover between the Edwards-Wilkinson and the KPZ universality classes for an initially flat interface.