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 181 records · Page 10Linked to original sources
PubMed2006

Metric for measuring the effectiveness of clustering of DNA microarray expression.

BACKGROUND: The recent advancement of microarray technology with lower noise and better affordability makes it possible to determine expression of several thousand genes simultaneously. The differentially expressed genes are filtered first and then clustered based on the expression profiles of the genes. A large number of clustering algorithms and distance measuring matrices are proposed in the literature. The popular ones among them include hierarchal clustering and k-means clustering. These algorithms have often used the Euclidian distance or Pearson correlation distance. The biologists or the practitioners are often confused as to which algorithm to use since there is no clear winner among algorithms or among distance measuring metrics. Several validation indices have been proposed in the literature and these are based directly or indirectly on distances; hence a method that uses any of these indices does not relate to any biological features such as biological processes or molecular functions. RESULTS: In this paper we have proposed a metric to measure the effectiveness of clustering algorithms of genes by computing inter-cluster cohesiveness and as well as the intra-cluster separation with respect to biological features such as biological processes or molecular functions. We have applied this metric to the clusters on the data set that we have created as part of a larger study to determine the cancer suppressive mechanism of a class of chemicals called retinoids.We have considered hierarchal and k-means clustering with Euclidian and Pearson correlation distances. Our results show that genes of similar expression profiles are more likely to be closely related to biological processes than they are to molecular functions. The findings have been supported by many works in the area of gene clustering. CONCLUSION: The best clustering algorithm of genes must achieve cohesiveness within a cluster with respect to some biological features, and as well as maximum separation between clusters in terms of the distribution of genes of a behavioral group across clusters. We claim that our proposed metric is novel in this respect and that it provides a measure of both inter and intra cluster cohesiveness. Best of all, computation of the proposed metric is easy and it provides a single quantitative value, which makes comparison of different algorithms easier. The maximum cluster cohesiveness and the maximum intra-cluster separation are indicated by the metric when its value is 0.We have demonstrated the metric by applying it to a data set with gene behavioral groupings such as biological process and molecular functions. The metric can be easily extended to other features of a gene such as DNA binding sites and protein-protein interactions of the gene product, special features of the intron-exon structure, promoter characteristics, etc. The metric can also be used in other domains that use two different parametric spaces; one for clustering and the other one for measuring the effectiveness.

Algorithms↗
PubMedDate not supplied

Ties in proximity and clustering compounds.

Hierarchical clustering algorithms such as Wards or complete-link are commonly used in compound selection and diversity analysis. Many such applications utilize binary representations of chemical structures, such as MACCS keys or Daylight fingerprints, and dissimilarity measures, such as the Euclidean or the Soergel measure. However, hierarchical clustering algorithms can generate ambiguous results owing to what is known in the cluster analysis literature as the ties in proximity problem, i.e., compounds or clusters of compounds that are equidistant from a compound or cluster in a given collection. Ambiguous ties can occur when clustering only a few hundred compounds, and the larger the number of compounds to be clustered, the greater the chance for significant ambiguity. Namely, as the number of "ties in proximity" increases relative to the total number of proximities, the possibility of ambiguity also increases. To ensure that there are no ambiguous ties, we show by a probabilistic argument that the number of compounds needs to be less than 2(n 1/4), where n is the total number of proximities, and the measure used to generate the proximities creates a uniform distribution without statistically preferred values. The common measures do not produce uniformly distributed proximities, but rather statistically preferred values that tend to increase the number of ties in proximity. Hence, the number of possible proximities and the distribution of statistically preferred values of a similarity measure, given a bit vector representation of a specific length, are directly related to the number of ties in proximities for a given data set. We explore the ties in proximity problem, using a number of chemical collections with varying degrees of diversity, given several common similarity measures and clustering algorithms. Our results are consistent with our probabilistic argument and show that this problem is significant for relatively small compound sets.

Journal Article↗
PubMed2005

A cluster pattern algorithm for the analysis of multiparametric cell assays.

