Mar 23, 2007, 01:30PM – 02:45PM, TLC 405B
Comparative Analysis of Molecular Interaction Networks
Dr. Mehmet Koyuturk, Purdue University, http://www.cs.purdue.edu/homes/koyuturk/
Emergence of high-throughput experiments and resulting databases capture relationships and interactions between biomolecules. These interactions enable modeling and analysis of a cell from a systems perspective – generally using network models. In this talk, we focus on development of computational tools and statistical models for comparative analysis of molecular interaction networks. These tools target understanding of functional modularity in the cell by extracting novel information from massive amounts of interaction data, through integration of cellular organization, functional hierarchy, and evolutionary conservation.
We first discuss the problem of identifying conserved sub-networks in a collection of interaction networks belonging to diverse species. The main algorithmic challenges here stem from the NP-hard subgraph isomorphism problem that underlies frequent subgraph discovery.Three decades of research into theoretical aspects of this problem has highlighted the futility of syntactic approaches, thus motivating use of semantic information. Using a biologically motivated homolog 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 standalone tool that conveys significant biological insights at near-interactive rates.
With a view to understanding the conservation and divergence of modular substructures, we also develop 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 to a graph optimization problem and develop heuristics to solve this problem efficiently. In order to assess the statistical significance of the patterns identified by our algorithms, we probabilistically analyze the distribution of highly connected and conserved subgraphs in random graphs. Our methods and algorithms are implemented on various platforms and tested extensively on a comprehensive collection of molecular interaction data, illustrating their effectiveness in terms of providing novel biological insights as well as computational efficiency.
This is joint work with Yohan Kim, Shankar Subramaniam (University of California, San Diego), Wojciech Szpankowski, and Ananth Grama (Purdue University) and is supported by the National Institutes of Health.
Mehmet Koyuturk received his B.S. (1998) and M.S. (2000) degrees in Electrical and Electronics Engineering, and Computer Engineering, respectively, from Bilkent University,Turkey. During his graduate studies at the Department of Computer Science at Purdue University, he worked on a number of problems in the areas of Computational Biology and Bioinformatics, Parallel and Distributed Computing, and Scientific Computing. His thesis focused on algorithmic and analytical aspects of comparative analysis of biological networks. His collaborations with domain experts in this area resulted in several significant publications and software tools. Since receiving his Ph.D. in August 2006, he has been a post-doctoral research associate in the same department.