Robust and efficient single-cell Hi-C clustering with approximate k-nearest neighbor graphs

Area of Science:

• Genomics
• Computational Biology
• Molecular Biology

Background:

• Hi-C technology reveals the 3D organization of chromatin.
• Single-cell Hi-C (scHi-C) provides insights into individual cell chromatin states.
• Clustering scHi-C data is computationally intensive due to high dimensionality and sparsity.

Purpose of the Study:

• To develop an efficient scHi-C clustering method.
• To reduce the computational resources required for analyzing large scHi-C datasets.
• To improve the accuracy of cell clustering based on chromatin folding properties.

Main Methods:

• Implemented an approximate nearest neighbors (ANN) approach.
• Utilized locality-sensitive hashing (LSH) for dimensionality reduction.
• Developed a scHi-C clustering algorithm within the scHiCExplorer software.

Main Results:

• The method efficiently processes large scHi-C datasets (e.g., 2600 cells at 10kb resolution) using manageable memory (40 GB).
• Achieved superior clustering quality compared to existing algorithms.
• Demonstrated computational feasibility where other methods failed even with 1 TB of memory.

Conclusions:

• The presented ANN-based clustering method offers a computationally efficient and effective solution for analyzing scHi-C data.
• This approach facilitates deeper understanding of chromatin organization at the single-cell level.
• The tool is readily available for the research community through GitHub and conda packages.