Clustering 100,000 protein structure decoys in minutes

Ab initio protein structure prediction methods first generate large sets of structural conformations as candidates (called decoys), and then select the most representative decoys through clustering techniques. Classical clustering methods are inefficient due to the pairwise distance calculation, and thus become infeasible when the number of decoys is large. In addition, the existing clustering approaches suffer from the arbitrariness in determining a distance threshold for proteins within a cluster: a small distance threshold leads to many small clusters, while a large distance threshold results in the merging of several independent clusters into one cluster. In this paper, we propose an efficient clustering method through fast estimating cluster centroids and efficient pruning rotation spaces. The number of clusters is automatically detected by information distance criteria. A package named ONION, which can be downloaded freely, is implemented accordingly. Experimental results on benchmark data sets suggest that ONION is 14 times faster than existing tools, and ONION obtains better selections for 31 targets, and worse selection for 19 targets compared to SPICKER’s selections. On an average PC, ONION can cluster 100,000 decoys in around 12 minutes.     

Entropy-based cluster validation and estimation of the number of clusters in gene expression data

Many external and internal validity measures have been proposed in order to estimate the number of clusters in gene expression data but as a rule they do not consider the analysis of the stability of the groupings produced by a clustering algorithm. Based on the approach assessing the predictive power or stability of a partitioning, we propose the new measure of cluster validation and the selection procedure to determine the suitable number of clusters. The validity measure is based on the estimation of the "clearness" of the consensus matrix, which is the result of a resampling clustering scheme or consensus clustering. According to the proposed selection procedure the stable clustering result is determined with the reference to the validity measure for the null hypothesis encoding for the absence of clusters. The final number of clusters is selected by analyzing the distance between the validity plots for initial and permutated data sets. We applied the selection procedure to estimate the clustering results on several datasets. As a result the proposed procedure produced an accurate and robust estimate of the number of clusters, which are in agreement with the biological knowledge and gold standards of cluster quality.     

Detecting clusters of different geometrical shapes in microarray gene expression data

MOTIVATION: Clustering has been used as a popular technique for finding groups of genes that show similar expression patterns under multiple experimental conditions. Many clustering methods have been proposed for clustering gene-expression data, including the hierarchical clustering, k-means clustering and self-organizing map (SOM). However, the conventional methods are limited to identify different shapes of clusters because they use a fixed distance norm when calculating the distance between genes. The fixed distance norm imposes a fixed geometrical shape on the clusters regardless of the actual data distribution. Thus, different distance norms are required for handling the different shapes of clusters. RESULTS: We present the Gustafson-Kessel (GK) clustering method for microarray gene-expression data. To detect clusters of different shapes in a dataset, we use an adaptive distance norm that is calculated by a fuzzy covariance matrix (F) of each cluster in which the eigenstructure of F is used as an indicator of the shape of the cluster. Moreover, the GK method is less prone to falling into local minima than the k-means and SOM because it makes decisions through the use of membership degrees of a gene to clusters. The algorithmic procedure is accomplished by the alternating optimization technique, which iteratively improves a sequence of sets of clusters until no further improvement is possible. To test the performance of the GK method, we applied the GK method and well-known conventional methods to three recently published yeast datasets, and compared the performance of each method using the Saccharomyces Genome Database annotations. The clustering results of the GK method are more significantly relevant to the biological annotations than those of the other methods, demonstrating its effectiveness and potential for clustering gene-expression data. AVAILABILITY: The software was developed using Java language, and can be executed on the platforms that JVM (Java Virtual Machine) is running. It is available from the authors upon request. SUPPLEMENTARY INFORMATION: Supplementary data are available at http://dragon.kaist.ac.kr/gk.     

生物序列的聚类分析

