Search PubMed⌕ Search

SEARCH · Search PubMed

Results for “Clustering Algorithms”

Search indexed PubMed citations on genomics, clinical trials, systematic reviews and public health. Explore titles, authors and supplied subject terms, then open the PubMed record.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 127 records · Page 7Linked to original sources
PubMed2004

Methods for detecting functional classifications in neuroimaging data.

Data-driven statistical methods are useful for examining the spatial organization of human brain function. Cluster analysis is one approach that aims to identify spatial classifications of temporal brain activity profiles. Numerous clustering algorithms are available, and no one method is optimal for all areas of application because an algorithm's performance depends on specific characteristics of the data. K-means and fuzzy clustering are popular for neuroimaging analyses, and select hierarchical procedures also appear in the literature. It is unclear which clustering methods perform best for neuroimaging data. We conduct a simulation study, based on PET neuroimaging data, to evaluate the performances of several clustering algorithms, including a new procedure that builds on the kth nearest neighbor method. We also examine three stopping rules that assist in determining the optimal number of clusters. Five hierarchical clustering algorithms perform best in our study, some of which are new to neuroimaging analyses, with Ward's and the beta-flexible methods exhibiting the strongest performances. Furthermore, Ward's and the beta-flexible methods yield the best performances for noisy data, and the popular K-means and fuzzy clustering procedures also perform reasonably well. The stopping rules also exhibit good performances for the top five clustering algorithms, and the pseudo-T2 and pseudo-F stopping rules are superior for noisy data. Based on our simulations for both noisy and unscaled PET neuroimaging data, we recommend the combined use of the pseudo-F or pseudo-T2 stopping rule along with either Ward's or the beta-flexible clustering algorithm.

Algorithms↗
PubMed2006

Randomized maps for assessing the reliability of patients clusters in DNA microarray data analyses.

OBJECTIVE: Clustering algorithms may be applied to the analysis of DNA microarray data to identify novel subgroups that may lead to new taxonomies of diseases defined at bio-molecular level. A major problem related to the identification of biologically meaningful clusters is the assessment of their reliability, since clustering algorithms may find clusters even if no structure is present. METHODOLOGY: Recently, methods based on random "perturbations" of the data, such as bootstrapping, noise injections techniques and random subspace methods have been applied to the problem of cluster validity estimation. In this framework, we propose stability measures that exploits the high dimensionality of DNA microarray data and the redundancy of information stored in microarray chips. To this end we randomly project the original gene expression data into lower dimensional subspaces, approximately preserving the distance between the examples according to the Johnson-Lindenstrauss (JL) theory. The stability of the clusters discovered in the original high dimensional space is estimated by comparing them with the clusters discovered in randomly projected lower dimensional subspaces. The proposed cluster-stability measures may be applied to validate and to quantitatively assess the reliability of the clusters obtained by a large class of clustering algorithms. RESULTS AND CONCLUSION: We tested the effectiveness of our approach with high dimensional synthetic data, whose distribution is a priori known, showing that the stability measures based on randomized maps correctly predict the number of clusters and the reliability of each individual cluster. Then we showed how to apply the proposed measures to the analysis of DNA microarray data, whose underlying distribution is unknown. We evaluated the validity of clusters discovered by hierarchical clustering algorithms in diffuse large B-cell lymphoma (DLBCL) and malignant melanoma patients, showing that the proposed reliability measures can support bio-medical researchers in the identification of stable clusters of patients and in the discovery of new subtypes of diseases characterized at bio-molecular level.

Algorithms↗
PubMed2005

TA-clustering: cluster analysis of gene expression profiles through Temporal Abstractions.

