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 289 records · Page 16Linked to original sources

PubMed2002

ProClust: improved clustering of protein sequences with an extended graph-based approach.

MOTIVATION: The problem of finding remote homologues of a given protein sequence via alignment methods is not fully solved. In fact, the task seems to become more difficult with more data. As the size of the database increases, so does the noise level; the highest alignment scores due to random similarities increase and can be higher than the alignment score between true homologues. Comparing two sequences with an arbitrary alignment method yields a similarity value which may indicate an evolutionary relationship between them. A threshold value is usually chosen to distinguish between true homologue relationships and random similarities. To compensate for the higher probability of spurious hits in larger databases, this threshold is increased. Increasing specificity however leads to decreased sensitivity as a matter of principle. Sensitivity can be recovered by utilizing refined protocols. A number of approaches to this challenge have made use of the fact that proteins are often members of some larger protein family. This can be exploited by using position-specific substitution matrices or profiles, or by making use of transitivity of homology. Transitivity refers to the concept of concluding homology between proteins A and C based on homology between A and a third protein B and between B and C. It has been demonstrated that transitivity can lead to substantial improvement in recognition of remote homologues particularly in cases where the alignment score of A and C is below the noise level. A natural limit to the use of transitivity is imposed by domains. Domains, compact independent sub-units of proteins, are often shared between otherwise distinct proteins, and can cause substantial problems by incorrectly linking otherwise unrelated proteins. RESULTS: We extend a graph-based clustering algorithm which uses an asymmetric distance measure, scaling similarity values based on the length of the protein sequences compared. Additionally, the significance of alignment scores is taken into account and used for a filtering step in the algorithm. Post-processing, to merge further clusters based on profile HMMs is proposed. SCOP sequences and their super-family level classification are used as a test set for a clustering computed with our method for the joint data set containing both SCOP and SWISS-PROT. Note, the joint data set includes all multi-domain proteins, which contain the SCOP domains that are a potential source of incorrect links. Our method compares at high specificities very favorably with PSI-Blast, which is probably the most widely-used tool for finding remote homologues. We demonstrate that using transitivity with as many as twelve intermediate sequences is crucial to achieving this level of performance. Moreover, from analysis of false positives we conclude that our method seems to correctly bound the degree of transitivity used. This analysis also yields explicit guidance in choosing parameters. The heuristics of the asymmetric distance measure used neither solve the multi-domain problem from a theoretical point of view, nor do they avoid all types of problems we have observed in real data. Nevertheless, they do provide a substantial improvement over existing approaches. AVAILABILITY: The complete software source is freely available to all users under the GNU General Public License (GPL) from http://www.bioinformatik.uni-koeln.de/~proclust/download/

Algorithms↗

PubMed2004

Influence of microarrays experiments missing values on the stability of gene groups by hierarchical clustering.

BACKGROUND: Microarray technologies produced large amount of data. The hierarchical clustering is commonly used to identify clusters of co-expressed genes. However, microarray datasets often contain missing values (MVs) representing a major drawback for the use of the clustering methods. Usually the MVs are not treated, or replaced by zero or estimated by the k-Nearest Neighbor (kNN) approach. The topic of the paper is to study the stability of gene clusters, defined by various hierarchical clustering algorithms, of microarrays experiments including or not MVs. RESULTS: In this study, we show that the MVs have important effects on the stability of the gene clusters. Moreover, the magnitude of the gene misallocations is depending on the aggregation algorithm. The most appropriate aggregation methods (e.g. complete-linkage and Ward) are highly sensitive to MVs, and surprisingly, for a very tiny proportion of MVs (e.g. 1%). In most of the case, the MVs must be replaced by expected values. The MVs replacement by the kNN approach clearly improves the identification of co-expressed gene clusters. Nevertheless, we observe that kNN approach is less suitable for the extreme values of gene expression. CONCLUSION: The presence of MVs (even at a low rate) is a major factor of gene cluster instability. In addition, the impact depends on the hierarchical clustering algorithm used. Some methods should be used carefully. Nevertheless, the kNN approach constitutes one efficient method for restoring the missing expression gene values, with a low error level. Our study highlights the need of statistical treatments in microarray data to avoid misinterpretation.

