Uncovering the functional organization of molecular interaction networks using network embeddings based on graphlet topology

Abstract

[eng] For this purpose, Spatial Analysis of Functional Enrichment (SAFE) framework was proposed to uncover functional regions in a network by embedding it in 2-dimensions (2D) using the Spring embedding algorithm. However, biological networks often have a heterogeneous degree distribution, i.e., nodes in the network have varying numbers of neighbours. In this case, the Spring embedding sometimes provides uninformative, densely packed embeddings best described as a ‘hairball’. On the other hand, hyperbolic embeddings, such as the Coalescent embedding, maps a network onto a disk, so that nodes of high topological importance (i.e., of high node degree) are placed closer to the center of such disk. Additionally, these embedding methods only capture node connectivity information (i.e., which nodes are connected) but does not consider network structure (i.e., wiring or topology), which captures complementary information. The state-of-the-art methods to capture network structure are based on graphlets, which are small, connected, non-isomorphic, induced sub-graphs (e.g., triangles, paths). To better capture the functional organization of networks with heterogeneous degree distributions, taking into account different types of graphlet-based wiring patterns, in this work we introduce the graphlet-based Spring (GraSpring) and the graphlet-based Coalescent (GraCoal) embeddings. Furthermore, we extend the popular SAFE framework to take as input these two newly proposed embedding methods and we use SAFE to evaluate their performance on three types of molecular interaction networks (genetic interaction, protein-protein interaction and co-expression) of various model organisms. We show that the performance in terms of functional information uncovered by each of the embedding algorithms varies depending on the type of network considered and also the model organism considered. For instance, we show that GraCoals better capture the functional and spatial organization of the genetic interaction networks of four species (fruit fly, budding yeast, fission yeast and E. coli ). Moreover, we discover that GraCoals capture different topology-function relationships depending on the species. We show that triangle-based GraCoals capture functional redundancy in GI networks of species whose genome is characterised by high counts of duplicated genes.