This paper describes a new technique for clustering short time series of gene expression data. The technique is a generalization of the template-based clustering and is based on a qualitative representation of profiles which are labelled using trend Temporal Abstractions (TAs); clusters are then dynamically identified on the basis of this qualitative representation. Clustering is performed in an efficient way at three different levels of aggregation of qualitative labels, each level corresponding to a distinct degree of qualitative representation. The developed TA-clustering algorithm provides an innovative way to cluster gene profiles. We show the developed method to be robust, efficient and to perform better than the standard hierarchical agglomerative clustering approach when dealing with temporal dislocations of time series. Results of the TA-clustering algorithm can be visualized as a three-level hierarchical tree of qualitative representations and as such easy to interpret. We demonstrate the utility of the proposed algorithm on a set of two simulated data sets and on a study of gene expression data from S. cerevisiae.

Algorithms↗
PubMed2004

Gene clustering based on clusterwide mutual information.

Cluster analysis of gene-wide expression data from DNA microarray hybridization studies has proved to be a useful tool for identifying biologically relevant groupings of genes and constructing gene regulatory networks. The motivation for considering mutual information is its capacity to measure a general dependence among gene random variables. We propose a novel clustering strategy based on minimizing mutual information among gene clusters. Simulated annealing is employed to solve the optimization problem. Bootstrap techniques are employed to get more accurate estimates of mutual information when the data sample size is small. Moreover, we propose to combine the mutual information criterion and traditional distance criteria such as the Euclidean distance and the fuzzy membership metric in designing the clustering algorithm. The performances of the new clustering methods are compared with those of some existing methods, using both synthesized data and experimental data. It is seen that the clustering algorithm based on a combined metric of mutual information and fuzzy membership achieves the best performance. The supplemental material is available at www.gspsnap.tamu.edu/gspweb/zxb/glioma_zxb.

Algorithms↗
PubMed2002

Computational identification of transcription factor binding sites via a transcription-factor-centric clustering (TFCC) algorithm.

While microarray-based expression profiling has facilitated the use of computational methods to find potential cis-regulatory promoter elements, few current in silico approaches explicitly link regulatory motifs with the transcription factors that bind them. We have thus developed a TF-centric clustering (TFCC) algorithm that may provide such missing information through incorporation of biological knowledge about TFs. TFCC is a semi-supervised clustering algorithm which relies on the assumption that the expression profiles of some TFs may be related to those of the genes under their control. We examined this premise and found the vicinities of TFs in expression space are often enriched with the genes they regulate. So, instead of clustering genes based on the mutual similarity of their expression profiles to each other, we used TFs as seeds to group together genes whose expression patterns correlate with that of a particular TF. Then a Gibbs sampling algorithm was applied to search for shared cis-regulatory elements in promoters of clustered genes. Our working hypothesis was that if a TF-centric cluster indeed contains many targets of the seeding TF, at least one of the discovered motifs would be the site bound by the very same TF. We tested the TFCC approach on eight cell cycle and sporulation regulating TFs whose binding sites have been previously characterized in Saccharomyces cerevisiae, and correctly identified binding site motifs for half of them. In addition, we also made de novo predictions for some unknown TF binding sites.

Algorithms↗
PubMed2006

Clustering of gene expression data: performance and similarity analysis.

BACKGROUND: DNA Microarray technology is an innovative methodology in experimental molecular biology, which has produced huge amounts of valuable data in the profile of gene expression. Many clustering algorithms have been proposed to analyze gene expression data, but little guidance is available to help choose among them. The evaluation of feasible and applicable clustering algorithms is becoming an important issue in today's bioinformatics research. RESULTS: In this paper we first experimentally study three major clustering algorithms: Hierarchical Clustering (HC), Self-Organizing Map (SOM), and Self Organizing Tree Algorithm (SOTA) using Yeast Saccharomyces cerevisiae gene expression data, and compare their performance. We then introduce Cluster Diff, a new data mining tool, to conduct the similarity analysis of clusters generated by different algorithms. The performance study shows that SOTA is more efficient than SOM while HC is the least efficient. The results of similarity analysis show that when given a target cluster, the Cluster Diff can efficiently determine the closest match from a set of clusters. Therefore, it is an effective approach for evaluating different clustering algorithms. CONCLUSION: HC methods allow a visual, convenient representation of genes. However, they are neither robust nor efficient. The SOM is more robust against noise. A disadvantage of SOM is that the number of clusters has to be fixed beforehand. The SOTA combines the advantages of both hierarchical and SOM clustering. It allows a visual representation of the clusters and their structure and is not sensitive to noises. The SOTA is also more flexible than the other two clustering methods. By using our data mining tool, Cluster Diff, it is possible to analyze the similarity of clusters generated by different algorithms and thereby enable comparisons of different clustering methods.

