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 451 records · Page 25Linked to original sources

PubMed2003

Rival penalized competitive learning (RPCL): a topology-determining algorithm for analyzing gene expression data.

DNA arrays have become the immediate choice in the analysis of large-scale expression measurements. Understanding the expression pattern of genes provide functional information on newly identified genes by computational approaches. Gene expression pattern is an indicator of the state of the cell, and abnormal cellular states can be inferred by comparing expression profiles. Since co-regulated genes, and genes involved in a particular pathway, tend to show similar expression patterns, clustering expression patterns has become the natural method of choice to differentiate groups. However, most methods based on cluster analysis suffer from the usual problems (i) dead units, and (ii) the problem of determining the correct number of clusters (k) needed to classify the data. Selecting the k has been an open problem of pattern recognition and statistics for decades. Since clustering reveals similar patterns present in the data, fixing this number strongly influences the quality of the result. While there is no theoretical solution to this problem, the number of clusters can be decided by a heuristic clustering algorithm called rival penalized competitive learning (RPCL). We present a novel implementation of RPCL that transforms the correct number of clusters problem to the tractable problem of clustering based on the degree of similarity. This is biologically significant since our implementation clusters functionally co-regulated genes and genes that present similar patterns of expression. This new approach reveals potential genes that are co-involved in a biological process. This implementation of the RPCL algorithm is useful in differentiating groups involved in concerted functional regulation and helps to progressively home into patterns, which are closely similar.

Algorithms↗

PubMed2002

Inference from clustering with application to gene-expression microarrays.

There are many algorithms to cluster sample data points based on nearness or a similarity measure. Often the implication is that points in different clusters come from different underlying classes, whereas those in the same cluster come from the same class. Stochastically, the underlying classes represent different random processes. The inference is that clusters represent a partition of the sample points according to which process they belong. This paper discusses a model-based clustering toolbox that evaluates cluster accuracy. Each random process is modeled as its mean plus independent noise, sample points are generated, the points are clustered, and the clustering error is the number of points clustered incorrectly according to the generating random processes. Various clustering algorithms are evaluated based on process variance and the key issue of the rate at which algorithmic performance improves with increasing numbers of experimental replications. The model means can be selected by hand to test the separability of expected types of biological expression patterns. Alternatively, the model can be seeded by real data to test the expected precision of that output or the extent of improvement in precision that replication could provide. In the latter case, a clustering algorithm is used to form clusters, and the model is seeded with the means and variances of these clusters. Other algorithms are then tested relative to the seeding algorithm. Results are averaged over various seeds. Output includes error tables and graphs, confusion matrices, principal-component plots, and validation measures. Five algorithms are studied in detail: K-means, fuzzy C-means, self-organizing maps, hierarchical Euclidean-distance-based and correlation-based clustering. The toolbox is applied to gene-expression clustering based on cDNA microarrays using real data. Expression profile graphics are generated and error analysis is displayed within the context of these profile graphics. A large amount of generated output is available over the web.

Computational Biology↗

PubMed2005

A method for calling gains and losses in array CGH data.

Array CGH is a powerful technique for genomic studies of cancer. It enables one to carry out genome-wide screening for regions of genetic alterations, such as chromosome gains and losses, or localized amplifications and deletions. In this paper, we propose a new algorithm 'Cluster along chromosomes' (CLAC) for the analysis of array CGH data. CLAC builds hierarchical clustering-style trees along each chromosome arm (or chromosome), and then selects the 'interesting' clusters by controlling the False Discovery Rate (FDR) at a certain level. In addition, it provides a consensus summary across a set of arrays, as well as an estimate of the corresponding FDR. We illustrate the method using an application of CLAC on a lung cancer microarray CGH data set as well as a BAC array CGH data set of aneuploid cell strains.

Algorithms↗

PubMed2002

Multivariate analysis of the ecoregion delineation for aquatic systems.

