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 235 records · Page 13Linked to original sources
PubMed2003

Detection of mutual phase synchronization in multivariate signals and application to phase ensembles and chaotic data.

This work presents a method for the detection of mutual phase synchronization in nonstationary time series. We show how the application of a cluster algorithm that considers spatiotemporal structures of data follows from the general condition of phase-synchronized data. In view of the topology of phasic data, we reformulate the K-means cluster algorithm on a flat torus and apply a segmentation index derived in an earlier work [A. Hutt and H. Riedel, Physica D 177, 203 (2003)]. This index is extended by means of averaging in order to reflect phase synchronization in ensembles of multivariate time series. The method is illustrated using simulated multivariate phase dynamics and arrays of chaotic systems, in which temporal segments of phase-synchronized states are registered. A comparison with results from an existing bivariate synchronization index reveals major advantages of our method.

Journal Article↗
PubMed1994

Clinical low vision resource usage prediction.

In an era of increased demands and constrained budgets, it is necessary to make the best use of all available resources. This is difficult when specialized vision care, such as low vision clinical assessment, is involved because of the heterogeneity of the patient populations seen by such clinics. PURPOSE. This research attempts to discover if these diverse patient populations can be identified and clustered into groups based upon similarity of clinical resources use. Specifically, the inquiry examines the potential for a low vision patient resource utilization classification scheme at the Low Vision Clinic (LVC) in the Centre for Sight Enhancement (CSE), University of Waterloo. METHODS. From a sample of 99 patients consulting the LVC in a 3-month period, retrospective data collection involved abstracting and coding medical records containing information detailing each patient's demographic, diagnostic, therapeutic, and resource utilization characteristics. Cluster analysis using Hartigan's block clustering algorithm was then applied to the data. A replication study was completed using a sample of 99 patients visiting the LVC 1 year later. RESULTS. Patients can be classified into five iso-resource groups, hereby termed low vision patient resource groups (LVPRGs). The clusters represent a resource consistent and clinically coherent scheme for classifying low vision patients based upon resource requirements. As a measure of repeatability, the groups reemerged in the replication study. CONCLUSIONS. If the groupings demonstrate robustness in a field test, clustering algorithms in general, and LVPRGs in specific, may offer useful tools to enhance resource utilization in the LVC setting.

Adult↗
PubMed2002

DNA microarrays: a new diagnostic tool and its implications in colorectal cancer.

Effective treatment of colorectal cancer requires early detection and diagnostic and prognostic accuracy in characterizing patients of various risk groups. The development of DNA microarray makes it possible to analyze thousands of genes in a single tissue sample in one experiment and to characterize the biological behavior of colorectal cancer cells. Different cluster algorithms have been used to analyze large datasets on gene expression data, and initial results show significant differences between colorectal cancer and normal colon tissue. Although more than 6000 genes have been analyzed between colorectal cancer and normal tissue, different expression levels have been found in only 100-500 transcripts depending on the cluster algorithm. Most transcripts belong to genes involved in cell growth regulation, differentiation of cells, ribosomal proteins or metalloproteinase. A future goal in microarray technology will be the development of clustered gene chips which characterize each tumor type specifically and focus on gene expression that specifies cell identity.

Biomarkers, Tumor↗
PubMed2003

An automated method for finding molecular complexes in large protein interaction networks.

BACKGROUND: Recent advances in proteomics technologies such as two-hybrid, phage display and mass spectrometry have enabled us to create a detailed map of biomolecular interaction networks. Initial mapping efforts have already produced a wealth of data. As the size of the interaction set increases, databases and computational methods will be required to store, visualize and analyze the information in order to effectively aid in knowledge discovery. RESULTS: This paper describes a novel graph theoretic clustering algorithm, "Molecular Complex Detection" (MCODE), that detects densely connected regions in large protein-protein interaction networks that may represent molecular complexes. The method is based on vertex weighting by local neighborhood density and outward traversal from a locally dense seed protein to isolate the dense regions according to given parameters. The algorithm has the advantage over other graph clustering methods of having a directed mode that allows fine-tuning of clusters of interest without considering the rest of the network and allows examination of cluster interconnectivity, which is relevant for protein networks. Protein interaction and complex information from the yeast Saccharomyces cerevisiae was used for evaluation. CONCLUSION: Dense regions of protein interaction networks can be found, based solely on connectivity data, many of which correspond to known protein complexes. The algorithm is not affected by a known high rate of false positives in data from high-throughput interaction techniques. The program is available from ftp://ftp.mshri.on.ca/pub/BIND/Tools/MCODE.