通过不同的聚类方式,对公共数据库中生物序列数据进行生物信息的挖掘,以达到在更广泛和更深入的框架中了解它们之间的相互关系的目的。以帕金森病相关基因所对应的mRNA序列为例,使用双序列比对的得分值作为序列之间的距离定义。同时为解决不同聚类分析之间的差异,分别采用模糊聚类和层次聚类两种不同的方法进行聚类分析。并由不同聚类方法得到的一致分类聚类的结果为基因功能分类提供支持,为进一步揭示生物序列所蕴涵的生物学知识和生物学规律提供可参考的依据。     

Polar Chemoreceptor Clustering by Coupled Trimers of Dimers

Receptors of bacterial chemotaxis form clusters at the cell poles, where clusters act as “antennas” to amplify small changes in ligand concentration. It is worthy of note that chemoreceptors cluster at multiple length scales. At the smallest scale, receptors form dimers, which assemble into stable timers of dimers. At a large scale, trimers form large polar clusters composed of thousands of receptors. Although much is known about the signaling properties emerging from receptor clusters, it is unknown how receptors localize at the cell poles and what the determining factors are for cluster size. Here, we present a model of polar receptor clustering based on coupled trimers of dimers, where cluster size is determined as a minimum of the cluster-membrane free energy. This energy has contributions from the cluster-membrane elastic energy, penalizing large clusters due to their high intrinsic curvature, and receptor-receptor coupling that favors large clusters. We find that the reduced cluster-membrane curvature mismatch at the curved cell poles leads to large and robust polar clusters, in line with experimental observation, whereas lateral clusters are efficiently suppressed.     

Parallel Clustering Algorithm for Large Data Sets with Applications in Bioinformatics

Large sets of bioinformatical data provide a challenge in time consumption while solving the cluster identification problem, and that is why a parallel algorithm is so needed for identifying dense clusters in a noisy background. Our algorithm works on a graph representation of the data set to be analyzed. It identifies clusters through the identification of densely intraconnected subgraphs. We have employed a minimum spanning tree (MST) representation of the graph and solve the cluster identification problem using this representation. The computational bottleneck of our algorithm is the construction of an MST of a graph, for which a parallel algorithm is employed. Our high-level strategy for the parallel MST construction algorithm is to first partition the graph, then construct MSTs for the partitioned subgraphs and auxiliary bipartite graphs based on the subgraphs, and finally merge these MSTs to derive an MST of the original graph. The computational results indicate that when running on 150 CPUs, our algorithm can solve a cluster identification problem on a data set with 1,000,000 data points almost 100 times faster than on single CPU, indicating that this program is capable of handling very large data clustering problems in an efficient manner. We have implemented the clustering algorithm as the software CLUMP.     

Inferential Clustering Approach for Microarray Experiments with Replicated Measurements

Cluster analysis has proven to be a useful tool for investigating the association structure among genes in a microarray data set. There is a rich literature on cluster analysis and various techniques have been developed. Such analyses heavily depend on an appropriate (dis)similarity measure. In this paper, we introduce a general clustering approach based on the confidence interval inferential methodology, which is applied to gene expression data of microarray experiments. Emphasis is placed on data with low replication (three or five replicates). The proposed method makes more efficient use of the measured data and avoids the subjective choice of a dissimilarity measure. This new methodology, when applied to real data, provides an easy-to-use bioinformatics solution for the cluster analysis of microarray experiments with replicates (see the Appendix). Even though the method is presented under the framework of microarray experiments, it is a general algorithm that can be used to identify clusters in any situation. The method's performance is evaluated using simulated and publicly available data set. Our results also clearly show that our method is not an extension of the conventional clustering method based on correlation or euclidean distance.     

Clustering microarray gene expression data using weighted Chinese restaurant process

