SEARCH · PubMed Health

Results for “Clustering Algorithms”

Explore indexed PubMed citations for clinical trials, systematic reviews and public health research. Read source abstracts and follow each citation to its original PubMed record.

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

At least 1,297 records · Page 72Linked to original sources

PubMed2004

Hybrid clustering for microarray image analysis combining intensity and shape features.

BACKGROUND: Image analysis is the first crucial step to obtain reliable results from microarray experiments. First, areas in the image belonging to single spots have to be identified. Then, those target areas have to be partitioned into foreground and background. Finally, two scalar values for the intensities have to be extracted. These goals have been tackled either by spot shape methods or intensity histogram methods, but it would be desirable to have hybrid algorithms which combine the advantages of both approaches. RESULTS: A new robust and adaptive histogram type method is pixel clustering, which has been successfully applied for detecting and quantifying microarray spots. This paper demonstrates how the spot shape can be effectively integrated in this approach. Based on the clustering results, a bivalence mask is constructed. It estimates the expected spot shape and is used to filter the data, improving the results of the cluster algorithm. The quality measure 'stability' is defined and evaluated on a real data set. The improved clustering method is compared with the established Spot software on a data set with replicates. CONCLUSION: The new method presents a successful hybrid microarray image analysis solution. It incorporates both shape and histogram features and is specifically adapted to deal with typical microarray image characteristics. As a consequence of the filtering step pixels are divided into three groups, namely foreground, background and deletions. This allows a separate treatment of artifacts and their elimination from the further analysis.

Algorithms↗

PubMed2006

Structures of bimetallic clusters.

We report an optimization algorithm for studying bimetallic nanoclusters. The algorithm combines two state-of-the-art methods, the genetic algorithm and the basin hopping approach, widely employed in the literature for predicting structures of pure metallic and nonmetallic clusters. To critically test the present algorithm and its use in determining the lowest-energy structures of bimetallic nanoclusters, we apply it to study the bimetallic clusters Cu(n)Au(38-n) (0< or =n< or =38). It is predicted that the Au atoms, being larger in size than the Cu atoms, prefer to occupy surface sites showing thus the segregating behavior. As the atom fraction of Cu increases, the bimetallic cluster Cu(n)Au(38-n), as a whole, first takes on an amorphous structure and is followed by dramatic changes in structure with the Cu atoms revealing hexagonal, then assuming pentagonal, and finally shifting to octahedral symmetry in the Cu-rich range.

Journal Article↗

PubMed2001

Percolation clustering: a novel approach to the clustering of gene expression patterns in Dictyostelium development.

We present a novel approach to the clustering of gene expression patterns based on the mutual connectivity of the patterns. Unlike certain widely used methods (e.g., self-organizing maps and K-means) which essentially force gene expression data into a fixed number of predetermined clustering structures, our approach aims to reveal the natural tendency of the data to cluster, in analogy to the physical phenomenon of percolation. The approach is probabilistic in nature, and as such accommodates the possibility that one gene participates in multiple clusters. The result is cast in terms of the connectivity of each gene to a certain number of (significant) clusters. A computationally efficient algorithm is developed to implement our approach. Performance of the method is illustrated by clustering both constructed data and gene expression data obtained from Dictyostelium development.

Algorithms↗

PubMed2006

Robust Bayesian clustering.

A new variational Bayesian learning algorithm for Student-t mixture models is introduced. This algorithm leads to (i) robust density estimation, (ii) robust clustering and (iii) robust automatic model selection. Gaussian mixture models are learning machines which are based on a divide-and-conquer approach. They are commonly used for density estimation and clustering tasks, but are sensitive to outliers. The Student-t distribution has heavier tails than the Gaussian distribution and is therefore less sensitive to any departure of the empirical distribution from Gaussianity. As a consequence, the Student-t distribution is suitable for constructing robust mixture models. In this work, we formalize the Bayesian Student-t mixture model as a latent variable model in a different way from Svensén and Bishop [Svensén, M., & Bishop, C. M. (2005). Robust Bayesian mixture modelling. Neurocomputing, 64, 235-252]. The main difference resides in the fact that it is not necessary to assume a factorized approximation of the posterior distribution on the latent indicator variables and the latent scale variables in order to obtain a tractable solution. Not neglecting the correlations between these unobserved random variables leads to a Bayesian model having an increased robustness. Furthermore, it is expected that the lower bound on the log-evidence is tighter. Based on this bound, the model complexity, i.e. the number of components in the mixture, can be inferred with a higher confidence.

Algorithms↗

PubMed2005

An improved biclustering algorithm and its application to gene expression spectrum analysis.

