Evolutionary analysis reveals low coverage as the major challenge for protein interaction network alignment.

Local alignments of protein interaction networks have found little conservation among several species. While this could be a consequence of the incompleteness of interaction data-sets and presence of error, an intriguing prospect is that the process of network evolution is sufficient to erase any evidence of conservation. Here, we aim to test this hypothesis using models of network evolution and also investigate the role of error in the results of network alignment. We devised a distance metric based on summary statistics to assess the fit between experimental and simulated network alignments. Our results indicate that network evolution alone is unlikely to account for the poor quality alignments given by real data. Alignments of simulated networks undergoing evolution are considerably (4 to 5 times) larger than real alignments. We compare several error models in their ability to explain this discrepancy. Our estimates of false negative rates vary from 20 to 60% dependent on whether incomplete proteome sampling is taken into account or not. We also find that false positives appear to affect network alignments little compared to false negatives indicating that incompleteness, not spurious links, is the major challenge for interactome-level comparisons.