(a) in local network alignment, we wish to identify local regions that are similar across multiple networks. The similarity combines topological similarity and node similarity. When looking for matching dense subgraphs, the solution may align nodes { 1, 2, 3, 4} to either {A, B, C, D} or {E, F, G, H}.

(b)

(b) in network querying, instances of a small network are searched for in another, usually much larger, network. For illustration purposes, assume we define a network based on the sky map where nodes represent the stars. Close stars are connected by an edge and the similarity between stars is determined according to their luminosity (graphically represented by both size and color). A known constellation may serve as a query to look for similar patterns.

(c)

(c) in global network alignment,
the goal is to align all the
nodes from one network with
those of the other network,
while optimizing node and edge
similarity. in the given example,
assuming all nodes are equally
similar, a clique such as
the one given by the nodes
{ 1, 2, 3, 4} could be locally
aligned to either {A, B, C, D} or
{E, F, G, H}. however, when
globally aligning the entire
networks, the additional
information given by the topology
of the nodes { 5, 6, 7, 8, 9}
disambiguates the choice.

 

In this review, we survey the field of comparative network analysis with an emphasis on the arising computational problems and the different methods that have been used to tackle them, starting from heuristic approaches, going through parameterized algorithms that perform well on practical instances, and ending with optimal integer linear programming (ILP)-based solutions that rely on powerful, yet available, industrial solvers. We demonstrate the applications of these methods to predict protein function and interaction, infer the organization of protein-protein interaction networks into their underlying functional modules, and link biological processes within and across species.

A Roadmap to Network
Comparison techniques
We view a PPI network of a given
species as a graph G = (V, E), where V is
the set of proteins of the given species
and E is the set of pairwise interactions
among them. In a network compari-
son problem, one is given two or more
networks along with sequence infor-
mation for their member proteins. The
goal is to identify similarities between
the compared networks, which could
be either local or global in nature
(Figure 1). The underlying assump-
tion is that the networks have evolved
from a common ancestral network,
and hence, evolutionarily related pro-
teins should display similar sequence
and interaction patterns. For ease of
presentation, we focus in the descrip-
tion below on pairwise comparisons,
but the problems and their solutions
generalize to multiple networks.