Cheng and Church algorithm is an important approach in biclustering algorithms. In this paper, the process of the extended space in the second stage of Cheng and Church algorithm is improved and the selections of two important parameters are discussed. The results of the improved algorithm used in the gene expression spectrum analysis show that, compared with Cheng and Church algorithm, the quality of clustering results is enhanced obviously, the mining expression models are better, and the data possess a strong consistency with fluctuation on the condition while the computational time does not increase significantly.

Algorithms↗

PubMed2004

Method to find community structures based on information centrality.

Community structures are an important feature of many social, biological, and technological networks. Here we study a variation on the method for detecting such communities proposed by Girvan and Newman and based on the idea of using centrality measures to define the community boundaries [M. Girvan and M. E. J. Newman, Proc. Natl. Acad. Sci. U.S.A. 99, 7821 (2002)]. We develop an algorithm of hierarchical clustering that consists in finding and removing iteratively the edge with the highest information centrality. We test the algorithm on computer generated and real-world networks whose community structure is already known or has been studied by means of other methods. We show that our algorithm, although it runs to completion in a time O(n4) , is very effective especially when the communities are very mixed and hardly detectable by the other methods.

Algorithms↗

PubMedDate not supplied

Estimation of CSF, white and gray matter volumes in hydrocephalic children using fuzzy clustering of MR images.

An algorithm and set of procedures for measuring volumes of cerebrospinal fluid (CSF), white matter, and gray matter from transaxial magnetic resonance images (MRI) of the brain are described. The algorithm is a variant of the fuzzy c-means clustering method for texture identification. This technique is used mainly to solve the problem of volume averaging of tissue compartments, but also has other advantages. It is fast, accurate, and relatively operator independent. Furthermore, it does not depend on statistical assumptions such as data normality, nor does it require any a priori heuristics. The procedure was tested successfully on imaged phantoms of known volume composition and compared with results achieved using a standard morphometric measurement approach. The procedure was also applied to brain MRIs of three clinically normal children and three age-matched children with hydrocephalus using both proton density and T2-weighted images. The algorithm was able to detect the expected increased amounts of CSF and decreased amounts of white matter characteristic of the hydrocephalic brain.

Algorithms↗

PubMed2004

Robust image segmentation using FCM with spatial constraints based on new kernel-induced distance measure.

Fuzzy c-means clustering (FCM) with spatial constraints (FCM_S) is an effective algorithm suitable for image segmentation. Its effectiveness contributes not only to the introduction of fuzziness for belongingness of each pixel but also to exploitation of spatial contextual information. Although the contextual information can raise its insensitivity to noise to some extent, FCM_S still lacks enough robustness to noise and outliers and is not suitable for revealing non-Euclidean structure of the input data due to the use of Euclidean distance (L2 norm). In this paper, to overcome the above problems, we first propose two variants, FCM_S1 and FCM_S2, of FCM_S to aim at simplifying its computation and then extend them, including FCM_S, to corresponding robust kernelized versions KFCM_S, KFCM_S1 and KFCM_S2 by the kernel methods. Our main motives of using the kernel methods consist in: inducing a class of robust non-Euclidean distance measures for the original data space to derive new objective functions and thus clustering the non-Euclidean structures in data; enhancing robustness of the original clustering algorithms to noise and outliers, and still retaining computational simplicity. The experiments on the artificial and real-world datasets show that our proposed algorithms, especially with spatial constraints, are more effective.

Algorithms↗

PubMed2004

A new, structurally nonredundant, diverse data set of protein-protein interfaces and its implications.

Here, we present a diverse, structurally nonredundant data set of two-chain protein-protein interfaces derived from the PDB. Using a sequence order-independent structural comparison algorithm and hierarchical clustering, 3799 interface clusters are obtained. These yield 103 clusters with at least five nonhomologous members. We divide the clusters into three types. In Type I clusters, the global structures of the chains from which the interfaces are derived are also similar. This cluster type is expected because, in general, related proteins associate in similar ways. In Type II, the interfaces are similar; however, remarkably, the overall structures and functions of the chains are different. The functional spectrum is broad, from enzymes/inhibitors to immunoglobulins and toxins. The fact that structurally different monomers associate in similar ways, suggests "good" binding architectures. This observation extends a paradigm in protein science: It has been well known that proteins with similar structures may have different functions. Here, we show that it extends to interfaces. In Type III clusters, only one side of the interface is similar across the cluster. This structurally nonredundant data set provides rich data for studies of protein-protein interactions and recognition, cellular networks and drug design. In particular, it may be useful in addressing the difficult question of what are the favorable ways for proteins to interact. (The data set is available at http://protein3d.ncifcrf.gov/~keskino/ and http://home.ku.edu.tr/~okeskin/INTERFACE/INTERFACES.html.)

Algorithms↗

PubMed1993

A cluster and scotoma analysis based on empiric criteria.

From a collection of 288 visual fields of glaucomatous or glaucoma suspects, 30 were selected at random and were analyzed by one expert interpreter. Visual field damage varied from nonexistent to severe. The interpreter defined clusters or scotomas subjectively according to adjacency criteria: adjacent test locations which exceeded a critical loss value were grouped as clusters or scotomas. A computer algorithm has been devised which simulates such evaluation methods. In general, a standard setting of several parameters produced a cluster display containing the same number of clusters as determined by the expert interpreter. Another display mode grouped clusters according to polygonal areas of a predetermined size (Voronoi diagram). Due to the broad selection of visual field defects, the specificity of the program with regard to various field decay patterns was small and it should thus be applicable to a broad spectrum of glaucomatous field damage.

Algorithms↗

PubMed2002

NMR implementation of a parallel search algorithm.

Recently it has been shown that the dynamics of a cluster of dipolar-coupled spins can be manipulated to store and process a large amount of information in a parallel way [Chem. Phys. Lett. 360, 161 (2002)]]. Here it is further demonstrated that it is possible to realize a cascade of parallel bitwise operations on a spin cluster so that an algorithm of parallel search can be experimentally implemented by means of nuclear magnetic resonance.