Algorithms↗
PubMed2005

Comparative gene expression analysis by differential clustering approach: application to the Candida albicans transcription program.

Differences in gene expression underlie many of the phenotypic variations between related organisms, yet approaches to characterize such differences on a genome-wide scale are not well developed. Here, we introduce the "differential clustering algorithm" for revealing conserved and diverged co-expression patterns. Our approach is applied at different levels of organization, ranging from pair-wise correlations within specific groups of functionally linked genes, to higher-order correlations between such groups. Using the differential clustering algorithm, we systematically compared the transcription program of the fungal pathogen Candida albicans with that of the model organism Saccharomyces cerevisiae. Many of the identified differences are related to the differential requirement for mitochondrial function in the two yeasts. Distinct regulation patterns of cell cycle genes and of amino acid metabolic genes were also revealed and, in some cases, could be linked to the differential appearance of cis-regulatory elements in the gene promoter regions. Our study provides a comprehensive framework for comparative gene expression analysis and a rich source of hypotheses for uncharacterized open reading frames and putative cis-regulatory elements in C. albicans.

Candida albicans↗
PubMed1990

Fuzzy sets-based classification of electron microscopy images of biological macromolecules with an application to ribosomal particles.

Pattern recognition methods based on the theory of fuzzy sets are tested for their ability to classify electron microscopy images of biological specimens. The concept of fuzzy sets was chosen for its ability to represent classes of objects that are vaguely described from the measured data. A number of partitional clustering algorithms and an extensive set of cluster-validity functionals (some already reported and some newly developed) have been applied to a test-data set and to two real-data sets of images. One of the real-data sets corresponded to images of the Escherichia coli 50S ribosomal subunits depleted of proteins L7/L12 and the other set to images of the E. coli 70S monosome in the range of overlap views. These two latter sets had been previously studied by another clustering methodology. The new results obtained by the application of fuzzy clustering techniques will be compared to those previously obtained and some conclusions about the consistency of these classifications will be drawn from this comparison.

Algorithms↗
PubMed2002

Invaded cluster simulations of the XY model in two and three dimensions.

The invaded cluster algorithm is used to study the XY model in two and three dimensions up to sizes 2000(2) and 120(3), respectively. A soft spin O(2) model, in the same universality class as the three-dimensional XY model, is also studied. The static critical properties of the model and the dynamical properties of the algorithm are reported. The results are K(c)=0.454 12(2) for the three-dimensional XY model and eta=0.037(2) for the three-dimensional XY universality class. For the two-dimensional XY model the results are K(c)=1.120(1) and eta=0.251(5). The invaded cluster algorithm does not show any critical slowing for the magnetization or critical temperature estimator for the two-dimensional or three-dimensional XY models.

Journal Article↗
PubMed2004

Pathway analysis of informative genes from microarray data reveals that metabolism and signal transduction genes distinguish different subtypes of lymphomas.

