Better Network Modules: New tools for protein network analysis

Summarized Yeast Interactome


Faculty:  Carl Kingsford

Graduate Students: Saket Navlakha, Guillaume Marçais, Dave Kelley, Darya Filippova, Justin Malin, Geet Duggal, Emre Sefer.

Undergraduates: Megan Riordian, Aashish Gadani (as part of the CBCB Summer Internship Program, which is partially supported by this grant).


This work is supported by the NSF through grant ABI-0849899 to Carl Kingsford

Graph clustering as a tool for understanding protein interaction networks

Recently developed high-throughput techniques are being used to sample protein-protein interactions from many organisms and are creating a wealth of data that must be analyzed computationally. A central challenge in the study of these networks is finding biologically meaningful and interpretable modules within them. We will develop new algorithms and a suite of software tools based on a general and flexible definition of a "network module" in order to extract meaningful biological clusters from noisy and incomplete interaction data.

The new tools and algorithms will be used to improve visualization of protein interaction networks, identify protein complexes and biological processes embedded within the network data, and to discover redundant pathways from synthetic lethal interaction data. They will also be applied to comparing the interaction networks of several different species. The resulting network analysis software will expand the capabilities of both systems biologists and biologists working on particular protein complexes and pathways to make better use of noisy network data, and the proposed visualization software will vastly improve researchers’ capability to interactively explore these networks. Our predictions will be deposited in a public database that we will create in order to collect computationally predicted annotations made by us and other groups.

The tools will strengthen our understanding of the organization of biological networks, and it will have broader impact by increasing the information technology infrastructure available for the analysis of interaction data, providing better transfer of hypotheses between computational biologists and biologists, and by the training of undergraduates in a summer internship program.


  • VI-Cut - Software for choosing hierarchical clusterings given partial cluster information
  • ModuTree - Software for finding near-optimal solutions to network modularity problems


Papers supported by the project:

Preliminary and prior work related to the project:

Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation