OPTINF · Optimization and inference algorithms from the theory of disordered systems: theoretical challenges and applications to large-scale inverse problems in systems biology

The project is focused on two objectives: the study of optimization and inference algorithms based on advanced statistical physics methods for disordered systems, and their application to large-scale inverse problems in computational systems biology.In last years, fundamentally new approaches to large-scale optimization and inference problems have emerged at the interface between Statistical Mechanics and Computer Science. Partly this was made possible by extending ideas from the statistical physics of disordered systems to applications in computer science. Indeed, the application of methods originally developed for the analysis of spin glasses to hard optimization problems led to the definition of message passing algorithms (MPAs), a new class of algorithms that on many difficult problems showed performance definitely superior to Monte Carlo schemes. The field presents many conceptual open problems and applications of great potential impact.MPAs are intrinsically parallel and can be used to tackle optimization problems over large networks of constraints. Their probabilistic foundations are still largely unexplored and thus their study can contribute greatly to computational statistical physics.At the same time, these new techniques are becoming key tools in fields such as computational systems biology, where the exponential increase of molecular data is posing new computational challenges in the study of biological systems composed by many interacting molecular components. It is a fact that the advances in sequencing and other high throughput technologies deeply transformed the world of biological research over the last 10-15 years. This project aims at bringing the MPAs techniques to the full benefit of biological research.