Identification of Topologically Associated Domains via Infomap Entropy Minimization

Accurately identifying topologically associated domains (TADs) from high-throughput chromosome conformation capture (Hi-C) contact maps is fundamental to decoding chromatin architecture and its regulatory functions. Despite numerous existing tools, achieving a balance between computational time and the mathematical optimality of TAD partitions remains a significant challenge. In this study, we formulate TAD identification as a graph partitioning problem guided by the principle of Infomap entropy minimization. We introduce InfoTAD, a novel algorithm that models the hierarchical organization of chromatin interactions through an Infomap entropy encoding tree. A primary theoretical contribution of this work is the rigorous proof that finding an optimal encoding tree with minimal Infomap entropy is Nondeterministic Polynomial-time hard (NP-hard). To circumvent this complexity, we propose an efficient approximation algorithm that integrates a discretization strategy with dynamic programming, specifically tailored to the linear constraints of Hi-C contact maps. Comparative benchmarks on simulated datasets show that InfoTAD consistently achieves higher accuracy and lower Infomap entropy than other methods. Furthermore, application to real Hi-C contact matrices from human cell lines (GM12878 and IMR90) reveals that the boundaries identified by InfoTAD are significantly enriched with structural proteins, underscoring its biological precision and potential for advancing genomic research.