Source-linked AI summary
Uncovering Biological Network Function via Graphlet Degree Signatures
Tijana Milenkovic, Natasa Przulj
TL;DR
The paper asks whether local PPI network structure can reveal protein function, especially for unclassified proteins. It compares proteins through graphlet-degree signatures and finds that topologically similar groups share several biological properties, supporting predictions for unclassified yeast proteins.
Problem
Relating PPI network topology to biological function and inferring functions for numerous unclassified proteins remain major challenges.
Method
The method clusters PPI-network proteins by weighted similarity between 73-coordinate graphlet-orbit signatures and evaluates shared biological properties.
Results
Across yeast and human PPI networks, topologically similar clusters share protein complexes, biological functions, subcellular or cellular localizations, tissue expressions, or biological processes.
Takeaways & Limitations
The method provides guidelines for predicting complex, functional-group, and subcellular-compartment membership of yet-unclassified yeast proteins.
Takeaways & Limitations
Using graphlets larger than five nodes would increase computational complexity beyond the current O(|V|^5), although the algorithm is easily parallelized.
Abstract
from arXiv · showhide
Proteins are essential macromolecules of life and thus understanding their function is of great importance. The number of functionally unclassified proteins is large even for simple and well studied organisms such as baker's yeast. Methods for determining protein function have shifted their focus from targeting specific proteins based solely on sequence homology to analyses of the entire proteome based on protein-protein interaction (PPI) networks. Since proteins aggregate to perform a certain function, analyzing structural properties of PPI networks may provide useful clues about the biological function of individual proteins, protein complexes they participate in, and even larger subcellular machines. We design a sensitive graph theoretic method for comparing local structures of node neighborhoods that demonstrates that in PPI networks, biological function of a node and its local network structure are closely related. The method groups topologically similar proteins under this measure in a PPI network and shows that these protein groups belong to the same protein complexes, perform the same biological functions, are localized in the same subcellular compartments, and have the same tissue expressions. Moreover, we apply our technique on a proteome-scale network data and infer biological function of yet unclassified proteins demonstrating that our method can provide valuable guidelines for future experimental research.
1 INTRODUCTION
The paper addresses the challenge of relating PPI network topology to protein function and predicting functions for unclassified proteins. It proposes clustering proteins by similar local topological surroundings rather than requiring dense connectivity.
- Motivation: PPI networks represent proteins as nodes and physical interactions as undirected edges, reflecting the interconnected nature of biological processes.
- Related approaches: Determining protein function from PPI networks has been approached through neighborhood-based, global optimization, and dense-cluster methods.
- Approach: The proposed method clusters nodes with similar topological surroundings and identifies groups sharing complexes, functions, compartments, or tissue expressions.
- Application: The method is applied to predict protein-complex, functional-group, and subcellular-compartment membership for unclassified yeast proteins.
- Approach: Unlike dense-region clustering, its clusters contain nodes with similar topological signatures that need not be connected or located in the same network region.
2 METHODS
The method represents each protein by graphlet-orbit counts and compares these signatures using weighted, log-scaled coordinate distances. Proteins whose similarity exceeds an experimentally chosen threshold are clustered together.
- Graphlet signatures: A graphlet is a small connected non-isomorphic induced subgraph, and the method counts graphlets touching each node across 2- to 5-node graphlets.The degree of a node is the first coordinate because an edge is the only 2-node graphlet.
- Graphlet signatures: Each node signature has 73 coordinates corresponding to graphlet automorphism orbits.
- Weighted similarity: Orbit weights decrease with the number of other orbits affecting them, assigning greater importance to less-dependent orbits.The weighting uses a slow-increasing logarithm of each orbit's dependency count, scaled by the maximum count of 73.
- Weighted similarity: The per-orbit distance uses weighted absolute differences between log2-transformed orbit counts, reducing domination by coordinates differing by several orders of magnitude.Adding 1 prevents logarithms from diverging, while normalization scales the distance to [0, 1].
- Similarity and clustering: Clusters contain a node and all network nodes whose signature similarity exceeds a chosen threshold, experimentally set to 0.9–0.95.Thresholds below 0.9 produce especially large clusters, while higher thresholds produce only a few small clusters.
3 RESULTS AND DISCUSSION
The method was evaluated across six yeast and three human PPI networks, showing that topologically similar protein clusters share biological properties and can support function prediction.
- Evaluation setup: The analysis covered six yeast and three human PPI networks, evaluating clusters against organism-specific protein properties.Yeast properties were protein complexes, biological functions, and subcellular localizations; human properties were cellular components, tissue expressions, and biological processes.
- Evaluation measures: Hit-rate measures the largest common category as a percentage of cluster size, while miss-rate measures nodes lacking any common category with another cluster member.The strict and flexible schemes use different annotation specificities, with the flexible scheme using less specific categories.
- Yeast results: 86% of yeast clusters had localization hit-rates above 90% in vonMering-core, while 72% of clusters across all yeast networks had miss-rates below 10%.For biological functions, 81% of clusters across all six yeast networks had miss-rates below 10%.
- Human results: In human networks, 86% of clusters had cellular-component hit-rates above 50%, while tissue-expression hit-rates exceeded 50% for 74% of BIOGRID and HPRD clusters and 98% of Rual clusters.Biological-process hit-rates above 50% occurred in 55% of BIOGRID, 45% of HPRD, and 33% of Rual clusters.
- Robustness and prediction: Lower-confidence yeast interactions reduced hit-rates relative to the high-confidence network, but low miss-rates remained preserved across all three protein properties.The comparison indicates robustness to noise in the PPI data while retaining the reported cluster-level patterns.
- Robustness and prediction: The method predicted properties for 115 unclassified yeast proteins with degree greater than four, with overlapping predictions across networks and a successful PWP1 rRNA-processing prediction.The approach forms clusters around an unclassified protein and assigns the most common properties among classified cluster members.
- Yeast results: 44% of clusters in vonMering-core achieved a 100% protein-complex hit-rate under the flexible scheme.This network primarily used TAP and HMS-PCI interactions, which are known to favor protein complexes.
- Scope and computational considerations: Using larger graphlets is feasible but increases computational complexity beyond the current O(|V|^5) search over 2-5-node graphlets.The algorithm is described as embarrassingly parallel, and signature similarity is represented on a [0, 1] scale.
4 CONCLUSION
The paper presents a graph-theoretic method linking local network topology with biological function in real-world networks. Applied to proteome-scale PPI networks, it also predicts functions for uncharacterized proteins and offers guidance for future experiments.
- The method detects relationships between local topology and function in real-world networks.
- In yeast and human PPI networks, protein-neighborhood topology is linked to complexes, functions, compartments, tissue expressions, and biological processes.
- The method predicts biological functions for uncharacterized proteins and can provide guidelines for future experimental research.