The phylogenetic profile of a protein is a string that encodes the presence or absence of the protein in every fully sequenced genome. Because proteins that participate in a common structural complex or metabolic pathway are likely to evolve in a correlated fashion, the phylogenetic profiles of such proteins are often similar or at least related to each other. The question we address in this paper is the following: how to measure the similarity between two profiles, in an evolutionarily relevant way, in order to develop efficient function prediction methods?