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,261 records · Page 70Linked to original sources

PubMed2007

Microsolvation of an ionic dopant in small (4)He clusters: OH(+)((3)sigma)((4)He)(N) via genetic algorithm optimizations.

The optimized spatial structures of the small clusters (with N up to 33) formed by an increasing number of (4)He atoms, which act as a microsolvent surrounding the OH(+) ionic molecular dopant, are obtained using a sum-of-potentials scheme corrected by three-body (3B) effects. The most stable structures are generated using the type of genetic algorithm described herein, and the sequential formation of regular shell structures is analyzed in detail. Possible quantum corrections for both the solvent distributions and the stable energetics are analyzed and discussed.

Journal Article↗

PubMedDate not supplied

[ClusterTree-RS: the binary tree algorithm for identification of co-regulated genes by clustering regulatory signals].

Identification of groups of co-regulated genes (regulons) is an important part of studying transcriptional regulation. One possible approach is to cluster regulatory sites that were found using experimental or computational techniques, such as phylogenetic footprinting. This strategy doesn't require a priori knowledge about co-regulation and allows finding putative new members of known groups of co-regulated genes (i.e. a new regulon). Also, it allows finding new putative regulons, which is especially important for poorly annotated genomes. We have developed ClusterTree-RS, an algorithm for clustering regulatory signals using binary trees; it is presented in this paper along with some testing results on simulated and real data. The algorithm is implemented in Java and took about 2 hours 40 minutes to cluster 1500 input signals on a computer with AMD Athlon 1.91 GHz CPU.

Algorithms↗

PubMed2006

A system for learning statistical motion patterns.

Analysis of motion patterns is an effective approach for anomaly detection and behavior prediction. Current approaches for the analysis of motion patterns depend on known scenes, where objects move in predefined ways. It is highly desirable to automatically construct object motion patterns which reflect the knowledge of the scene. In this paper, we present a system for automatically learning motion patterns for anomaly detection and behavior prediction based on a proposed algorithm for robustly tracking multiple objects. In the tracking algorithm, foreground pixels are clustered using a fast accurate fuzzy K-means algorithm. Growing and prediction of the cluster centroids of foreground pixels ensure that each cluster centroid is associated with a moving object in the scene. In the algorithm for learning motion patterns, trajectories are clustered hierarchically using spatial and temporal information and then each motion pattern is represented with a chain of Gaussian distributions. Based on the learned statistical motion patterns, statistical methods are used to detect anomalies and predict behaviors. Our system is tested using image sequences acquired, respectively, from a crowded real traffic scene and a model traffic scene. Experimental results show the robustness of the tracking algorithm, the efficiency of the algorithm for learning motion patterns, and the encouraging performance of algorithms for anomaly detection and behavior prediction.

Algorithms↗

PubMed2003

Kernel hierarchical gene clustering from microarray expression data.

MOTIVATION: Unsupervised analysis of microarray gene expression data attempts to find biologically significant patterns within a given collection of expression measurements. For example, hierarchical clustering can be applied to expression profiles of genes across multiple experiments, identifying groups of genes that share similar expression profiles. Previous work using the support vector machine supervised learning algorithm with microarray data suggests that higher-order features, such as pairwise and tertiary correlations across multiple experiments, may provide significant benefit in learning to recognize classes of co-expressed genes. RESULTS: We describe a generalization of the hierarchical clustering algorithm that efficiently incorporates these higher-order features by using a kernel function to map the data into a high-dimensional feature space. We then evaluate the utility of the kernel hierarchical clustering algorithm using both internal and external validation. The experiments demonstrate that the kernel representation itself is insufficient to provide improved clustering performance. We conclude that mapping gene expression data into a high-dimensional feature space is only a good idea when combined with a learning algorithm, such as the support vector machine that does not suffer from the curse of dimensionality. AVAILABILITY: Supplementary data at www.cs.columbia.edu/compbio/hiclust. Software source code available by request.

Algorithms↗

PubMed2005

Unsupervised pattern recognition: an introduction to the whys and wherefores of clustering microarray data.

