[talks] J Song general exam

Melissa M Lawson mml at CS.Princeton.EDU
Mon May 7 09:48:16 EDT 2007

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.


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


Bioinformatics by Mount - Chapters: 3, 4, 5, 7, 10.


- 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

- 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

- 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

More information about the talks mailing list