Comparative analysis of molecular interaction data provides
understanding of functional modularity in the cell by integrating
cellular organization, functional hierarchy, and evolutionary
conservation. In this talk, we address a number of algorithmic issues
associated with comparative analysis of interaction networks.
We first discuss the problem of identifying common sub-networks
in a collection of networks belonging to diverse species.
The main algorithmic challenges stem from the exponential worst-case
complexity of the underlying mining problem involving large
patterns, as well as the NP-hardness of the subgraph isomorphism
problem. Using a biologically motivated ortholog-contraction
technique for relating proteins across species, we render this
problem tractable. We experimentally show that the proposed 
method can be used as a pruning heuristic that accelerates 
existing techniques significantly, as well as a stand-alone tool 
that conveys significant biological insights at near-interactive 
rates.

With a view to understanding the conservation and divergence of
functional modules, we have developed a network alignment algorithm,
which is grounded in theoretical models of network evolution. Through
graph-theoretic modeling of evolutionary events in terms of matches,
mismatches, and duplications, we reduce the alignment problem into a
graph optimization problem, and develop effective heuristics to solve
this problem efficiently. We probabilistically analyze
the existence of highly connected and conserved subgraphs in random
graphs, in order to assess the statistical significance of identified
patterns. Our methods and algorithms are implemented on various
platforms and tested extensively on a comprehensive collection of
molecular interaction data, illustrating the effectiveness of the
algorithms in terms of providing novel biological insights as well
as computational efficiency.