Algorithms↗
PubMed2002

Making sense of EST sequences by CLOBBing them.

BACKGROUND: Expressed sequence tags (ESTs) are single pass reads from randomly selected cDNA clones. They provide a highly cost-effective method to access and identify expressed genes. However, they are often prone to sequencing errors and typically define incomplete transcripts. To increase the amount of information obtainable from ESTs and reduce sequencing errors, it is necessary to cluster ESTs into groups sharing significant sequence similarity. RESULTS: As part of our ongoing EST programs investigating 'orphan' genomes, we have developed a clustering algorithm, CLOBB (Cluster on the basis of BLAST similarity) to identify and cluster ESTs. CLOBB may be used incrementally, preserving original cluster designations. It tracks cluster-specific events such as merging, identifies 'superclusters' of related clusters and avoids the expansion of chimeric clusters. Based on the Perl scripting language, CLOBB is highly portable relying only on a local installation of NCBI's freely available BLAST executable and can be usefully applied to > 95 % of the current EST datasets. Analysis of the Danio rerio EST dataset demonstrates that CLOBB compares favourably with two less portable systems, UniGene and TIGR Gene Indices. CONCLUSIONS: CLOBB provides a highly portable EST clustering solution and is freely downloaded from: http://www.nematodes.org/CLOBB

Algorithms↗
PubMed2006

Spiral ganglion cell site of excitation I: comparison of scala tympani and intrameatal electrode responses.

To determine the site of excitation on the spiral ganglion cell in response to electrical stimulation similar to that from a cochlear implant, single-fiber responses to electrical stimuli delivered by an electrode positioned in the scala tympani were compared to responses from stimuli delivered by an electrode placed in the internal auditory meatus. The response to intrameatal stimulation provided a control set of data with a known excitation site, the central axon of the spiral ganglion cell. For both intrameatal and scala tympani stimuli, the responses to single-pulse, summation, and refractory stimulus protocols were recorded. The data demonstrated that summation pulses, as opposed to single pulses, are likely to give the most insightful measures for determination of the site of excitation. Single-fiber summation data for both scala tympani and intrameatally stimulated fibers were analyzed with a clustering algorithm. Combining cluster analysis and additional numerical modeling data, it was hypothesized that the scala tympani responses corresponded to central excitation, peripheral excitation adjacent to the cell body, and peripheral excitation at a site distant from the cell body. Fibers stimulated by an intrameatal electrode demonstrated the greatest range of jitter measurements indicating that greater fiber independence may be achieved with intrameatal stimulation.

Algorithms↗
PubMed1998

A Fast and Robust Cluster Update Algorithm for Image Segmentation in Spin-Lattice Models Without Annealing. Visual Latencies Revisited.

