title: Optimized leaf ordering with class labels for hierarchical clustering.
abstract: Hierarchical clustering is extensively used in the bioinformatics community to analyze biomedical data. These data are often tagged with class labels, as e.g. disease subtypes or gene ontology (GO) terms. Heatmaps in connection with dendrograms are the common standard to visualize results of hierarchical clustering. The heatmap can be enriched by an additional color bar at the side, indicating for each instance in the data set to which class it belongs. In the ideal case, when the clustering matches perfectly with the classes, one would expect that instances from the same class cluster together and the color bar consists of well-separated color blocks without frequent alteration of colors (classes). But even in the case when instances from the same class cluster perfectly together, the dendrogram might not reflect this important aspect due to the fact that its representation is not unique. In this paper, we propose a leaf ordering algorithm for the dendrogram that preserving the hierarchical clustering result tries to group instances from the same class together. It is based on the concept of dynamic programming which can efficiently compute the optimal or nearly optimal order, consistent with the structure of the tree.
authors: Department of Bioinformatics, United Institute of Informatics Problems, Surganova Str. 6, Minsk 220012, Belarus.
authors: Natalia
authors: N
authors: Novoselova
authors: Biostatistics, Helmholtz Centre for Infection Research, Inhoffenstraße 7, 38124, Braunschweig, Germany.
authors: Junxi
authors: J
authors: Wang
authors: Biostatistics, Helmholtz Centre for Infection Research, Inhoffenstraße 7, 38124, Braunschweig, Germany.|Department of Computer Science, Ostfalia University of Applied Sciences, Salzdahlumer Straße 46/48, 38302, Wolfenbüttel, Germany.
authors: Frank
authors: F
authors: Klawonn
mesh_terms: D000465:Algorithms; D002453:Cell Cycle / Q000235:genetics; D016000:Cluster Analysis; D020869:Gene Expression Profiling / Q000379:methods; D020411:Oligonucleotide Array Sequence Analysis / Q000379:methods*; D011336:Probability; D012441:Saccharomyces cerevisiae / Q000166:cytology / Q000235:genetics; D013269:Stochastic Processes
keywords: Hierarchical clustering; biomedical data; dendrogram; dynamic programming; leaf ordering