The issue of multiparametric analysis of complex single cell assays of both static and flow cytometry (SC and FC, respectively) has become common in recent years. In such assays, the analysis of changes, applying common statistical parameters and tests, often fails to detect significant differences between the investigated samples. The cluster pattern similarity (CPS) measure between two sets of gated clusters is based on computing the difference between their density distribution functions' set points. The CPS was applied for the discrimination between two observations in a four-dimensional parameter space. The similarity coefficient (r) ranges between 0 (perfect similarity) to 1 (dissimilar). Three CPS validation tests were carried out: on the same stock samples of fluorescent beads, yielding very low r's (0, 0.066); and on two cell models: mitogenic stimulation of peripheral blood mononuclear cells (PBMC), and apoptosis induction in Jurkat T cell line by H2O2. In both latter cases, r indicated similarity (r < 0.23) within the same group, and dissimilarity (r > 0.48) otherwise. This classification and algorithm approach offers a measure of similarity between samples. It relies on the multidimensional pattern of the sample parameters. The algorithm compensates for environmental drifts in this apparatus and assay; it also may be applied to more than four dimensions.

Algorithms↗
PubMed1993

Cross-validation of protein structural class prediction using statistical clustering and neural networks.

We present an approach to predicting protein structural class that uses amino acid composition and hydrophobic pattern frequency information as input to two types of neural networks: (1) a three-layer back-propagation network and (2) a learning vector quantization network. The results of these methods are compared to those obtained from a modified Euclidean statistical clustering algorithm. The protein sequence data used to drive these algorithms consist of the normalized frequency of up to 20 amino acid types and six hydrophobic amino acid patterns. From these frequency values the structural class predictions for each protein (all-alpha, all-beta, or alpha-beta classes) are derived. Examples consisting of 64 previously classified proteins were randomly divided into multiple training (56 proteins) and test (8 proteins) sets. The best performing algorithm on the test sets was the learning vector quantization network using 17 inputs, obtaining a prediction accuracy of 80.2%. The Matthews correlation coefficients are statistically significant for all algorithms and all structural classes. The differences between algorithms are in general not statistically significant. These results show that information exists in protein primary sequences that is easily obtainable and useful for the prediction of protein structural class by neural networks as well as by standard statistical clustering algorithms.

Algorithms↗
PubMed2003

EXCAVATOR: a computer program for efficiently mining gene expression data.

Massive amounts of gene expression data are generated using microarrays for functional studies of genes and gene expression data clustering is a useful tool for studying the functional relationship among genes in a biological process. We have developed a computer package EXCAVATOR for clustering gene expression profiles based on our new framework for representing gene expression data as a minimum spanning tree. EXCAVATOR uses a number of rigorous and efficient clustering algorithms. This program has a number of unique features, including capabilities for: (i) data- constrained clustering; (ii) identification of genes with similar expression profiles to pre-specified seed genes; (iii) cluster identification from a noisy background; (iv) computational comparison between different clustering results of the same data set. EXCAVATOR can be run from a Unix/Linux/DOS shell, from a Java interface or from a Web server. The clustering results can be visualized as colored figures and 2-dimensional plots. Moreover, EXCAVATOR provides a wide range of options for data formats, distance measures, objective functions, clustering algorithms, methods to choose number of clusters, etc. The effectiveness of EXCAVATOR has been demonstrated on several experimental data sets. Its performance compares favorably against the popular K-means clustering method in terms of clustering quality and computing time.

Algorithms↗
PubMed2006

A study on fuzzy C-means clustering-based systems in automatic spike detection.

In this study, different systems based on the fuzzy C-means (FCM) clustering algorithm are utilized for the detection of epileptic spikes in electroencephalogram (EEG) records. The systems are constructed as either single or two-stages. In contrast to single-stage systems, the two-stage system comprises a pre-classifier stage realized by a neural network. The FCM based two-stage system is also compared to a similar system implemented using the K-means clustering algorithm. The results imply that an FCM based two-stage system should be preferred as the spike detection system.

Algorithms↗
PubMed2001

Assessment of heart disease using fuzzy classification techniques.