Cluster Analysis↗

PubMed2005

Automated variable weighting in k-means type clustering.

This paper proposes a k-means type clustering algorithm that can automatically calculate variable weights. A new step is introduced to the k-means clustering process to iteratively update variable weights based on the current partition of data and a formula for weight calculation is proposed. The convergency theorem of the new clustering process is given. The variable weights produced by the algorithm measure the importance of variables in clustering and can be used in variable selection in data mining applications where large and complex real data are often involved. Experimental results on both synthetic and real data have shown that the new algorithm outperformed the standard k-means type algorithms in recovering clusters in data.

Algorithms↗

PubMed2006

RBR: library-less repeat detection for ESTs.

MOTIVATION: Repeat sequences in ESTs are a source of problems, in particular for clustering. ESTs are therefore commonly masked against a library of known repeats. High quality repeat libraries are available for the widely studied organisms, but for most other organisms the lack of such libraries is likely to compromise the quality of EST analysis. RESULTS: We present a fast, flexible and library-less method for masking repeats in EST sequences, based on match statistics within the EST collection. The method is not linked to a particular clustering algorithm. Extensive testing on datasets using different clustering methods and a genomic mapping as reference shows that this method gives results that are better than or as good as those obtained using RepeatMasker with a repeat library. AVAILABILITY: The implementation of RBR is available under the terms of the GPL from http://www.ii.uib.no/~ketil/bioinformatics CONTACT: ketil.malde@bccs.uib.no SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Algorithms↗

PubMed2002

Density of points clustering, application to transcriptomic data analysis.

With the increasing amount of data produced by high-throughput technologies in many fields of science, clustering has become an integral step in exploratory data analysis in order to group similar elements into classes. However, many clustering algorithms can only work properly if aided by human expertise. For example, one parameter which is crucial and often manually set is the number of clusters present in the analyzed set. We present a novel stopping rule to find the optimal number of clusters based on the comparison of the density of points inside the clusters and between them. The method is evaluated on synthetic as well as on real transcriptomic data and compared with two current methods. Finally, we illustrate its usefulness in the analysis of the expression profiles of promyelocytic cells before and after treatment with all-trans retinoic acid. Simultaneous clustering for gene regulation and absolute initial expression levels allowed the identification of numerous genes associated with signal transduction revealing the complexity of retinoic acid signaling.

Algorithms↗

PubMed1998

Automatic tumor segmentation using knowledge-based techniques.

