Finding new partners in signaling pathways with message-passing algorithms

After a brief introduction to algorithmic complexity and some examples of graph problems in biology, I will present the formalism and algorithm we developed for the large-scale reconstruction of a signalling network, based on protein-protein interaction and transcriptomics data. The model we developed in consisted in modeling this reconstruction as a combinatorial optimization problem called the "Prize-collecting Steiner tree problem", and our algorithm, was applied to the reconstruction of the pheromone pathway in S. cerevisiae, with results that we were able to verify experimentally.