JiMin Song will present her research seminar/general exam on Thursday May 10 in Room 302 (note room!). The members of her committee are: Mona Singh (advisor), Olga Troyanskaya, and Tom Funkhouser. Everyone is invited to attend her talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Her abstract and reading list follow below. -------------------------------- Abstract Protein interactions play a key role in almost all biological processes. Recently, high-throughput experiments have uncovered large networks of protein-protein interactions for several species, including human, fruit fly and yeast. It has been postulated that analysis of these protein interaction maps should provide hints to the cell's higher-level organization, and help uncover protein functions, complexes and pathways. A protein-protein interaction network is considered as an undirected graph such that nodes are proteins and edges are interactions between two proteins. Graph clustering methods provide one way for analyzing these networks in order to uncover functional modules and protein complexes. I introduce an evaluation framework for analyzing graph clustering methods. I consider six different evaluation measures, taking into account biological process, cellular component, and protein complex annotations, to compare four diverse graph clustering algorithms. I selected four graph clustering methods, a spectral clustering method, a Markov clustering method, a density-periphery based clustering method, and a clique-finding clustering method. I find that the clique-finding clustering method consistently out performs the others, suggesting that future research along these lines should focus on methods with similar properties. Reading list Textbook: Bioinformatics by Mount - Chapters: 3, 4, 5, 7, 10. Papers: - E Alm and AP Arkin, Biological networks, Curr. Opin. Struct. Biol 2003 - LH Hartwell et al, From molecular to modular cell biology, Nature 1999 - Spirin and Mirny, Protein complexes and functional modules in molecular networks, PNAS 2003 - Sharan et al, Network-based prediction of protein function, EMBO 2007 - Newman, Modularity and community structure in networks, PNAS 2006 - Enright et al, An efficient algorithm for large-scale detection of protein families, NAR 2002 - Altaf-Ul-Amin, Development and implementation of an algorithm for detection of protein complexes in large interaction networks, BMC Bioinformatics 2006 - Palla et al, Uncovering the overlapping community structure of complex networks in nature and society, Nature 2005 - Brohee and van Helden, Evaluation of clustering algorithms for protein-protein interaction networks, BMC Bioinformatics 2006