An optimization framework for hierarchical clustering

Area of Science:

• Computational Biology
• Bioinformatics
• Data Science

Background:

• Hierarchical clustering is a key problem in computational biology, with traditional methods like average linkage lacking a clear objective and often producing suboptimal results.
• Existing greedy heuristics, while common, are myopic and fail to capture global data structures effectively.
• A recent combinatorial optimization criterion for hierarchical clustering is NP-hard to minimize, necessitating improved algorithmic approaches.

Purpose of the Study:

• To introduce a novel hierarchical clustering method, DOMUS, that addresses the limitations of traditional greedy approaches.
• To develop a method that combines local and global data considerations for more accurate hierarchical structures.
• To provide a robust and effective tool for various clustering applications, including single-cell RNA sequencing.

Main Methods:

• DOMUS employs an average-linkage-based approach that integrates multiple data views.
• The method learns to blend these views into a unified similarity measure.
• It combines local and global considerations for improved hierarchical structure generation.

Main Results:

• DOMUS consistently outperforms strong baselines, including beam search heuristics, on synthetic and benchmark datasets.
• The method demonstrates superior performance on single-cell RNA sequencing data compared to the state-of-the-art HiDeF algorithm.
• Rigorous benchmarking validates the real-world applicability and effectiveness of DOMUS.

Conclusions:

• DOMUS offers a significant advancement in hierarchical clustering by effectively integrating multiple data perspectives.
• The method provides a more structurally sound and accurate alternative to traditional greedy algorithms.
• DOMUS is a valuable tool for computational biology and bioinformatics, particularly for analyzing complex datasets like single-cell RNA sequencing data.