In this paper we discuss the classification results of cardiac patients of ischemical cardiopathy, valvular heart disease, and arterial hypertension, based on 19 characteristics (descriptors) including ECHO data, effort testings, and age and weight. In this order we have used different fuzzy clustering algorithms, namely hierarchical fuzzy clustering, hierarchical and horizontal fuzzy characteristics clustering, and a new clustering technique, fuzzy hierarchical cross-classification. The characteristics clustering techniques produce fuzzy partitions of the characteristics involved and, thus, are useful tools for studying the similarities between different characteristics and for essential characteristics selection. The cross-classification algorithm produces not only a fuzzy partition of the cardiac patients analyzed, but also a fuzzy partition of their considered characteristics. In this way it is possible to identify which characteristics are responsible for the similarities or dissimilarities observed between different groups of patients.

Adult↗
PubMed2006

Gene expression in the cell cycle of human T lymphocytes: I. Predicted gene and protein networks.

The key genes involved in the cell cycle of human T lymphocytes were identified by iterative searches of gene-related databases, as derived also from DNA microarray experimentation, revealing and predicting interactions between those genes, assigning scores to each of the genes according to numbers of interaction for each gene weighted by significance of each interaction, and finally applying several types of clustering algorithms to genes basing on the assigned scores. All clustering algorithms applied, both hierarchical and K-means, invariably selected the same six "leader" genes involved in controlling the cell cycle of human T lymphocytes. Relations of the six genes to experimental data describing switching between stages of cell cycle of human T lymphocytes are discussed.

Algorithms↗
PubMed2000

Comparison of 2D fingerprint types and hierarchy level selection methods for structural grouping using Ward's clustering

Four different two-dimensional fingerprint types (MACCS, Unity, BCI, and Daylight) and nine methods of selecting optimal cluster levels from the output of a hierarchical clustering algorithm were evaluated for their ability to select clusters that represent chemical series present in some typical examples of chemical compound data sets. The methods were evaluated using a Ward's clustering algorithm on subsets of the publicly available National Cancer Institute HIV data set, as well as with compounds from our corporate data set. We make a number of observations and recommendations about the choice of fingerprint type and cluster level selection methods for use in this type of clustering

Journal Article↗
PubMed2005

A new algorithm for comparing and visualizing relationships between hierarchical and flat gene expression data clusterings.

MOTIVATION: Clustering is one of the most widely used methods in unsupervised gene expression data analysis. The use of different clustering algorithms or different parameters often produces rather different results on the same data. Biological interpretation of multiple clustering results requires understanding how different clusters relate to each other. It is particularly non-trivial to compare the results of a hierarchical and a flat, e.g. k-means, clustering. RESULTS: We present a new method for comparing and visualizing relationships between different clustering results, either flat versus flat, or flat versus hierarchical. When comparing a flat clustering to a hierarchical clustering, the algorithm cuts different branches in the hierarchical tree at different levels to optimize the correspondence between the clusters. The optimization function is based on graph layout aesthetics or on mutual information. The clusters are displayed using a bipartite graph where the edges are weighted proportionally to the number of common elements in the respective clusters and the weighted number of crossings is minimized. The performance of the algorithm is tested using simulated and real gene expression data. The algorithm is implemented in the online gene expression data analysis tool Expression Profiler. AVAILABILITY: http://www.ebi.ac.uk/expressionprofiler

Algorithms↗
PubMed2004

Open source clustering software.

SUMMARY: We have implemented k-means clustering, hierarchical clustering and self-organizing maps in a single multipurpose open-source library of C routines, callable from other C and C++ programs. Using this library, we have created an improved version of Michael Eisen's well-known Cluster program for Windows, Mac OS X and Linux/Unix. In addition, we generated a Python and a Perl interface to the C Clustering Library, thereby combining the flexibility of a scripting language with the speed of C. AVAILABILITY: The C Clustering Library and the corresponding Python C extension module Pycluster were released under the Python License, while the Perl module Algorithm::Cluster was released under the Artistic License. The GUI code Cluster 3.0 for Windows, Macintosh and Linux/Unix, as well as the corresponding command-line program, were released under the same license as the original Cluster code. The complete source code is available at http://bonsai.ims.u-tokyo.ac.jp/mdehoon/software/cluster. Alternatively, Algorithm::Cluster can be downloaded from CPAN, while Pycluster is also available as part of the Biopython distribution.

