title: How frequently do clusters occur in hierarchical clustering analysis? A graph theoretical approach to studying ties in proximity.
abstract: BACKGROUND
  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.
  
  
  RESULTS
  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.
  
  
  CONCLUSIONS
  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.Graphical abstractFour cluster contrast functions identifying statistically sound clusters within dendrograms considering ties in proximity.
authors.affiliation: Fundación Instituto de Inmunología de Colombia (FIDIC), Bogotá, Colombia ; Laboratorio de Química Teórica, Universidad de Pamplona, Pamplona, Colombia.
authors.forename: Wilmer
authors.initials: W
authors.lastname: Leal
authors.affiliation: Fundación Instituto de Inmunología de Colombia (FIDIC), Bogotá, Colombia ; Laboratorio de Química Teórica, Universidad de Pamplona, Pamplona, Colombia ; Corporación SCIO, Bogotá, Colombia.
authors.forename: Eugenio J
authors.initials: EJ
authors.lastname: Llanos
authors.affiliation: Laboratorio de Química Teórica, Universidad de Pamplona, Pamplona, Colombia ; Bioinformatics Group, Department of Computer Science, Universität Leipzig, Leipzig, Germany.
authors.forename: Guillermo
authors.initials: G
authors.lastname: Restrepo
authors.affiliation: Fundación Instituto de Inmunología de Colombia (FIDIC), Bogotá, Colombia ; Universidad del Rosario, Bogotá, Colombia.
authors.forename: Carlos F
authors.initials: CF
authors.lastname: Suárez
authors.affiliation: Fundación Instituto de Inmunología de Colombia (FIDIC), Bogotá, Colombia ; Universidad Nacional de Colombia, Bogotá, Colombia.
authors.forename: Manuel Elkin
authors.initials: ME
authors.lastname: Patarroyo
keywords: Cluster frequency; Cluster stability; Dendrogram; Hierarchical cluster analysis (HCA); Molecular descriptor; Ties in proximity
references.citation: J Am Chem Soc. 2014 Apr 16;136(15):5670-82
references.pmid: 24694294
references.citation: J Chem Inf Model. 2006 May-Jun;46(3):1098-106
references.pmid: 16711730
references.citation: J Chem Inf Model. 2010 Jul 26;50(7):1189-204
references.pmid: 20572635
references.citation: Bioinformatics. 2005 Feb 1;21(3):364-78
references.pmid: 15374873
references.citation: J Chem Inf Model. 2013 Sep 23;53(9):2402-8
references.pmid: 23906322
references.citation: J Chem Inf Model. 2008 Oct;48(10):2054-65
references.pmid: 18816024
references.citation: J Chem Inf Model. 2006 Jan-Feb;46(1):221-30
references.pmid: 16426058
references.citation: J Chem Inf Model. 2007 May-Jun;47(3):761-70
references.pmid: 17465522
references.citation: Genome Res. 2004 Mar;14(3):380-90
references.pmid: 14993204
references.citation: J Chem Inf Comput Sci. 2001 Jan-Feb;41(1):134-46
references.pmid: 11206366
references.citation: J Cheminform. 2012 Mar 17;4(1):7
references.pmid: 22424447
references.citation: J Cheminform. 2015 Mar 25;7:11
references.pmid: 25866564
references.citation: J Cheminform. 2014 Sep 17;6(1):44
references.pmid: 25264459
references.citation: J Am Chem Soc. 2011 Oct 26;133(42):16786-9
references.pmid: 21967478
references.citation: J Cheminform. 2015 Jul 07;7:33
references.pmid: 26150895
references.citation: J Chem Inf Comput Sci. 2004 Jan-Feb;44(1):68-75
references.pmid: 14741012
references.citation: J Cheminform. 2012 Dec 17;4(1):37
references.pmid: 23244782