The basis of a majority of biological functions is formed by protein-protein interactions. Experimental approaches to identify interaction surfaces between proteins are laborious or serendipitous tasks and include the generation of co-crystal structures to gain detailed molecular pictures of interactions. The genomic era is starting to provide completely new and promising possibilities: The number of sequenced bacterial genomes approaches 1000. Amplification of some interacting systems (e.g. two-component signal transduction) increases the number of homologous proteins by a factor of about 10-fold beyond the genome number; organization in operons allows for an in-silico identification of interaction partners. In our work, we propose a message-passing approach to infer networks of statistically coupled residues between interacting protein partners. In the case of bacterial two-component signal transduction systems, where interaction surfaces are known due to the existence of an exemplary co-crystal structure, we successfully identify these surfaces bothe for kinase / response-regulator pairs and response-regulator homodimers from the knowledge of multispecies sequence data alone. The infered model (in statistical-physics language a disordered 21-states Potts model) is able to capture details of these interactions down to single amino-acid resolution and to distinguish interacting from non-interacting protein pairs. Our work therefore provides an example for a successfull application of statistical-mechanics tools to computational systems biology. It is done in collaboration with J.A. Hoch, T. Hwa, H. Szurmant and R.A. White.