Algorithms↗
PubMed2006

SemBiosphere: a semantic web approach to recommending microarray clustering services.

Clustering is a popular method for analyzing microarray data. Given the large number of clustering algorithms being available, it is difficult to identify the most suitable ones for a particular task. It is also difficult to locate, download, install and run the algorithms. This paper describes a matchmaking system, SemBiosphere, which solves both problems. It recommends clustering algorithms based on some minimal user requirement inputs and the data properties. An ontology was developed in OWL, an expressive ontological language, for describing what the algorithms are and how they perform, in addition to how they can be invoked. This allows machines to "understand" the algorithms and make the recommendations. The algorithm can be implemented by different groups and in different languages, and run on different platforms at geographically distributed sites. Through the use of XML-based web services, they can all be invoked in the same standard way. The current clustering services were transformed from the non-semantic web services of the Biosphere system, which includes a variety of algorithms that have been applied to microarray gene expression data analysis. New algorithms can be incorporated into the system without too much effort. The SemBiosphere system and the complete clustering ontology can be accessed at http://yeasthub2.gersteinlab. org/sembiosphere/.

Algorithms↗
PubMed2002

Adaptive quality-based clustering of gene expression profiles.

MOTIVATION: Microarray experiments generate a considerable amount of data, which analyzed properly help us gain a huge amount of biologically relevant information about the global cellular behaviour. Clustering (grouping genes with similar expression profiles) is one of the first steps in data analysis of high-throughput expression measurements. A number of clustering algorithms have proved useful to make sense of such data. These classical algorithms, though useful, suffer from several drawbacks (e.g. they require the predefinition of arbitrary parameters like the number of clusters; they force every gene into a cluster despite a low correlation with other cluster members). In the following we describe a novel adaptive quality-based clustering algorithm that tackles some of these drawbacks. RESULTS: We propose a heuristic iterative two-step algorithm: First, we find in the high-dimensional representation of the data a sphere where the "density" of expression profiles is locally maximal (based on a preliminary estimate of the radius of the cluster-quality-based approach). In a second step, we derive an optimal radius of the cluster (adaptive approach) so that only the significantly coexpressed genes are included in the cluster. This estimation is achieved by fitting a model to the data using an EM-algorithm. By inferring the radius from the data itself, the biologist is freed from finding an optimal value for this radius by trial-and-error. The computational complexity of this method is approximately linear in the number of gene expression profiles in the data set. Finally, our method is successfully validated using existing data sets. AVAILABILITY: http://www.esat.kuleuven.ac.be/~thijs/Work/Clustering.html

Algorithms↗
PubMed2005

Noise-robust soft clustering of gene expression time-course data.

Clustering is an important tool in microarray data analysis. This unsupervised learning technique is commonly used to reveal structures hidden in large gene expression data sets. The vast majority of clustering algorithms applied so far produce hard partitions of the data, i.e. each gene is assigned exactly to one cluster. Hard clustering is favourable if clusters are well separated. However, this is generally not the case for microarray time-course data, where gene clusters frequently overlap. Additionally, hard clustering algorithms are often highly sensitive to noise. To overcome the limitations of hard clustering, we applied soft clustering which offers several advantages for researchers. First, it generates accessible internal cluster structures, i.e. it indicates how well corresponding clusters represent genes. This can be used for the more targeted search for regulatory elements. Second, the overall relation between clusters, and thus a global clustering structure, can be defined. Additionally, soft clustering is more noise robust and a priori pre-filtering of genes can be avoided. This prevents the exclusion of biologically relevant genes from the data analysis. Soft clustering was implemented here using the fuzzy c-means algorithm. Procedures to find optimal clustering parameters were developed. A software package for soft clustering has been developed based on the open-source statistical language R. The package called Mfuzz is freely available.

Algorithms↗
PubMed1979

Numerical taxonomy of Actinomadura and related actinomycetes.