The ecoregion concept is a popular method of understanding the spatial distribution of the environment', however, it has yet to be adequately demonstrated that the environment is distributed in accordance with these bounded units. In this paper, we generated a testable hypothesis based on the current usage of ecoregions: the ecoregion classification will allow for discrimination between lakes of different water quality. The ecoregion classification should also be more effective better than a comparably scaled classification based on political boundaries, land-use class, or random grouping. To test this hypothesis we used the Environmental Monitoring and Assessment Program (EMAP) lake water chemistry data from the northeast United States. The water chemistry data were reduced to four components using principal component analysis. For comparison to an optimal grouping of these data we used K-means cluster analysis to define the extent at which these lakes could be segregated into distinct classes. Jackknifed discriminant analysis was used to determine the classification rate of ecoregions, the three alternative spatial classification methods, and the clustering algorithm. The classification based on ecoregions was successful for 35% of the lakes included in this study, in comparison to the clustered groups accuracy of 98%. These results suggest that the large scale spatial distribution of ecosystem types is more complicated than that suggested by the present ecoregion boundaries. Further tests of ecoregion delineations are needed and alternative large-scale management strategies should be investigated.

Algorithms↗

PubMed1995

Computer-aided detection of clustered microcalcifications on digital mammograms.

A computer-aided diagnosis scheme to assist radiologists in detecting clustered microcalcifications from mammograms is being developed. Starting with a digital mammogram, the scheme consists of three steps. First, the image is filtered so that the signal-to-noise ratio of microcalcifications is increased by suppression of the normal background structure of the breast. Secondly, potential microcalcifications are extracted from the filtered image with a series of three different techniques: a global thresholding based on the grey-level histogram of the full filtered image, an erosion operator for eliminating very small signals, and a local adaptive grey-level thresholding. Thirdly, some false-positive signals are eliminated by means of a texture analysis technique, and a non-linear clustering algorithm is then used for grouping the remaining signals. With this method, the scheme can detect approximately 85% of true clusters, with an average of two false clusters detected per image.

Breast Diseases↗

PubMed2002

Computerised intrapartum diagnosis of fetal hypoxia based on fetal heart rate monitoring and fetal pulse oximetry recordings utilising wavelet analysis and neural networks.

OBJECTIVE: To develop a computerised system that will assist the early diagnosis of fetal hypoxia and to investigate the relationship between the fetal heart rate variability and the fetal pulse oximetry recordings. DESIGN: Retrospective off-line analysis of cardiotocogram and FSpO2 recordings. SETTING: The Maternity Unit of the 2nd Department of Obstetrics and Gynaecology, Aretaieion Hospital, University of Athens. POPULATION: Sixty-one women of more than 37 weeks of gestation were monitored throughout labour. METHODS: Multiresolution wavelet analysis was applied in each 10-minute period of second stage of labour focussing on long term variability changes in different frequency ranges and statistical analysis was performed in the associated 10-minute FSpO2 recordings. Self-organising map neural network was used to categorise the different 10-minute fetal heart rate patterns and the associated 10-minute FSpO2 recordings. MAIN OUTCOME MEASURES: Umbilical artery pH of < or = 7.20 and Apgar score at 5 minutes of < or = 7 formed the inclusion criteria of the risk group. RESULTS: After using k-means clustering algorithm, the two-dimensional output layer of the self-organising map neural network was divided into three distinct clusters. All the cases that mapped in cluster 3 belonged in the risk group except one. The sensitivity of the system was 83.3% and the specificity 97.9% for the detection of risk group cases. CONCLUSIONS: A relationship between the fetal heart rate variability in different frequency ranges and the time in which FSpO2 is less than 30% was noticed. Fetal pulse oximetry seems to be an important additional source of information. Computerised analysis of the fetal heart rate monitoring and pulse oximetry recordings is a promising technique in objective intrapartum diagnosis of fetal hypoxia. Further evaluation of this technique is mandatory to evaluate its efficacy and reliability in interpreting fetal heart rate recordings.

Adult↗

PubMed1999

ProtoMap: automatic classification of protein sequences, a hierarchy of protein families, and local maps of the protein space.

