Non-backtracking walks reveal compartments in sparse chromatin interaction networks

Abstract

Chromatin communities stabilized by protein machinery play essential role in gene regulation and refine global polymeric folding of the chromatin fiber. However, treatment of these communities in the framework of the classical network theory (stochastic block model, SBM) does not take into account intrinsic linear connectivity of the chromatin loci. Here we propose the "polymer" block model, paving the way for community detection in polymer networks. On the basis of this new model we modify the non-backtracking flow operator and suggest the first protocol for annotation of compartmental domains in sparse single cell Hi-C matrices. In particular, we prove that our approach corresponds to the maximum entropy principle. The benchmark analyses demonstrates that the spectrum of the polymer non-backtracking operator resolves the true compartmental structure up to the theoretical detectability threshold, while all commonly used operators fail above it. We test various operators on real data and conclude that the sizes of the non-backtracking single cell domains are most close to the sizes of compartments from the population data. Moreover, the found domains clearly segregate in the gene density and correlate with the population compartmental mask, corroborating biological significance of our annotation of the chromatin compartmental domains in single cells Hi-C matrices.

References in corpus (18)

• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Modularity and community structure in networks
• Community detection in graphs
• Cooperative Game Theory Approaches for Network Partitioning
• Hierarchical organization of modularity in metabolic networks
• Hierarchical Organization in Complex Networks
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Spectral redemption: clustering sparse networks
• Spectral methods for network community detection and graph partitioning
• Community detection in networks: Modularity optimization and maximum likelihood are equivalent
• Spectra and eigenvectors of scale-free networks
• Spectra of random graphs with arbitrary expected degrees
• Spectral methods for the detection of network community structure: a comparative analysis
• Detectability of communities in heterogeneous networks
• Eigenvalue tunnelling and decay of quenched random networks
• Eigenvalue Repulsion and Eigenfunction Localization in Sparse Non-Hermitian Random Matrices
• Random matrix analysis for gene interaction networks in cancer cells