One hundred and fifty-six Actinomadura strains, marker strains of related taxa, and related isolates from bagasse and fodder were the subject of numerical phenetic analyses using 90 unit characters. The data were examined using the simple matching (SSM), Jaccard (SJ) and pattern (DP) coefficients and clustering was achieved using both single and average linkage algorithms. Cluster composition was not markedly affected either by the coefficient or clustering algorithms used or by test error, estimated at 4.5%. Actinomadura dassonvillei, Actinomadura madurae and Streptomyces somaliensis formed good taxospecies, but the separation of Actinomadura pelletieri strains into two clusters by SJ and SSM analysis requires further study. The single representatives of Actinomadura helvata, Actinomadura pusilla, Actinomadura roseoviolacea, Actinomadura spadix and Actinomadura verrucosopora seemed to form new centres of variation while Actinomadura citrea and Actinomadura malachitica showed much similarity with Actinomadura madurae. Most of the isolates form bagasse and fodder were recovered in two well-defined phena, provisionally labelled clusters 'A' and 'B' which showed little similarity to either Actinomadura or Nocardia strains. The effect of the different coefficients on the aggregation of clusters is discussed.

Nocardiaceae↗
PubMed1997

Computer-assisted analysis of medulloblastoma. A cytologic study.

OBJECTIVE: To explore data from a set of cases of medulloblastoma to see whether quantitative image analysis might suggest evidence for the existence of lower and higher grade lesions. STUDY DESIGN: Fourteen consecutive cases of medulloblastoma were obtained. Smears were stained with toluidine blue. For each case, 50 nuclei were measured and a number of densitometric features extracted. RESULTS: The existence of two subgroups of cases, identified as lower and higher grade groups, was suggested by a plot of the total optical density versus nuclear area. Two nuclear texture features--the number of pixels with the same optical density value occurring consecutively in the nucleus and the proportion of pixels in the high optical density range--divided the cases into the same subgroups. The use of a clustering algorithm established two clusters that corresponded to that subgrouping except for one case. Discriminant analysis gave an identical classification, with the misplaced case having a borderline discriminant function score. An unsupervised learning algorithm based on an adaptive distance metric formed two clusters and assigned the borderline case to the low grade subgroup. The grouping obtained by quantitative analysis was only partly related to the grade of nuclear atypia subjectively evaluated. CONCLUSION: In our series of medulloblastomas, quantitative analysis provided a means of detecting differences in the nuclear size and texture that allowed the classification of cases into two subgroups.

Adult↗
PubMed2001

Fuzzy K-means clustering with missing values.

Fuzzy K-means clustering algorithm is a popular approach for exploring the structure of a set of patterns, especially when the clusters are overlapping or fuzzy. However, the fuzzy K-means clustering algorithm cannot be applied when the real-life data contain missing values. In many cases, the number of patterns with missing values is so large that if these patterns are removed, then sufficient number of patterns is not available to characterize the data set. This paper proposes a technique to exploit the information provided by the patterns with the missing values so that the clustering results are enhanced. There are various preprocessing methods to substitute the missing values before clustering the data. However, instead of repairing the data set at the beginning, the repairing can be carried out incrementally in each iteration based on the context. In that case, it is more likely that less uncertainty is added while incorporating the repair work. This scheme is further consolidated in this paper by fine-tuning the missing values using the information from other attributes. The applications of the proposed method in medical domain have produced good performance.

Algorithms↗
PubMed2003

Complementary techniques of clustering and composite pattern analysis to Saccharomyces cerevisiae gene expression.

We present the combined application of clustering and composite pattern analysis to Saccharomyces cerevisiae gene expression and sequence data. The aim is to devise a system for the efficient investigation of the upstream regions associated with regulating the coordinated transcriptional response of genes via the location of cis-acting elements. The clustering algorithm presented allows clusters to overlap in light of the fact that many genes are regulated by multiple factors and/or are associated with multiple functions in the organism. The sequence clusters are analysed for shared monad and dyad patterns. These motifs are commonly regarded as putative cis-acting regulatory elements. Computationally, dyad patterns may be difficult and expensive to discover and verify if the sequences are very large. This has highlighted the need to obtain maximally--with regards to the pattern in question--'enriched' sets of sequences to uncover these motifs. We present overlapping clusters as an ideal basis for the discovery of conserved motifs.

Algorithms↗