Detecting community structures in Hi-C genomic data

Community detection (CD) algorithms are applied to Hi-C data to discover new communities of loci in the 3D conformation of human and mouse DNA. We find that CD has some distinct advantages over pre-existing methods: (1) it is capable of finding a variable number of communities, (2) it can detect communities of DNA loci either adjacent or distant in the 1D sequence, and (3) it allows us to obtain a principled value of k, the number of communities present. Forcing k = 2, our method recovers earlier findings of Lieberman-Aiden, et al. (2009), but letting k be a parameter, our method obtains as optimal value k* = 6, discovering new candidate communities. In addition to discovering large communities that partition entire chromosomes, we also show that CD can detect small-scale topologically associating domains (TADs) such as those found in Dixon, et al. (2012). CD thus provides a natural and flexible statistical framework for understanding the folding structure of DNA at multiple scales in Hi-C data.

• Publication year

  2015

• Venue

  Annual Conference on Information Sciences and Systems

• Publication date

  2015-09-17

• Fields of study

  Biology, Mathematics, Computer Science

• Identifiers
  DOI 10.1109/CISS.2016.7460568arXiv 1509.05121
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Image processing

  2020cited by this paper
• Functional organization of the human 4D Nucleome

  2015cited by this paper
• Disruptions of topological chromatin domains cause pathogenic rewiring of gene-enhancer interactions.

  2015cited by this paper
• Edge Label Inference in Generalized Stochastic Block Models: from Spectral Theory to Impossibility Results

  2014cited by this paper
• Decoding Binary Node Labels from Censored Edge Measurements: Phase Transition and Efficient Recovery

  2014cited by this paper
• A 3D map of the human genome at kilobase resolution reveals principles of chromatin looping.

  2014cited by this paper
• Identification of alternative topological domains in chromatin

  2014cited by this paper
• Efficient discovery of overlapping communities in massive networks

  2013cited by this paper
• Topological Domains in Mammalian Genomes Identified by Analysis of Chromatin Interactions

  2012cited by this paper
• Community Detection in the Labelled Stochastic Block Model

  2012cited by this paper
• Communities, modules and large-scale structure in networks

  2011cited by this paper
• Stochastic blockmodels and community structure in networks

  2010cited by this paper
• Long-range enhancers on 8q24 regulate c-Myc

  2010cited by this paper
• Community detection algorithms: a comparative analysis: invited presentation, extended abstract

  2009cited by this paper
• Chromatin loops in gene regulation.

  2009cited by this paper
• A Survey of Statistical Network Models

  2009cited by this paper
• Disease-specific gene repositioning in breast cancer

  2009cited by this paper
• Community detection in graphs

  2009cited by this paper
• Comprehensive Mapping of Long-Range Interactions Reveals Folding Principles of the Human Genome

  2009cited by this paper
• Gene Regulation in the Third Dimension

  2008cited by this paper
• Inference of population structure using multilocus genotype data: dominant markers and null alleles

  2007cited by this paper
• Detecting functional modules in the yeast protein-protein interaction network

  2006cited by this paper
• Lamin A-Dependent Nuclear Defects in Human Aging

  2006cited by this paper
• Cluster analysis for gene expression data: a survey

  2004cited by this paper
• A long-range Shh enhancer regulates expression in the developing limb and fin and is associated with preaxial polydactyly.

  2003cited by this paper
• Amazon.com Recommendations: Item-to-Item Collaborative Filtering

  2003cited by this paper
• Scanning Human Gene Deserts for Long-Range Enhancers

  2003cited by this paper
• Controlling the double helix

  2003cited by this paper
• Random graph models of social networks

  2002cited by this paper
• Gene expression patterns of breast carcinomas distinguish tumor subclasses with clinical implications

  2001cited by this paper
• I and i

  2001cited by this paper
• Community structure in social and biological networks

  2001cited by this paper
• Inference of population structure using multilocus genotype data.

  2000cited by this paper
• Detecting protein function and protein-protein interactions from genome sequences.

  1999cited by this paper
• Normalized cuts and image segmentation

  1997cited by this paper
• Image Processing, Analysis and Machine Vision

  1993cited by this paper