A system that automatically segments and labels glioblastoma-multiforme tumors in magnetic resonance images (MRI's) of the human brain is presented. The MRI's consist of T1-weighted, proton density, and T2-weighted feature images and are processed by a system which integrates knowledge-based (KB) techniques with multispectral analysis. Initial segmentation is performed by an unsupervised clustering algorithm. The segmented image, along with cluster centers for each class are provided to a rule-based expert system which extracts the intracranial region. Multispectral histogram analysis separates suspected tumor from the rest of the intracranial region, with region analysis used in performing the final tumor labeling. This system has been trained on three volume data sets and tested on thirteen unseen volume data sets acquired from a single MRI system. The KB tumor segmentation was compared with supervised, radiologist-labeled "ground truth" tumor volumes and supervised k-nearest neighbors tumor segmentations. The results of this system generally correspond well to ground truth, both on a per slice basis and more importantly in tracking total tumor volume during treatment over time.

Algorithms↗

PubMed2002

How well do we understand the clusters found in microarray data?

We wished to quantify the state-of-the-art of our understanding of clusters in microarray data. To do this we systematically compared the clusters produced on sets of microarray data using a representative set of clustering algorithms (hierarchical, k-means, and a modified version of QT_CLUST) with the annotation schemes MIPS, GeneOntology and GenProtEC. We assumed that if a cluster reflected known biology its members would share related ontological annotations. This assumption is the basis of "guilt-by-association" and is commonly used to assign the putative function of proteins. To statistically measure the relationship between cluster and annotation we developed a new predictive discriminatory measure. We found that the clusters found in microarray data do not in general agree with functional annotation classes. Although many statistically significant relationships can be found, the majority of clusters are not related to known biology (as described in annotation ontologies). This implies that use of guilt-by-association is not supported by annotation ontologies. Depending on the estimate of the amount of noise in the data, our results suggest that bioinformatics has only codified a small proportion of the biological knowledge required to understand microarray data.

Algorithms↗

PubMedDate not supplied

[Color categorization and the structure of perceptive color].

This paper is an attempt to develop a coherent framework for understanding, simulating, and predicting color categories. The process of color categorization can be understood as a structuring of preceding color experience on the basis of statistical distribution of light in observers environment. A proposed computational model of color categorization includes: 1) distribution of R, G, B pixel values representing a sample of 630 color images of natural scenes (analogue of physical light experience); 2) transformation of the R, G, B pixel values into L*u*v* coordinates of the CIELUV color space (analogue of the process of color perception); 3) distribution of the L*u*v* coordinates representing the sample of the color images (analogue of perceived color experience); 4) k-means clustering algorithm of the L*u*v* coordinates representing the sample of the color images (analogue of the process of color categorization); 5) location and order of color clusters (analogue of location and order of color categories). The proposed computational model enables us to predict the location and order of color categories, being consistent with psycholinguistic data.

Algorithms↗

PubMed2004

Identifying projected clusters from gene expression profiles.

In microarray gene expression data, clusters may hide in certain subspaces. For example, a set of co-regulated genes may have similar expression patterns in only a subset of the samples in which certain regulating factors are present. Their expression patterns could be dissimilar when measuring in the full input space. Traditional clustering algorithms that make use of such similarity measurements may fail to identify the clusters. In recent years a number of algorithms have been proposed to identify this kind of projected clusters, but many of them rely on some critical parameters whose proper values are hard for users to determine. In this paper, a new algorithm that dynamically adjusts its internal thresholds is proposed. It has a low dependency on user parameters while allowing users to input some domain knowledge should they be available. Experimental results show that the algorithm is capable of identifying some interesting projected clusters.

Algorithms↗

PubMed1999

Dynamical cluster analysis of cortical fMRI activation.

Localized changes in cortical blood oxygenation during voluntary movements were examined with functional magnetic resonance imaging (fMRI) and evaluated with a new dynamical cluster analysis (DCA) method. fMRI was performed during finger movements with eight subjects on a 1.5-T scanner using single-slice echo planar imaging with a 107-ms repetition time. Clustering based on similarity of the detailed signal time courses requires besides the used distance measure no assumptions about spatial location and extension of activation sites or the shape of the expected activation time course. We discuss the basic requirements on a clustering algorithm for fMRI data. It is shown that with respect to easy adjustment of the quantization error and reproducibility of the results DCA outperforms the standard k-means algorithm. In contrast to currently used clustering methods for fMRI, like k-means or fuzzy k-means, DCA extracts the appropriate number and initial shapes of representative signal time courses from data properties during run time. With DCA we simultaneously calculate a two-dimensional projection of cluster centers (MDS) and data points for online visualization of the results. We describe the new DCA method and show for the well-studied motor task that it detects cortical activation loci and provides additional information by discriminating different shapes and phases of hemodynamic responses. Robustness of activity detection is demonstrated with respect to repeated DCA runs and effects of different data preprocessing are shown. As an example of how DCA enables further analysis we examined activation onset times. In areas SMA, M1, and S1 simultaneous and sequential activation (in the given order) was found.

Cerebral Cortex↗

PubMed1990

A new segmentation algorithm for knowledge acquisition in tissue-characterizing magnetic resonance imaging.

