Ultrafast and interpretable single-cell 3D genome analysis with Fast-Higashi

Abstract

Single-cell Hi-C (scHi-C) technologies can probe three-dimensional (3D) genome structures in single cells and their cell-to-cell variability. However, existing scHi-C analysis methods are hindered by the data quality and the complex 3D genome patterns. The lack of computational scalability and interpretability poses further challenges for large-scale scHi-C analysis. Here, we introduce Fast-Higashi, an ultrafast and interpretable method based on tensor decomposition that can jointly identify cell identities and chromatin meta-interactions. Fast-Higashi is able to simultaneously model multiple tensors with unmatched features of different sizes. A new partial random walk with restart (Partial RWR) algorithm in Fast-Higashi efficiently mitigates data sparseness. Extensive evaluations on real scHi-C datasets demonstrate the advantage of Fast-Higashi over existing methods for embedding, leading to improved delineation of rare cell types and better reconstruction of developmental trajectories. Fast-Higashi can directly infer chromatin meta-interactions, identify 3D genome features that define distinct cell types, and help elucidate cell type-specific connections between genome structure and function. Moreover, Fast-Higashi can be generalized to incorporate other single-cell omics data. Fast-Higashi provides a highly efficient and interpretable scHi-C analysis solution that is applicable to a broad range of biological contexts.