Topology entropy: Enhancing graph partitioning for TAD identification and single-cell clustering

Entropy quantifies the limits of information compression and provides a theoretical foundation for exploring complex structures in large-scale graphs. However, effective metrics are needed to capture the intricate structural details in biological graphs. In this paper, we introduce the topology entropy encoding tree to quantify the complexity of biological graphs and show that minimizing the associated entropy is equivalent to optimal graph partitioning. We develop two methods, TEC-O and TEC-U, for partitioning ordered and unordered biological graphs. TEC-O is applied to identify Topologically Associated Domains (TADs) in Hi-C contact maps, while TEC-U is used for cell clustering in single-cell sequencing data. Results from simulated datasets demonstrate that topology entropy is robust to noise and effectively captures structural information, outperforming existing methods. Experiments on Hi-C data from five cell lines and ten single-cell sequencing datasets show that TEC-O and TEC-U achieve the highest accuracy in TAD detection and cell clustering, respectively, providing biologically meaningful insights.