Graph Aligner
GRAaph ALigner (GRAAL)[1] is an algorithm for global network alignment that is based solely on network topology. It aligns two networks G and H by producing an alignment that consists of a set of ordered pairs (x, y), where x is a node in G and y is a node in H. 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 (out to distance 4). 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 (one node from each network) with high graphlet degree signature similarity. It then expands the alignment radially outward around the seed as far as practical using a greedy algorithm (see [Kuchaiev et al., 2010][1] for details).
GRAAL was used to align two protein-protein interaction (PPI) networks and predict biological function of unannotated proteins based on the function of their annotated aligned partners.[1] 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.[1] All of this was achieved using solely network topological information.