Cargando…

A methodology to assess the intrinsic discriminative ability of a distance function and its interplay with clustering algorithms for microarray data analysis

BACKGROUND: Clustering is one of the most well known activities in scientific investigation and the object of research in many disciplines, ranging from statistics to computer science. Following Handl et al., it can be summarized as a three step process: (1) choice of a distance function; (2) choice...

Descripción completa

Detalles Bibliográficos
Autores principales: Giancarlo, Raffaele, Lo Bosco, Giosué, Pinello, Luca, Utro, Filippo
Formato: Online Artículo Texto
Lenguaje:English
Publicado: BioMed Central 2013
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3548704/
https://www.ncbi.nlm.nih.gov/pubmed/23369037
http://dx.doi.org/10.1186/1471-2105-14-S1-S6
_version_ 1782256351123079168
author Giancarlo, Raffaele
Lo Bosco, Giosué
Pinello, Luca
Utro, Filippo
author_facet Giancarlo, Raffaele
Lo Bosco, Giosué
Pinello, Luca
Utro, Filippo
author_sort Giancarlo, Raffaele
collection PubMed
description BACKGROUND: Clustering is one of the most well known activities in scientific investigation and the object of research in many disciplines, ranging from statistics to computer science. Following Handl et al., it can be summarized as a three step process: (1) choice of a distance function; (2) choice of a clustering algorithm; (3) choice of a validation method. Although such a purist approach to clustering is hardly seen in many areas of science, genomic data require that level of attention, if inferences made from cluster analysis have to be of some relevance to biomedical research. RESULTS: A procedure is proposed for the assessment of the discriminative ability of a distance function. That is, the evaluation of the ability of a distance function to capture structure in a dataset. It is based on the introduction of a new external validation index, referred to as Balanced Misclassification Index (BMI, for short) and of a nontrivial modification of the well known Receiver Operating Curve (ROC, for short), which we refer to as Corrected ROC (CROC, for short). The main results are: (a) a quantitative and qualitative method to describe the intrinsic separation ability of a distance; (b) a quantitative method to assess the performance of a clustering algorithm in conjunction with the intrinsic separation ability of a distance function. The proposed procedure is more informative than the ones available in the literature due to the adopted tools. Indeed, the first one allows to map distances and clustering solutions as graphical objects on a plane, and gives information about the bias of the clustering algorithm with respect to a distance. The second tool is a new external validity index which shows similar performances with respect to the state of the art, but with more flexibility, allowing for a broader spectrum of applications. In fact, it allows not only to quantify the merit of each clustering solution but also to quantify the agglomerative or divisive errors due to the algorithm. CONCLUSIONS: The new methodology has been used to experimentally study three popular distance functions, namely, Euclidean distance d(2), Pearson correlation d(r )and mutual information d(MI). Based on the results of the experiments, we have that the Euclidean and Pearson correlation distances have a good intrinsic discrimination ability. Conversely, the mutual information distance does not seem to offer the same flexibility and versatility as the other two distances. Apparently, that is due to well known problems in its estimation. since it requires that a dataset must have a substantial number of features to be reliable. Nevertheless, taking into account such a fact, together with results presented in Priness et al., one receives an indication that d(MI )may be superior to the other distances considered in this study only in conjunction with clustering algorithms specifically designed for its use. In addition, it results that K-means, Average Link, and Complete link clustering algorithms are in most cases able to improve the discriminative ability of the distances considered in this study with respect to clustering. The methodology has a range of applicability that goes well beyond microarray data since it is independent of the nature of the input data. The only requirement is that the input data must have the same format of a "feature matrix". In particular it can be used to cluster ChIP-seq data.
format Online
Article
Text
id pubmed-3548704
institution National Center for Biotechnology Information
language English
publishDate 2013
publisher BioMed Central
record_format MEDLINE/PubMed
spelling pubmed-35487042013-02-04 A methodology to assess the intrinsic discriminative ability of a distance function and its interplay with clustering algorithms for microarray data analysis Giancarlo, Raffaele Lo Bosco, Giosué Pinello, Luca Utro, Filippo BMC Bioinformatics Research BACKGROUND: Clustering is one of the most well known activities in scientific investigation and the object of research in many disciplines, ranging from statistics to computer science. Following Handl et al., it can be summarized as a three step process: (1) choice of a distance function; (2) choice of a clustering algorithm; (3) choice of a validation method. Although such a purist approach to clustering is hardly seen in many areas of science, genomic data require that level of attention, if inferences made from cluster analysis have to be of some relevance to biomedical research. RESULTS: A procedure is proposed for the assessment of the discriminative ability of a distance function. That is, the evaluation of the ability of a distance function to capture structure in a dataset. It is based on the introduction of a new external validation index, referred to as Balanced Misclassification Index (BMI, for short) and of a nontrivial modification of the well known Receiver Operating Curve (ROC, for short), which we refer to as Corrected ROC (CROC, for short). The main results are: (a) a quantitative and qualitative method to describe the intrinsic separation ability of a distance; (b) a quantitative method to assess the performance of a clustering algorithm in conjunction with the intrinsic separation ability of a distance function. The proposed procedure is more informative than the ones available in the literature due to the adopted tools. Indeed, the first one allows to map distances and clustering solutions as graphical objects on a plane, and gives information about the bias of the clustering algorithm with respect to a distance. The second tool is a new external validity index which shows similar performances with respect to the state of the art, but with more flexibility, allowing for a broader spectrum of applications. In fact, it allows not only to quantify the merit of each clustering solution but also to quantify the agglomerative or divisive errors due to the algorithm. CONCLUSIONS: The new methodology has been used to experimentally study three popular distance functions, namely, Euclidean distance d(2), Pearson correlation d(r )and mutual information d(MI). Based on the results of the experiments, we have that the Euclidean and Pearson correlation distances have a good intrinsic discrimination ability. Conversely, the mutual information distance does not seem to offer the same flexibility and versatility as the other two distances. Apparently, that is due to well known problems in its estimation. since it requires that a dataset must have a substantial number of features to be reliable. Nevertheless, taking into account such a fact, together with results presented in Priness et al., one receives an indication that d(MI )may be superior to the other distances considered in this study only in conjunction with clustering algorithms specifically designed for its use. In addition, it results that K-means, Average Link, and Complete link clustering algorithms are in most cases able to improve the discriminative ability of the distances considered in this study with respect to clustering. The methodology has a range of applicability that goes well beyond microarray data since it is independent of the nature of the input data. The only requirement is that the input data must have the same format of a "feature matrix". In particular it can be used to cluster ChIP-seq data. BioMed Central 2013-01-14 /pmc/articles/PMC3548704/ /pubmed/23369037 http://dx.doi.org/10.1186/1471-2105-14-S1-S6 Text en Copyright ©2013 Giancarlo et al.; licensee BioMed Central Ltd. http://creativecommons.org/licenses/by/2.0 This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
spellingShingle Research
Giancarlo, Raffaele
Lo Bosco, Giosué
Pinello, Luca
Utro, Filippo
A methodology to assess the intrinsic discriminative ability of a distance function and its interplay with clustering algorithms for microarray data analysis
title A methodology to assess the intrinsic discriminative ability of a distance function and its interplay with clustering algorithms for microarray data analysis
title_full A methodology to assess the intrinsic discriminative ability of a distance function and its interplay with clustering algorithms for microarray data analysis
title_fullStr A methodology to assess the intrinsic discriminative ability of a distance function and its interplay with clustering algorithms for microarray data analysis
title_full_unstemmed A methodology to assess the intrinsic discriminative ability of a distance function and its interplay with clustering algorithms for microarray data analysis
title_short A methodology to assess the intrinsic discriminative ability of a distance function and its interplay with clustering algorithms for microarray data analysis
title_sort methodology to assess the intrinsic discriminative ability of a distance function and its interplay with clustering algorithms for microarray data analysis
topic Research
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3548704/
https://www.ncbi.nlm.nih.gov/pubmed/23369037
http://dx.doi.org/10.1186/1471-2105-14-S1-S6
work_keys_str_mv AT giancarloraffaele amethodologytoassesstheintrinsicdiscriminativeabilityofadistancefunctionanditsinterplaywithclusteringalgorithmsformicroarraydataanalysis
AT loboscogiosue amethodologytoassesstheintrinsicdiscriminativeabilityofadistancefunctionanditsinterplaywithclusteringalgorithmsformicroarraydataanalysis
AT pinelloluca amethodologytoassesstheintrinsicdiscriminativeabilityofadistancefunctionanditsinterplaywithclusteringalgorithmsformicroarraydataanalysis
AT utrofilippo amethodologytoassesstheintrinsicdiscriminativeabilityofadistancefunctionanditsinterplaywithclusteringalgorithmsformicroarraydataanalysis
AT giancarloraffaele methodologytoassesstheintrinsicdiscriminativeabilityofadistancefunctionanditsinterplaywithclusteringalgorithmsformicroarraydataanalysis
AT loboscogiosue methodologytoassesstheintrinsicdiscriminativeabilityofadistancefunctionanditsinterplaywithclusteringalgorithmsformicroarraydataanalysis
AT pinelloluca methodologytoassesstheintrinsicdiscriminativeabilityofadistancefunctionanditsinterplaywithclusteringalgorithmsformicroarraydataanalysis
AT utrofilippo methodologytoassesstheintrinsicdiscriminativeabilityofadistancefunctionanditsinterplaywithclusteringalgorithmsformicroarraydataanalysis