Title: Protein Interaction Module Detection Using Matrix-Based Graph Algorithms

Speaker: Dr. Chris Ding, faculty candidate

Time: 10:40 AM , Feb. 26, Mon, 2007

Place: CSE 404

ABSTRACT:

Proteins carry out most cellular processes as protein modules. Systematic identification of protein functional modules provide essential knowledge linking proteome dynamics to cellular functions. We briefly outline the rapidly evolving field of genomics and clarify the vital role of protein interaction studies. We then describe two matrix-based graph algorithms for computing protein interaction modules: spectral clustering and clique/biclique algorithms. Matrix-based learning algorithms is going through a Renaissance period and is shaping up as a major new direction. In this talk, we outline several fundamental advances in the field. We show that the NP-hard seemingly intractable clustering and clique problems can be solved efficiently using matrix-based algorithms. Applying these algorithms to Yeast, Pyrococcus, Sulfolobus, Halobacterium interaction networks, we obtain a large number of protein interaction modules, many of them conserved across several species and some of them have been experimentally verified by our collaborators. We discuss their biological significance. Many uncharacterized proteins are found to be new members of important protein complexes.

Dr. Chris Ding is a staff computer scientist at Lawrence Berkeley National Laboratory. His research focus on bioinformatics, machine mining, information retrieval, and high performance computing. He earned a Ph.D. from Columbia, worked at Caltech and Jet Propulsion Lab before joining Berkeley Lab in 1996. He served on many NSF review panels, program committees of many data mining and bioinformatics conferences, and editorial board of Int'l J. Data Mining and Bioinformatics. He won two best paper awards and has given several tutorials on spectral clustering, PCA and matrix factorization based learning, and bioinformatics in leading machine learning conferences. He has given invited seminars at Stanford, Berkeley, Carnegie Mellon, U. Alberta, U. Hong Kong, IBM Research, Google Research.