Tissue-characterizing magnetic resonance imaging (MRI) is a new imaging method for differentiation and biochemical characterization of tissue based on multidimensional MR-parameter information. To support knowledge acquisition in tissue-characterizing MRI, a new segmentation algorithm has been developed by using clustering techniques. The visualization of the complex biochemical MR-parameter information is performed by extraction of regions with similar biochemical properties. The clustering algorithm leads to an easy and comfortable handling of the complex tissue-characteristic MR information and supports knowledge acquisition for knowledge-based tissue characterization.

Brain↗

PubMed2004

Candidates for novel RNA topologies.

Because the functional repertiore of RNA molecules, like proteins, is closely linked to the diversity of their shapes, uncovering RNA's structural repertoire is vital for identifying novel RNAs, especially in genomic sequences. To help expand the limited number of known RNA families, we use graphical representation and clustering analysis of RNA secondary structures to predict novel RNA topologies and their abundance as a function of size. Representing the essential topological properties of RNA secondary structures as graphs enables enumeration, generation, and prediction of novel RNA motifs. We apply a probabilistic graph-growing method to construct the RNA structure space encompassing the topologies of existing and hypothetical RNAs and cluster all RNA topologies into two groups using topological descriptors and a standard clustering algorithm. Significantly, we find that nearly all existing RNAs fall into one group, which we refer to as "RNA-like"; we consider the other group "non-RNA-like". Our method predicts many candidates for novel RNA secondary topologies, some of which are remarkably similar to existing structures; interestingly, the centroid of the RNA-like group is the tmRNA fold, a pseudoknot having both tRNA-like and mRNA-like functions. Additionally, our approach allows estimation of the relative abundance of pseudoknot and other (e.g. tree) motifs using the "edge-cut" property of RNA graphs. This analysis suggests that pseudoknots dominate the RNA structure universe, representing more than 90% when the sequence length exceeds 120 nt; the predicted trend for <100 nt agrees with data for existing RNAs. Together with our predictions for novel "RNA-like" topologies, our analysis can help direct the design of functional RNAs and identification of novel RNA folds in genomes through an efficient topology-directed search, which grows much more slowly in complexity with RNA size compared to the traditional sequence-based search.

Algorithms↗

PubMed2004

Expressed gene clusters associated with cellular sensitivity and resistance towards anti-viral and anti-proliferative actions of interferon.

Interferons (IFN) are multi-functional proteins that induce a large number of genes which mediate many biological processes including host defense, cell growth control, signaling, and metabolism. Bioinformatics analysis of the 3'-untranslated regions of IFN-stimulated genes (ISGs) showed that the AU-rich elements (ARE) exist in approximately 10% of the mRNA induced by IFN. The human epithelial cell lines, WISH and 293, and the human B cell lines, Daudi and RPMI 1788, were assessed for their response to type-I IFN. Due to their differential response to the anti-viral and anti-proliferative action of IFN-alpha, they were used as cellular models for genome wide ARE-gene expression. The anti-viral and anti-proliferative actions of IFN-alpha were substantially more potent against WISH and Daudi cells than 293 and RPMI 1788 cells, respectively. These results correlated with the Stat1-driven gene expression as assessed by monitoring the expression of Stat1-mediated IFN-inducible 6-16 mRNA. Interferons were able to induce a significant proportion of common and distinct ARE-genes, but the patterns of expression were different and dependent on the type of the cell, type of IFN, and status of the cellular sensitivity to IFN. Clustering algorithms generated two informative expressed gene clusters that were selectively associated with cellular sensitivity and resistance to the anti-viral and anti-proliferative action of IFN. Use of rationally designed microarray experiments in IFN biology yielded informative clusters that may provide candidate genes for diagnostic or for evaluation of therapeutic possibilities.

Antiviral Agents↗

PubMed2005

How does gene expression clustering work?

Clustering is often one of the first steps in gene expression analysis. How do clustering algorithms work, which ones should we use and what can we expect from them?

Algorithms↗

PubMed2006

3000 years of solitude: extreme differentiation in the island isolates of Dalmatia, Croatia.

