Optimized leaf ordering with class labels for hierarchical clustering.

Area of Science:

• Bioinformatics
• Computational Biology
• Data Visualization

Background:

• Hierarchical clustering is a standard technique for analyzing biomedical data with class labels, such as disease subtypes or Gene Ontology (GO) terms.
• Heatmaps and dendrograms are commonly used to visualize clustering results, often with an added color bar indicating class membership.
• The standard dendrogram representation may not always clearly reflect class groupings, even when clustering accurately separates classes.

Purpose of the Study:

• To develop a leaf ordering algorithm for dendrograms that preserves hierarchical clustering results.
• To improve the visualization of class labels within dendrograms by grouping instances of the same class together.
• To provide a more intuitive representation of class structure in biomedical data analysis.

Main Methods:

• A novel leaf ordering algorithm for dendrograms was developed.
• The algorithm is based on dynamic programming principles.
• It computes an optimal or near-optimal leaf order that is consistent with the dendrogram's tree structure.

Main Results:

• The proposed algorithm effectively groups instances of the same class together in the dendrogram.
• This improved ordering enhances the visual separation of class blocks in the heatmap's color bar.
• The algorithm preserves the integrity of the underlying hierarchical clustering structure.

Conclusions:

• The new leaf ordering algorithm offers a significant improvement for visualizing class-aware hierarchical clustering in biomedical data.
• This method aids in better interpretation of clustering results, particularly for identifying distinct biological groups or disease subtypes.
• The dynamic programming approach provides an efficient way to achieve optimal or near-optimal class-preserving leaf orders.