MOTIVATION: Clustering microarray gene expression data is a powerful tool for elucidating co-regulatory relationships among genes. Many different clustering techniques have been successfully applied and the results are promising. However, substantial fluctuation contained in microarray data, lack of knowledge on the number of clusters and complex regulatory mechanisms underlying biological systems make the clustering problems tremendously challenging. RESULTS: We devised an improved model-based Bayesian approach to cluster microarray gene expression data. Cluster assignment is carried out by an iterative weighted Chinese restaurant seating scheme such that the optimal number of clusters can be determined simultaneously with cluster assignment. The predictive updating technique was applied to improve the efficiency of the Gibbs sampler. An additional step is added during reassignment to allow genes that display complex correlation relationships such as time-shifted and/or inverted to be clustered together. Analysis done on a real dataset showed that as much as 30% of significant genes clustered in the same group display complex relationships with the consensus pattern of the cluster. Other notable features including automatic handling of missing data, quantitative measures of cluster strength and assignment confidence. Synthetic and real microarray gene expression datasets were analyzed to demonstrate its performance. AVAILABILITY: A computer program named Chinese restaurant cluster (CRC) has been developed based on this algorithm. The program can be downloaded at http://www.sph.umich.edu/csg/qin/CRC/.     

Clustering of resting state networks

Background

The goal of the study was to demonstrate a hierarchical structure of resting state activity in the healthy brain using a data-driven clustering algorithm.

Methodology/Principal Findings

The fuzzy-c-means clustering algorithm was applied to resting state fMRI data in cortical and subcortical gray matter from two groups acquired separately, one of 17 healthy individuals and the second of 21 healthy individuals. Different numbers of clusters and different starting conditions were used. A cluster dispersion measure determined the optimal numbers of clusters. An inner product metric provided a measure of similarity between different clusters. The two cluster result found the task-negative and task-positive systems. The cluster dispersion measure was minimized with seven and eleven clusters. Each of the clusters in the seven and eleven cluster result was associated with either the task-negative or task-positive system. Applying the algorithm to find seven clusters recovered previously described resting state networks, including the default mode network, frontoparietal control network, ventral and dorsal attention networks, somatomotor, visual, and language networks. The language and ventral attention networks had significant subcortical involvement. This parcellation was consistently found in a large majority of algorithm runs under different conditions and was robust to different methods of initialization.

Conclusions/Significance

The clustering of resting state activity using different optimal numbers of clusters identified resting state networks comparable to previously obtained results. This work reinforces the observation that resting state networks are hierarchically organized.     

A Comparison Study on Similarity and Dissimilarity Measures in Clustering Continuous Data

Similarity or distance measures are core components used by distance-based clustering algorithms to cluster similar data points into the same clusters, while dissimilar or distant data points are placed into different clusters. The performance of similarity measures is mostly addressed in two or three-dimensional spaces, beyond which, to the best of our knowledge, there is no empirical study that has revealed the behavior of similarity measures when dealing with high-dimensional datasets. To fill this gap, a technical framework is proposed in this study to analyze, compare and benchmark the influence of different similarity measures on the results of distance-based clustering algorithms. For reproducibility purposes, fifteen publicly available datasets were used for this study, and consequently, future distance measures can be evaluated and compared with the results of the measures discussed in this work. These datasets were classified as low and high-dimensional categories to study the performance of each measure against each category. This research should help the research community to identify suitable distance measures for datasets and also to facilitate a comparison and evaluation of the newly proposed similarity or distance measures with traditional ones.     

Clustering vertical ground reaction force curves produced during countermovement jumps

The aim of this study is to assess and compare the performance of commonly used hierarchical, partitional (k-means) and Gaussian model-based (Expectation–Maximization algorithm) clustering techniques to appropriately identify subgroup patterns within vertical ground reaction force data, using a continuous waveform analysis. In addition, we also compared the performance across each technique using normalized and non-normalization input scores. Both generated and real data (one hundred and twenty two vertical jumps) were analyzed. The performance of each cluster technique was measured by assessing the ability to explain variances in jump height using a stepwise regression analysis. Only k-means (normalized scores; 82%) and hierarchical clustering (normalized scores; 85%) were able to extend the ability to describe variances in jump height beyond that achieved using the group analysis (i.e. one cluster; 78%). Further, our findings strongly indicate the need to normalize the input data (similarity measure) when clustering. In contrast to the group analysis, the subgroup analysis was able to identify cluster specific phases of variance, which improved the ability to explain variances in jump height, due to the identification of cluster specific predictor variables. Our findings therefore highlight the benefit of performing a subgroup analysis and may explain, at least in part, the contrasting findings between previous studies that used a single group level of analysis.     

