Statistical physics, combinatorial optimization and biological inference

The Statistical Physics of Disordered Systems offers an incredible wealth of theoretical and algorithmic tools, which can be used to model and analyze some of the most involved complex systems. Problems as different as spin glasses in Statistical Physics, combinatorial optimization in Computer Science (e.g. graph coloring, satisfiability) and statistical inference in Computational Systems Biology (e.g. complex molecular networks like protein-protein interaction and gene-regulatory networks) share many aspects in their mathematical formulation. Ideas developed in one field can be successfully transferred to the benefit of the other fields. In the first part of my presentation, I will explain the connection between statistical physics and combinatorial optimization. Using graph coloring as a prototypical example, I will show how statistical physics helps to understand the solution space structure, to locate phase transitions and to connect them to the computational complexity of the problem. Further more, I will discuss how statistical mechanics tools, originally developed for the theoretical treatment of disordered systems, can be reinterpreted in terms of highly efficient algorithms for optimization and inference, thus opening the way towards analyzing real-world complex systems. One of the major fields of application of such algorithms is the inference of complex molecular networks in systems biology. In the second part of my talk, I will discuss the example of protein-protein interactions. More precisely, I will show how the sequence variability of large protein families (evolutionarily related proteins showing structural and functional conservation) can be used (i) to identify protein-protein interaction interfaces, (ii) to predict high-resolution protein complexes, and (iii) to shed light on interaction specificity and to reconstruct signaling networks in bacteria.