Unraveling protein networks with power graph analysis.

Networks play a crucial role in computational biology, yet their analysis and representation is still an open problem. Power Graph Analysis is a lossless transformation of biological networks into a compact, less redundant representation, exploiting the abundance of cliques and bicliques as elementary topological motifs. We demonstrate with five examples the advantages of Power Graph Analysis. Investigating protein-protein interaction networks, we show how the catalytic subunits of the casein kinase II complex are distinguishable from the regulatory subunits, how interaction profiles and sequence phylogeny of SH3 domains correlate, and how false positive interactions among high-throughput interactions are spotted. Additionally, we demonstrate the generality of Power Graph Analysis by applying it to two other types of networks. We show how power graphs induce a clustering of both transcription factors and target genes in bipartite transcription networks, and how the erosion of a phosphatase domain in type 22 non-receptor tyrosine phosphatases is detected. We apply Power Graph Analysis to high-throughput protein interaction networks and show that up to 85% (56% on average) of the information is redundant. Experimental networks are more compressible than rewired ones of same degree distribution, indicating that experimental networks are rich in cliques and bicliques. Power Graphs are a novel representation of networks, which reduces network complexity by explicitly representing re-occurring network motifs. Power Graphs compress up to 85% of the edges in protein interaction networks and are applicable to all types of networks such as protein interactions, regulatory networks, or homology networks.

Drug repositioning through incomplete bi-cliques in an integrated drug-target-disease network.

Recently, there has been much interest in gene-disease networks and polypharmacology as a basis for drug repositioning. Here, we integrate data from structural and chemical databases to create a drug-target-disease network for 147 promiscuous drugs, their 553 protein targets, and 44 disease indications. Visualizing and analyzing such complex networks is still an open problem. We approach it by mining the network for network motifs of bi-cliques. In our case, a bi-clique is a subnetwork in which every drug is linked to every target and disease. Since the data are incomplete, we identify incomplete bi-cliques, whose completion introduces novel, predicted links from drugs to targets and diseases. We demonstrate the power of this approach by repositioning cardiovascular drugs to parasitic diseases, by predicting the cancer-related kinase PIK3CG as a novel target of resveratrol, and by identifying for five drugs a shared binding site in four serine proteases and novel links to cancer, cardiovascular, and parasitic diseases.

Network compression as a quality measure for protein interaction networks.

With the advent of large-scale protein interaction studies, there is much debate about data quality. Can different noise levels in the measurements be assessed by analyzing network structure? Because proteomic regulation is inherently co-operative, modular and redundant, it is inherently compressible when represented as a network. Here we propose that network compression can be used to compare false positive and false negative noise levels in protein interaction networks. We validate this hypothesis by first confirming the detrimental effect of false positives and false negatives. Second, we show that gold standard networks are more compressible. Third, we show that compressibility correlates with co-expression, co-localization, and shared function. Fourth, we also observe correlation with better protein tagging methods, physiological expression in contrast to over-expression of tagged proteins, and smart pooling approaches for yeast two-hybrid screens. Overall, this new measure is a proxy for both sensitivity and specificity and gives complementary information to standard measures such as average degree and clustering coefficients.