Abstract A number of predictive methods have been designed to predict protein interaction from sequence or expression data. On the experimental front, however, high-throughput proteomics technologies are starting to yield large volumes of protein-protein interaction data. High-quality experimental protein interaction maps constitute the natural dataset upon which to build interaction predictions. Thus the motivation to develop the first interaction-based protein interaction map prediction algorithm. A technique to predict protein-protein interaction maps across organisms is introduced, the ‘interaction-domain pair profile’ method. The method uses a high-quality protein interaction map with interaction domain information as input to predict an interaction map in another organism. It combines sequence similarity searches with clustering based on interaction patterns and interaction domain information. We apply this approach to the prediction of an interaction map of Escherichia coli from the recently published interaction map of the human gastric pathogen Helicobacter pylori. Results are compared with predictions of a second inference method based only on full-length protein sequence similarity — the “naive” method. The domain-based method is shown to i) eliminate a significant amount of false-positives of the naive method that are the consequences of multi-domain proteins; ii) increase the sensitivity compared to the naive method by identifying new potential interactions. Availability: Contact the authors. Contact: vschachter@hybrigenics.fr