From disordered systems physics to biological data analysis

Title of the research project

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

Scientific area 

Complex systems, systems biology

Project coordinator

Riccardo Zecchina

Abstract  

An interdisciplinary project proposing cross-fertilization between statistical physics computational biology.  OPTINF  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.

Description of the research project 

Recently, new approaches to large-scale optimization and inference problems have emerged at the interface between Statistical Mechanics, Probability Theory and Computer Science. Examples include classical methods like Monte-Carlo sampling and simulated annealing, but more importantly also recent advances in message-passing algorithms (MPAs). Indeed, the application of methods originally developed for the analysis of spin glass models (e.g. functional cavity approach) to  hard optimization problems led to the definition of MPAs, a new class of  parallel algorithms that on many problem classes  traditionally believed to be computationally intractable  showed  performance vastly superior to classical methods based on Monte Carlo-like schemes. MPAs are intrinsically parallel and can be used to tackle optimization problems over large networks of constraints.

At the same time, these new techniques are already becoming key tools in fields such as computational biology, where the exponential increase of molecular data is posing new computational challenges in the processes of  identification of  biological systems composed by a multitude  interacting components (genes, proteins, RNAs, ...). This project aims at filling an existing methodological gap  and  to  bring the  message-passing techniques to the full benefit of biological research.  It  is related to  questions ranging from  Theoretical  Challenges (sampling, optimization, inference by cavity  equations and out-of-equilibrium methods, and multiple symmetry breaking effects)  to Algorithms and Applications, namely MPAs  for key  large-scale  inverse problems in  computational biology and machine learning.

Impact on society

The project develops algorithms for data analysis with a particular attention to biological data. It is a fundamental frontier research that could be used in other disciplinary fields, for example to identify genetic regulation mechanisms with the objective of designing personalized care. The study has the potential to greatly contribute to discrete mathematics and probability, two branches of mathematics on which most of the modern numerical methods of statistical physics are based. It engages an international research group which guarantees a strong impact in a scientific field where European research is leading.

Short CV of project coordinator 

Riccardo Zecchina obtained the master’s degree in  Electronic Engineering from  Politecnico di Torino and the PhD in theoretical Physics from Università di  Torino. He is currently Full professor of Theoretical Physics at Politecnico di Torino. He directs a research group at the  Human Genetics Foundation (HuGeF) and he is Fellow at Collegio Carlo Alberto.

He has worked at the International Centre for Theoretical Physics in Trieste for 10 years .  He has been visiting scientist at Microsoft Research (Redmond and Boston, USA) and at Université d’Orsay (Paris, France).

His research interests lie at the interface between statistical physics, computer science and  information theory. His current research interest are focused on machine learning and computational neuroscience.

He is author or co-author of about 120 reviewed articles on scientific journals (including Nature, Science, PNAS, Physical Review Letters, Theoretical Computer Science). In 2016 he received the prestigious Lars Onsager prize in Theoretical Statistical Physics by the American Physical 

Working group 

Carlo Baldassi, Carlo Lucibello, Federica Gerace,  Luca Saglietti, Alessandro Ingrosso, Thomas Gueudre, Andrea Pagnani, Carla Bosia (Politecnico di Torino and Human Genetics Foundation) 

Collaborators:

Marc Mezard (ENS Paris, FR) , Alfredo Braunstein (Polito), Martin Weigt (Paris VII)

Jennifer Chayes, Christian Borgs (Microsoft Research, USA)

     OPTINF project has received funding from the European Research Council (ERC) under the European Union’s Seventh Framework  Programme FP7 2007-2013,  grant agreement No 267915