Bioinformatics Seminar

Wednesday, November 5, 2008
3:00 - 4:00
Room 457 Blocker

Ananth Grama

Computer Science
Purdue University

Comparative Analysis of Molecular Interaction Networks

Abstract

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 National Science Foundation and National Institutes of Health.