We investigate the space of all protein sequences in search of clusters of related proteins. Our aim is to automatically detect these sets, and thus obtain a classification of all protein sequences. Our analysis, which uses standard measures of sequence similarity as applied to an all-vs.-all comparison of SWISSPROT, gives a very conservative initial classification based on the highest scoring pairs. The many classes in this classification correspond to protein subfamilies. Subsequently we merge the subclasses using the weaker pairs in a two-phase clustering algorithm. The algorithm makes use of transitivity to identify homologous proteins; however, transitivity is applied restrictively in an attempt to prevent unrelated proteins from clustering together. This process is repeated at varying levels of statistical significance. Consequently, a hierarchical organization of all proteins is obtained. The resulting classification splits the protein space into well-defined groups of proteins, which are closely correlated with natural biological families and superfamilies. Different indices of validity were applied to assess the quality of our classification and compare it with the protein families in the PROSITE and Pfam databases. Our classification agrees with these domain-based classifications for between 64.8% and 88.5% of the proteins. It also finds many new clusters of protein sequences which were not classified by these databases. The hierarchical organization suggested by our analysis reveals finer subfamilies in families of known proteins as well as many novel relations between protein families.

Algorithms↗

PubMed2003

Generalized Kohonen's competitive learning algorithms for ophthalmological MR image segmentation.

Kohonen's self-organizing map is a two-layer feedforward competitive learning network. It has been used as a competitive learning clustering algorithm. In this paper, we generalize Kohonen's competitive learning (KCL) algorithm with fuzzy and fuzzy-soft types called fuzzy KCL (FKCL) and fuzzy-soft KCL (FSKCL). These generalized KCL algorithms fuse the competitive learning with soft competition and fuzzy c-means (FCM) membership functions. We then apply these generalized KCLs to MRI and MRA ophthalmological segmentations. These KCL-based MRI segmentation techniques are useful in reducing medical image noise effects using a learning mechanism. They may be particularly helpful in clinical diagnosis. Two real cases with MR image data recommended by an ophthalmologist are examined. First case is a patient with Retinoblastoma in her left eye, an inborn malignant neoplasm of the retina frequently metastasis beyond the lacrimal cribrosa. The second case is a patient with complete left side oculomotor palsy immediately after a motor vehicle accident. Her brain MRI with MRA, skull routine, orbital CT, and cerebral angiography did not reveal brainstem lesions, skull fractures, or vascular anomalies. These generalized KCL algorithms were used in segmenting the ophthalmological MRIs. KCL, FKCL and FSKCL comparisons are made. Overall, the FSKCL algorithm is recommended for use in MR image segmentation as an aid to small lesion diagnosis.

Algorithms↗

PubMed1996

Post-acquisition correction of MR inhomogeneities.

Signal inhomogeneities in volumetric head MR scans are a major obstacle to segmentation and neuromorphometry. The fuzzy c-means (FCM) statistical clustering algorithm was extended to estimate and retrospectively correct a multiplicative inhomogeneity field in T1-weighted head MR scans. The method was tested on a mathematically simulated object and on seven whole head 3D MR scans. Once initial parameters governing operation of the algorithm were chosen for this class of images, results were obtained without intervention for individual MR studies. Post-acquisition inhomogeneity correction by extended FCM clustering improved overall image uniformity and separability of gray and white matter intensities.

Algorithms↗

PubMed2002

Probabilistic clustering of sequences: inferring new bacterial regulons by comparative genomics.

Genome-wide comparisons between enteric bacteria yield large sets of conserved putative regulatory sites on a gene-by-gene basis that need to be clustered into regulons. Using the assumption that regulatory sites can be represented as samples from weight matrices (WMs), we derive a unique probability distribution for assignments of sites into clusters. Our algorithm, "PROCSE" (probabilistic clustering of sequences), uses Monte Carlo sampling of this distribution to partition and align thousands of short DNA sequences into clusters. The algorithm internally determines the number of clusters from the data and assigns significance to the resulting clusters. We place theoretical limits on the ability of any algorithm to correctly cluster sequences drawn from WMs when these WMs are unknown. Our analysis suggests that the set of all putative sites for a single genome (e.g., Escherichia coli) is largely inadequate for clustering. When sites from different genomes are combined and all the homologous sites from the various species are used as a block, clustering becomes feasible. We predict 50-100 new regulons as well as many new members of existing regulons, potentially doubling the number of known regulatory sites in E. coli.

Bacteria↗

PubMedDate not supplied

Generalizing the plurality method for forming hospital service areas.

