GEM: A manifold learning based framework for reconstructing spatial organizations of chromosomes

Guangxiang Zhu, Wenxuan Deng, Hailin Hu, Rui Ma, Sai Zhang, Jinglin Yang, Jian Peng, Tommy Kaplan, Jianyang ZengbioRxiv 2017 · DOI

TL;DR

This paper introduces GEM, a novel manifold learning framework that reconstructs the 3D organization of chromosomes from Hi-C data. Unlike previous methods, GEM doesn't assume a direct relationship between interaction frequencies and distances, instead learning this relationship while also incorporating biophysical energy constraints, leading to more accurate and physically plausible models. A key innovation is GEM's ability to recover missing long-range genomic interactions, a significant advancement for understanding genome structure and function.

What Problem Does This Paper Address?

Understanding how chromosomes are spatially organized within the nucleus is crucial for deciphering gene regulation, DNA replication, and overall genome integrity. Technologies like Hi-C have revolutionized our ability to measure interaction frequencies between different genomic regions, providing a wealth of data about these 3D structures. However, accurately reconstructing these complex 3D arrangements from Hi-C data is challenging due to experimental noise, data sparsity, and the dynamic nature of chromatin. Existing methods often rely on strong assumptions about the relationship between interaction frequencies and spatial distances, which can introduce biases and limit their accuracy. Furthermore, these methods typically produce a single static model, failing to capture the dynamic nature of chromatin.

Methods

GEM (Genomic organization reconstructor based on conformational Energy and Manifold learning) is a novel framework that addresses these challenges. It leverages manifold learning, a technique from machine learning for dimensionality reduction, to directly embed the "neighboring affinities" (derived from Hi-C interaction frequencies) from the high-dimensional Hi-C space into a low-dimensional 3D Euclidean space.

Key aspects of GEM's methodology include:

  • No Pre-assumed Relationship: Unlike many prior methods that assume a specific mathematical relationship (e.g., inverse proportion) between Hi-C interaction frequencies and spatial distances, GEM learns this relationship implicitly through its optimization process.
  • Conformational Energy Integration: GEM incorporates a biophysical energy model (including stretching, bending, and excluded volume terms) to ensure that the reconstructed 3D structures are physically plausible and stable. This is a significant departure from methods that solely rely on interaction frequency data.
  • Ensemble of Conformations: Recognizing that chromatin is dynamic, GEM models an ensemble of conformations rather than a single static structure. This is achieved through a multi-conformation optimization strategy.
  • Optimization Objective: GEM minimizes a cost function that balances the fitness to Hi-C data (measured by KL divergence) and the biophysical feasibility (measured by conformational energy).
  • Two-Stage Optimization: To address potential "sinking" issues in the optimization process, GEM employs a two-stage approach: first, an average structure is computed, which then serves as an initial structure for the multi-conformation optimization.

Datasets

GEM was validated on:

  • Simulated Hi-C data: Generated using a Brownian simulation method with varying parameters (trapping rate, maximum interaction probability, standard deviation of Gaussian function, number of cells) to test the robustness of GEM under different conditions.
  • Experimental Hi-C data:
    • Yeast Hi-C data (Duan et al., 2010).
  • Human Hi-C data from multiple sources, including datasets from different restriction enzymes (e.g., HindIII vs. NcoI) to assess mutual validation.
  • Fluorescence In Situ Hybridization (FISH) data: Sparse pairwise distance constraints from FISH studies were used to validate reconstructed structures.
  • Capture Hi-C data: Used to test GEM's ability to recover missing long-range genomic interactions, specifically promoter-promoter and promoter-enhancer contacts.

Key Insights and Ideas

  • Learning the Frequency-Distance Relationship: The most significant insight is that GEM can effectively learn the complex, non-explicit relationship between Hi-C interaction frequencies and spatial distances, bypassing the need for potentially inaccurate pre-assumptions. This allows for more accurate and less biased reconstructions.
  • Biophysical Plausibility Matters: Incorporating conformational energy significantly improves the quality of the reconstructed 3D structures, ensuring they are not just statistically consistent with Hi-C data but also physically realistic.
  • Dynamics are Key: Modeling chromatin as an ensemble of conformations, rather than a single structure, better reflects its dynamic nature and provides a more comprehensive view of genome organization.
  • Recovering Missing Information: GEM's ability to infer missing long-range genomic interactions is a groundbreaking application, opening new avenues for studying genome regulation and function where traditional Hi-C data might be incomplete.

