How frequently do clusters occur in hierarchical clustering analysis? A graph theoretical approach to studying ties in proximity
Open Access
- 25 January 2016
- journal article
- research article
- Published by Springer Nature in Journal of Cheminformatics
- Vol. 8 (1) , 1-16
Abstract
Hierarchical cluster analysis (HCA) is a widely used classificatory technique in many areas of scientific knowledge. Applications usually yield a dendrogram from an HCA run over a given data set, using a grouping algorithm and a similarity measure. However, even when such parameters are fixed, ties in proximity (i.e. two equidistant clusters from a third one) may produce several different dendrograms, having different possible clustering patterns (different classifications). This situation is usually disregarded and conclusions are based on a single result, leading to questions concerning the permanence of clusters in all the resulting dendrograms; this happens, for example, when using HCA for grouping molecular descriptors to select that less similar ones in QSAR studies. Representing dendrograms in graph theoretical terms allowed us to introduce four measures of cluster frequency in a canonical way, and use them to calculate cluster frequencies over the set of all possible dendrograms, taking all ties in proximity into account. A toy example of well separated clusters was used, as well as a set of 1666 molecular descriptors calculated for a group of molecules having hepatotoxic activity to show how our functions may be used for studying the effect of ties in HCA analysis. Such functions were not restricted to the tie case; the possibility of using them to derive cluster stability measurements on arbitrary sets of dendrograms having the same leaves is discussed, e.g. dendrograms from variations of HCA parameters. It was found that ties occurred frequently, some yielding tens of thousands of dendrograms, even for small data sets. Our approach was able to detect trends in clustering patterns by offering a simple way of measuring their frequency, which is often very low. This would imply, that inferences and models based on descriptor classifications (e.g. QSAR) are likely to be biased, thereby requiring an assessment of their reliability. Moreover, any classification of molecular descriptors is likely to be far from unique. Our results highlight the need for evaluating the effect of ties on clustering patterns before classification results can be used accurately.Keywords
This publication has 31 references indexed in Scilit:
- Voting-based consensus clustering for combining multiple clusterings of chemical structuresJournal of Cheminformatics, 2012
- CheS-Mapper - Chemical Space Mapping and Visualization in 3DJournal of Cheminformatics, 2012
- Making SharePoint® Chemically Aware™Journal of Cheminformatics, 2012
- Preoxidation for Colorimetric Sensor Array Detection of VOCsJournal of the American Chemical Society, 2011
- Trust, But Verify: On the Importance of Chemical Structure Curation in Cheminformatics and QSAR Modeling ResearchJournal of Chemical Information and Modeling, 2010
- Using Molecular Docking, 3D-QSAR, and Cluster Analysis for Screening Structurally Diverse Data Sets of Pharmacological InterestJournal of Chemical Information and Modeling, 2008
- VISCANA: Visualized Cluster Analysis of Protein−Ligand Interaction Based on the ab Initio Fragment Molecular Orbital Method for Virtual Ligand ScreeningJournal of Chemical Information and Modeling, 2005
- Iterative Cluster Analysis of Protein Interaction DataBioinformatics, 2004
- Topological Study of the Periodic SystemJournal of Chemical Information and Computer Sciences, 2004
- Predicting properties of molecules using graph invariantsJournal of Mathematical Chemistry, 1991