Image segmentation in spin-lattice models relies on the fast and reliable assignment of correct labels to those groups of spins that represent the same object. Commonly used local spin-update algorithms are slow because in each iteration only a single spin is flipped and a careful annealing schedule has to be designed in order to avoid local minima and correctly label larger areas. Updating of complete spin clusters is more efficient, but often clusters that should represent different objects will be conjoined. In this study, we propose a cluster update algorithm that, similar to most local update algorithms, calculates an energy function and determines the probability for flipping a whole cluster of spins by the energy gain calculated for a neighborhood of the regarded cluster. The novel algorithm, called energy-based cluster update (ECU algorithm), is compared to its predecessors. A convergence proof is derived, and it is shown that the algorithm outperforms local update algorithms by far in speed and reliability. At the same time it is more robust and noise tolerant than other versions of cluster update algorithms, making annealing completely unnecessary. The reduction in computational effort achieved this way allows us to segment real images in about 1-5 sec on a regular workstation. The ECU-algorithm can recover fine details of the images, and it is to a large degree robust with respect to luminance-gradients across objects. In a final step, we introduce luminance dependent visual latencies (Opara and Worgotter, 1996; Worgotter, Opara, Funke, and Eysel, 1996) into the spin-lattice model. This step guarantees that only spins representing pixels with similar luminance become activated at the same time. The energy function is then computed only for the interaction of the regarded cluster with the currently active spins. This latency mechanism improves the quality of the image segmentation by another 40%. The results shown are based on the evaluation of gray-level differences. It is important to realize that all algorithmic components can be transferred easily to arbitrary image features, like disparity, texture, and motion.

Journal Article↗
PubMed2000

An algorithm for clustering cDNA fingerprints.

Clustering large data sets is a central challenge in gene expression analysis. The hybridization of synthetic oligonucleotides to arrayed cDNAs yields a fingerprint for each cDNA clone. Cluster analysis of these fingerprints can identify clones corresponding to the same gene. We have developed a novel algorithm for cluster analysis that is based on graph theoretic techniques. Unlike other methods, it does not assume that the clusters are hierarchically structured and does not require prior knowledge on the number of clusters. In tests with simulated libraries the algorithm outperformed the Greedy method and demonstrated high speed and robustness to high error rate. Good solution quality was also obtained in a blind test on real cDNA fingerprints.

Algorithms↗
PubMed2004

Protein complex prediction via cost-based clustering.

MOTIVATION: Understanding principles of cellular organization and function can be enhanced if we detect known and predict still undiscovered protein complexes within the cell's protein-protein interaction (PPI) network. Such predictions may be used as an inexpensive tool to direct biological experiments. The increasing amount of available PPI data necessitates an accurate and scalable approach to protein complex identification. RESULTS: We have developed the Restricted Neighborhood Search Clustering Algorithm (RNSC) to efficiently partition networks into clusters using a cost function. We applied this cost-based clustering algorithm to PPI networks of Saccharomyces cerevisiae, Drosophila melanogaster and Caenorhabditis elegans to identify and predict protein complexes. We have determined functional and graph-theoretic properties of true protein complexes from the MIPS database. Based on these properties, we defined filters to distinguish between identified network clusters and true protein complexes. CONCLUSIONS: Our application of the cost-based clustering algorithm provides an accurate and scalable method of detecting and predicting protein complexes within a PPI network.

Algorithms↗
PubMed2005

Visualization methods for statistical analysis of microarray clusters.

BACKGROUND: The most common method of identifying groups of functionally related genes in microarray data is to apply a clustering algorithm. However, it is impossible to determine which clustering algorithm is most appropriate to apply, and it is difficult to verify the results of any algorithm due to the lack of a gold-standard. Appropriate data visualization tools can aid this analysis process, but existing visualization methods do not specifically address this issue. RESULTS: We present several visualization techniques that incorporate meaningful statistics that are noise-robust for the purpose of analyzing the results of clustering algorithms on microarray data. This includes a rank-based visualization method that is more robust to noise, a difference display method to aid assessments of cluster quality and detection of outliers, and a projection of high dimensional data into a three dimensional space in order to examine relationships between clusters. Our methods are interactive and are dynamically linked together for comprehensive analysis. Further, our approach applies to both protein and gene expression microarrays, and our architecture is scalable for use on both desktop/laptop screens and large-scale display devices. This methodology is implemented in GeneVAnD (Genomic Visual ANalysis of Datasets) and is available at http://function.princeton.edu/GeneVAnD. CONCLUSION: Incorporating relevant statistical information into data visualizations is key for analysis of large biological datasets, particularly because of high levels of noise and the lack of a gold-standard for comparisons. We developed several new visualization techniques and demonstrated their effectiveness for evaluating cluster quality and relationships between clusters.