Journal Article↗

PubMed2003

Discrimination between gene expression patterns in the invasive margin and the tumour core of malignant melanomas.

Genes that determine the invasive capacity of the invasive front of malignant melanomas (MM) have not yet been systematically investigated in vivo. Therefore, we combined laser pressure catapulting (LPC) microdissection with cDNA microarray technology (DermArray, Research Genetics, representing about 5700 genes) to systematically analyse differences in gene expression profiles between the invasive margin and the tumour centre in nine cases of vertical growth phase MM. Signal-to-noise statistical algorithms combined with hierarchical clustering were performed to determine class-separating genes. The gene encoding phosphoenolpyruvate carboxykinase 1 (PEPCK), the Homo sapiens gene similar to Saccharomyces cerevisiae SSM4 (TEB4), the gene encoding ribosomal protein L19, the Homo sapiens gene similar to the Aspergillus nidulans SudD (a suppressor of the bimD6 homologue), the gene encoding the interleukin-3 receptor alpha subunit, the gene encoding the inositol 1,4,5-triphosphate 3-kinase isoenzyme, and three anonymous expressed sequence tags were identified as class-separating genes. These genes significantly discriminate between the invasive front and the tumour centre. Using this set of genes, 15 out of 18 LPC-dissected MM regions could be grouped correctly. We conclude that the candidate genes identified could spark further research on MM progression and may provide novel prognostic parameters.

Algorithms↗

PubMed2005

Cluster analysis: an alternative method for covariate selection in population pharmacokinetic modeling.

To be analyzed, the heterogeneity characterizing biological data calls for using appropriate models involving numerous variables. A high variable number could become problematic when one needs to determine a priori the most significant variable combination in order to reduce the inter-individual variability (IIV). Alternatively to multiple introductions of single variables, we propose a single introduction of a multivariate variable. We present cluster analysis as a stratification strategy that combines the initial single covariates to build a multivariate categorical covariate. It is an exploratory multivariate analysis that outlines homogeneous categories of individuals (clusters) according to similarities from the set of covariates. It includes many clustering techniques combining a distance measure and a linkage algorithm, and leading to various stratification patterns. The cluster analysis approach is illustrated by a case study on cortisol kinetics in 82 patients after intravenous bolus administration of synacthen (synthetic corticotropin). Using NONMEM, a basic infusion model was initially achieved for cortisol, and then a classical covariate selection was applied to improve IIV. The best fit was between the elimination rate constant k and the body mass index (BMI), which improved IIV of k. An alternative method is presented consisting in the population into homogeneous and non-overlapping groups by applying a cluster analysis. Such categorization (or clustering) was carried out using Euclidean distance and complete-linkage algorithm. This algorithm gave five dissimilar clusters that differed by increasing BMI, obesity duration, and waist-hip ratio. The dispersion of k according to the five clusters showed three distinctvariation ranges a priori, which corresponded a posteriori(after NONMEM modeling) to three sub-populations of k. After grouping the clusters that had similar variation ranges of k, we obtained three final clusters representing non-obese, intermediate, and extreme obese sub-populations. The pharmacokinetic model based on three clusters was better than the basic model, similar to the classical covariate model, but had a stronger interpretability: It showed that the stimulation and elimination of cortisol were higher in the extreme obese followed by intermediate then non-obese subjects.

Adrenocorticotropic Hormone↗

PubMed2006

Test of multiscaling in a diffusion-limited-aggregation model using an off-lattice killing-free algorithm.