Clustering has become an integral part of microarray data analysis and interpretation. The algorithmic basis of clustering -- the application of unsupervised machine-learning techniques to identify the patterns inherent in a data set -- is well established. This review discusses the biological motivations for and applications of these techniques to integrating gene expression data with other biological information, such as functional annotation, promoter data and proteomic data.

Algorithms↗

PubMed2005

High-throughput inference of protein-protein interfaces from unassigned NMR data.

SUMMARY: We cast the problem of identifying protein-protein interfaces, using only unassigned NMR spectra, into a geometric clustering problem. Identifying protein-protein interfaces is critical to understanding inter- and intra-cellular communication, and NMR allows the study of protein interaction in solution. However it is often the case that NMR studies of a protein complex are very time-consuming, mainly due to the bottleneck in assigning the chemical shifts, even if the apo structures of the constituent proteins are known. We study whether it is possible, in a high-throughput manner, to identify the interface region of a protein complex using only unassigned chemical shifts and residual dipolar coupling (RDC) data. We introduce a geometric optimization problem where we must cluster the cells in an arrangement on the boundary of a 3-manifold, where the arrangement is induced by a spherical quadratic form [corrected] The arrangement is induced by a spherical quadratic form, which in turn is parameterized by a SO(3)xR2. We show that this formalism derives directly from the physics of RDCs. We present an optimal algorithm for this problem that runs in O(n3 log n) time for an n-residue protein. We then use this clustering algorithm as a subroutine in a practical algorithm for identifying the interface region of a protein complex from unassigned NMR data. We present the results of our algorithm on NMR data for seven proteins from five protein complexes, and show that our approach is useful for high-throughput applications in which we seek to rapidly identify the interface region of a protein complex. AVAILABILITY: Contact authors for source code.

Algorithms↗

PubMed1986

Cluster analysis: a simple, versatile, and robust algorithm for endocrine pulse detection.

Endocrine signaling provides one critical means of physiological communication within an organism. Many endocrine signals exhibit an episodic or pulsatile configuration. In an effort to provide a versatile and statistically based algorithm for investigating the regulation of endocrine pulse signals, we have formulated a computerized algorithm in which a pulse is defined as a statistically significant increase in a "cluster" of hormone values followed by a statistically significant decrease in a second cluster of values. The increase or decrease is judged in relation to the actual experimental error expressed by the replicates in the presumptive nadir and peak data clusters. The program permits the operator to specify the cluster sizes of test peaks and pre- and postpeak nadirs. This method is largely insensitive to unstable base-line hormone concentrations and is not adversely affected by varying pulse amplitudes, widths, or configurations within the endocrine series. In addition, the simple statistical basis for this algorithm renders it minimally dependent on explicit or a priori assumptions about rates of hormone secretion or disappearance. The program has been validated for false-positive errors against a wide range of intraseries coefficients of variation (4-52%). We have illustrated its performance for profiles of luteinizing hormone, follicle-stimulating hormone, growth hormone, prolactin, adrenocorticotropic hormone, and cortisol and compared these episodic patterns with those of stable serum constituents (total serum protein and calcium), which do not exhibit pulsatile fluctuation.

Adrenocorticotropic Hormone↗

PubMed2005

Clustering gene expression data with kernel principal components.

Kernel principal component analysis (KPCA) has been applied to data clustering and graphic cut in the last couple of years. This paper discusses the application of KPCA to microarray data clustering. A new algorithm based on KPCA and fuzzy C-means is proposed. Experiments with microarray data show that the proposed algorithms is in general superior to traditional algorithms.

Algorithms↗

PubMed2002

A thematic analysis of the AIDS literature.

Faced with the need for human comprehension of any large collection of objects, a time honored approach has been to cluster the objects into groups of closely related objects. Individual groups are then summarized in some convenient manner to provide a more manageable view of the data. Such methods have been applied to document collections with mixed results. If a hard clustering of the data into mutually exclusive clusters is performed then documents are frequently forced into one cluster when they may contain important information that would also appropriately make them candidates for other clusters. If a soft clustering is used there still remains the problem of how to provide a useful summary of the data in a cluster. Here we introduce a new algorithm to produce a soft clustering of document collections that is based on the concept of a theme. A theme is conceptually a subject area that is discussed by multiple documents in the database. A theme has two potential representations that may be viewed as dual to each other. First it is represented by the set of documents that discuss the subject or theme and second it is also represented by the set of key terms that are typically used to discuss the theme. Our algorithm is an EM algorithm in which the term representation and the document representation are explicit components and each is used to refine the other in an alternating fashion. Upon convergence the term representation provides a natural summary of the document representation (the cluster). We describe how to optimize the themes produced by this process and give the results of applying the method to a database of over fifty thousand PubMed documents dealing with the subject of AIDS. How themes may improve access to a document collection is also discussed.