Algorithms↗
PubMed2007

Assignment of polar states for protein amino acid residues using an interaction cluster decomposition algorithm and its application to high resolution protein structure modeling.

We have developed a new method (Independent Cluster Decomposition Algorithm, ICDA) for creating all-atom models of proteins given the heavy-atom coordinates, provided by X-ray crystallography, and the pH. In our method the ionization states of titratable residues, the crystallographic mis-assignment of amide orientations in Asn/Gln, and the orientations of OH/SH groups are addressed under the unified framework of polar states assignment. To address the large number of combinatorial possibilities for the polar hydrogen states of the protein, we have devised a novel algorithm to decompose the system into independent interacting clusters, based on the observation of the crucial interdependence between the short range hydrogen bonding network and polar residue states, thus significantly reducing the computational complexity of the problem and making our algorithm tractable using relatively modest computational resources. We utilize an all atom protein force field (OPLS) and a Generalized Born continuum solvation model, in contrast to the various empirical force fields adopted in most previous studies. We have compared our prediction results with a few well-documented methods in the literature (WHATIF, REDUCE). In addition, as a preliminary attempt to couple our polar state assignment method with real structure predictions, we further validate our method using single side chain prediction, which has been demonstrated to be an effective way of validating structure prediction methods without incurring sampling problems. Comparisons of single side chain prediction results after the application of our polar state prediction method with previous results with default polar state assignments indicate a significant improvement in the single side chain predictions for polar residues.

Algorithms↗
PubMed2003

Comparisons and validation of statistical clustering techniques for microarray gene expression data.

MOTIVATION: With the advent of microarray chip technology, large data sets are emerging containing the simultaneous expression levels of thousands of genes at various time points during a biological process. Biologists are attempting to group genes based on the temporal pattern of their expression levels. While the use of hierarchical clustering (UPGMA) with correlation 'distance' has been the most common in the microarray studies, there are many more choices of clustering algorithms in pattern recognition and statistics literature. At the moment there do not seem to be any clear-cut guidelines regarding the choice of a clustering algorithm to be used for grouping genes based on their expression profiles. RESULTS: In this paper, we consider six clustering algorithms (of various flavors!) and evaluate their performances on a well-known publicly available microarray data set on sporulation of budding yeast and on two simulated data sets. Among other things, we formulate three reasonable validation strategies that can be used with any clustering algorithm when temporal observations or replications are present. We evaluate each of these six clustering methods with these validation measures. While the 'best' method is dependent on the exact validation strategy and the number of clusters to be used, overall Diana appears to be a solid performer. Interestingly, the performance of correlation-based hierarchical clustering and model-based clustering (another method that has been advocated by a number of researchers) appear to be on opposite extremes, depending on what validation measure one employs. Next it is shown that the group means produced by Diana are the closest and those produced by UPGMA are the farthest from a model profile based on a set of hand-picked genes. AVAILABILITY: S+ codes for the partial least squares based clustering are available from the authors upon request. All other clustering methods considered have S+ implementation in the library MASS. S+ codes for calculating the validation measures are available from the authors upon request. The sporulation data set is publicly available at http://cmgm.stanford.edu/pbrown/sporulation

Algorithms↗
PubMed1999

Clustering and the design of preference-assessment surveys in healthcare.

OBJECTIVE: To show cluster analysis as a potentially useful tool in defining common outcomes empirically and in facilitating the assessment of preferences for health states. DATA SOURCES: A survey of 224 patients with ventricular arrhythmias treated at Kaiser Permanente of Northern California. STUDY DESIGN/METHODS: Physical functioning was measured using the Duke Activity Status Index (DASI), and mental status and vitality using the Medical Outcomes Study Short Form-36 items (SF-36). A "k-means" clustering algorithm was used to identify prototypical health states, in which patients in the same cluster shared similar responses to items in the survey. PRINCIPAL FINDINGS: The clustering algorithm yielded four prototypical health states. Cluster 1 (21 percent of patients) was characterized by high scores on physical functioning, vitality, and mental health. Cluster 2 (33 percent of patients) had low physical function but high scores on vitality and mental health. Cluster 3 (29 percent of patients) had low physical function and low vitality but preserved mental health. Cluster 4 (17 percent of patients) had low scores on all scales. These clusters served as the basis of written descriptions of the health states. CONCLUSIONS: Employing a clustering algorithm to analyze health status survey data enables researchers to gain a data-driven, concise summary of the experiences of patients.

