A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Dunn index Internal <s> 1. Introduction. 2. Partitioning Around Medoids (Program PAM). 3. Clustering large Applications (Program CLARA). 4. Fuzzy Analysis. 5. Agglomerative Nesting (Program AGNES). 6. Divisive Analysis (Program DIANA). 7. Monothetic Analysis (Program MONA). Appendix 1. Implementation and Structure of the Programs. Appendix 2. Running the Programs. Appendix 3. Adapting the Programs to Your Needs. Appendix 4. The Program CLUSPLOT. References. Author Index. Subject Index. <s> BIB001 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Dunn index Internal <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> BIB002 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Dunn index Internal <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> Dunn index Internal <s> Gene expression profiling is an emerging technology for identifying genes whose activity may be helpful in assessing disease prognosis and guiding therapy. Gene expression profiling examines the composition of cellular mRNA populations. The identity of the Ribo Nucleic Acid (RNA) transcripts that make up these populations and the number of these transcripts in the cell provide information about the global activity of genes that give rise to them. The number of mRNA transcripts derived from a given gene is a measure of the “expression” of that gene. Given that messenger RNA (mRNA) molecules are translated into proteins, changes in mRNA levels are ultimately related to changes in the protein composition of the cells, and consequently to changes in the properties and functions of tissues and cells in the body. Gene Expression Profiling has been applied to numerous mammalian tissues, as well as plants, yeast, and bacteria. These studies have examined the effects of treating cells with chemicals and the consequences of over expression of regulatory factors in transected cells. Studies also have compared mutant constraints with parental strains to delineate functional pathways. In the cancer research, such investigation has been used to find gene expression changes in transformed cells and metastases, to identify diagnostics markers, and to classify tumors based on their gene expression profiles. Microarray is a high throughput technology that allows uncovering of thousands of genes concurrently. The microarray data is represented in the form of matrix, where the row represents genes, columns represent the <s> BIB004 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Dunn index Internal <s> Gene selection (GS) is an important research area in the analysis of DNA-microarray data, since it involves gene discovery meaningful for a particular target annotation or able to discriminate expression profiles of samples coming from different populations. In this context, a wide number of filter methods have been proposed in the literature to identify subsets of relevant genes in accordance with prefixed targets. Despite the fact that there is a wide number of proposals, the complexity imposed by this problem (GS) remains a challenge. Hence, this paper proposes a novel approach for gene selection by using cluster techniques and filter methods on the found groupings to achieve informative gene subsets. As a result of applying our methodology to Colon cancer data, we have identified the best informative gene subset between several one subsets. According to the above, the reached results have proven the reliability of the approach given in this paper. <s> BIB005 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Dunn index Internal <s> In the bioinformatics and clinical research areas, microarray technology has been widely used to distinguish a cancer dataset between normal and tumour samples. However, the high dimensionality of gene expression data affects the classification accuracy of an experiment. Thus, feature selection is needed to select informative genes and remove non-informative genes. Some of the feature selection methods, yet, ignore the interaction between genes. Therefore, the similar genes are clustered together and dissimilar genes are clustered in other groups. Hence, to provide a higher classification accuracy, this research proposed k-means clustering and infinite feature selection for identifying informative genes in the selected subset. This research has been applied to colorectal cancer and small round blue cell tumors datasets. Eventually, this research successfully obtained higher classification accuracy than the previous work. <s> BIB006 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Dunn index Internal <s> Accurate cancer classification and responses to treatment are important in clinical cancer research since cancer acts as a family of gene-based diseases. Microarray technology has widely developed to measure gene expression level changes under normal and experimental conditions. Normally, gene expression data are high dimensional and characterized by small sample sizes. Thus, feature selection is needed to find the smallest number of informative genes and improve the classification accuracy and the biological interpretability results. Due to some feature selection methods neglect the interactions among genes, thus, clustering is used to group the similar genes together. Besides, the quality of the selected data can determine the effectiveness of the classifiers. This research proposed clustering and feature selection approaches to classify the gene expression data of colorectal cancer. Subsequently, a feature selection approach based on centroid clustering provide higher classification accuracy compared with other approaches. <s> BIB007 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Dunn index Internal <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> BIB008 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Dunn index Internal <s> Kmeans is one of the most-efficient hard-clustering algorithms. It has been successfully applied to a number of problems. However, the efficiency of kmeans is dependent on its initialization of cluster centres. Different swarm intelligence techniques are applied for clustering problem. In this work, we have considered Ant Lion Optimization (ALO) which is a stochastic global optimization models. In this work Kmeans has been integrated with ALO for optimal clustering. The statistical measures of different performance metrics has been calculated and compared. The proposed method performs preferably better than Kmeans and PSO-Kmeans in terms of sum of intracluster distances and F-measure. <s> BIB009 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Dunn index Internal <s> Summary Cellular signaling networks coordinate physiological processes in all multicellular organisms. Within networks, modules switch their function to control signaling activity in response to the cellular context. However, systematic approaches to map the interplay of such modules have been lacking. Here, we generated a context-dependent genetic interaction network of a metazoan's signaling pathway. Using Wnt signaling in Drosophila as a model, we measured >290,000 double perturbations of the pathway in a baseline state, after activation by Wnt ligand or after loss of the tumor suppressor APC. We found that genetic interactions within the Wnt network globally rewired after pathway activation. We derived between-state networks that showed how genes changed their function between state-specific networks. This related pathway inhibitors across states and identified genes required for pathway activation. For instance, we predicted and confirmed the ER-resident protein Catsup to be required for ligand-mediated Wnt signaling activation. Together, state-dependent and between-state genetic interaction networks identify responsive functional modules that control cellular pathways. <s> BIB010 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Dunn index Internal <s> Abstract With the increasing penetration of security threats, the severity of their impact on the underlying network has increased manifold. Hence, a robust anomaly detection technique, Fuzzified Cuckoo based Clustering Technique (F-CBCT), is proposed in this paper which operates in two phases: training and detection. The training phase is supported using Decision Tree followed by an algorithm based on hybridization of Cuckoo Search Optimization and K-means clustering. In the designed algorithm, a multi-objective function based on Mean Square Error and Silhouette Index is employed to evaluate the two simultaneous distance functions namely-Classification measure and Anomaly detection measure. Once the system is trained, detection phase is initiated in which a fuzzy decisive approach is used to detect anomalies on the basis of input data and distance functions computed in the previous phase. Experimental results in terms of detection rate (96.86%), false positive rate (1.297%), accuracy (97.77%) and F-Measure (98.30%) prove the effectiveness of the proposed model. <s> BIB011 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Dunn index Internal <s> Because the K-Means algorithm is easy to fall into the local optimum and the Cuckoo search (CS) algorithm is affected by the step size, this paper proposes a K-Means clustering algorithm based on improved cuckoo search (ICS-Kmeans). The algorithm is compared with the original K-means, the Kmeans algorithm based on particle swarm optimization (PSO-Kmeans) and the K-Means algorithm based on the cuckoo search (CS-Kmeans). The experimental results show that the proposed algorithm can obtain better clustering effect, faster convergence rate and better accuracy rate through the experimental test on the UCI standard data set. The algorithm is also applied to the clustering of the characteristic parameters of the heart sound MFCC. The results show that a better clustering center can be obtained, the algorithm converges fast. <s> BIB012 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Dunn index Internal <s> ABSTRACTImage clustering is a critical and essential component of image analysis to several fields and could be considered as an optimization problem. Cuckoo Search (CS) algorithm is an optimization algorithm that simulates the aggressive reproduction strategy of some cuckoo species.In this paper, a combination of CS and classical algorithms (KM, FCM, and KHM) is proposed for unsupervised satellite image classification. Comparisons with classical algorithms and also with CS are performed using three cluster validity indices namely DB, XB, and WB on synthetic and real data sets. Experimental results confirm the effectiveness of the proposed approach. <s> BIB013 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Dunn index Internal <s> The aim of this study was to introduce a novel global measure of graph complexity: Shannon graph complexity (SGC). This measure was specifically developed for weighted graphs, but it can also be applied to binary graphs. The proposed complexity measure was designed to capture the interplay between two properties of a system: the ‘information’ (calculated by means of Shannon entropy) and the ‘order’ of the system (estimated by means of a disequilibrium measure). SGC is based on the concept that complex graphs should maintain an equilibrium between the aforementioned two properties, which can be measured by means of the edge weight distribution. In this study, SGC was assessed using four synthetic graph datasets and a real dataset, formed by electroencephalographic (EEG) recordings from controls and schizophrenia patients. SGC was compared with graph density (GD), a classical measure used to evaluate graph complexity. Our results showed that SGC is invariant with respect to GD and independent of node degree... <s> BIB014 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Dunn index Internal <s> Abstract K-Means is a popular cluster analysis method which aims to partition a number of data points into K clusters. It has been successfully applied to a number of problems. However, the efficiency of K-Means depends on its initialization of cluster centers. Different swarm intelligence techniques are applied to clustering problem for enhancing the performance. In this work a hybrid clustering approach based on K-means and Ant Lion Optimization has been considered for optimal cluster analysis. Ant Lion Optimization (ALO) is a stochastic global optimization model. The performance of the proposed algorithm is compared against the performance of K-Means, KMeans-PSO, KMeans-FA, DBSCAN and Revised DBSCAN clustering methods based on different performance metrics. Experimentation is performed on eight datasets, for which the statistical analysis is carried out. The obtained results indicate that the hybrid of K-Means and Ant Lion Optimization method performs preferably better than the other three algorithms in terms of sum of intracluster distances and F-measure. <s> BIB015
Ratio of the smallest distance among observations in the different cluster to the most considerable intra-cluster distance. BIB008 BIB002 Euclidean distance Internal Compute distances between the objects to quantify their degree of dissimilarity. BIB005 BIB006 BIB001 BIB007 Inter-cluster distance Internal Quantify the degree of separation between individual clusters. BIB009 Manhattan distance Internal Correspond to the sum of lengths of the other two sides of a triangle. BIB001 Pearson correlation coefficients (PCC) Internal Measure between-state functional similarity. BIB002 BIB010 Silhouette width Internal Measure the degree of confidence in a clustering assignment and lie in the interval [−1, +1], with well-clustered observations having values near +1 and near -1 for poorly clustered observations. BIB008 BIB003 BIB005 BIB006 BIB011 BIB007 Square sum function of the error Internal Measure the quality of cluster either by compactness or homogeneity. BIB012 BIB002 BIB013 Entropy External Measure mutual information based on the probability distribution of random variables.  BIB004 BIB014 F-measure External Assess the quality of clustering result at the level of entire partitioning and not for an individual cluster only. BIB009 BIB002  BIB015 