Abstract: Determining protein function is a fundamental biological challenge, and protein-protein interaction networks are an increasingly useful data source from which to computationally predict protein annotations. One approach to automated detection of protein complexes and prediction of biological processes is to divide an interaction network into biologically meaningful modules or clusters. I will present several graph clustering techniques and illustrate their usefulness for predicting protein annotations. I will describe a novel method to decompose a hierarchical tree decomposition into a collection of clusters that optimally match a set of known annotations. We find that our approach generally outperforms commonly used heuristics for identifying protein complexes from hierarchical clusterings. The technique is general and may be of use in other applications where hierarchical clustering is used. I will also show how a graph compression technique called graph summarization leads to more biologically.. - Adam Kraut

..meaningful modules than other graph clustering algorithms. - Adam Kraut

Analyze networks and recover complexes or proteins involved in the same biological process by graph clustering approach - Adam Kraut

New technique, Graph Summarization - Adam Kraut

Want modules with proteins having similar cellular roles - Adam Kraut

Similar interaction partners implies similar cellular roles - Adam Kraut

Similar interaction partners implies redundancy; redundancy implies compressibility - Adam Kraut

Use supernodes as modules - Adam Kraut

Greedy GS; hierarchical merging procedure; has natural stopping point when you can't compress anymore - Adam Kraut

Compares to Newman Modularity, Markov Clustering, MCODE; Graph Summarization finds more modules - Adam Kraut

Useful to combine GS, MCL, MCODE for predictions (each have unique predictions) - Adam Kraut

GS is good for annotation prediction; confirmed on complexes and biological processes; preferable to MCL, MCODE, NSP - Adam Kraut

Q: "What's the biological relevance!?" A: "Predicting function (assigning GO terms)" - Adam Kraut

Variation of Information between clusterings C and D; uncertainty in clustering C given D plus the uncertainty in D given C - Adam Kraut

VI-CUT; choose the cut in the hierarchical decomposition that minimizes the variation of information - Adam Kraut

Performance metric: MIPS annotation; VI-CUT outperforms Brun, Enrich, Snip methods - Adam Kraut

VI-CUT for Metagenomics; determining population diversity; take 16s RNA -> MSA -> Hierarchical decomposition tree -> Make cuts to estimate number of OTU (operational taxonomy unit) - Adam Kraut

Applied to WWW; compression ratio around 50% - Adam Kraut