  The function of a protein is defined by its interaction partners. Thus,
topology-driven network alignment of the protein-protein interaction (PPI)
networks of two species should uncover similar interaction patterns and allow
identification of functionally similar proteins. Howver, few of the fifty or
more algorithms for PPI network alignment have demonstrated a significant link
between network topology and functional similarity, and none have recovered
orthologs using network topology alone. We find that the major contributing
factors to this failure are: (i) edge densities in current PPI networks are too
low to expect topological network alignment to succeed; (ii) when edge
densities are high enough, some measures of topological similarity easily
uncover functionally similar proteins while others do not; and (iii) most
network alignment algorithms fail to optimize their own topological objective
functions, hampering their ability to use topology effectively. We demonstrate
that SANA-the Simulated Annealing Network Aligner-significantly outperforms
existing aligners at optimizing their own objective functions, even achieving
near-optimal solutions when optimal solution is known. We offer the first
demonstration of global network alignments based on topology alone that align
functionally similar proteins with p-values in some cases below 1e-300. We
predict that topological network alignment has a bright future as edge
densities increase towards the value where good alignments become possible. We
demonstrate that when enough common topology is present at high enough edge
densities-for example in the recent, partly synthetic networks of the
Integrated Interaction Database-topological network alignment easily recovers
most orthologs, paving the way towards high-throughput functional prediction
based on topology-driven network alignment.