Recent clinicopathological studies identified a unique subgroup of diffuse large B-cell lymphoma (DLBCL) that expresses CD5 on the cell surface. This 'de novo CD5+ DLBCL' comprises 10% of all DLBCL and has a poorer prognosis than CD5- DLBCL. Comparison of gene expression profiles between de novo CD5+ DLBCLs and CD5- DLBCLs shows that de novo CD5+ DLBCL expresses high levels of integrin beta1 in tumor cells and CD36 in the vascular cells. On the other hand, comparison between mantle cell lymphomas (MCLs) and DLBCLs expectedly identified cyclin D1 as a top feature gene. To gain insight into the molecular pathway differences among the three types of lymphoma, we evaluated the functional categories of groups of genes important for the discrimination among the three groups. We first selected 280 (from 2,142) genes, according to their individual discriminatory power. We then used the gene-shaving clustering algorithm and identified 22 clusters of genes. Of the 22 clusters, six were highly correlated with the class labels of the patients and the top three clusters accounted for the major difference among the three lymphoma subtypes. A multidimensional scaling (MDS) analysis using the average genes from the top three clusters separated the three lymphoma subtypes quite well. The functions of the genes in the top three gene clusters showed a significant enrichment of metabolism and signal transduction. To further examine whether genes of particular functions reflect more faithfully the difference between the subtypes of lymphomas, we separated the 280 informative genes into six different functional groups and performed MDS analysis using each of the gene groups. Four of the gene-function groups (metabolism, signal transduction pathway, transcriptional factors, cell adhesion and migration), separated the three lymphoma subtypes well, whereas apoptosis genes and cell cycle genes did not result in good separation.

Algorithms↗
PubMed2004

Minimum entropy clustering and applications to gene expression analysis.

Clustering is a common methodology for analyzing the gene expression data. In this paper, we present a new clustering algorithm from an information-theoretic point of view. First, we propose the minimum entropy (measured on a posteriori probabilities) criterion, which is the conditional entropy of clusters given the observations. Fano's inequality indicates that it could be a good criterion for clustering. We generalize the criterion by replacing Shannon's entropy with Havrda-Charvat's structural alpha-entropy. Interestingly, the minimum entropy criterion based on structural alpha-entropy is equal to the probability error of the nearest neighbor method when alpha = 2. This is another evidence that the proposed criterion is good for clustering. With a non-parametric approach for estimating a posteriori probabilities, an efficient iterative algorithm is then established to minimize the entropy. The experimental results show that the clustering algorithm performs significantly better than k-means/medians, hierarchical clustering, SOM, and EM in terms of adjusted Rand index. Particularly, our algorithm performs very well even when the correct number of clusters is unknown. In addition, most clustering algorithms produce poor partitions in presence of outliers while our method can correctly reveal the structure of data and effectively identify outliers simultaneously.

Algorithms↗
PubMed2006

Odour encoding in olfactory neuronal networks beyond synchronization.

It has been suggested that odour encoding in olfactory systems occurs by synchronized firing in neuronal populations. Neurons correlated in terms of the Lempel-Ziv distance of spike trains and the sequential superparamagnetic clustering algorithm belong to the same cluster if they show similar, but not necessarily synchronous, firing patterns. Using multielectrode array recordings from the rat olfactory bulb, we have determined cluster incidence and stability in the neuronal network using both the Lempel-Ziv distance and a measure of synchronization. In the Lempel-Ziv paradigm, we found pronounced stabilization and destabilization effects in the neuronal network in response to odour presentation when compared with the synchronization paradigm. This suggests that synchronization alone may be insufficient for understanding olfactory coding.

Action Potentials↗
PubMed1979

Application of stepwise cluster analysis in medical research.

A stepwise clustering algorithm, a method of multivariate statistical analysis, is suggested in this paper. The algorithm is designed for solving problems connected with stepwise regression. It is efficient not only in handling both continuous and discrete variables, but also in the nonlinear relationships between the variables. The above procedure was used in an attempt to find out the causal association of esophageal cancer with its precursors, i.e. nitrates and nitrites of nitrosamines, some of which are known to be carcinogenic. An analysis has been made of the correlation between esophageal cancer as well as severe epithelial hyperplasia of the esophagus and the concentrations of NO3- and NO2- in the drinking water. The samples used were collected from 495 wells in 49 production brigades of the Yaocun Commune in Linxian County, Honan Province. The result indicates that esophageal cancer is definitely connected with the levels of NO3- (summer) and NO2- (spring) in the drinking water. Severe epithelial hyperplasia is defintely connected with the contents of NO2- and NO3- in the drinking water collected in spring, autumn and winter. Our preliminary analysis shows that the stepwise clustering algorithm is a useful statistical method to be used for medical research.

