Small-coupling expansion for multiple sequence alignment.

The alignment of biological sequences such as DNA, RNA, and proteins, is one of the basic tools that allow to detect evolutionary patterns, as well as functional or structural characterizations between homologous sequences in different organisms. Typically, state-of-the-art bioinformatics tools are based on profile models that assume the statistical independence of the different sites of the sequences. Over the last years, it has become increasingly clear that homologous sequences show complex patterns of long-range correlations over the primary sequence as a consequence of the natural evolution process that selects genetic variants under the constraint of preserving the functional or structural determinants of the sequence. Here, we present an alignment algorithm based on message passing techniques that overcomes the limitations of profile models. Our method is based on a perturbative small-coupling expansion of the free energy of the model that assumes a linear chain approximation as the zeroth-order of the expansion. We test the potentiality of the algorithm against standard competing strategies on several biological sequences.

Statistical mechanics of inference in epidemic spreading.

We investigate the information-theoretical limits of inference tasks in epidemic spreading on graphs in the thermodynamic limit. The typical inference tasks consist in computing observables of the posterior distribution of the epidemic model given observations taken from a ground-truth (sometimes called planted) random trajectory. We can identify two main sources of quenched disorder: the graph ensemble and the planted trajectory. The epidemic dynamics however induces nontrivial long-range correlations among individuals' states on the latter. This results in nonlocal correlated quenched disorder which unfortunately is typically hard to handle. To overcome this difficulty, we divide the dynamical process into two sets of variables: a set of stochastic independent variables (representing transmission delays), plus a set of correlated variables (the infection times) that depend deterministically on the first. Treating the former as quenched variables and the latter as dynamic ones, computing disorder average becomes feasible by means of the replica-symmetric cavity method. We give theoretical predictions on the posterior probability distribution of the trajectory of each individual, conditioned to observations on the state of individuals at given times, focusing on the susceptible infectious (SI) model. In the Bayes-optimal condition, i.e., when true dynamic parameters are known, the inference task is expected to fall in the replica-symmetric regime. We indeed provide predictions for the information theoretic limits of various inference tasks, in form of phase diagrams. We also identify a region, in the Bayes-optimal setting, with strong hints of replica-symmetry breaking. When true parameters are unknown, we show how a maximum-likelihood procedure is able to recover them with mostly unaffected performance.

Closest-vector problem and the zero-temperature p-spin landscape for lossy compression.

We consider a high-dimensional random constrained optimization problem in which a set of binary variables is subjected to a linear system of equations. The cost function is a simple linear cost, measuring the Hamming distance with respect to a reference configuration. Despite its apparent simplicity, this problem exhibits a rich phenomenology. We show that different situations arise depending on the random ensemble of linear systems. When each variable is involved in at most two linear constraints, we show that the problem can be partially solved analytically, in particular we show that upon convergence, the zero-temperature limit of the cavity equations returns the optimal solution. We then study the geometrical properties of more general random ensembles. In particular we observe a range in the density of constraints at which the system enters a glassy phase where the cost function has many minima. Interestingly, the algorithmic performances are only sensitive to another phase transition affecting the structure of configurations allowed by the linear constraints. We also extend our results to variables belonging to GF(q), the Galois field of order q. We show that increasing the value of q allows to achieve a better optimum, which is confirmed by the replica-symmetric cavity method predictions.