A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Category 1: Partitioning Clustering <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> Category 1: Partitioning Clustering <s> The self-organizing map (SOM) is an excellent tool in exploratory phase of data mining. It projects input space on prototypes of a low-dimensional regular grid that can be effectively utilized to visualize and explore properties of the data. When the number of SOM units is large, to facilitate quantitative analysis of the map and the data, similar units need to be grouped, i.e., clustered. In this paper, different approaches to clustering of the SOM are considered. In particular, the use of hierarchical agglomerative clustering and partitive clustering using K-means are investigated. The two-stage procedure-first using SOM to produce the prototypes that are then clustered in the second stage-is found to perform well when compared with direct clustering of the data and to reduce the computation time. <s> BIB002 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Category 1: Partitioning Clustering <s> Clustering is a mostly unsupervised procedure and the majority of clustering algorithms depend on certain assumptions in order to define the subgroups present in a data set. As a consequence, in most applications the resulting clustering scheme requires some sort of evaluation regarding its validity. In this paper we present a clustering validity procedure, which evaluates the results of clustering algorithms on data sets. We define a validity index, S Dbw, based on well-defined clustering criteria enabling the selection of optimal input parameter values for a clustering algorithm that result in the best partitioning of a data set. We evaluate the reliability of our index both theoretically and experimentally, considering three representative clustering algorithms run on synthetic and real data sets. We also carried out an evaluation study to compare S Dbw performance with other known validity indices. Our approach performed favorably in all cases, even those in which other indices failed to indicate the correct partitions in a data set. <s> BIB003 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Category 1: Partitioning Clustering <s> Motivation: Clustering analysis of data from DNA microarra yh ybridization studies is essential for identifying biologically relevant groups of genes. Partitional clustering methods such as K-means or self-organizing maps assign each gene to a single cluster. However, these methods do not provide information about the influence of a given gene for the overall shape of clusters. Here we apply a fuzzy partitioning method, Fuzzy C-means (FCM), to attribute cluster membership values to genes. Results: Am ajor problem in applying the FCM method for clustering microarray data is the choice of the fuzziness parameter m .W eshow that the commonly used value m = 2 is not appropriate for some data sets, and that optimal values for m vary widely from one data set to another. We propose an empirical method, based on the distribution of distances between genes in a given data set, to determine an adequate value for m .B ysetting threshold levels for the membership values, genes which are tigthly associated to a given cluster can be selected. Using a yeast cell cycle data set as an example, we show that this selection increases the overall biological significance of the genes within the cluster. Availability: Supplementary text and Matlab functions are available at http://www-igbmc.u-strasbg.fr/fcm/ <s> BIB004 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Category 1: Partitioning Clustering <s> Abstract Clustering is a branch of multivariate analysis that is used to create groups of data. While there are currently a variety of techniques that are used for creating clusters, many require defining additional information, including the actual number of clusters, before they can be carried out. The case study of this research presents a novel neural network that is capable of creating groups by using a combination of hierarchical clustering and self-organizing maps, without requiring the number of existing clusters to be specified beforehand. Key words: Clustering, SOM, hierarchical clustering, PAM, Dendrogram, 1. Introduction Cluster analysis is a branch of multivariate statistical analysis that is used for detecting patterns in the classification of elements. Cluster analysis is used in a wide variety of fields including bioinformatics [9] [19] and surveillance [14] [15]. The methods used for clustering differ considerably according to the type of data and the amount of available information. Clustering techniques are typically broken down into the following categories [18] [19] <s> BIB005 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Category 1: Partitioning Clustering <s> The Fuzzy c-means is one of the most popular ongoing area of research among all types of researchers including Computer science, Mathematics and other areas of engineering, as well as all areas of optimization practices. Several problems from various areas have been effectively solved by using FCM and its different variants. But, for efficient use of the algorithm in various diversified applications, some modifications or hybridization with other algorithms are needed. A comprehensive survey on FCM and its applications in more than one decade has been carried out in this paper to show the efficiency and applicability in a mixture of domains. Also, another intention of this survey is to encourage new researchers to make use of this simple algorithm (which is popularly called soft classification model) in problem solving. <s> BIB006 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Category 1: Partitioning Clustering <s> Data analysis is used as a common method in modern science research, which is across communication science, computer science and biology science. Clustering, as the basic composition of data analysis, plays a significant role. On one hand, many tools for cluster analysis have been created, along with the information increase and subject intersection. On the other hand, each clustering algorithm has its own strengths and weaknesses, due to the complexity of information. In this review paper, we begin at the definition of clustering, take the basic elements involved in the clustering process, such as the distance or similarity measurement and evaluation indicators, into consideration, and analyze the clustering algorithms from two perspectives, the traditional ones and the modern ones. All the discussed clustering algorithms will be compared in detail and comprehensively shown in Appendix Table 22. <s> BIB007 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Category 1: Partitioning Clustering <s> Subspace clustering is the task of identifying clusters in subspaces of the input dimensions of a given dataset. Noisy data in certain attributes cause difficulties for traditional clustering algorithms, because the high discrepancies within them can make objects appear too different to be grouped in the same cluster. This requires methods specially designed for subspace clustering. This paper presents our second approach to subspace and projected clustering based on self-organizing maps (SOMs), which is a local adaptive receptive field dimension selective SOM. By introducing a time-variant topology, our method is an improvement in terms of clustering quality, computational cost, and parameterization. This enables the method to identify the correct number of clusters and their respective relevant dimensions, and thus it presents nearly perfect results in synthetic datasets and surpasses our previous method in most of the real-world datasets considered. <s> BIB008 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Category 1: Partitioning Clustering <s> The paper touches upon the problem of implementation Partition Around Medoids (PAM) clustering algorithm for the Intel Many Integrated Core architecture. PAM is a form of well-known k-Medoids clustering algorithm and is applied in various subject domains, e.g. bioinformatics, text analysis, intelligent transportation systems, etc. An optimized version of PAM for the Intel Xeon Phi coprocessor is introduced where OpenMP parallelizing technology, loop vectorization, tiling technique and efficient distance matrix computation for Euclidean metric are used. Experimental results for different data sets confirm the efficiency of the proposed algorithm. <s> BIB009 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Category 1: Partitioning Clustering <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> BIB010 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Category 1: Partitioning Clustering <s> Penetrability is a dominant factor in selecting the suitable drilling method, adjustment of machine parameters and tool wear analysis. In this paper, it is aimed to classify the rock penetrability using Artificial Bee Colony (ABC) algorithm as one of the powerful meta-heuristic algorithms and Self-Organizing Map (SOM) as one of the precise scientific tools. For this purpose, eight different rocks from open pit mines and highway slopes were classified into four separate clusters according to physical and mechanical properties of rock including uniaxial compressive strength, mean Mohs hardness, Young modulus and Schimazek’s F-abrasivity. To evaluate and validate the obtained clusters, field studies were performed and the drilling rate of studied rocks was measured. The results of field study were compared with the results of ABC algorithm and SOM. The results showed that, the studied rocks were reliably classified with respect to their drilling rate. It is concluded that applied techniques can be used for solving the complex rock engineering problems specially in engineering classification of rocks. <s> BIB011 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Category 1: Partitioning Clustering <s> Discovering the similar groups is a popular primary step in analysis of biomedical data, which cannot be identified manually. Many supervised and unsupervised machine learning and statistical approaches have been developed to solve this problem. Clustering is an unsupervised learning approach, which organizes the data into similar groups, and is used to discover the intrinsic hidden structure of data. In this paper, we used clustering by fast search and find of density peaks (CDP) approach for cancer subtyping and identification of normal tissues from tumor tissues. In additional, we also address the preprocessing and underlying distance matrix's impact on finalized groups. We have performed extensive experiments on real-world and synthetic cancer gene expression microarray data sets and compared obtained results with state-of-the-art clustering approaches. <s> BIB012 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Category 1: Partitioning Clustering <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> BIB013 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Category 1: Partitioning Clustering <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> BIB014 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Category 1: Partitioning Clustering <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> BIB015 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Category 1: Partitioning Clustering <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> BIB016 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Category 1: Partitioning Clustering <s> Clustering is the most common method for organizing unlabeled data into its natural groups (called clusters), based on similarity (in some sense or another) among data objects. The Partitioning Around Medoids (PAM) algorithm belongs to the partitioning-based methods of clustering widely used for objects categorization, image analysis, bioinformatics and data compression, but due to its high time complexity, the PAM algorithm cannot be used with large datasets or in any embedded or real-time application. In this work, we propose a simple and scalable parallel architecture for the PAM algorithm to reduce its running time. This architecture can easily be implemented either on a multi-core processor system to deal with big data or on a reconfigurable hardware platform, such as FPGA and MPSoCs, which makes it suitable for real-time clustering applications. Our proposed model partitions data equally among multiple processing cores. Each core executes the same sequence of tasks simultaneously on its respective data subset and shares intermediate results with other cores to produce results. Experiments show that the computational complexity of the PAM algorithm is reduced exponentially as we increase the number of cores working in parallel. It is also observed that the speedup graph of our proposed model becomes more linear with the increase in number of data points and as the clusters become more uniform. The results also demonstrate that the proposed architecture produces the same results as the actual PAM algorithm, but with reduced computational complexity. <s> BIB017 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Category 1: Partitioning Clustering <s> Clustering in high-dimensional data space is a difficult task due to the interference from different dimensions. A dimension may be relevant for some clusters and irrelevant for other data. Subspace clustering aims at finding local cluster structures in certain related subspace. We propose a novel approach to finding subspace clusters based on the trained Self-Organizing Map neural network (SOM). The proposed method takes advantage of nonlinear mapping of SOM and search for subspace clusters on input neurons instead of the whole data space. Experiment results show that the proposed method performs better compared with original SOM and some traditional subspace clustering algorithms. <s> BIB018
Detection of clusters using partitioning clustering has low time complexity and high computational cost BIB007 . However, there are specific problems related to this technique. One of these problems is detecting clusters inappropriate for non-convex data. This could be because clustering techniques cannot spatially separate the data BIB003 . Other disadvantages are the need to initialize the number of clusters beforehand, and that the clustering result is sensitive to the intended number of possible clusters. Fuzzy C Means (FCM), k-means clustering, Partitioning Around Medoids (PAM), and Self-Organizing Maps (SOM) are all examples of partitioning clustering BIB012 BIB005 BIB013 BIB014 BIB004 BIB006   BIB010 BIB015 BIB016 BIB001 BIB002 BIB008 BIB011 BIB018 . PAM is a variation of k-means clustering BIB009 , and it is more robust in terms of accuracy compared to k-means clustering, for instance, when applied to classify cancer types  BIB017 .