We test the multiscaling issue of diffusion-limited-aggregation (DLA) clusters using a modified algorithm. This algorithm eliminates killing the particles at the death circle. Instead, we return them to the birth circle at a random relative angle taken from the evaluated distribution. In addition, we use a two-level hierarchical memory model that allows using large steps in conjunction with an off-lattice realization of the model. Our algorithm still seems to stay in the framework of the original DLA model. We present an accurate estimate of the fractal dimensions based on the data for a hundred clusters with 50 million particles each. We find that multiscaling cannot be ruled out. We also find that the fractal dimension is a weak self-averaging quantity. In addition, the fractal dimension, if calculated using the harmonic measure, is a nonmonotonic function of the cluster radius. We argue that the controversies in the data interpretation can be due to the weak self-averaging and the influence of intrinsic noise.

Journal Article↗

PubMed1995

A New Zealand replication of the IPAM clustering model for low back patients.

OBJECTIVE: This study examined the reliability of the three-cluster model for chronic low back pain patients found using the Integrated Psychosocial Assessment Model (IPAM). A replication study using a sample of patients from a different country was completed. PATIENTS: Seventy patients (average age = 47.05 years, SD = 16.11) with chronic low back pain of noncancer origin participated in the study. Sixty-two of these patients were attending The Auckland New Zealand Regional Pain Service, while a further eight were attending a private practice pain service in Auckland. OUTCOME MEASURES: Subjects were assessed on the IPAM, which measures pain intensity, disability, coping strategies, attitudes towards and beliefs about pain, depression and illness behaviour, the Medical Examination and Diagnostic Information Coding System, and the Multidimensional Pain Inventory. RESULTS: Cluster analyses using the kappa-means algorithm were performed on the IPAM data. The three-cluster solution was preferred according to both the Variance Ratio Criterion and cluster interpretability. Two of the three clusters correlated highly with clusters retrieved in the original study (r = 0.78, r = 0.71), while the third cluster showed partial resemblance (correlation of r = 0.31). Clusters were named "In Control," "Depressed and Disabled," and "High Deniers and Somatizisers." No differences were found on the physical pathology scores between clusters. Decision rules for cluster assignation resulted in 68% of the sample being correctly assigned. CONCLUSIONS: Support for this cluster model from two countries suggests its value in providing a multidimensional picture of patients with chronic low back pain. The possibility of using such cluster groups for determining treatment type is discussed.

Adaptation, Psychological↗

PubMed2005

Statistical evaluation of a bottom-up clustering for single particle molecular images.

We examined the statistical performance of clustering single particle molecular images by bottom-up clustering, a hierarchical algorithm, using simulated protein images with a low signal-to-noise ratio. Using covariance for the measure of similarity together with the iterative alignment, our method was found to be fairly robust against noise. Clustering tests of four known protein structures were performed at three levels of noise and with three levels of smoothing. A significant effect of smoothing was confirmed in our results for images with noise suggesting an effective degree of smoothing depending on the noise and structural features of the target molecule. The consistency of clustering results was evaluated by the average solid angle of projection, and the precision of our clustering results was checked by the average image correlation between the obtained cluster image and the true projection. Once image features are extracted appropriately, the average solid angle also represents the degree of clustering precision.

Algorithms↗

PubMedDate not supplied

SOM-based algorithms for qualitative variables.

It is well known that the SOM algorithm achieves a clustering of data which can be interpreted as an extension of Principal Component Analysis, because of its topology-preserving property. But the SOM algorithm can only process real-valued data. In previous papers, we have proposed several methods based on the SOM algorithm to analyze categorical data, which is the case in survey data. In this paper, we present these methods in a unified manner. The first one (Kohonen Multiple Correspondence Analysis, KMCA) deals only with the modalities, while the two others (Kohonen Multiple Correspondence Analysis with individuals, KMCA_ind, Kohonen algorithm on DISJonctive table, KDISJ) can take into account the individuals, and the modalities simultaneously.

Algorithms↗

PubMed1990

Simulation of paleocortex performs hierarchical clustering.

Simulations were performed of layers I and II of olfactory paleocortex, as connected to its primary input structure, olfactory bulb. Induction of synaptic long-term potentiation by means of repetitive sampling of inputs caused the simulation to organize encodings of learned cues into a hierarchical memory that uncovered statistical relationships in the cue environment, corresponding to the performance of hierarchical clustering by the biological network. Simplification led to characterization of those parts of the network responsible for the mechanism, resulting in a novel, efficient algorithm for hierarchical clustering. The hypothesis is put forward that these corticobulbar networks and circuitry of similar design in other brain regions contain computational elements sufficient to construct perceptual hierarchies for use in recognizing environmental cues.

Animals↗