Affiliations: [a] Department of Materials Science and Engineering, University of Illinois at Urbana-Champaign, Urbana, IL, USA | [b] Department of Materials Science and Engineering, Northwestern University, Evanston, IL, USA | [c] Department of Chemical and Biomolecular Engineering, University of Illinois at Urbana-Champaign, Urbana, IL, USA
Correspondence:
[*]
Corresponding author: Andrew L. Ferguson, Department of Materials Science and Engineering, University of Illinois at Urbana-Champaign, Urbana, IL 61801, USA. Tel.: +86 217 300 2354; Fax: +86 217 333 2736; E-mail:alf@illinois.edu
Abstract: We present a new algorithm, global positioning graph
matching (GPGM), to perform global network alignments between pairs of
undirected graphs by minimizing a dissimilarity score over matched vertices.
We define structural dissimilarities based on a random walk over each graph
to provide a robust measure of the global graph topology using a nonlinear
manifold learning algorithm known as diffusion maps. Measures of
vertex-vertex dissimilarity are straightforwardly incorporated in a convex
combination. We have tested our approach in pairwise alignments of
protein-protein interaction networks of Xenopus laevis (frog), Rattus norvegicus (rat), Caenorhabditis elegans (worm), Mus musculus (mouse),
and Drosophila melanogaster (fly). When vertex-vertex dissimilarities are incorporated using homology scores between protein sequences, the performance of GPGM is
comparable to that of the IsoRank algorithm (Singh et al. Proc. Natl. Acad.
Sci. USA 105 35 12763 (2008)). When homology information is not included,
GPGM discovers superior alignments, making it well suited to graph matching
applications where vertex labels are unknown or undefined.
