A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Gene Network Clustering Techniques <s> We study a number of open issues in spectral clustering: (i) Selecting the appropriate scale of analysis, (ii) Handling multi-scale data, (iii) Clustering with irregular background clutter, and, (iv) Finding automatically the number of groups. We first propose that a 'local' scale should be used to compute the affinity between each pair of points. This local scaling leads to better clustering especially when the data includes multiple scales and when the clusters are placed within a cluttered background. We further suggest exploiting the structure of the eigenvectors to infer automatically the number of groups. This leads to a new algorithm in which the final randomly initialized k-means stage is eliminated. <s> BIB001 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Gene Network Clustering Techniques <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> Gene Network Clustering Techniques <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> BIB003 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Gene Network Clustering Techniques <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> BIB004 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Gene Network Clustering Techniques <s> Clustering refers to the task of identifying groups or clusters in a data set. In density-based clustering, a cluster is a set of data objects spread in the data space over a contiguous region of high density of objects. Density-based clusters are separated from each other by contiguous regions of low density of objects. Data objects located in low-density regions are typically considered noise or outliers. © 2011 John Wiley & Sons, Inc. WIREs Data Mining Knowl Discov 2011 1 231–240 DOI: 10.1002/widm.30 ::: ::: This article is categorized under: ::: ::: Technologies > Structure Discovery and Clustering <s> BIB005 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Gene Network Clustering Techniques <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> BIB006 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Gene Network Clustering Techniques <s> Information-maximization clustering learns a probabilistic classifier in an unsupervised manner so that mutual information between feature vectors and cluster assignments is maximized. A notable advantage of this approach is that it only involves continuous optimization of model parameters, which is substantially easier to solve than discrete optimization of cluster assignments. However, existing methods still involve non-convex optimization problems, and therefore finding a good local optimal solution is not straightforward in practice. In this paper, we propose an alternative information-maximization clustering method based on a squared-loss variant of mutual information. This novel approach gives a clustering solution analytically in a computationally efficient way via kernel eigenvalue decomposition. Furthermore, we provide a practical model selection procedure that allows us to objectively optimize tuning parameters included in the kernel function. Through experiments, we demonstrate the usefulness of the proposed approach. <s> BIB007 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Gene Network Clustering Techniques <s> We survey agglomerative hierarchical clustering algorithms and discuss efficient implementations that are available in R and other software environments. We look at hierarchical self-organizing maps and mixture models. We review grid-based clustering, focusing on hierarchical density-based approaches. Finally, we describe a recently developed very efficient (linear time) hierarchical clustering algorithm, which can also be viewed as a hierarchical grid-based algorithm. This review adds to the earlier version, Murtagh F, Contreras P. Algorithms for hierarchical clustering: an overview, Wiley Interdiscip Rev: Data Mining Knowl Discov 2012, 2, 86–97. WIREs Data Mining Knowl Discov 2017, 7:e1219. doi: 10.1002/widm.1219 ::: ::: This article is categorized under: ::: ::: Algorithmic Development > Hierarchies and Trees ::: Technologies > Classification ::: Technologies > Structure Discovery and Clustering <s> BIB008 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Gene Network Clustering Techniques <s> A review based on different types of clustering algorithms with their corresponding data sets has been proposed. In this paper, we have given a complete comparative statistical analysis of various clustering algorithms. Clustering algorithms usually employ distance metric or similarity metric to cluster the data set into different partitions. Well known clustering algorithms have been widely used in various disciplines. Type of clustering algorithm used depends upon the application and data set used in that field. Numerical data set is comparatively easy to implement as data are invariably real number and can be used for statistical applications. Others type of data set such as categorical, time series, boolean, and spatial, temporal have limited applications. By viewing the statistical analysis, it is observed that there is no optimal solution for handling problems with large data sets of mixed and categorical attributes. Some of the algorithms can be applied but their performance degrades as the size of data keeps on increasing. <s> BIB009 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Gene Network Clustering Techniques <s> consist of hundreds of thousands of small and cost effective sensor nodes. Sensor nodes are used to sense the environmental or physiological parameters like temperature, pressure, etc. For the connectivity of the sensor nodes, they use wireless transceiver to send and receive the inter-node signals. Sensor nodes, because connect their selves wirelessly, use routing process to route the packet to make them reach from source to destination. These sensor nodes run on batteries and they carry a limited battery life. Clustering is the process of creating virtual sub-groups of the sensor nodes, which helps the sensor nodes to lower routing computations and to lower the size routing data. There is a wide space available for the research on energy efficient clustering algorithms for the WSNs. LEACH, PEGASIS and HEED are the popular energy efficient clustering protocols for WSNs. In this research, we are working on the development of a hybrid model using LEACH based energy efficient and K-means based quick clustering algorithms to produce a new cluster scheme for WSNs with dynamic selection of the number of the clusters automatically. In the proposed method, finding an optimum "k" value is performed by Elbow method and clustering is done by k-means algorithm, hence routing protocol LEACH which is a traditional energy efficient protocol takes the work ahead of sending data from the cluster heads to the base station. The results of simulation show that at the end of some certain part of running the proposed algorithm, at some point the marginal gain will drop dramatically and gives an angle in the graph. The correct "k" i.e. number of clusters is chosen at this point, hence the "elbow criterion". <s> BIB010 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Gene Network Clustering Techniques <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> BIB011 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Gene Network Clustering Techniques <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> BIB012 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Gene Network Clustering Techniques <s> Abstract Clustering is an important technique to deal with large scale data which are explosively created in internet. Most data are high-dimensional with a lot of noise, which brings great challenges to retrieval, classification and understanding. No current existing approach is “optimal” for large scale data. For example, DBSCAN requires O(n2) time, Fast-DBSCAN only works well in 2 dimensions, and ρ-Approximate DBSCAN runs in O(n) expected time which needs dimension D to be a relative small constant for the linear running time to hold. However, we prove theoretically and experimentally that ρ-Approximate DBSCAN degenerates to an O(n2) algorithm in very high dimension such that 2D > > n. In this paper, we propose a novel local neighborhood searching technique, and apply it to improve DBSCAN, named as NQ-DBSCAN, such that a large number of unnecessary distance computations can be effectively reduced. Theoretical analysis and experimental results show that NQ-DBSCAN averagely runs in O(n*log(n)) with the help of indexing technique, and the best case is O(n) if proper parameters are used, which makes it suitable for many realtime data. <s> BIB013 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Gene Network Clustering Techniques <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> BIB014 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Gene Network Clustering Techniques <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> BIB015 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Gene Network Clustering Techniques <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> BIB016 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Gene Network Clustering Techniques <s> Abstract Density-based clustering has been widely used in many fields. A new effective grid-based and density-based spatial clustering algorithm, GRIDEN, is proposed in this paper, which supports parallel computing in addition to multi-density clustering. It constructs grids using hyper-square cells and provides users with parameter k to control the balance between efficiency and accuracy to increase the flexibility of the algorithm. Compared with conventional density-based algorithms, it achieves much higher performance by eliminating distance calculations among points based on the newly proposed concept of e-neighbor cells. Compared with conventional grid-based algorithms, it uses a set of symmetric ( 2 k + 1 ) D cells to identify dense cells and the density-connected relationships among cells. Therefore, the maximum calculated deviation of e-neighbor points in the grid-based algorithm can be controlled to an acceptable level through parameter k. In our experiments, the results demonstrate that GRIDEN can achieve a reliable clustering result that is infinite closed with respect to the exact DBSCAN as parameter k grows, and it requires computational time that is only linear to N. <s> BIB017
In general, clustering can be categorized into partitioning, hierarchical, grid-based, and densitybased techniques BIB012 BIB003 BIB005 BIB009 BIB013 . In Table 1 , we show differences among categories of clustering techniques. The table also provides some information such as time complexity, computing efficiency, convergence rate, scalability, and initialization of cluster number. Partitioning clustering assigns the data objects into a number of clusters fixed beforehand. This technique identifies the number of centroids and assigns the objects to the nearest centroid. Hierarchical clustering groups the data based on the distance of the objects to form clusters. This technique can be either started with large Several previous studies have noted the importance of clustering to identify co-expressed genes in a cluster and inactive genes in another cluster BIB014 BIB015 . Clustering can also discover the fundamental hidden structure of biomedical data, which can be used for diagnosis and treatments BIB015 . In addition, clustering is extremely vital for identifying cancer subtyping and the detection of the tumor. Researchers typically focus on clustering by assuming the number of clusters beforehand, which can be seen in BIB006 BIB012 . This problem can lead to the inability of the clustering techniques to obtain an optimal number of centroids and hence results in poor quality of clusters BIB012 BIB016 . In previous studies, several proposed approaches managed to discover the optimal number of clusters by simply tuning and optimizing the parameters of the clustering method. This can be done by repeating the process of analyzing the eigenvalues of the affinity matrix, which are equal to the number of desired clusters BIB001 . In addition, rotating normalized eigenvectors and squared-loss mutual information (SMI) can be employed in the clustering process to obtain an optimal number of clusters BIB007  . Besides, the elbow method and the average silhouette method are the other examples to identify the optimal number of clusters in previous studies  BIB010 . The elbow method identifies the optimal number of clusters by calculating sum of squared error for each number of clusters (k) from a range of k values. The average silhouette method computes the average silhouette values of genes for different values of k (number of clusters). Then, this method selects the optimal number of clusters that has the maximum average silhouette values from the range of k values. Optimization of the objective function and validation of clustering can improve the quality of clusters BIB012 . The optimization for the objective function of clustering can identify the best solution among a set of solutions. On the other hand, clustering validation is used to determine clusters in the data using an appropriate measurement BIB003 . Clustering validation can also evaluate the goodness of the clustering structure based on the given class labels BIB004 . Thus, validation is an essential step because it assists in the identification of which cluster is more informative compared to other clusters BIB011 . This paper focuses on reviewing existing computational methods on genes clustering using the notion of optimizing the objective function and validation. In general, clustering can be categorized into partitioning, hierarchical, grid-based, and density-based techniques BIB012 BIB003 BIB005 BIB009 BIB013 . In Table 1 , we show differences among categories of clustering techniques. The table also provides some information such as time complexity, computing efficiency, convergence rate, scalability, and initialization of cluster number. Partitioning clustering assigns the data objects into a number of clusters fixed beforehand. This technique identifies the number of centroids and assigns the objects to the nearest centroid. Hierarchical clustering groups the data based on the distance of the objects to form clusters. This technique can be either started with large data and aggregated into a small group or started from a small group of data and merged until all the data are in one large group. Grid-based clustering divides each dimension of data space to form a grid structure. Density-based clustering separates the data according to the density of the objects. Traditionally, hierarchical, grid-based, and density-based techniques do not require cluster number as an input parameter BIB005 BIB002 . In the view of Jain BIB003 , hierarchical clustering is more versatile than partitioning clustering. With the discovery of clusters with good robustness and flexibility, grid-based and density-based techniques have been particularly useful BIB017 . They are also helpful for dealing with large spatial data and the proper use of expert knowledge. Grid-based and density-based techniques also aim to identify data densities and to split the data space into grid structures when looking for groupings BIB008 . Grid-based clustering techniques are more efficient compared to density-based clustering techniques; however, the use of summarized information makes these techniques lose effectiveness in cases where the number of dimensions increases  . In Table 2 , we present several examples of clustering techniques done by previous researchers. The table also summarizes the advantages and the disadvantages of the techniques. From this table, k-means clustering is the most popular technique, even though k-means suffers from the shortcoming of identifying the number of potential clusters before the clustering setup. Table 2 . Examples of popular clustering techniques along with their advantages and disadvantages.