A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Clustering Validation in Measurements <s> Motivation: The discovery of novel biological knowledge from the ab initio analysis of post-genomic data relies upon the use of unsupervised processing methods, in particular clustering techniques. Much recent research in bioinformatics has therefore been focused on the transfer of clustering methods introduced in other scientific fields and on the development of novel algorithms specifically designed to tackle the challenges posed by post-genomic data. The partitions returned by a clustering algorithm are commonly validated using visual inspection and concordance with prior biological knowledge---whether the clusters actually correspond to the real structure in the data is somewhat less frequently considered. Suitable computational cluster validation techniques are available in the general data-mining literature, but have been given only a fraction of the same attention in bioinformatics. ::: ::: Results: This review paper aims to familiarize the reader with the battery of techniques available for the validation of clustering results, with a particular focus on their application to post-genomic data analysis. Synthetic and real biological datasets are used to demonstrate the benefits, and also some of the perils, of analytical clustervalidation. ::: ::: Availability: The software used in the experiments is available at http://dbkweb.ch.umist.ac.uk/handl/clustervalidation/ ::: ::: Contact: J.Handl@postgrad.manchester.ac.uk ::: ::: Supplementary information: Enlarged colour plots are provided in the Supplementary Material, which is available at http://dbkweb.ch.umist.ac.uk/handl/clustervalidation/ <s> BIB001 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Clustering Validation in Measurements <s> Organizing data into sensible groupings is one of the most fundamental modes of understanding and learning. As an example, a common scheme of scientific classification puts organisms into a system of ranked taxa: domain, kingdom, phylum, class, etc. Cluster analysis is the formal study of methods and algorithms for grouping, or clustering, objects according to measured or perceived intrinsic characteristics or similarity. Cluster analysis does not use category labels that tag objects with prior identifiers, i.e., class labels. The absence of category information distinguishes data clustering (unsupervised learning) from classification or discriminant analysis (supervised learning). The aim of clustering is to find structure in data and is therefore exploratory in nature. Clustering has a long and rich history in a variety of scientific fields. One of the most popular and simple clustering algorithms, K-means, was first published in 1955. In spite of the fact that K-means was proposed over 50 years ago and thousands of clustering algorithms have been published since then, K-means is still widely used. This speaks to the difficulty in designing a general purpose clustering algorithm and the ill-posed problem of clustering. We provide a brief overview of clustering, summarize well known clustering methods, discuss the major challenges and key issues in designing clustering algorithms, and point out some of the emerging and useful research directions, including semi-supervised clustering, ensemble clustering, simultaneous feature selection during data clustering, and large scale data clustering. <s> BIB002 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Clustering Validation in Measurements <s> Clustering validation has long been recognized as one of the vital issues essential to the success of clustering applications. In general, clustering validation can be categorized into two classes, external clustering validation and internal clustering validation. In this paper, we focus on internal clustering validation and present a detailed study of 11 widely used internal clustering validation measures for crisp clustering. From five conventional aspects of clustering, we investigate their validation properties. Experiment results show that S\_Dbw is the only internal validation measure which performs well in all five aspects, while other measures have certain limitations in different application scenarios. <s> BIB003 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Clustering Validation in Measurements <s> Clustering validation has long been recognized as one of the vital issues essential to the success of clustering applications. In general, clustering validation can be categorized into two classes, external clustering validation and internal clustering validation. In this paper, we focus on internal clustering validation and present a study of 11 widely used internal clustering validation measures for crisp clustering. The results of this study indicate that these existing measures have certain limitations in different application scenarios. As an alternative choice, we propose a new internal clustering validation measure, named clustering validation index based on nearest neighbors (CVNN), which is based on the notion of nearest neighbors. This measure can dynamically select multiple objects as representatives for different clusters in different situations. Experimental results show that CVNN outperforms the existing measures on both synthetic data and real-world data in different application scenarios. <s> BIB004 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Clustering Validation in Measurements <s> This article presents a newly proposed selection process for genetic algorithms on a class of unconstrained optimization problems. The k-means genetic algorithm selection process (KGA) is composed of four essential stages: clustering, membership phase, fitness scaling and selection. Inspired from the hypothesis that clustering the population helps to preserve a selection pressure throughout the evolution of the population, a membership probability index is assigned to each individual following the clustering phase. Fitness scaling converts the membership scores in a range suitable for the selection function which selects the parents of the next generation. Two versions of the KGA process are presented: using a fixed number of clusters K (KGAf) and via an optimal partitioning Kopt (KGAo) determined by two different internal validity indices. The performance of each method is tested on seven benchmark problems. <s> BIB005 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Clustering Validation in Measurements <s> Due to uncertainty and inherent noise present in gene expression data, clustering of the data is a challenging task. The common assumption of many clustering algorithms is that each gene belongs to a cluster. However, few genes are functionally inactive, i.e. not participate in any biological process during experimental conditions and should be segregated from clusters. Based on this observation, a clustering method is proposed in this article that clusters co-expressed genes and segregates functionally inactive genes and noise. The proposed method formed a cluster if the difference in expression levels of genes with a specified gene is less than a threshold t in each experimental condition; otherwise, the specified gene is marked as functionally inactive or noise. The proposed method is applied on 10 yeast gene expression data, and the result shows that it performs well over existing one. <s> BIB006
Previous studies have evaluated the identified gene clustering in terms of distance BIB006 . If they are not within a distance regarding a specified gene in each experimental condition, then the specified gene is classified as an inactive gene. Otherwise, the specified gene is co-expressed. Clustering validation can be measured in terms of internal and external criteria BIB002 BIB003 BIB005 BIB004 . Table 6 summarizes the differences between internal and external validations. In general, internal criteria can assess the fitness between clustering structure and data. External criteria can measure the performance by matching cluster structure to prior information. As mentioned by Handl et al. BIB001 , internal validation suffers from bias regarding clusters number and partitioning structure from data. The goal of internal validation is measured based on compactness and separation BIB003 BIB004 . Compactness is defined as a measure of how close the objects are in a cluster based on variance. Separation measures either how a cluster is distinct or how well separated it is from other clusters. Handl et al. BIB001 held the view that external validation can suffer from biases in a partitioning according to cluster number and distribution of groups with class sizes. Table 7 sets out examples of measurements to validate the quality of clusters. As can be seen from the table, previous studies commonly used Euclidean distance and silhouette width. In general, silhouette width can validate the clustering performance in terms of pairwise difference between and within cluster distances BIB003 BIB004 . The maximum values of the silhouette width can identify an optimal number of clusters. Table 6 . The difference in measurements between internal and external validations.