Dense Neuron Clustering Explains Connectivity Statistics in Cortical Microcircuits

Local cortical circuits appear highly non-random, but the underlying connectivity rule remains elusive. Here, we analyze experimental data observed in layer 5 of rat neocortex and suggest a model for connectivity from which emerge essential observed non-random features of both wiring and weighting. These features include lognormal distributions of synaptic connection strength, anatomical clustering, and strong correlations between clustering and connection strength. Our model predicts that cortical microcircuits contain large groups of densely connected neurons which we call clusters. We show that such a cluster contains about one fifth of all excitatory neurons of a circuit which are very densely connected with stronger than average synapses. We demonstrate that such clustering plays an important role in the network dynamics, namely, it creates bistable neural spiking in small cortical circuits. Furthermore, introducing local clustering in large-scale networks leads to the emergence of various patterns of persistent local activity in an ongoing network activity. Thus, our results may bridge a gap between anatomical structure and persistent activity observed during working memory and other cognitive processes.     

基于聚类分析方法的酒后人脑状态研究

目的:本文对酒精引起的人脑状态变化进行讨论。通过对客观记录的受试者摄入酒精事件的脑电图数据进行系统聚类分析,从而分析摄入酒精事件与21导联电极分类的关系,进而为有关人脑的其它研究提供实验和理论根据。方法:选取4名习惯用右手、健康的人进行实验,采用标准21个脑电极的10-20导联系统,获取受试者在安静闭眼和摄入一定量啤酒的2个事件的脑电图数据。然后进行数据分析。数据分析的方法是系统聚类分析方法。程序实现采用独立设计的脑电图分析工具箱和聚类分析程序。结果:对脑电图数据聚类分析后发现,未喝酒时脑电活动大致按前额部和中央、后头部、两侧得到3个聚类簇;摄入200毫升啤酒后,受试者P1和P2的大部分额部电极、中央部电极以及后头部电极聚类为一个簇,个别颞部、后头部电极聚类为一个簇,或单个电极独立为一簇,形成孤立点;摄入400毫升啤酒后,受试者P3和P4的大部分额极电极、额部电极、中央部电极以及后头部电极聚类为一个簇,个别额部、中央部、颞部单个电极独立为一簇,形成孤立点。结论:脑电活动对摄入酒精有显著反应。由于人在安静闭眼状态下,后头部记录到的α波较为显著,所以未喝酒时前后头部脑电信号相关性较弱,受试者前后头部的电极基本不在一个聚类簇中;摄入酒精后,受试者大部分额部、中央部和后头部电极聚类为一簇,即前后头部脑电信号的相关性增强,这说明在酒精的作用下,前头部α波增加,α波呈现扩大和增强的趋势。     

Inference from clustering with application to gene-expression microarrays.

There are many algorithms to cluster sample data points based on nearness or a similarity measure. Often the implication is that points in different clusters come from different underlying classes, whereas those in the same cluster come from the same class. Stochastically, the underlying classes represent different random processes. The inference is that clusters represent a partition of the sample points according to which process they belong. This paper discusses a model-based clustering toolbox that evaluates cluster accuracy. Each random process is modeled as its mean plus independent noise, sample points are generated, the points are clustered, and the clustering error is the number of points clustered incorrectly according to the generating random processes. Various clustering algorithms are evaluated based on process variance and the key issue of the rate at which algorithmic performance improves with increasing numbers of experimental replications. The model means can be selected by hand to test the separability of expected types of biological expression patterns. Alternatively, the model can be seeded by real data to test the expected precision of that output or the extent of improvement in precision that replication could provide. In the latter case, a clustering algorithm is used to form clusters, and the model is seeded with the means and variances of these clusters. Other algorithms are then tested relative to the seeding algorithm. Results are averaged over various seeds. Output includes error tables and graphs, confusion matrices, principal-component plots, and validation measures. Five algorithms are studied in detail: K-means, fuzzy C-means, self-organizing maps, hierarchical Euclidean-distance-based and correlation-based clustering. The toolbox is applied to gene-expression clustering based on cDNA microarrays using real data. Expression profile graphics are generated and error analysis is displayed within the context of these profile graphics. A large amount of generated output is available over the web.     

