A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Introduction <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> Introduction <s> Applications of clustering algorithms in biomedical research are ubiquitous, with typical examples including gene expression data analysis, genomic sequence analysis, biomedical document mining, and MRI image analysis. However, due to the diversity of cluster analysis, the differing terminologies, goals, and assumptions underlying different clustering algorithms can be daunting. Thus, determining the right match between clustering algorithms and biomedical applications has become particularly important. This paper is presented to provide biomedical researchers with an overview of the status quo of clustering algorithms, to illustrate examples of biomedical applications based on cluster analysis, and to help biomedical researchers select the most suitable clustering algorithms for their own applications. <s> BIB002 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Introduction <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> Introduction <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> Introduction <s> In recent years, there is an increasing interest in the research community in finding community structure in complex networks. The networks are usually represented as graphs, and the task is usually cast as a graph clustering problem. Traditional clustering algorithms and graph partitioning algorithms have been applied to this problem. New graph clustering algorithms have also been proposed. Random walk based clustering, in which the similarities between pairs of nodes in a graph are usually estimated using random walk with restart (RWR) algorithm, is one of the most popular graph clustering methods. Most of these clustering algorithms only find disjoint partitions in networks; however, communities in many real-world networks often overlap to some degree. In this paper, we propose an efficient clustering method based on random walks for discovering communities in graphs. The proposed method makes use of network topology and edge weights, and is able to discover overlapping communities. We analyze the effect of parameters in the proposed method on clustering results. We evaluate the proposed method on real world social networks that are well documented in the literature, using both topological-based and knowledge-based evaluation methods. We compare the proposed method to other clustering methods including recently published Repeated Random Walks, and find that the proposed method achieves better precision and accuracy values in terms of six statistical measurements including both data-driven and knowledge-driven evaluation metrics. <s> BIB005 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Introduction <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> Introduction <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> Introduction <s> Motivation: The accurate prediction of disease status is a central challenge in clinical cancer research. Microarray-based gene biomarkers have been identified to predict outcome and outperformed traditional clinical parameters. However, the robustness of the individual gene biomarkers is questioned due to their little reproducibility between different cohorts of patients. Substantial progress in treatment requires advances in methods to identify robust biomarkers. Several methods incorporating pathway information have been proposed to identify robust pathway markers and build classifiers at the level of functional categories rather than of individual genes. However, current methods consider the pathways as simple gene sets but ignore the pathway topological information, which is essential to infer a more robust pathway activity. Results: Here, we propose a directed random walk (DRW)-based method to infer the pathway activity. DRW evaluates the topological importance of each gene by capturing the structure information embedded in the directed pathway network. The strategy of weighting genes by their topological importance greatly improved the reproducibility of pathway activities. Experiments on 18 cancer data sets showed that the proposed method yielded a more accurate and robust overall performance compared to several existing genebased and pathway-based classification methods. The resulting risk active pathways are more reliable in guiding therapeutic selection and the development of pathway-specific therapeutic strategies. Availability: DRW is freely available at <s> BIB008 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Introduction <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> BIB009 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Introduction <s> Precise cancer classification is a central challenge in clinical cancer research such as diagnosis, prognosis and metastasis prediction. Most existing cancer classification methods based on gene or metabolite biomarkers were limited to single genomics or metabolomics, and lacked integration and utilization of multiple ‘omics’ data. The accuracy and robustness of these methods when applied to independent cohorts of patients must be improved. In this study, we propose a directed random walk-based method to evaluate the topological importance of each gene in a reconstructed gene–metabolite graph by integrating information from matched gene expression profiles and metabolomic profiles. The joint use of gene and metabolite information contributes to accurate evaluation of the topological importance of genes and reproducible pathway activities. We constructed classifiers using reproducible pathway activities for precise cancer classification and risk metabolic pathway identification. We applied the proposed method to the classification of prostate cancer. Within-dataset experiments and cross-dataset experiments on three independent datasets demonstrated that the proposed method achieved a more accurate and robust overall performance compared to several existing classification methods. The resulting risk pathways and topologically important differential genes and metabolites provide biologically informative models for prostate cancer prognosis and therapeutic strategies development. <s> BIB010 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Introduction <s> Graph clustering is an important technique to understand the relationships between the vertices in a big graph. In this paper, we propose a novel random-walk-based graph clustering method. The proposed method restricts the reach of the walking agent using an inflation function and a normalization function. We analyze the behavior of the limited random walk procedure and propose a novel algorithm for both global and local graph clustering problems. Previous random-walk-based algorithms depend on the chosen fitness function to find the clusters around a seed vertex. The proposed algorithm tackles the problem in an entirely different manner. We use the limited random walk procedure to find attracting vertices in a graph and use them as features to cluster the vertices. According to the experimental results on the simulated graph data and the real-world big graph data, the proposed method is superior to the state-of-the-art methods in solving graph clustering problems. Since the proposed method uses the embarrassingly parallel paradigm, it can be efficiently implemented and embedded in any parallel computing environment such as a MapReduce framework. Given enough computing resources, we are capable of clustering graphs with millions of vertices and hundreds millions of edges in a reasonable time. <s> BIB011 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Introduction <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> BIB012 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Introduction <s> Accurately predicting the survival outcome of patients is of great importance in clinical cancer research. In the past decade, building survival prediction models based on gene expression data has received increasing interest. However, the existing methods are mainly based on individual gene signatures, which are known to have limited prediction accuracy on independent datasets and unclear biological relevance. Here, we propose a novel pathway-based survival prediction method called DRWPSurv in order to accurately predict survival outcome. DRWPSurv integrates gene expression profiles and prior gene interaction information to topologically infer survival associated pathway activities, and uses the pathway activities as features to construct Lasso-Cox model. It uses topological importance of genes evaluated by directed random walk to enhance the robustness of pathway activities and thereby improve the predictive performance. We applied DRWPSurv on three independent breast cancer datasets and compared the predictive performance with a traditional gene-based method and four pathway-based methods. Results showed that pathway-based methods obtained comparable or better predictive performance than the gene-based method, whereas DRWPSurv could predict survival outcome with better accuracy and robustness among the pathway-based methods. In addition, the risk pathways identified by DRWPSurv provide biologically informative models for breast cancer prognosis and treatment. <s> BIB013 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Introduction <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> Introduction <s> Accurately predicting patient risk and identifying survival biomarkers are two important tasks in survival analysis. For the emerging high-throughput gene expression data, random survival forest (RSF) is attracting more and more attention as it not only shows excellent performance on survival prediction problems with high-dimensional variables, but also is capable of identifying important variables according to variable importance automatically calculated within the algorithm. However, RSF still suffers from some problems such as limited predictive accuracy on independent datasets and limited biological interpretation of survival biomarkers. In this study, we integrated gene interaction information into a Reweighted RSF model (RRSF) to improve predictive accuracy and identify biologically meaningful survival markers. We applied RRSF to the prediction of patients with glioblastoma multiforme (GBM) and esophageal squamous cell carcinoma (ESCC). With a reconstructed global pathway network and an mRNA-lncRNA co-expression network as the prior gene interaction information, RRSF showed better overall predictive performance than RSF on three GBM and two ESCC datasets. In addition, RRSF identified a two-gene and three-lncRNA signature, which showed robust prognostic values and had high biological relevance to the development of GBM and ESCC, respectively. <s> BIB015 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Introduction <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> BIB016 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Introduction <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> BIB017 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Introduction <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> BIB018
Analysis of gene expression levels is essential in studying and detecting genes functions. According to Chandra and Tripathi BIB014 , genes that have similar gene expression levels are likely to involve similar biological functions. The authors showed that the clustering process was quite useful to identify co-expressed genes in a group of genes and, in addition, to detect unique genes in different groups. groups. Therefore, clustering can be quite helpful to extract valuable knowledge from a large amount of biological data BIB002 , which could lead to prevention, prognosis, and treatment in biomedical research. Cai et al. BIB005 developed a random walk-based technique to cluster similar genes. The authors show that the proposed method was useful in strengthening the interaction between genes by considering the types of interactions that exist in the same group of genes. Many previous random walk-based methods managed to extract local information from a large graph without knowledge of the whole graph data BIB011 . In a random walk-based method, a gene is important if it interacts with many other genes BIB008 BIB010 BIB013 BIB015 . As illustrated in Figure 1 , gene 1 has a higher degree than gene 2 (two outgoing links) compared to one outgoing link from gene 3 to gene 4. In this case, gene 1 is the most important gene among the four genes shown in the hypothetical gene network. Several previous studies have noted the importance of clustering to identify co-expressed genes in a cluster and inactive genes in another cluster BIB014 BIB016 . Clustering can also discover the fundamental hidden structure of biomedical data, which can be used for diagnosis and treatments BIB016 . 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 BIB017 . 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 BIB017 BIB018 . 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  BIB009 . 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 BIB017 . 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 BIB012 . This paper focuses on reviewing existing computational methods on genes clustering using the notion of optimizing the objective function and validation.