Graphlet-based hyperbolic embeddings capture evolutionary dynamics in genetic networks

Abstract

MotivationSpatial Analysis of Functional Enrichment (SAFE) is a popular tool for biologists to investigate the functional organisation of biological networks via highly intuitive 2D functional maps. To create these maps, SAFE uses Spring embedding to project a given network into a 2D space in which nodes connected in the network are near each other in space. However, many biological networks are scale-free, containing highly connected hub nodes. Because Spring embedding fails to separate hub nodes, it provides uninformative embeddings that resemble a "hairball". In addition, Spring embedding only captures direct node connectivity in the network and does not consider higher-order node wiring patterns, which are best captured by graphlets, small, connected, non-isomorphic, induced subgraphs. The scale-free structure of biological networks is hypothesised to stem from an underlying low-dimensional hyperbolic geometry, which novel hyperbolic embedding methods try to uncover. These include coalescent embedding, which projects a network onto a 2D disk. ResultsTo better capture the functional organisation of scale-free biological networks, whilst also going beyond simple direct connectivity patterns, we introduce Graphlet Coalescent (GraCoal) embedding, which embeds nodes nearby on a hyperbolic disk if they tend to touch a given graphlet together. We use GraCoal embedding to extend SAFE. Through SAFE-enabled enrichment analysis, we show that GraCoal embeddings captures the functional organisation of the genetic interaction networks of fruit fly, budding yeast, fission yeast and E. coli better than graphlet-based Spring embedding. We show that depending on the underlying graphlet, GraCoal embeddings capture different topology-function relationships. We show that triangle-based GraCoal embedding captures functional redundancy between paralogous genes. Availabilityhttps://gitlab.bsc.es/dtello/graphlet-based-SAFE Contactnatasha@bsc.as Supplementary informationSupplementary data are available at Bioinformatics online.