Clustering threshold gradient descent regularization: with applications to microarray studies

MOTIVATION: An important goal of microarray studies is to discover genes that are associated with clinical outcomes, such as disease status and patient survival. While a typical experiment surveys gene expressions on a global scale, there may be only a small number of genes that have significant influence on a clinical outcome. Moreover, expression data have cluster structures and the genes within a cluster have correlated expressions and coordinated functions, but the effects of individual genes in the same cluster may be different. Accordingly, we seek to build statistical models with the following properties. First, the model is sparse in the sense that only a subset of the parameter vector is non-zero. Second, the cluster structures of gene expressions are properly accounted for. RESULTS: For gene expression data without pathway information, we divide genes into clusters using commonly used methods, such as K-means or hierarchical approaches. The optimal number of clusters is determined using the Gap statistic. We propose a clustering threshold gradient descent regularization (CTGDR) method, for simultaneous cluster selection and within cluster gene selection. We apply this method to binary classification and censored survival analysis. Compared to the standard TGDR and other regularization methods, the CTGDR takes into account the cluster structure and carries out feature selection at both the cluster level and within-cluster gene level. We demonstrate the CTGDR on two studies of cancer classification and two studies correlating survival of lymphoma patients with microarray expressions. AVAILABILITY: R code is available upon request. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.     

Using Hamming Distance as Information for SNP-Sets Clustering and Testing in Disease Association Studies

The availability of high-throughput genomic data has led to several challenges in recent genetic association studies, including the large number of genetic variants that must be considered and the computational complexity in statistical analyses. Tackling these problems with a marker-set study such as SNP-set analysis can be an efficient solution. To construct SNP-sets, we first propose a clustering algorithm, which employs Hamming distance to measure the similarity between strings of SNP genotypes and evaluates whether the given SNPs or SNP-sets should be clustered. A dendrogram can then be constructed based on such distance measure, and the number of clusters can be determined. With the resulting SNP-sets, we next develop an association test HDAT to examine susceptibility to the disease of interest. This proposed test assesses, based on Hamming distance, whether the similarity between a diseased and a normal individual differs from the similarity between two individuals of the same disease status. In our proposed methodology, only genotype information is needed. No inference of haplotypes is required, and SNPs under consideration do not need to locate in nearby regions. The proposed clustering algorithm and association test are illustrated with applications and simulation studies. As compared with other existing methods, the clustering algorithm is faster and better at identifying sets containing SNPs exerting a similar effect. In addition, the simulation studies demonstrated that the proposed test works well for SNP-sets containing a large proportion of neutral SNPs. Furthermore, employing the clustering algorithm before testing a large set of data improves the knowledge in confining the genetic regions for susceptible genetic markers.     

Evaluation and optimization of clustering in gene expression data analysis

MOTIVATION: A measurement of cluster quality is needed to choose potential clusters of genes that contain biologically relevant patterns of gene expression. This is strongly desirable when a large number of gene expression profiles have to be analyzed and proper clusters of genes need to be identified for further analysis, such as the search for meaningful patterns, identification of gene functions or gene response analysis. RESULTS: We propose a new cluster quality method, called stability, by which unsupervised learning of gene expression data can be performed efficiently. The method takes into account a cluster's stability on partition. We evaluate this method and demonstrate its performance using four independent, real gene expression and three simulated datasets. We demonstrate that our method outperforms other techniques listed in the literature. The method has applications in evaluating clustering validity as well as identifying stable clusters. AVAILABILITY: Please contact the first author.