Better Network Modules: New tools for protein network analysis
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
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
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
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
- 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:
- G. Duggal, S. Navlakha, M. Girvan, and C. Kingsford. Uncovering
Many Views of Biological Networks Using Ensembles of Near-Optimal Partitions.
To appear in MultiClust: 1st International Workshop on Discovering, Summarizing
and Using Multiple Clusterings at KDD 2010.
- J. R. White, S. Navlakha, N. Nagarajan, M. Ghodsi, C.
Kingsford, and M. Pop. Alignment and
clustering of phylogenetic markers - implications for microbial diversity
studies. BMC Bioinformatics 2010, 11:152.
- G. Lapizco Encinas, Carl Kingsford, and James Reggia. Particle
Swarm Optimization for Multimodal Combinatorial Problems and its application to
Protein Design. To appear in IEEE Congress on Evolutionary Computation,
- S. Navlakha and C. Kingsford. The Power of Protein Interaction Networks
for Associating Genes with Diseases. Bioinformatics, 2010; doi:
10.1093/bioinformatics/btq076. [Supporting Website]
- C. Kingsford, M. C. Schatz, and Mihai Pop. Assembly
complexity of prokaryotic genomes using short reads. BMC
Bioinformatics 11:21, 2010. (Top 10 most-viewed articles
- D. E. Kelley and C. Kingsford. Extracting between-pathway
models from E-MAP interactions using expected graph compression. To appear in
- S. Navlakha and C. Kingsford. Exploring Biological Network
Dynamics with Ensembles of Graph Partitions. In Proceedings of Pac.
Symp. Biocomp. 2010, pages 166-177.
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