MOSAIC: MOtif Set with mAximal InfluenCe on network.

Abstract

Biological networks, characterized by complex interactions among genes, proteins, and metabolites, are often modeled as graphs to study their organizational principles and dynamics. Network motifs-recurring, statistically significant subgraphs provide critical insights into the functional properties and structural organization of these networks. Existing research has explored various facets of motif detection, including enumeration, edge and node independence, dynamic updates, multi-layered networks, and stochastic settings. Although there have been studies in exploring the functionality of individual motif instances, a significant gap remains in understanding how collections of motif instances act as a group to influence the overall functionality of the network. In this paper, we aim to fill this gap. We model the influence of collections of motifs as a novel problem, which we call the Closest $k$-Motif Set Selection problem. We prove that this problem is NP-hard and develop MOSAIC (MOtif Set with mAximal InfluenCe), a novel greedy algorithm to address this problem. MOSAIC operates in two phases: an initialization phase for computing distances between motifs and nodes, and an update phase that incrementally selects motif instances to optimize their collective impact on the network. We prove that MOSAIC is efficient with a low degree polynomial time complexity. Our experimental results demonstrate that MOSAIC achieves optimal or near-optimal results, and scales to the entire human network efficiently. Our experiments on the human transcriptional regulatory network demonstrate that MOSAIC can identify Alzheimer's genes effectively, and select Alzheimer's genes that are missed by state-of-the-art node-based selection methods. This work advances our understanding of motif-based network analysis and opens new avenues for exploring the functional implications of network motifs.