GRAaph ALigner is an algorithm for global network alignment that is based solely on network topology. It aligns two networks and by producing an alignment that consists of a set of ordered pairs, where is a node in and is a node in. GRAAL matches pairs of nodes originating in different networks based on their graphlet degree signature similarities, where a higher similarity between two nodes corresponds to a higher topological similarity between their extended neighborhoods. GRAAL produces global alignments, i.e., it aligns each node in the smaller network to exactly one node in the larger network. The matching proceeds using a technique analogous to the "seed and extend" approach of the popular BLAST algorithm for sequence alignment: it first chooses a single "seed" pair of nodes with high graphlet degree signature similarity. It then expands the alignment radially outward around the seed as far as practical using a greedy algorithm.
Method
When aligning two graphs and, GRAAL first computes costs of aligning each node in G with each node in. The cost of aligning two nodes takes into account the graphlet degree signature similarity between them, modified to reduce the cost as the degrees of both nodes increase, since higher degree nodes with similar signatures provide a tighter constraint than correspondingly similar low degree nodes. In this way, GRAAL align the densest parts of the networks first. Let be the degree of a node in network, let be the maximum degree of nodes in, let be the graphlet degree signature similarity of nodes and, and let be a parameter in that controls the contribution of the node signature similarity to the cost function, then the cost of aligning nodes and is computed as:
.
A cost of corresponds to a pair of topologically identical nodes and, while a cost close to corresponds to a pair of topologically different nodes. GRAAL chooses as the initial seed a pair of nodes, and, that have the smallest cost. Ties are broken randomly. Once the seed is found, GRAAL builds "spheres" of all possible radii around nodes and. A sphere of radius around node is the set of nodes that are at distance from, where the distance is the length of the shortest path from to. Spheres of the same radius in two networks are then greedily aligned together by searching for the pairs and that are not already aligned and that can be aligned with the minimal cost. When all spheres around the seed have been aligned, some nodes in both networks may remain unaligned. For this reason, GRAAL repeats the same algorithm on a pair of networks for and, and searches for the new seed again, if necessary. Network is defined as a new network having the same set of nodes as and having if and only if the distance between nodes and in is less than or equal to, i.e.,. Note that. Using,, allows us to align a path of length in one network to a single edge in another network, which is analogous to allowing "insertions" or "deletions" in a sequence alignment. GRAAL stops when each node from is aligned to exactly one node in.
Application
GRAAL was used to align two protein-protein interaction networks and predict biological function of unannotated proteins based on the function of their annotated aligned partners. Also, GRAAL was used to compute a pairwise all-to-all network similarity matrix between metabolic networks of a group of species and then build their phylogenetic tree. All of this was achieved using solely network topological information.
