Multi-SANA: Comparing Topological Objective Functions for Multiple Network Alignment

<p>All life on Earth is related, so that some molecular interactions are common across almost all living cells, with the number of common interactions increasing as we look at more closely related species. In particular, we expect the {\it protein-protein interaction} (PPI) networks of closely-related species to share high levels of similarity. This similarity may facilitate the transfer of functional knowledge between model species and human. {\it Multiple Network Alignment} is the process of uncovering the connection similarity between 3 or more networks simultaneously. Existing algorithms for multiple network alignment rely on sequence similarities to help drive the alignments, and no comprehensive study has been done to determine the most effective ways to utilize network connectivity---network topology---to drive multiple network alignment. Here we devise and empirically test the efficacy of several measures of topological similarity between three or more networks. To evolve the alignments towards optimal, we use simulated annealing as the search algorithm since it is agnostic to the objective being optimized. We test the measures both on the partially synthetic and highly similar PPI networks from the {\it Integrated Interaction Database}, as well as on real PPI networks from a recent BioGRID release.</p>