The upcoming Health Care Financing Administration's Fourth Scope of Work for peer review organizations (PROs) envisions much use of geographic analysis of utilization rates and quality of care. Proper analysis of utilization rates requires each PRO to form multiple sets of hospital service areas. The method used most often in the literature is the plurality method. Because this method can create fractured service areas and can leave hospitals without a service area, the service areas and their associated hospitals often are reworked by hand. This last step drastically raises the effort required to form service areas and makes the method nonreproducible. This report defines the generalized plurality method for forming the hospital service areas that are central to the study of use patterns via small area analysis. This new method is a true generalization of the plurality method. Like the plurality method, it forms service areas by allowing geographic areas to "vote" for their preferred hospital. The generalization is achieved by allowing near-ties in the voting to cause clustering of hospitals. Hence it is a clustering algorithm that operates on both the geographic areas (sources) and the hospitals (destinations) at the same time. It is a nonhierarchical, nonagglomerative cluster method. There are several free parameters that may be chosen to adjust the effect of the clustering by adjusting the definition of a near-tie, as well as the sensitivity of the clustering to near-ties from sources with a small number of votes. This automated method enjoys many major advantages over the methods commonly appearing in the literature: it is completely reproducible, it is quick, and it does not require the a priori convening of a panel of experts. It thus can be applied easily to a wide variety of types of care that would not necessarily have the same service areas.

Algorithms↗

PubMed1999

Distinctive gene expression patterns in human mammary epithelial cells and breast cancers.

cDNA microarrays and a clustering algorithm were used to identify patterns of gene expression in human mammary epithelial cells growing in culture and in primary human breast tumors. Clusters of coexpressed genes identified through manipulations of mammary epithelial cells in vitro also showed consistent patterns of variation in expression among breast tumor samples. By using immunohistochemistry with antibodies against proteins encoded by a particular gene in a cluster, the identity of the cell type within the tumor specimen that contributed the observed gene expression pattern could be determined. Clusters of genes with coherent expression patterns in cultured cells and in the breast tumors samples could be related to specific features of biological variation among the samples. Two such clusters were found to have patterns that correlated with variation in cell proliferation rates and with activation of the IFN-regulated signal transduction pathway, respectively. Clusters of genes expressed by stromal cells and lymphocytes in the breast tumors also were identified in this analysis. These results support the feasibility and usefulness of this systematic approach to studying variation in gene expression patterns in human cancers as a means to dissect and classify solid tumors.

Algorithms↗

PubMed2001

Adaptable fuzzy C-Means for improved classification as a preprocessing procedure of brain parcellation.

Parcellation, one of several brain analysis methods, is a procedure popular for subdividing the regions identified by segmentation into smaller topographically defined units. The fuzzy clustering algorithm is mainly used to preprocess parcellation into several segmentation methods, because it is very appropriate for the characteristics of magnetic resonance imaging (MRI), such as partial volume effect and intensity inhomogeneity. However, some gray matter, such as basal ganglia and thalamus, may be misclassified into the white matter class using the conventional fuzzy C-Means (FCM) algorithm. Parcellation has been nearly achieved through manual drawing, but it is a tedious and time-consuming process. We propose improved classification using successive fuzzy clustering and implementing the parcellation module with the modified graphic user interface (GUI) for the convenience of users.

Algorithms↗

PubMed2003

SNP subset selection for genetic association studies.

Association studies for disease susceptibility genes rely on the high density of SNPs within candidate genes. However, the linkage disequilibrium between SNPs imply that not all SNPs identified in the candidate region need be genotyped. Here we develop several approaches to SNP subset selection, which can substantially reduce the number of SNPs to be genotyped in an association study. We apply clustering algorithms to pairwise linkage disequilibrium measures, with SNP subsets determined for different cut-off values of Delta using nearest and furthest neighbour clusters. Alternatively, SNP subsets may be determined by the proportion of haplotypes they identify. We also show how power calculations, based on the average power to identify a SNP as the disease susceptibility mutation using haplotype-based or logistic regression based statistical analyses, can be used to choose SNP subsets. All these methods provide a ranking method for subsets of a specific size, but do not provide criteria for overall choice of SNP subset size. We develop such criteria by incorporating power calculations into a decision analysis, where the choice of SNP subset size depends on the genotyping costs and the perceived benefits of identifying association. These methods are illustrated using eleven SNPs in the MMP2 gene.

Cluster Analysis↗

PubMed1991

Particle track structure and its correlation with radiobiological endpoint.

