Uncovering Biological Network Function via Graphlet Degree Signatures

By Tijana Milenkoviæ, Natasa Przulj. Cancer Informatics, 2008

392 citations recorded by the source corpus.

Motivation 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 interact 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. Results 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 summarizes a protein's local topology in a PPI network into the vector of graphlet degrees called the signature of the protein and computes the signature similarities between all protein pairs. We group topologically similar proteins under this measure in a PPI network and show 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 such as disease protein prediction. Availability Data is available upon request.

Subfields: Cell Biology, Computational Theory and Mathematics, Molecular Biology

View Paper: https://www.semanticscholar.org/paper/86775225af9de81c2797de86856cdf356faeb500

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Cell Biology

In Computational Theory and Mathematics

In Molecular Biology

Citations in the corpus

Exploiting ontology graph for predicting sparsely annotated gene function (2015, methodology): “the neighborhood can be used to characterize each node and to establish pairwise affinity scores (Gligorijevic et al., 2014; Milenkovic et al., 2010; Milenkovic and Przulj, 2008).”
Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting (2020, methodology): “The closely related concept of graphlets [44], [80], [81], [82], different from motifs in being induced subgraphs, has been used to analyse the distribution of realworld networks and as a topological signature for network similarity.”
Using PPI network autocorrelation in hierarchical multi-label classification trees for gene function prediction (2013, background): “Milenkovic and Przulj [48] relate the PPI network structure to protein complexes.”
A combinatorial approach to graphlet counting (2014, methodology): “Milenković and Pržulj (2008) designed a method for comparing node neighbourhoods based on graphlets and demonstrated that clusters of nodes in protein–protein interaction (PPI) networks, obtained with their graphlet-based distance measure, share common protein properties.”
GNNGuard: Defending Graph Neural Networks against Adversarial Attacks (2020, methodology): “To measure the local topology of nodes, we use graphlet degree vectors [53] which reflect nodes’ structural properties, e.”