Acquired Immunodeficiency Syndrome↗

PubMed2006

Predicting calcium-binding sites in proteins - a graph theory and geometry approach.

Identifying calcium-binding sites in proteins is one of the first steps towards predicting and understanding the role of calcium in biological systems for protein structure and function studies. Due to the complexity and irregularity of calcium-binding sites, a fast and accurate method for predicting and identifying calcium-binding protein is needed. Here we report our development of a new fast algorithm (GG) to detect calcium-binding sites. The GG algorithm uses a graph theory algorithm to find oxygen clusters of the protein and a geometric algorithm to identify the center of these clusters. A cluster of four or more oxygen atoms has a high potential for calcium binding. High performance with about 90% site sensitivity and 80% site selectivity has been obtained for three datasets containing a total of 123 proteins. The results suggest that a sphere of a certain size with four or more oxygen atoms on the surface and without other atoms inside is necessary and sufficient for quickly identifying the majority of the calcium-binding sites with high accuracy. Our finding opens a new avenue to visualize and analyze calcium-binding sites in proteins facilitating the prediction of functions from structural genomic information.

Algorithms↗

PubMedDate not supplied

Determination of liver volume from CT scans using histogram cluster analysis.

The histogram cluster analysis procedure (HICAP), which was developed by NASA for processing satellite images, classifies images into discrete clusters of pixels according to one or more arbitrary imaging variables. We incorporated this nonparametric, multivariate procedure in a semiautomatic computer algorithm for calculating total liver volume from CT scans and compared its performance with that of a human observer. Total liver volumes were calculated from CT scans in adult patients by the algorithm and by an experienced radiologist using the trackball controlled cursor at the CT console. Variability in the computer calculated volumes was determined by repeating calculations three times over the course of 3-12 months. Using HICAP in the univariate mode, we calculated total liver volumes from 28 contrast enhanced CT scans in 27 patients. Liver volumes calculated by the semiautomatic and manual methods had a median absolute difference of 3.6% (Vcomputer = 1.08 * Vmanual - 99.52 cc; r2 = 0.99). Median day-to-day variability of the computer calculated volumes was 1.9% (95% confidence interval: 1.3-2.7%). Using HICAP in a bivariate mode to illustrate its ability to incorporate two image features in one analysis, we studied an additional patient and compared total liver volume calculated from the univariate data set defined by the contrast enhanced CT scan with that calculated from the bivariate data set defined by nonenhanced and contrast enhanced CT scans. The HICAP errors were 4.1% in the univariate analysis and 0.4% in the bivariate analysis. It is concluded that this statistical clustering algorithm provides a clinically accurate, repeatable, and feasible method of in vivo liver volume determination.

Adult↗

PubMed2024

GRable Version 1.0: A Software Tool for Site-Specific Glycoform Analysis With Improved MS1-Based Glycopeptide Detection With Parallel Clustering and Confidence Evaluation With MS2 Information.