Communities with increased shared ancestry represent invaluable tools for genetic studies of complex traits. "1001 Dalmatians" research program collects biomedical information for genetic epidemiological research from multiple small isolated populations ('metapopulation') in the islands of Dalmatia, Croatia. Random samples of 100 individuals from 10 small island settlements (n<2000 inhabitants) were collected in 2002 and 2003. These island communities were carefully chosen to represent a wide range of distinct and well-documented demographic histories. Here, we analysed their genetic make-up using 26 short tandem repeat (STR) markers, at least 5 cM apart. We found a very high level of differentiation between most of these island communities based on Wright's fixation indexes, even within the same island. The model-based clustering algorithm, implemented in STRUCTURE, defined six clusters with very distinct genetic signatures, four of which corresponded to single villages. The extent of background LD, assessed with eight linked markers on Xq13-21, paralleled the extent of differentiation and was also very high in most of the populations under study. For each population, demographic history was characterised and 12 "demographic history" variables were tentatively defined. Following stepwise regression, the demographic history variable that most significantly predicted the extent of LD was the proportion of locally born grandparents. Strong isolation and endogamy are likely to be the main forces maintaining this highly structured overall population.

Cluster Analysis↗

PubMed2005

Maximum significance clustering of oligonucleotide microarrays.

MOTIVATION: Affymetrix high-density oligonucleotide microarrays measure the expression of DNA transcripts using probesets, i.e. multiple probes per transcript. Usually, these multiple measurements are transformed into a single probeset expression level before data analysis proceeds; any information on variability is lost. In this paper we demonstrate how individual probe measurements can be used in a statistic for differential expression. Furthermore, we show how this statistic can serve as a criterion for clustering microarrays. RESULTS: A novel clustering algorithm using this maximum significance criterion is demonstrated to be more efficient with the measured data than competing techniques for dealing with repeated measurements, especially when the sample size is small.

Algorithms↗

PubMed2004

Dual geometric worm algorithm for two-dimensional discrete classical lattice models.

We present a dual geometrical worm algorithm for two-dimensional Ising models. The existence of such dual algorithms was first pointed out by Prokof'ev and Svistunov [Phys. Rev. Lett. 87, 160601 (2001)]]. The algorithm is defined on the dual lattice and is formulated in terms of bond variables and can therefore be generalized to other two-dimensional models that can be formulated in terms of bond variables. We also discuss two related algorithms formulated on the direct lattice, applicable in any dimension. These latter algorithms turn out to be less efficient but of considerable intrinsic interest. We show how such algorithms quite generally can be "directed" by minimizing the probability for the worms to erase themselves. Explicit proofs of detailed balance are given for all the algorithms. In terms of computational efficiency the dual geometrical worm algorithm is comparable to well known cluster algorithms such as the Swendsen-Wang and Wolff algorithms, however, it is quite different in structure and allows for a very simple and efficient implementation. The dual algorithm also allows for a very elegant way of calculating the domain wall free energy.

Journal Article↗

PubMed2005

Object-based image analysis using multiscale connectivity.

This paper introduces a novel approach for image analysis based on the notion of multiscale connectivity. We use the proposed approach to design several novel tools for object-based image representation and analysis which exploit the connectivity structure of images in a multiscale fashion. More specifically, we propose a nonlinear pyramidal image representation scheme, which decomposes an image at different scales by means of multiscale grain filters. These filters gradually remove connected components from an image that fail to satisfy a given criterion. We also use the concept of multiscale connectivity to design a hierarchical data partitioning tool. We employ this tool to construct another image representation scheme, based on the concept of component trees, which organizes partitions of an image in a hierarchical multiscale fashion. In addition, we propose a geometrically-oriented hierarchical clustering algorithm which generalizes the classical single-linkage algorithm. Finally, we propose two object-based multiscale image summaries, reminiscent of the well-known (morphological) pattern spectrum, which can be useful in image analysis and image understanding applications.

Algorithms↗