Protein Mover’s Distance: A Geometric Approach for Global Alignment of PPI Networks

We present a novel geometric method for the problem of global alignment of protein-protein interaction (PPI) networks. A PPI network can be viewed as a node-edge graph and its alignment  often needs to solve some generalized version of the subgraph isomorphism problem which is notoriously challenging and NP-hard. We propose a two-step algorithm for the global PPI network alignment which consists of an Embedding Step and a Geometric Step. Our algorithm first applies three different graph embedding techniques that preserve the topological structure of the original PPI networks and maps the problem from graph domain to geometric domain. Then we define a new objective function, called ``Protein Mover’s Distance (PMD)” to evaluate the alignment of two PPI networks. PMD is similar to the well known ``Earth Mover’s Distance”; however, we also incorporate some other information, e.g., the functional annotation of proteins. Our algorithm computes a rigid transformation for one of the embedded PPI networks so as to minimize its  PMD to the other PPI network.  By using the flow values of the resulting PMD as the matching scores, we are able to obtain the desired alignment. Comparing with existing methods, our algorithm globally optimizes the problem and yields an alignment with better quality.