SCUDDO: an unsupervised clustering algorithm for single-cell Hi-C maps using diagonal diffusion operators

<h4>Motivation</h4>Advances in high-throughput chromatin conformation capture have provided insight into the three-dimensional structure and organization of chromatin. While bulk Hi-C experiments capture spatio-temporally averaged chromatin interactions across millions of cells, single-cell Hi-C experiments report on the chromatin interactions of individual cells. Supervised and unsupervised algorithms have been developed to embed single-cell Hi-C maps and identify different cell types. However, single-cell Hi-C maps are often difficult to cluster due to their high sparsity, with state-of-the-art algorithms achieving a maximum Adjusted Rand Index (ARI) of only ≲0.4 on several datasets.<h4>Results</h4>We introduce a novel unsupervised algorithm, Single-cell Clustering Using Diagonal Diffusion Operators (SCUDDO), to embed and cluster single-cell Hi-C maps. We evaluate SCUDDO on four previously difficult-to-cluster single-cell Hi-C datasets, and show that it can outperform other current algorithms in ARI by ≳0.2. Further, SCUDDO outperforms all other tested algorithms even when we restrict the number of intrachromosomal maps for each cell type and when we use only a small fraction of contacts in each Hi-C map. Thus, SCUDDO can capture the underlying latent features of single-cell Hi-C maps and provide accurate labelling of cell types even when cell types are not known a priori.<h4>Availability and implementation</h4>SCUDDO is freely available at https://www.github.com/lmaisuradze/scuddo as well as https://doi.org/10.6084/m9.figshare.31759915. The tested datasets are publicly available and can be downloaded from the Gene Expression Omnibus.