Comparative Analysis of Molecular Interaction Networks
--


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 analytical and
algorithmic issues associated with comparative analysis of
interaction networks. We first discuss the problem of identifying
conserved sub-networks in a collection of networks belonging to
diverse species. The main algorithmic challenges stem from the
exponential worst-case complexity associated with the underlying
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 also investigate network alignment
algorithms, leveraging 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.
We probabilistically analyze the existence of highly connected
and conserved subgraphs in random graphs, in order to assess
the statistical significance of identified patterns. Using these
measures as optimization criteria, we develop algorithms with
significantly better performance in terms of precision and
recall, compared to existing methods. Software resulting from
these analytical studies are available as frequently accessed
services, plugins to commonly used analysis frameworks
(Cytoscape), and as standalone programs, over the public
domain.



--
This work is in collaboration with Mehmet Koyuturk (CWRU),
and Yohan Kim and Shankar Subramaniam (UCSD). It is sponsored
by the US National Science Foundation and US National Institutes
of Health.