Deciphering the network of protein interactions that underlines cellular op
erations has become one of the main tasks of proteomics and computational b
iology. Recently, a set of bioinformatics approaches has emerged for the pr
ediction of possible interactions by combining sequence and genomic informa
tion. Even though the initial results are very promising, the current metho
ds are still far from perfect. We propose here a new way of discovering pos
sible protein-protein interactions based on the comparison of the evolution
ary distances between the sequences of the associated protein families, an
idea based on previous observations of correspondence between the phylogene
tic trees of associated proteins in systems such as ligands and receptors.
Here, we extend the approach to different test sets, including the statisti
cal evaluation of their capacity to predict protein interactions. To demons
trate the possibilities of the system to perform large-scale predictions of
interactions, we present the application to a collection of more than 67 0
00 pairs of E.coli proteins, of which 2742 are predicted to correspond to i
nteracting proteins.