Humans↗
PubMed1998

A set-theoretic approach to database searching and clustering.

MOTIVATION: In this paper, we introduce an iterative method of database searching and apply it to design a database clustering algorithm applicable to an entire protein database. The clustering procedure relies on the quality of the database searching routine and further improves its results based on a set-theoretic analysis of a highly redundant yet efficient to generate cluster system. RESULTS: Overall, we achieve unambiguous assignment of 80% of SWISS-PROT sequences to non-overlapping sequence clusters in an entirely automatic fashion. Our results are compared to an expert-generated clustering for validation. The database searching method is fast and the clustering technique does not require time-consuming all-against-all comparison. This allows for fast clustering of large amounts of sequences. AVAILABILITY: The resulting clustering for the PIR1 (Release 51) and SWISS-PROT (Release 34) databases is available over the Internet from http://www.dkfz-heidelberg.de/tbi/services/modest/b rowsesysters.pl. CONTACT: a.krause@dkfz-heidelberg.de; m.vingron@dkfz-heidelberg.de

Algorithms↗
PubMed1986

Improved, computer-generated system for pyocin typing of Pseudomonas aeruginosa.

We applied numerical clustering algorithms to the selection of a new indicator strain set for the pyocin typing of Pseudomonas aeruginosa. The new indicator set is composed of selected indicator strains from the sets described in 1966 by Gillies and Govan (J. Pathol. Bacteriol. 91:339-345) and in 1974 by Jones, Zakanycz, Thomas, and Farmer (Appl. Microbiol. 27:400-406) and is designated the G-F set. This indicator set consists of 14 indicator strains which typed 99.5% of 114 test cultures, has a high degree of discrimination (10 patterns encompass 50% of the test strains), and provides 62.3% reproducibility of the same typing pattern in duplicate tests done on different days. The G-F set of indicator strains provides slightly higher percentages of typable cultures than either of the other two sets, has greater discriminatory capability, and is more reproducible than they are. We recommend that the G-F set of indicator strains be used instead of the two other sets for pyocin typing of P. aeruginosa. We also tested a recently described overlay procedure for pyocin testing of P. aeruginosa and found it to be superior to previous methods in that it is easier to perform, it provides answers in only 24 h instead of 48 h, and it can be used to type mucoid strains (which previous techniques could not readily do). Thus, the application of numerical clustering algorithms and use of a revised typing procedure have produced an improved system for pyocin typing of P. aeruginosa. Similar procedures may be applicable to other typing systems.

Algorithms↗
PubMed2005

Unsupervised clustering in mRNA expression profiles.

The development of microarray technologies gives scientists the ability to examine, discover and monitor the mRNA transcript levels of thousands of genes in a single experiment. Nonetheless, the tremendous amount of data that can be obtained from microarray studies presents a challenge for data analysis. The most commonly used computational approach for analyzing microarray data is cluster analysis, since the number of genes is usually very high compared to the number of samples. In this paper, we investigate the application of the recently proposed k-windows clustering algorithm on gene expression microarray data. This algorithm apart from identifying the clusters present in a data set also calculates their number and thus requires no special knowledge about the data. To improve the quality of the clustering, we employ various dimension reduction techniques and propose a hybrid one. The results obtained by the application of the algorithm exhibit high classification success.

Algorithms↗
PubMed2005

Functional magnetic resonance imaging activation detection: fuzzy cluster analysis in wavelet and multiwavelet domains.

