A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Self-Organizing Maps (SOM)s Partitioning <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> Self-Organizing Maps (SOM)s Partitioning <s> Data mining applications place special requirements on clustering algorithms including: the ability to find clusters embedded in subspaces of high dimensional data, scalability, end-user comprehensibility of the results, non-presumption of any canonical data distribution, and insensitivity to the order of input records. We present CLIQUE, a clustering algorithm that satisfies each of these requirements. CLIQUE identifies dense clusters in subspaces of maximum dimensionality. It generates cluster descriptions in the form of DNF expressions that are minimized for ease of comprehension. It produces identical results irrespective of the order in which input records are presented and does not presume any specific mathematical form for data distribution. Through experiments, we show that CLIQUE efficiently finds accurate cluster in large high dimensional datasets. <s> BIB002 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Self-Organizing Maps (SOM)s Partitioning <s> Although cancer classification has improved over the past 30 years, there has been no general approach for identifying new cancer classes (class discovery) or for assigning tumors to known classes (class prediction). Here, a generic approach to cancer classification based on gene expression monitoring by DNA microarrays is described and applied to human acute leukemias as a test case. A class discovery procedure automatically discovered the distinction between acute myeloid leukemia (AML) and acute lymphoblastic leukemia (ALL) without previous knowledge of these classes. An automatically derived class predictor was able to determine the class of new leukemia cases. The results demonstrate the feasibility of cancer classification based solely on gene expression monitoring and suggest a general strategy for discovering and predicting cancer classes for other types of cancer, independent of previous biological knowledge. <s> BIB003 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Self-Organizing Maps (SOM)s Partitioning <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> BIB004 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Self-Organizing Maps (SOM)s Partitioning <s> A reliable and precise classification of tumors is essential for successful diagnosis and treatment of cancer. cDNA microarrays and high-density oligonucleotide chips are novel biotechnologies increasingly used in cancer research. By allowing the monitoring of expression levels in cells for thousands of genes simultaneously, microarray experiments may lead to a more complete understanding of the molecular variations among tumors and hence to a finer and more informative classification. The ability to successfully distinguish between tumor classes (already known or yet to be discovered) using gene expression data is an important aspect of this novel approach to cancer classification. This article compares the performance of different discrimination methods for the classification of tumors based on gene expression data. The methods include nearest-neighbor classifiers, linear discriminant analysis, and classification trees. Recent machine learning approaches, such as bagging and boosting, are also considere... <s> BIB005 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Self-Organizing Maps (SOM)s Partitioning <s> Genome wide protein networks have become reality in recent years due to high throughput methods for detecting protein interactions. Recent studies show that a networked representation of proteins provides a more accurate model of biological systems and processes compared to conventional pair-wise analyses. Complementary to the availability of protein networks, various graph analysis techniques have been proposed to mine these networks for pathway discovery, function assignment, and prediction of complex membership. In this paper, we propose using random walks on graphs for the complex/pathway membership problem. We evaluate the proposed technique on three different probabilistic yeast networks using a benchmark dataset of 27 complexes from the MIPS complex catalog database and 10 pathways from the KEGG pathway database. Furthermore, we compare the proposed technique to two other existing techniques both in terms of accuracy and running time performance, thus addressing the scalability issue of such analysis techniques for the first time. Our experiments show that the random walk technique achieves similar or better accuracy with more than 1,000 times speed-up compared to the best competing technique. <s> BIB006 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Self-Organizing Maps (SOM)s Partitioning <s> In the era of globalization, traditional theories and models of social systems are shifting their focus from isolation and independence to networks and connectedness. Analyzing these new complex social models is a growing, and computationally demanding area of research. In this study, we investigate the integration of genetic algorithms (GAs) with a random-walk-based distance measure to find subgroups in social networks. We test our approach by synthetically generating realistic social network data sets. Our clustering experiments using random-walk-based distances reveal exceptionally accurate results compared with the experiments using Euclidean distances. <s> BIB007 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Self-Organizing Maps (SOM)s Partitioning <s> Clustering web sessions is to group web sessions based on similarity and consists of minimizing the intra-group similarity and maximizing the inter-group similarity. The other question that arises is how to measure similarity between web sessions. Here in this paper we adopted a CLIQUE (CLUstering in QUEst) algorithm for clustering web sessions for web personalization. Then we adopted various similarity measures like Euclidean distance, projected Euclidean distance Jaccard, cosine and fuzzy dissimilarity measures to measure the similarity of web sessions using sequence alignment to determine learning behaviors. This has significant results when comparing similarities between web sessions with various measures, we performed a variety of experiments in the context of density based clustering, based on sequence alignment to measure similarities between web sessions where sessions are chronologically ordered sequences of page visits. <s> BIB008 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Self-Organizing Maps (SOM)s Partitioning <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> BIB009 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Self-Organizing Maps (SOM)s Partitioning <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> BIB010 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Self-Organizing Maps (SOM)s Partitioning <s> Discovering clusters from a dataset with different shapes, density, and scales is a known challenging problem in data clustering. In this paper, we propose the RElative COre MErge (RECOME) clustering algorithm. The core of RECOME is a novel density measure, i.e., Relative $K$ nearest Neighbor Kernel Density (RNKD). RECOME identifies core objects with unit RNKD, and partitions non-core objects into atom clusters by successively following higher-density neighbor relations toward core objects. Core objects and their corresponding atom clusters are then merged through $\alpha$-reachable paths on a KNN graph. Furthermore, we discover that the number of clusters computed by RECOME is a step function of the $\alpha$ parameter with jump discontinuity on a small collection of values. A jump discontinuity discovery (JDD) method is proposed using a variant of the Dijkstra's algorithm. RECOME is evaluated on three synthetic datasets and six real datasets. Experimental results indicate that RECOME is able to discover clusters with different shapes, density and scales. It achieves better clustering results than established density-based clustering methods on real datasets. Moreover, JDD is shown to be effective to extract the jump discontinuity set of parameter $\alpha$ for all tested dataset, which can ease the task of data exploration and parameter tuning. <s> BIB011 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Self-Organizing Maps (SOM)s Partitioning <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> BIB012 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Self-Organizing Maps (SOM)s Partitioning <s> Amyotrophic lateral sclerosis (ALS) is an incurable and fatal disorder characterized by the progressive loss of motor neurons in the cerebral cortex, brain stem, and spinal cord. Sporadic ALS form accounts for the majority of patients, but in 1–13.5% of cases the disease is inherited. The diagnosis of ALS is mainly based on clinical assessment and electrophysiological examinations with a history of symptom progression and is then made with a significant delay from symptom onset. Thus, the identification of biomarkers specific for ALS could be of a fundamental importance in the clinical practice. An ideal biomarker should display high specificity and sensitivity for discriminating ALS from control subjects and from ALS-mimics and other neurological diseases, and should then monitor disease progression within individual patients. microRNAs (miRNAs) are considered promising biomarkers for neurodegenerative diseases, since they are remarkably stable in human body fluids and can reflect physiological and pathological processes relevant for ALS. Here, we review the state of the art of miRNA biomarker identification for ALS in cerebrospinal fluid (CSF), blood and muscle tissue; we discuss advantages and disadvantages of different approaches, and underline the limits but also the great potential of this research for future practical applications. <s> BIB013 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Self-Organizing Maps (SOM)s Partitioning <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> BIB014
Suitable for data survey and getting good insight into the cluster structure of data for data mining purposes. Distance dissimilarity is ignored. BIB004 BIB009 BIB012 BIB014 Agglomerative Nesting (AGNES) Build a hierarchy of clustering from a small cluster and then merge until all data are in one large group. Starts with details and then works up to large clusters, which is affected by unfortunate decisions in the first step. BIB010 BIB001 EISEN Clustering Hierarchical (agglomerative) Carry out a clustering in which a mean vector represents each cluster from data in the group. Starts with details and then works up to large clusters, which can be affected by unfortunate decisions in the first step. BIB010 Divisive Analysis (DIANA) Hierarchical (divisive) Perform a task starting from a large cluster containing all data to only a single dataset. Not generally available and rarely applied in most studies. BIB010 BIB001 Clustering in Quest (CLIQUE) Grid-based Can automatically find subspaces in lower-dimensional subspaces with high-density clusters. Ignores all projections of dimensional subspaces. BIB002 BIB008 Considers the interaction between two genes. BIB006 BIB007  Relative Core Merge (RECOME) Density-based Can characterize based on a step function of its parameter. Scalability issue. Hard to handle a large volume of data. BIB011 According to the reviewed clustering techniques in Table 2 , this experimental work aims to investigate which category of clustering techniques would perform better in clustering genes. Gene expression data from the leukemia microarray study by Golub et al. BIB003 are used in this study. These data consist of 3051 genes, 38 tumor mRNA samples [27 acute lymphoblastic leukemia (ALL) and 11 acute myeloid leukemia (AML)] BIB005 . The clustering techniques investigated in this experimental work are k-means clustering (partitioning), agglomerative nesting (AGNES) (hierarchical), clustering in quest (CLIQUE) (grid-based), and density-based spatial clustering of applications with noise (DBSCAN) (density-based). The results in terms of percentage of accuracy are shown in Table 3 . The experimental work was carried out using stratified ten-fold cross-validation and a support vector machine as a classifier. The selected clusters in Table 3 were validated based on silhouette width. According to Table 3 , the CLIQUE was able to achieve the highest classification accuracy when applied on the leukemia dataset compared to other clustering techniques. In addition, Table 3 also shows several genes were biologically validated as prognostic markers for leukemia when PubMed text mining was used. Prognostic marker was commonly used to differentiate between good or poor disease outcomes BIB013 . This validation was done to show the relationship between genes and prognostic markers of leukemia  . Although CLIQUE achieved the best classification accuracy, the technique identified 67 genes as prognostic markers of leukemia out of 919 genes in the selected cluster. On the other hand, k-means had the best performance in identifying prognostic markers of leukemia (8%). The remaining techniques were able to achieve between 6% and 8% in determining the prognostic markers of leukemia over the number of genes in the selected clusters. Note: k is the number of clusters to be selected; dimensions are divided into several equal-width intervals; density is the density threshold; minPts is the minimum size of clusters.