TL;DR
This paper introduces HiC-SGL, a novel method for imputing missing data in single-cell Hi-C (scHi-C) experiments and simultaneously learning cell embeddings for clustering. By leveraging subgraph extraction and a Transformer-based graph encoder, HiC-SGL effectively captures both local genomic structure and inter-cell variability, outperforming existing methods in imputation accuracy and cell type identification.
What Problem Does This Paper Address?
Single-cell Hi-C (scHi-C) technology allows us to study the 3D organization of the genome within individual cells, revealing crucial insights into cellular heterogeneity and function. However, scHi-C data is notoriously sparse, with a vast majority of potential interactions missing due to experimental limitations. This sparsity poses a significant challenge for downstream analyses like reconstructing 3D genome structures or clustering cells into distinct types. Existing imputation methods for scHi-C data have limitations, and there's a need for a more robust approach that can effectively handle this data sparsity while also extracting meaningful biological information for downstream tasks.
Methods
HiC-SGL employs an encoder-decoder architecture. The encoder has two key components:
- Cell Encoder: This part processes the entire cell's contact map, using Principal Component Analysis (PCA) for dimensionality reduction and a Multi-Layer Perceptron (MLP) to generate a global cell embedding. This embedding captures overall cell characteristics like type and state.
- Subgraph Encoder: This is the core innovation. For each potential interaction (edge) to be imputed, HiC-SGL extracts a "k-hop neighborhood subgraph" around that edge. This subgraph represents the local genomic context. Crucially, this subgraph is then fed into a Transformer-based graph neural network. This architecture, adapted from natural language processing, allows for a more expressive way to learn relationships within the subgraph compared to traditional Graph Neural Networks (GNNs). The Transformer's attention mechanism is modified to incorporate the subgraph's adjacency matrix, effectively learning how local structural information influences link prediction.
The decoder then uses both the global cell embedding and the local subgraph embedding to predict the probability of an interaction existing between two genomic loci. The model is trained using a binary cross-entropy loss function, treating existing interactions as positive samples and sampled non-interactions as negative samples.
Datasets
The authors evaluated HiC-SGL on three publicly available scHi-C datasets:
- Ramani et al. dataset [14]: Contains 621 cells from four human cell types (GM12878, HAP1, HeLa, K562) at 1-Mb resolution.
- 4DN sci-Hi-C dataset [41]: Includes 12,005 cells from five human cell types (GM12878, H1ESC, HAP1, HFFc6, IMR90) at 1-Mb resolution.
- Nagano et al. dataset [12]: Comprises 1175 cells representing different cell cycle stages (G1, mid-S, late-S, G2) at 250-kb resolution.
For evaluation, they simulated missing data by randomly removing 10% of existing edges and used sampled non-existing edges as negative samples.
Key Insights and Ideas
- Subgraph Attention for Local Context: The key idea is that imputing a missing interaction requires understanding its local genomic neighborhood. Extracting k-hop subgraphs and processing them with a Transformer-based GNN allows the model to learn rich, context-aware representations of these local structures.
- Global Cell Embeddings Complement Local Information: Simply looking at local structure isn't enough. The global cell embedding captures cell-specific characteristics (like cell cycle phase or cell type) that influence interaction patterns, providing a crucial complementary signal for imputation.
- Transformer Architecture for Graphs: Adapting the Transformer's attention mechanism to graph data, specifically within subgraphs, proves more powerful than traditional GNNs. This allows for a more flexible and expressive way to model relationships, even in sparse data.
- Imputation Aids Downstream Tasks: The paper demonstrates that improved imputation directly leads to better performance in crucial downstream tasks like cell clustering and the identification of higher-order genomic structures like A/B compartments and TAD boundaries.
Key Results
- Superior Imputation Accuracy: HiC-SGL consistently outperformed existing methods (scHiCluster, Higashi, scDEC-Hi-C) in imputation accuracy across all three datasets, as measured by AUC and AUPR metrics (Figure 2A, 2B).
- Robustness to Resolution and Dropout: The model maintained high imputation accuracy across different genomic resolutions and showed better performance than other methods as the dropout (missing data) ratio increased (Figure 2C, 2D).
- Effective Cell Clustering: The learned cell embeddings from HiC-SGL enabled accurate clustering of cells, with competitive or superior Adjusted Rand Index (ARI) and Average Circular ROC (ACROC) scores compared to baseline methods (Table 2, Figure 3).
- Improved Identification of Genomic Structures: Imputing scHi-C data with HiC-SGL helped reveal clearer A/B compartment patterns (Figure 4B) and more distinct single-cell TAD boundaries (Figure 4C, 4D).
Limitations and Future Work
- Resolution Limitations: The paper acknowledges that the inherent sparsity of scHi-C data still limits high-resolution imputation and analysis, suggesting a need for further work to overcome this.
- Model Component Optimization: The authors suggest that improvements could be made in areas like the extraction range of subgraphs, the acquisition of initial cell features, and the negative sampling strategy during training.
- Computational Complexity: While the subgraph approach mitigates the complexity of full graph Transformers, it's still a computationally intensive task, especially for very large datasets or higher k-hop values.
Future work could focus on developing more efficient subgraph extraction methods, exploring alternative graph representation learning techniques, and applying HiC-SGL to a wider range of biological questions that leverage 3D genome structure.
Summary updated