A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Category 4: Density-Based Clustering <s> Clustering algorithms are attractive for the task of class identification in spatial databases. However, the application to large spatial databases rises the following requirements for clustering algorithms: minimal requirements of domain knowledge to determine the input parameters, discovery of clusters with arbitrary shape and good efficiency on large databases. The well-known clustering algorithms offer no solution to the combination of these requirements. In this paper, we present the new clustering algorithm DBSCAN relying on a density-based notion of clusters which is designed to discover clusters of arbitrary shape. DBSCAN requires only one input parameter and supports the user in determining an appropriate value for it. We performed an experimental evaluation of the effectiveness and efficiency of DBSCAN using synthetic data and real data of the SEQUOIA 2000 benchmark. The results of our experiments demonstrate that (1) DBSCAN is significantly more effective in discovering clusters of arbitrary shape than the well-known algorithm CLAR-ANS, and that (2) DBSCAN outperforms CLARANS by a factor of more than 100 in terms of efficiency. <s> BIB001 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Category 4: Density-Based Clustering <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> BIB002 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Category 4: Density-Based Clustering <s> Dense subgraphs of sparse graphs (communities), which appear in most real-world complex networks, play an important role in many contexts. Computing them however is generally expensive. We propose here a measure of similarities between vertices based on random walks which has several important advantages: it captures well the community structure in a network, it can be computed efficiently, it works at various scales, and it can be used in an agglomerative algorithm to compute efficiently the community structure of a network. We propose such an algorithm which runs in time O(mn2) and space O(n2) in the worst case, and in time O(n2log n) and space O(n2) in most real-world cases (n and m are respectively the number of vertices and edges in the input graph). <s> BIB003 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Category 4: Density-Based Clustering <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> BIB004 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Category 4: Density-Based Clustering <s> BackgroundThe etiology of cancer involves a complex series of genetic and environmental conditions. To better represent and study the intricate genetics of cancer onset and progression, we construct a network of biological interactions to search for groups of genes that compose cancer-related modules. Three cancer expression datasets are investigated to prioritize genes and interactions associated with cancer outcomes. Using a graph-based approach to search for communities of phenotype-related genes in microarray data, we find modules of genes associated with cancer phenotypes in a weighted interaction network.ResultsWe implement Walktrap, a random-walk-based community detection algorithm, to identify biological modules predisposing to tumor growth in 22 hepatocellular carcinoma samples (GSE14520), adenoma development in 32 colorectal cancer samples (GSE8671), and prognosis in 198 breast cancer patients (GSE7390). For each study, we find the best scoring partitions under a maximum cluster size of 200 nodes. Significant modules highlight groups of genes that are functionally related to cancer and show promise as therapeutic targets; these include interactions among transcription factors (SPIB, RPS6KA2 and RPS6KA6), cell-cycle regulatory genes (BRSK1, WEE1 and CDC25C), modulators of the cell-cycle and proliferation (CBLC and IRS2) and genes that regulate and participate in the map-kinase pathway (MAPK9, DUSP1, DUSP9, RIPK2). To assess the performance of Walktrap to find genomic modules (Walktrap-GM), we evaluate our results against other tools recently developed to discover disease modules in biological networks. Compared with other highly cited module-finding tools, jActiveModules and Matisse, Walktrap-GM shows strong performance in the discovery of modules enriched with known cancer genes.ConclusionsThese results demonstrate that the Walktrap-GM algorithm identifies modules significantly enriched with cancer genes, their joint effects and promising candidate genes. The approach performs well when evaluated against similar tools and smaller overall module size allows for more specific functional annotation and facilitates the interpretation of these modules. <s> BIB005 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Category 4: Density-Based Clustering <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> BIB006 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Category 4: Density-Based Clustering <s> The notion of density has been widely used in many spatial-temporal (ST) clustering methods. This paper proposes the novel notion of an ST density-wave, which is an extension of the notion of density. It also presents a new grid-based ST clustering algorithm called Gridwave based on the notion of ST density-waves and ST synchronization. The proposed algorithm can be used to discover synchronized changes in density among various locations as well as distinguish ST events and noise from market transaction data. Based on the theory of small-world networks, our algorithm can be used to evaluate ST synchronized correlations among regions with respective to the ST density over the whole network. To improve its performance, the proposed algorithm was implemented using parallel computing. To verify its feasibility, a real large-scale market transaction dataset was used to demonstrate the ST synchronized correlations and the final clustering results. Although our algorithm is applied in a domain-specific case, we suggest that the clustering notion and method could be generalized for other domain applications with similar ST data. <s> BIB007 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Category 4: Density-Based Clustering <s> Spatial data clustering has played an important role in the knowledge discovery in spatial databases. However, due to the increasing volume and diversity of data, conventional spatial clustering methods are inefficient even on moderately large data sets, and usually fail to discover clusters with diverse shapes and densities. To address these challenges, we propose a two-phase clustering method named KMDD (clustering by combining K-means with density and distance-based method) to fast find clusters with diverse shapes and densities in spatial databases. In the first phase, KMDD uses a partition-based algorithm (K-means) to cluster the data set into several relatively small spherical or ball-shaped subclusters. After that, each subcluster is given a local density; to merge subclusters, KMDD utilizes the idea that genuine cluster cores are characterized by a higher density than their neighbor subclusters and by a relatively large distance from subclusters with higher densities. Extensive experiments on both synthetic and real-world data sets demonstrate that the proposed algorithm has a near-linear time complexity with respect to the data set size and dimension, and has the capability to find clusters with diverse shapes and densities. <s> BIB008 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Category 4: Density-Based Clustering <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> BIB009 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Category 4: Density-Based Clustering <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> BIB010 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Category 4: Density-Based Clustering <s> Abstract The human papillomavirus (HPV), a common virus that infects the reproductive tract, may lead to malignant changes within the infection area in certain cases and is directly associated with such cancers as cervical cancer, anal cancer, and vaginal cancer. Identification of novel HPV infection related genes can lead to a better understanding of the specific signal pathways and cellular processes related to HPV infection, providing information for the development of more efficient therapies. In this study, several novel HPV infection related genes were predicted by a computation method based on the known genes involved in HPV infection from HPVbase. This method applied the algorithm of random walk with restart (RWR) to a protein-protein interaction (PPI) network. The candidate genes were further filtered by the permutation and association tests. These steps eliminated genes occupying special positions in the PPI network and selected key genes with strong associations to known HPV infection related genes based on the interaction confidence and functional similarity obtained from published databases, such as STRING, gene ontology (GO) terms and KEGG pathways. Our study identified 104 novel HPV infection related genes, a number of which were confirmed to relate to the infection processes and complications of HPV infection, as reported in the literature. These results demonstrate the reliability of our method in identifying HPV infection related genes. This article is part of a Special Issue entitled: Accelerating Precision Medicine through Genetic and Genomic Big Data Analysis edited by Yudong Cai & Tao Huang. <s> BIB011
Usually, the regions contain points with high density in the data space, which makes density-based clustering mistake them as clusters BIB008 . Mechanisms of aggregation in density can characterize the clustering BIB006 . A significant advantage of density-based clustering is that it can discover differently shaped clusters and noise from data BIB009 BIB010  . However, density-based clustering has a high runtime analysis to detect clusters BIB007 . DBSCAN, random walk, and Relative Core Merge (RECOME) are examples of density-based clustering BIB001 BIB006 BIB002 BIB004  . Historically, a random walk uses the theory of Markov chain  BIB003 . In most studies, the random walk has been used to infer and to optimize the structural properties of networks BIB003 BIB005 . Much of the current literature on the random walk is on ranking the genes concerning their specific probabilities from high to low  BIB011 . In literature, a random walk mostly uses the topological similarity in networks to identify genes with a similar disease.