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
Complex systems, systems biology
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
Carlo Baldassi, Carlo Lucibello, Federica Gerace, Luca Saglietti, Alessandro Ingrosso, Thomas Gueudre, Andrea Pagnani, Carla Bosia (Politecnico di Torino and Human Genetics Foundation)
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
- Budget: 1.260.000
- Start date: 1/07/2011
- End date: 30/06/2016