One of the possible ways to classify track structures is application of the conventional partition techniques of analysis of multidimensional data to the track structure. Using these cluster algorithms this paper attempts to find characteristics of radiation reflecting the spatial distribution of ionizations in the primary particle track. Absolute frequency distributions of clusters giving the mean number of clusters produced by radiation per unit of deposited energy have been computed for radiation of different qualities. The results were compared with the published experimental data of cell inactivation. For particular biological objects the critical properties of radiation correlating with the cell inactivation can be found and it seems that the occurrence of a cluster of at least four ionizations formed in a domain of approximately 2-3 nm correlates with the induction of double strand break.

Ions↗

PubMed2004

A strategy for assembling the maize (Zea mays L.) genome.

UNLABELLED: Because the bulk of the maize (Zea mays L.) genome consists of repetitive sequences, sequencing efforts are being targeted to its 'gene-rich' fraction. Traditional assembly programs are inadequate for this approach because they are optimized for a uniform sampling of the genome and inherently lack the ability to differentiate highly similar paralogs. RESULTS: We report the development of bioinformatics tools for the accurate assembly of the maize genome. This software, which is based on innovative parallel algorithms to ensure scalability, assembled 730,974 genomic survey sequences fragments in 4 h using 64 Pentium III 1.26 GHz processors of a commodity cluster. Algorithmic innovations are used to reduce the number of pairwise alignments significantly without sacrificing quality. Clone pair information was used to estimate the error rate for improved differentiation of polymorphisms versus sequencing errors. The assembly was also used to evaluate the effectiveness of various filtering strategies and thereby provide information that can be used to focus subsequent sequencing efforts.

Algorithms↗

PubMed2005

Quantifying visual similarity in clinical iconic graphics.

OBJECTIVE: The use of icons and other graphical components in user interfaces has become nearly ubiquitous. The interpretation of such icons is based on the assumption that different users perceive the shapes similarly. At the most basic level, different users must agree on which shapes are similar and which are different. If this similarity can be measured, it may be usable as the basis to design better icons. DESIGN: The purpose of this study was to evaluate a novel method for categorizing the visual similarity of graphical primitives, called Presentation Discovery, in the domain of mammography. Six domain experts were given 50 common textual mammography findings and asked to draw how they would represent those findings graphically. Nondomain experts sorted the resulting graphics into groups based on their visual characteristics. The resulting groups were then analyzed using traditional statistics and hypothesis discovery tools. Strength of agreement was evaluated using computational simulations of sorting behavior. MEASUREMENTS: Sorter agreement was measured at both the individual graphical and concept-group levels using a novel simulation-based method. "Consensus clusters" of graphics were derived using a hierarchical clustering algorithm. RESULTS: The multiple sorters were able to reliably group graphics into similar groups that strongly correlated with underlying domain concepts. Visual inspection of the resulting consensus clusters indicated that graphical primitives that could be informative in the design of icons were present. CONCLUSION: The method described provides a rigorous alternative to intuitive design processes frequently employed in the design of icons and other graphical interface components.

Algorithms↗

PubMed2001

Adaptive neuro-fuzzy inference system: an instant and architecture-free predictor for improved QSAR studies.

The application of an adaptive neuro-fuzzy inference system (ANFIS) has been developed for obtaining sufficient quantitative structure-activity relationships (QSAR) with high accuracy. To this end, a data set of 68 pyrimidines derivatives as DHFR inhibitors, described first in the excellent independent studies of Hansch et al. (J. Med. Chem. 1982, 25, 777-784 and J. Med. Chem. 1991, 34, 46-54) and later by So and Richards (J. Med. Chem. 1992, 35, 3201-3207), was examined. The ANFIS system, first time applied in the literature to QSAR studies, was trained using a hybrid algorithm consisting of back-propagation and least-squares estimation while the optimum number and shape of membership functions were obtained through the subtractive clustering algorithm. Prior to the development and evaluation of the ANFIS system, geometry optimization of the examined compounds was performed, deriving a series of diverse descriptors from which the best subset was selected by using a hybrid genetic algorithm system. The predictive abilities of the resulting models compared to those produced from classical multivariate regression such as linear and nonlinear (quadratic) partial least squares regression (PLS and QPLS, respectively). The ANFIS method outperformed both the PLS models as well as the published results, leading to substantial gain in both the prediction ability and the computation speed (almost instant training).

Algorithms↗