A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Conclusions <s> MOTIVATION ::: An increasing body of literature shows that genomes of eukaryotes can contain clusters of functionally related genes. Most approaches to identify gene clusters utilize microarray data or metabolic pathway databases to find groups of genes on chromosomes that are linked by common attributes. A generalized method that can find gene clusters regardless of the mechanism of origin would provide researchers with an unbiased method for finding clusters and studying the evolutionary forces that give rise to them. ::: ::: ::: RESULTS ::: We present an algorithm to identify gene clusters in eukaryotic genomes that utilizes functional categories defined in graph-based vocabularies such as the Gene Ontology (GO). Clusters identified in this manner need only have a common function and are not constrained by gene expression or other properties. We tested the algorithm by analyzing genomes of a representative set of species. We identified species-specific variation in percentage of clustered genes as well as in properties of gene clusters including size distribution and functional annotation. These properties may be diagnostic of the evolutionary forces that lead to the formation of gene clusters. ::: ::: ::: AVAILABILITY ::: A software implementation of the algorithm and example output files are available at http://fcg.tamu.edu/C_Hunter/. <s> BIB001 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Conclusions <s> We introduce the problem of identifying representative nodes in probabilistic graphs, motivated by the need to produce different simple views to large BisoNets. We define a probabilistic similarity measure for nodes, and then apply clustering methods to find groups of nodes. Finally, a representative is output from each cluster. We report on experiments with real biomedical data, using both the k-medoids and hierarchical clustering methods in the clustering step. The results suggest that the clustering based approaches are capable of finding a representative set of nodes. <s> BIB002 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Conclusions <s> Abstract Intelligent Kernel K-Means is a fully unsupervised clustering algorithm based on kernel. It is able to cluster kernel matrix without any information regarding to the number of required clusters. Our experiment using gene expression of human colorectal carcinoma had shown that the genes were grouped into three clusters. Global silhouette value and davies-bouldin index of the resulted clusters indicated that they are trustworthy and compact. To analyze the relationship between the clustered genes and phenotypes of clinical data, we performed correlation (CR) between each of three phenotypes (distant metastasis, cancer and normal tissues, and lymph node) with genes in each cluster of original dataset and permuted dataset. The result of the correlation had shown that Cluster 1 and Cluster 2 of original dataset had significantly higher CR than that of the permuted dataset. Among the three clusters, Cluster 3 contained smallest number of genes, but 16 out of 21 genes in that cluster were genes listed in Tumor Classifier List (TCL). <s> BIB003 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Conclusions <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> BIB004 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Conclusions <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> BIB005 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Conclusions <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> BIB006 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Conclusions <s> Specialized metabolites (also called natural products or secondary metabolites) derived from bacteria, fungi, marine organisms and plants constitute an important source of antibiotics, anti-cancer agents, insecticides, immunosuppressants and herbicides. Many specialized metabolites in bacteria and fungi are biosynthesized via metabolic pathways whose enzymes are encoded by clustered genes on a chromosome. Metabolic gene clusters comprise a group of physically co-localized genes that together encode enzymes for the biosynthesis of a specific metabolite. Although metabolic gene clusters are generally not known to occur outside of microbes, several plant metabolic gene clusters have been discovered in recent years. The discovery of novel metabolic pathways is being enabled by the increasing availability of high-quality genome sequencing coupled with the development of powerful computational toolkits to identify metabolic gene clusters. To provide a comprehensive overview of various bioinformatics methods for detecting gene clusters, we compare and contrast key aspects of algorithmic logic behind several computational tools, including 'NP.searcher', 'ClustScan', 'CLUSEAN', 'antiSMASH', 'SMURF', 'MIDDAS-M', 'ClusterFinder', 'CASSIS/SMIPS' and 'C-Hunter' among others. We also review additional tools such as 'NRPSpredictor' and 'SBSPKS' that can infer substrate specificity for previously identified gene clusters. The continual development of bioinformatics methods to predict gene clusters will help shed light on how organisms assemble multi-step metabolic pathways for adaptation to various ecological niches. <s> BIB007 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Conclusions <s> Quantifying or labeling the sample type with high quality is a challenging task, which is a key step for understanding complex diseases. Reducing noise pollution to data and ensuring the extracted intrinsic patterns in concordance with the primary data structure are important in sample clustering and classification. Here we propose an effective data integration framework named as HCI (High-order Correlation Integration), which takes an advantage of high-order correlation matrix incorporated with pattern fusion analysis (PFA), to realize high-dimensional data feature extraction. On the one hand, the high-order Pearson's correlation coefficient can highlight the latent patterns underlying noisy input datasets and thus improve the accuracy and robustness of the algorithms currently available for sample clustering. On the other hand, the PFA can identify intrinsic sample patterns efficiently from different input matrices by optimally adjusting the signal effects. To validate the effectiveness of our new method, we firstly applied HCI on four single-cell RNA-seq datasets to distinguish the cell types, and we found that HCI is capable of identifying the prior-known cell types of single-cell samples from scRNA-seq data with higher accuracy and robustness than other methods under different conditions. Secondly, we also integrated heterogonous omics data from TCGA datasets and GEO datasets including bulk RNA-seq data, which outperformed the other methods at identifying distinct cancer subtypes. Within an additional case study, we also constructed the mRNA-miRNA regulatory network of colorectal cancer based on the feature weight estimated from HCI, where the differentially expressed mRNAs and miRNAs were significantly enriched in well-known functional sets of colorectal cancer, such as KEGG pathways and IPA disease annotations. All these results supported that HCI has extensive flexibility and applicability on sample clustering with different types and organizations of RNA-seq data. <s> BIB008 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Conclusions <s> Support vector machine (SVM) parameters such as penalty parameter and kernel parameters have a great influence on the complexity and accuracy of SVM model. In this paper, quantum-behaved particle swarm optimization (QPSO) has been employed to optimize the parameters of SVM, so that the classification error can be reduced. To evaluate the proposed model (QPSO-SVM), the experiment adopted seven standard classification datasets which are obtained from UCI machine learning data repository. For verification, the results of the QPSO-SVM algorithm are compared with the standard PSO, and genetic algorithm (GA) which is one of the well-known optimization algorithms. Moreover, the results of QPSO are compared with the grid search, which is a conventional method of searching parameter values. The experimental results demonstrated that the proposed model is capable to find the optimal values of the SVM parameters. The results also showed lower classification error rates compared with standard PSO and GA algorithms. <s> BIB009 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Conclusions <s> Abstract Complex networks provide a powerful tool for data representation due to its ability to describe the interplay between topological, functional, and dynamical properties of the input data. A fundamental process in network-based (graph-based) data analysis techniques is the network construction from original data usually in vector form. Here, a natural question is: How to construct an “optimal” network regarding a given processing goal? This paper investigates structural optimization in the context of network-based data classification tasks. To be specific, we propose a particle swarm optimization framework which is responsible for building a network from vector-based data set while optimizing a quality function driven by the classification accuracy. The classification process considers both topological and physical features of the training and test data and employing PageRank measure for classification according to the importance concept of a test instance to each class. Results on artificial and real-world problems reveal that data network generated using structural optimization provides better results in general than those generated by classical network formation methods. Moreover, this investigation suggests that other kinds of network-based machine learning and data mining tasks, such as dimensionality reduction and data clustering, can benefit from the proposed structural optimization method. <s> BIB010
In summary, this paper reviewed examples of existing computational methods for clustering genes with similar biological functions. As a result, we found that partitioning, hierarchical, grid-based, and density-based are the categories of clustering techniques. Clustering can identify a high-quality cluster that is helpful in biological mechanisms and could lead to the identification of new genes related to potentially known or suspected cancer genes  BIB003 BIB002 . Among the categories of clustering, grid-based and density-based techniques are more suitable to be used to cluster objects in large spatial data. These techniques are inappropriate for artificial and biological datasets such as iris, wine, breast tissue, blood transfusion, and yeast datasets BIB005  . On the other hand, density-based clustering techniques are useful if used to cluster gene expression data  . Moreover, hierarchical clustering techniques are useful to handle synthetic and real datasets (e.g., image data). However, these techniques have some limitations when the data are very large  . Finally, partitioning clustering techniques are inappropriate for non-convex data but suitable for smaller datasets BIB004  BIB008 . Grid-based clustering (CLIQUE) was more efficient than other categories of clustering (e.g., k-means clustering, DBSCAN, and AGNES), but it was difficult to identify multiple clusters in cases of high dimensional data types. Although k-means clustering (category: partitioning) was sensitive to initializing the number of clusters, it provided a higher chance of identifying prognostic markers of leukemia. A prognostic marker is useful for identifying a disease outcome, which can be helpful in cancer treatment and drug discovery as well  . However, the quality of clusters is usually affected by initializing the number of intended clusters, especially for partitioning clustering. Therefore, the optimization of the objective function and validation can help clustering techniques to identify the optimal number of clusters with better quality BIB006 BIB009 . This paper also showed the two types of optimization strategies, which are population and evolution. Most of the existing techniques used for optimization utilize population strategies. Carneiro et al. BIB010 also concluded that the use of optimization could generate better classification together with the use of clustering and topological data. In addition, this paper also reviewed clustering validation and its measurements criteria. Internal and external criteria are commonly used to measure the cluster structure. Besides, genes in clusters can belong to a specific pathway, which can reflect the genes' functioning in biological processes BIB001 . For example, BCL2 associated with X apoptosis regulator (BAX) was among the genes identified in our experimental work, which is also a prognostic marker of leukemia. The BAX gene was encoded in the pro-apoptosis proteins, which could increase its expression and decrease the expression of anti-apoptosis (e.g., Bcl-2 gene) in the treatment of leukemia  BIB007 . Moreover, clustered genes can identify metabolic gene clusters related to the discovery of metabolite in bacteria and fungi BIB007 . Identifying genes in clusters can not only allow us to discover the informative gene and the prognostic marker for the specific disease, but it can also provide a clue about the cluster dictated by signature enzymes. The signature enzyme can catalyze reactions and further tailor the product. Hence, the genes can be encoded in the pathway with enzymes. Based on the experimental work, the CLIQUE and the k-means clustering techniques produce better results in terms of classification accuracy and identifying cancer markers. Therefore, this review suggests combining clustering techniques such as CLIQUE and k-means to yield more accurate gene clustering. Although the optimal cluster analysis is the focus of this review, the findings can be applied to different areas.