Compression-based inference of network motif sets
Open Access
- 10 October 2024
- journal article
- research article
- Published by Public Library of Science (PLoS) in PLOS Computational Biology
- Vol. 20 (10) , e1012460
Abstract
Physical and functional constraints on biological networks lead to complex topological patterns across multiple scales in their organization. A particular type of higher-order network feature that has received considerable interest is network motifs, defined as statistically regular subgraphs. These may implement fundamental logical and computational circuits and are referred to as “building blocks of complex networks”. Their well-defined structures and small sizes also enable the testing of their functions in synthetic and natural biological experiments. Here, we develop a framework for motif mining based on lossless network compression using subgraph contractions. This provides an alternative definition of motif significance which allows us to compare different motifs and select the collectively most significant set of motifs as well as other prominent network features in terms of their combined compression of the network. Our approach inherently accounts for multiple testing and correlations between subgraphs and does not rely on a priori specification of an appropriate null model. It thus overcomes common problems in hypothesis testing-based motif analysis and guarantees robust statistical inference. We validate our methodology on numerical data and then apply it on synaptic-resolution biological neural networks, as a medium for comparative connectomics, by evaluating their respective compressibility and characterize their inferred circuit motifs.Keywords
All Related Versions
Funding Information
- Agence Nationale de la Recherche (20CE45-0021)
- Agence Nationale de la Recherche (19-P3IA-0001)
This publication has 107 references indexed in Scilit:
- Testing biological network motif significance with exponential random graph modelsApplied Network Science, 2021
- Networks beyond pairwise interactions: Structure and dynamicsPhysics Reports, 2020
- Large-scale network motif analysis using compressionData Mining and Knowledge Discovery, 2020
- Neural Substrates of Drosophila Larval AnemotaxisCurrent Biology, 2019
- Competitive Disinhibition Mediates Behavioral Choice and Sequences in DrosophilaCell, 2016
- Rand-FaSE: fast approximate subgraph censusSocial Network Analysis and Mining, 2015
- Canonical Microcircuits for Predictive CodingNeuron, 2012
- Detecting Hierarchical Modularity in Biological Networks2009
- A Faster Algorithm for Detecting Network Motifs2005
- A Method for Detecting Structure in Sociometric Data1977