Adult↗
PubMed2004

Detection of functional modules from protein interaction networks.

Complex cellular processes are modular and are accomplished by the concerted action of functional modules (Ravasz et al., Science 2002;297:1551-1555; Hartwell et al., Nature 1999;402:C47-52). These modules encompass groups of genes or proteins involved in common elementary biological functions. One important and largely unsolved goal of functional genomics is the identification of functional modules from genomewide information, such as transcription profiles or protein interactions. To cope with the ever-increasing volume and complexity of protein interaction data (Bader et al., Nucleic Acids Res 2001;29:242-245; Xenarios et al., Nucleic Acids Res 2002;30:303-305), new automated approaches for pattern discovery in these densely connected interaction networks are required (Ravasz et al., Science 2002;297:1551-1555; Bader and Hogue, Nat Biotechnol 2002;20:991-997; Snel et al., Proc Natl Acad Sci USA 2002;99:5890-5895). In this study, we successfully isolate 1046 functional modules from the known protein interaction network of Saccharomyces cerevisiae involving 8046 individual pair-wise interactions by using an entirely automated and unsupervised graph clustering algorithm. This systems biology approach is able to detect many well-known protein complexes or biological processes, without reference to any additional information. We use an extensive statistical validation procedure to establish the biological significance of the detected modules and explore this complex, hierarchical network of modular interactions from which pathways can be inferred.

Algorithms↗
PubMed2006

Integrated analysis of multiple data sources reveals modular structure of biological networks.

It has been a challenging task to integrate high-throughput data into investigations of the systematic and dynamic organization of biological networks. Here, we presented a simple hierarchical clustering algorithm that goes a long way to achieve this aim. Our method effectively reveals the modular structure of the yeast protein-protein interaction network and distinguishes protein complexes from functional modules by integrating high-throughput protein-protein interaction data with the added subcellular localization and expression profile data. Furthermore, we take advantage of the detected modules to provide a reliably functional context for the uncharacterized components within modules. On the other hand, the integration of various protein-protein association information makes our method robust to false-positives, especially for derived protein complexes. More importantly, this simple method can be extended naturally to other types of data fusion and provides a framework for the study of more comprehensive properties of the biological network and other forms of complex networks.

Algorithms↗
PubMed2006

Study-level wavelet cluster analysis and data-driven signal models in pharmacological MRI.

In pharmacological MRI (phMRI) studies tracking signal changes following the acute administration of a compound, the spatiotemporal pattern of response is often unknown a priori. Moreover, when analysed within a general linear model (GLM) framework, the experimental paradigm of a single injection point under-informs the construction of an appropriate signal model, and information from pharmacokinetics or ancillary in vivo studies may be unavailable or insufficient to accurately describe the dynamic signal changes observed following injection of the drug. Here, we extend the application of a data-driven clustering algorithm, wavelet cluster analysis (WCA), to phMRI data from one or more groups of subjects in a study. A WCA decomposition of spatially concatenated time series' provides a compact overview of spatiotemporal response patterns across cohorts, highlighting typical temporal signatures, brain regions implicated in the response and inter-subject variability. Further, we demonstrate the use of regressors based on selected temporal components as suitable signal models in GLM-based analyses, resulting in a close fit to dynamic phMRI signal changes. This approach is illustrated with simulated data and two representative in vivo phMRI studies in the rat (nicotine and apomorphine challenges).

Animals↗