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.

Software

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

Publications

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, 2010.
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 Jan/Feb 2010.)
D. E. Kelley and C. Kingsford. Extracting between-pathway models from E-MAP interactions using expected graph compression. To appear in RECOMB 2010.
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:

S. Navlakha, J. White, N. Nagarajan, M. Pop, and C. Kingsford. Finding Biologically Accurate Clusterings in Hierarchical Tree Decompositions Using the Variation of Information. In Proceedings of RECOMB 2009. Lecture Notes in Computer Science 5541, pages 400-417. doi:10.1007/978-3-642-02008-7.
S. Navlakha, M. Schatz, and C. Kingsford. Revealing Biological Modules via Graph Summarization. Presented at RECOMB-SB/RG/DREAM3 satellite conference, 2008. Journal version in J. Comp. Biol. 16(2):253-264, 2009.

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