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

Area of Science:

• Computational Biology
• Graph Theory
• Bioinformatics

Background:

• Entropy is crucial for information compression and analyzing complex graph structures.
• Existing metrics struggle to capture intricate details in biological graphs.
• Novel approaches are needed for effective biological graph analysis.

Purpose of the Study:

• To introduce a novel metric, the topology entropy encoding tree, for quantifying biological graph complexity.
• To demonstrate that minimizing topology entropy is equivalent to optimal graph partitioning.
• To develop and apply methods for analyzing ordered and unordered biological graphs.

Main Methods:

• Developed topology entropy encoding tree (TEC) for graph complexity quantification.
• Created TEC-O for ordered graphs and TEC-U for unordered graphs.
• Applied TEC-O to Hi-C contact maps for Topologically Associated Domain (TAD) identification.
• Applied TEC-U to single-cell sequencing data for cell clustering.

Main Results:

• Topology entropy is robust to noise and captures structural information effectively.
• TEC-O and TEC-U outperform existing methods in simulated datasets.
• Experiments show highest accuracy in TAD detection (TEC-O) and cell clustering (TEC-U).
• Results provide biologically meaningful insights into genomic organization and cell populations.

Conclusions:

• Topology entropy encoding trees offer a powerful framework for biological graph analysis.
• Minimizing topology entropy provides an effective strategy for graph partitioning.
• TEC-O and TEC-U are accurate and robust tools for analyzing Hi-C and single-cell data, respectively.