High-throughput intact glycopeptide analysis is crucial for elucidating the physiological and pathological status of the glycans attached to each glycoprotein. Mass spectrometry-based glycoproteomic methods are challenging because of the diversity and heterogeneity of glycan structures. Therefore, we developed an MS1-based site-specific glycoform analysis method named "Glycan heterogeneity-based Relational IDentification of Glycopeptide signals on Elution profile (Glyco-RIDGE)" for a more comprehensive analysis. This method detects glycopeptide signals as a cluster based on the mass and chromatographic properties of glycopeptides and then searches for each combination of core peptides and glycan compositions by matching their mass and retention time differences. Here, we developed a novel browser-based software named GRable for semi-automated Glyco-RIDGE analysis with significant improvements in glycopeptide detection algorithms, including "parallel clustering." This unique function improved the comprehensiveness of glycopeptide detection and allowed the analysis to focus on specific glycan structures, such as pauci-mannose. The other notable improvement is evaluating the "confidence level" of the GRable results, especially using MS2 information. This function facilitated reduced misassignment of the core peptide and glycan composition and improved the interpretation of the results. Additional improved points of the algorithms are "correction function" for accurate monoisotopic peak picking; one-to-one correspondence of clusters and core peptides even for multiply sialylated glycopeptides; and "inter-cluster analysis" function for understanding the reason for detected but unmatched clusters. The significance of these improvements was demonstrated using purified and crude glycoprotein samples, showing that GRable allowed site-specific glycoform analysis of intact sialylated glycoproteins on a large-scale and in-depth. Therefore, this software will help us analyze the status and changes in glycans to obtain biological and clinical insights into protein glycosylation by complementing the comprehensiveness of MS2-based glycoproteomics. GRable can be freely run online using a web browser via the GlyCosmos Portal (https://glycosmos.org/grable).

Glycopeptides↗

PubMed1987

Glucose-6-phosphate dehydrogenase and malate dehydrogenase enzyme electrophoretic patterns amongst strains of Bacteroides fragilis.

Fifty-two strains of Bacteroides fragilis were examined for their enzyme electrophoretic patterns of glucose-6-phosphate dehydrogenase (G6PDH) and malate dehydrogenase (MDH). All strains tested possessed high levels of both enzymes but the G6PDH reduced NADP whereas MDH was NAD-dependent. Twenty-seven strains produced single bands of both G6PDH and MDH. In all cases G6PDH migrated faster than MDH. Strains clustered by a single linkage algorithm were recovered in eight clusters at the 77% similarity level. The remaining 25 strains produced multiple bands of one or both enzymes. These were recovered in six clusters at the 72% similarity level using the same algorithm. The results of this study revealed considerable heterogeneity of enzyme patterns within B. fragilis.

Bacteroides fragilis↗

PubMed2004

Analysis of the low molecular weight fraction of serum by LC-dual ESI-FT-ICR mass spectrometry: precision of retention time, mass, and ion abundance.

This study quantifies the experimental uncertainty for LC retention time, mass measurement precision, and ion abundance obtained from replicate nLC-dual ESI-FT-ICR analyses of the low molecular weight fraction of serum. We used ultrafiltration to enrich the < 10-kDa fraction of components from the high-abundance proteins in a pooled serum sample derived from ovarian cancer patients. The THRASH algorithm for isotope cluster detection was applied to five replicate nLC-dual ESI-FT-ICR chromatograms. A simple two-level grouping algorithm was applied to the more than 7000 isotope clusters found in each replicate and identified 497 molecular species that appeared in at least four of the replicates. In addition, a representative set of 231 isotope clusters, corresponding to 188 unique molecular species, were manually interpreted to verify the automated algorithm and to set its tolerances. For nLC retention time reproducibility, 95% of the 497 species had a 95% confidence interval of the mean of +/- 0.9 min or less without the use of chromatographic alignment procedures. Furthermore, 95% of the 497 species had a mass measurement precision of < or = 3.2 and < or = 6.3 ppm for internally and externally calibrated spectra, respectively. Moreover, 95% of replicate ion abundance measurements, covering an ion abundance range of approximately 3 orders of magnitude, had a coefficient of variation of less than 62% without using any normalization functions. The variability of ion abundance was independent of LC retention time, mass, and ion abundance quartile. These measures of analytical reproducibility establish a statistical rationale for differentiating healthy and disease patient populations for the elucidation of biomarkers in the low molecular fraction of serum.

Algorithms↗

PubMed1999

A fuzzy clustering based segmentation system as support to diagnosis in medical imaging.

In medical imaging uncertainty is widely present in data, because of the noise in acquisition and of the partial volume effects originating from the low resolution of sensors. In particular, borders between tissues are not exactly defined and memberships in the boundary regions are intrinsically fuzzy. Therefore, computer assisted unsupervised fuzzy clustering methods turn out to be particularly suitable for handling a decision making process concerning segmentation of multimodal medical images. By using the possibilistic c-means algorithm as a refinement of a neural network based clustering algorithm named capture effect neural network, we developed the possibilistic neuro fuzzy c-means algorithm (PNFCM). In this paper the PNFCM has been applied to two different multimodal data sets and the results have been compared to those obtained by using the classical fuzzy c-means algorithm. Furthermore, a discussion is presented about the role of fuzzy clustering as a support to diagnosis in medical imaging.

Algorithms↗

PubMed2004

Parallel programming of gradient-based iterative image reconstruction schemes for optical tomography.

Optical tomography (OT) is a fast developing novel imaging modality that uses near-infrared (NIR) light to obtain cross-sectional views of optical properties inside the human body. A major challenge remains the time-consuming, computational-intensive image reconstruction problem that converts NIR transmission measurements into cross-sectional images. To increase the speed of iterative image reconstruction schemes that are commonly applied for OT, we have developed and implemented several parallel algorithms on a cluster of workstations. Static process distribution as well as dynamic load balancing schemes suitable for heterogeneous clusters and varying machine performances are introduced and tested. The resulting algorithms are shown to accelerate the reconstruction process to various degrees, substantially reducing the computation times for clinically relevant problems.

Algorithms↗

PubMed2002

Analysis of expression profile using fuzzy adaptive resonance theory.

MOTIVATION: It is well understood that the successful clustering of expression profiles give beneficial ideas to understand the functions of uncharacterized genes. In order to realize such a successful clustering, we investigate a clustering method based on adaptive resonance theory (ART) in this report. RESULTS: We apply Fuzzy ART as a clustering method for analyzing the time series expression data during sporulation of Saccharomyces cerevisiae. The clustering result by Fuzzy ART was compared with those by other clustering methods such as hierarchical clustering, k-means algorithm and self-organizing maps (SOMs). In terms of the mathematical validations, Fuzzy ART achieved the most reasonable clustering. We also verified the robustness of Fuzzy ART using noised data. Furthermore, we defined the correctness ratio of clustering, which is based on genes whose temporal expressions are characterized biologically. Using this definition, it was proved that the clustering ability of Fuzzy ART was superior to other clustering methods such as hierarchical clustering, k-means algorithm and SOMs. Finally, we validate the clustering results by Fuzzy ART in terms of biological functions and evidence. AVAILABILITY: The software is available at http//www.nubio.nagoya-u.ac.jp/proc/index.html

Algorithms↗

PubMed2001

A hierarchical unsupervised growing neural network for clustering gene expression patterns.

MOTIVATION: We describe a new approach to the analysis of gene expression data coming from DNA array experiments, using an unsupervised neural network. DNA array technologies allow monitoring thousands of genes rapidly and efficiently. One of the interests of these studies is the search for correlated gene expression patterns, and this is usually achieved by clustering them. The Self-Organising Tree Algorithm, (SOTA) (Dopazo,J. and Carazo,J.M. (1997) J. Mol. Evol., 44, 226-233), is a neural network that grows adopting the topology of a binary tree. The result of the algorithm is a hierarchical cluster obtained with the accuracy and robustness of a neural network. RESULTS: SOTA clustering confers several advantages over classical hierarchical clustering methods. SOTA is a divisive method: the clustering process is performed from top to bottom, i.e. the highest hierarchical levels are resolved before going to the details of the lowest levels. The growing can be stopped at the desired hierarchical level. Moreover, a criterion to stop the growing of the tree, based on the approximate distribution of probability obtained by randomisation of the original data set, is provided. By means of this criterion, a statistical support for the definition of clusters is proposed. In addition, obtaining average gene expression patterns is a built-in feature of the algorithm. Different neurons defining the different hierarchical levels represent the averages of the gene expression patterns contained in the clusters. Since SOTA runtimes are approximately linear with the number of items to be classified, it is especially suitable for dealing with huge amounts of data. The method proposed is very general and applies to any data providing that they can be coded as a series of numbers and that a computable measure of similarity between data items can be used. AVAILABILITY: A server running the program can be found at: http://bioinfo.cnio.es/sotarray.

Algorithms↗