University of Minnesota
University Relations
myU OneStop

Go to unit's home.

Home | Seminars and Symposia | Past seminars/symposia: Friday, May 12, 2006

Comparative Analysis of Interaction Networks


Ananth Grama
Purdue University

Friday, May 12, 2006
11:15 am

402 Walter Library

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. Three decades of research into theoretical aspects of this problem has highlighted the futility of syntactic approaches to this problem — thus motivating use of semantic information. 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 also developed network alignment techniques, 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. This is joint work with Mehmet Koyuturk (Purdue University), and Yohan Kim and Shankar Subramaniam (University of California, San Diego). This work was supported by the National Institutes of Health Grant.