• Stochastic blockmodels: First steps

  1983cited by this paper
• Image processing

  1971cited by this paper

• Provable Filter for Real-world Graph Clustering

  2024cites this paper
• bioSBM: A Random Graph Model to Integrate Epigenomic Data in Chromatin Structure Prediction

  2024cites this paper
• Unsupervised Optimisation of GNNs for Node Clustering

  2024cites this paper
• Projected Tensor Power Method for Hypergraph Community Recovery

  2023cites this paper
• Uncertainty in GNN Learning Evaluations: A Comparison between Measures for Quantifying Randomness in GNN Community Detection

  2023cites this paper
• Uncertainty in GNN Learning Evaluations: The Importance of a Consistent Benchmark for Community Detection

  2023cites this paper
• Mutual information for the sparse stochastic block model

  2022cites this paper
• Goodness of fit for log-linear ERGMs

  2021cites this paper
• A network Lasso model for regression

  2021cites this paper
• Network Modeling in Biology: Statistical Methods for Gene and Brain Networks.

  2021influential citation
• Graph Clustering with Graph Neural Networks

  2020cites this paper
• Presenting a Meta-Heuristic Algorithm to Detect Regulatory Elements in the Genome of Breast Cancer Patients

  2020cites this paper
• Proposing a novel community detection approach to identify cointeracting genomic regions.

  2020cites this paper
• A Two-Stage Particle Competition Model for Unbalanced Community Detection in Complex Networks

  2020cites this paper
• Particle Competition for Unbalanced Community Detection in Complex Networks

  2020cites this paper
• Transient crosslinking kinetics optimize gene cluster interactions

  2019cites this paper
• Gene Regulatory Elements Extraction in Breast Cancer by Hi-C Data Using a Meta-Heuristic Method

  2019cites this paper
• Stochastic block models: A comparison of variants and inference methods

  2019cites this paper
• Unsupervised Community Detection with Modularity-Based Attention Model

  2019cites this paper
• NETWORK MODELLING OF TOPOLOGICAL DOMAINS USING HIC DATA By

  2018cites this paper
• Information-theoretic Limits for Community Detection in Network Models

  2018cites this paper
• Network enhancement as a general method to denoise weighted biological networks

  2018cites this paper
• Stochastic Block Model for Hypergraphs: Statistical limits and a semidefinite programming approach

  2018cites this paper
• Network analyses of 4D genome datasets automate detection of community-scale gene structure and plasticity

  2018cites this paper
• Mapping the spectrum of 3D communities in human chromosome conformation capture data

  2018cites this paper
• Detection and Extraction of Potential Promoter/Enhancer Interactions in Genome of Cancer Patients using an Evolutionary Multi-Objective Algorithm

  2018cites this paper
• Proof of the Achievability Conjectures for the General Stochastic Block Model

  2018cites this paper
• Criminal Network Community Detection Using Graphical Analytic Methods: A Survey

  2018cites this paper
• Local-Access Generators for Basic Random Graph Models by Amartya

  2018cites this paper
• Local Access to Huge Random Objects Through Partial Sampling

  2017cites this paper
• Testing-Based Community Detection Methods for Complex Networks

  2017cites this paper
• Information Theoretic Study of Gaussian Graphical Models and Their Applications

  2017cites this paper
• Community detection in hypergraphs, spiked tensor models, and Sum-of-Squares

  2017cites this paper
• Multi-scale structural community organisation of the human genome

  2017cites this paper
• Local-Access Generators for Basic Random Graph Models

  2017cites this paper
• Community detection and stochastic block models: recent developments

  2017influential citation
• NETWORK MODELLING OF TOPOLOGICAL DOMAINS USING HI-C DATA.

  2017cites this paper
• Case studies in network community detection

  2017cites this paper
• Significance-based community detection in weighted networks

  2016cites this paper
• The Continuous Configuration Model: A Null for Community Detection on Weighted Networks

  2016cites this paper
• Community detection and the stochastic block model

  2016cites this paper
• Detection in the stochastic block model with multiple clusters: proof of the achievability conjectures, acyclic BP, and the information-computation gap

  2015cites this paper