PURPOSE: To present novel feature spaces, based on multiscale decompositions obtained by scalar wavelet and multiwavelet transforms, to remedy problems associated with high dimension of functional magnetic resonance imaging (fMRI) time series (when they are used directly in clustering algorithms) and their poor signal-to-noise ratio (SNR) that limits accurate classification of fMRI time series according to their activation contents. MATERIALS AND METHODS: Using randomization, the proposed method finds wavelet/multiwavelet coefficients that represent the activation content of fMRI time series and combines them to define new feature spaces. Using simulated and experimental fMRI data sets, the proposed feature spaces are compared to the cross-correlation (CC) feature space and their performances are evaluated. In these studies, the false positive detection rate is controlled using randomization. To compare different methods, several points of the receiver operating characteristics (ROC) curves, using simulated data, are estimated and compared. RESULTS: The proposed features suppress the effects of confounding signals and improve activation detection sensitivity. Experimental results show improved sensitivity and robustness of the proposed method compared to the conventional CC analysis. CONCLUSION: More accurate and sensitive activation detection can be achieved using the proposed feature spaces compared to CC feature space. Multiwavelet features show superior detection sensitivity compared to the scalar wavelet features.

Algorithms↗
PubMed2005

What constitutes a population for the plant parasitic nematode Globodera pallida in its native area (Peru)?

Although numerous species are distributed in discrete populations easily recognised by geographical barriers, continuous populations are a common feature of plants or marine organisms. This is particularly true for soil organisms as their habitat is continuous and their range cannot easily be assessed as they are buried below ground. In the case of organisms for which standard methods such as Capture/Mark/Recapture cannot be used, population genetics provide a straightforward approach to delimitate populations. In this study, we have pursued this topic with a soil-dwelling nematode (Globodera pallida), which parasitises potato roots and is indigenous to South America. Potential barriers to gene flow were identified using the analysis of the F(ST)/(1-F(ST)) ratio against geographical distance and spatial autocorrelation combined with model-based clustering algorithm. Inside regions, neither genetic differentiation nor isolation by distance (IBD) occur among fields less than 50 km distant. We hypothesise that the large amount of gene flow revealed by the absence of genetic structure of this organism could be due to large passive dispersion inside an agronomic area where G. pallida has a continuous distribution and is found at high density. The first evidence of genetic differentiation appeared when a field was separated from others by an area free of farms (where G. pallida is absent or rare). Among regions, a high genetic structure coupled with an IBD pattern occurs as the consequences of the limitations of passive dispersal across deep valleys or high mountains. To our knowledge, this is the first study identifying the spatial limit of a population for a plant nematode parasite.

Algorithms↗
PubMed2002

Using noise signature to optimize spike-sorting and to assess neuronal classification quality.

We have developed a simple and expandable procedure for classification and validation of extracellular data based on a probabilistic model of data generation. This approach relies on an empirical characterization of the recording noise. We first use this noise characterization to optimize the clustering of recorded events into putative neurons. As a second step, we use the noise model again to assess the quality of each cluster by comparing the within-cluster variability to that of the noise. This second step can be performed independently of the clustering algorithm used, and it provides the user with quantitative as well as visual tests of the quality of the classification.

Action Potentials↗
PubMed2000

Genetic network inference: from co-expression clustering to reverse engineering.

MOTIVATION: Advances in molecular biological, analytical and computational technologies are enabling us to systematically investigate the complex molecular processes underlying biological systems. In particular, using high-throughput gene expression assays, we are able to measure the output of the gene regulatory network. We aim here to review datamining and modeling approaches for conceptualizing and unraveling the functional relationships implicit in these datasets. Clustering of co-expression profiles allows us to infer shared regulatory inputs and functional pathways. We discuss various aspects of clustering, ranging from distance measures to clustering algorithms and multiple-cluster memberships. More advanced analysis aims to infer causal connections between genes directly, i.e. who is regulating whom and how. We discuss several approaches to the problem of reverse engineering of genetic networks, from discrete Boolean networks, to continuous linear and non-linear models. We conclude that the combination of predictive modeling with systematic experimental verification will be required to gain a deeper insight into living organisms, therapeutic targeting and bioengineering.

Animals↗