Key Results

  • Superior Performance: GEM consistently outperformed state-of-the-art methods (MDS, ChromSDE, ShRec3D, BACH) in terms of Pearson correlation between reconstructed and original Hi-C data on simulated datasets.
  • Accurate Reconstruction: On experimental Hi-C data, GEM achieved high Pearson correlations (e.g., >0.93 for hold-out data, >0.8 for mutual validation between datasets), indicating accurate reconstruction of chromatin structures.
  • FISH Data Agreement: Reconstructed structures showed good agreement with sparse FISH distance constraints, further validating GEM's accuracy.
  • Physically Stable Structures: GEM-reconstructed structures exhibited lower conformational energy compared to other methods, suggesting greater biophysical stability.
  • Successful Recovery of Missing Interactions: GEM successfully identified and validated missing long-range genomic interactions (loops, promoter-promoter, and promoter-enhancer contacts) that were supported by other datasets and epigenetic features.

Limitations and Future Work

  • Parameter Selection: While GEM has only one primary parameter ($\lambda_E$), its selection can influence the trade-off between data fitness and structural feasibility. The paper discusses automatic methods (Bayesian score, TOPSIS) for parameter selection, but this remains an area for refinement.
  • Computational Efficiency: Multi-conformation optimization can be computationally intensive. The authors suggest using a smaller ensemble for large datasets or applications where structural diversity is less critical, and mention the potential for parallelization to accelerate the process.
  • Future Work: The authors highlight the potential of GEM for recovering missing long-range genomic interactions as a significant extended application. Further exploration of this capability and its biological implications is a clear future direction. Additionally, applying GEM to study structural diversity across different cell types, conditions, or species is a natural next step.

Summary updated

Abstract

Abstract Decoding the spatial organizations of chromosomes has crucial implications for studying eukaryotic gene regulation. Recently, Chromosomal conformation capture based technologies, such as Hi-C, have been widely used to uncover the interaction frequencies of genomic loci in high-throughput and genome-wide manner and provide new insights into the folding of three-dimensional (3D) genome structure. In this paper, we develop a novel manifold learning framework, called GEM ( G enomic organization reconstructor based on conformational E nergy and M anifold learning), to elucidate the underlying 3D spatial organizations of chromosomes from Hi-C data. Unlike previous chromatin structure reconstruction methods, which explicitly assume specific relationships between Hi-C interaction frequencies and spatial distances between distal genomic loci, GEM is able to reconstruct an ensemble of chromatin conformations by directly embedding the neigh-boring affinities from Hi-C space into 3D Euclidean space based on a manifold learning strategy that considers both the fitness of Hi-C data and the biophysical feasibility of the modeled structures, which are measured by the conformational energy derived from our current biophysical knowledge about the 3D polymer model. Extensive validation tests on both simulated interaction frequency data and experimental Hi-C data of yeast and human demonstrated that GEM not only greatly outperformed other state-of-art modeling methods but also reconstructed accurate chromatin structures that agreed well with the hold-out or independent Hi-C data and sparse geometric restraints derived from the previous fluorescence in situ hybridization (FISH) studies. In addition, as GEM can generate accurate spatial organizations of chromosomes by integrating both experimentally-derived spatial contacts and conformational energy, we for the first time extended our modeling method to recover long-range genomic interactions that are missing from the original Hi-C data. All these results indicated that GEM can provide a physically and physiologically valid 3D representations of the organizations of chromosomes and thus serve as an effective and useful genome structure reconstructor.
BibTeX
@misc{zhu2017gem,
  author = {Guangxiang Zhu and Wenxuan Deng and Hailin Hu and Rui Ma and Sai Zhang and Jinglin Yang and Jian Peng and Tommy Kaplan and Jianyang Zeng},
  title = {{GEM: A manifold learning based framework for reconstructing spatial organizations of chromosomes}},
  year = {2017},
  doi = {10.1101/161208},
  howpublished = {bioRxiv},
}
Figure