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

PubMed2004

Iterative class discovery and feature selection using Minimal Spanning Trees.

BACKGROUND: Clustering is one of the most commonly used methods for discovering hidden structure in microarray gene expression data. Most current methods for clustering samples are based on distance metrics utilizing all genes. This has the effect of obscuring clustering in samples that may be evident only when looking at a subset of genes, because noise from irrelevant genes dominates the signal from the relevant genes in the distance calculation. RESULTS: We describe an algorithm for automatically detecting clusters of samples that are discernable only in a subset of genes. We use iteration between Minimal Spanning Tree based clustering and feature selection to remove noise genes in a step-wise manner while simultaneously sharpening the clustering. Evaluation of this algorithm on synthetic data shows that it resolves planted clusters with high accuracy in spite of noise and the presence of other clusters. It also shows a low probability of detecting spurious clusters. Testing the algorithm on some well known micro-array data-sets reveals known biological classes as well as novel clusters. CONCLUSIONS: The iterative clustering method offers considerable improvement over clustering in all genes. This method can be used to discover partitions and their biological significance can be determined by comparing with clinical correlates and gene annotations. The MATLAB programs for the iterative clustering algorithm are available from http://linus.nci.nih.gov/supplement.html

Acute Disease↗

PubMed2006

A generalized clustering problem, with application to DNA microarrays.

We think of cluster analysis as class discovery. That is, we assume that there is an unknown mapping called clustering structure that assigns a class label to each observation, and the goal of cluster analysis is to estimate this clustering structure, that is, to estimate the number of clusters and cluster assignments. In traditional cluster analysis, it is assumed that such unknown mapping is unique. However, since the observations may cluster in more than one way depending on the variables used, it is natural to permit the existence of more than one clustering structure. This generalized clustering problem of estimating multiple clustering structures is the focus of this paper. We propose an algorithm for finding multiple clustering structures of observations which involves clustering both variables and observations. The number of clustering structures is determined by the number of variable clusters. The dissimilarity measure for clustering variables is based on nearest-neighbor graphs. The observations are clustered using weighted distances with weights determined by the clusters of the variables. The motivating application is to gene expression data.

Algorithms↗

PubMed2004

Frequency-sensitive competitive learning for scalable balanced clustering on high-dimensional hyperspheres.

Competitive learning mechanisms for clustering, in general, suffer from poor performance for very high-dimensional (>1000) data because of "curse of dimensionality" effects. In applications such as document clustering, it is customary to normalize the high-dimensional input vectors to unit length, and it is sometimes also desirable to obtain balanced clusters, i.e., clusters of comparable sizes. The spherical kmeans (spkmeans) algorithm, which normalizes the cluster centers as well as the inputs, has been successfully used to cluster normalized text documents in 2000+ dimensional space. Unfortunately, like regular kmeans and its soft expectation-maximization-based version, spkmeans tends to generate extremely imbalanced clusters in high-dimensional spaces when the desired number of clusters is large (tens or more). This paper first shows that the spkmeans algorithm can be derived from a certain maximum likelihood formulation using a mixture of von Mises-Fisher distributions as the generative model, and in fact, it can be considered as a batch-mode version of (normalized) competitive learning. The proposed generative model is then adapted in a principled way to yield three frequency-sensitive competitive learning variants that are applicable to static data and produced high-quality and well-balanced clusters for high-dimensional data. Like kmeans, each iteration is linear in the number of data points and in the number of clusters for all the three algorithms. A frequency-sensitive algorithm to cluster streaming data is also proposed. Experimental results on clustering of high-dimensional text data sets are provided to show the effectiveness and applicability of the proposed techniques. Index Terms-Balanced clustering, expectation maximization (EM), frequency-sensitive competitive learning (FSCL), high-dimensional clustering, kmeans, normalized data, scalable clustering, streaming data, text clustering.

Artificial Intelligence↗

PubMed2005

A hybrid genetic algorithm and expectation maximization method for global gene trajectory clustering.

Clustering time-course gene expression data (gene trajectories) is an important step towards solving the complex problem of gene regulatory network modeling and discovery as it significantly reduces the dimensionality of the gene space required for analysis. Traditional clustering methods that perform hill-climbing from randomly initialized cluster centers are prone to produce inconsistent and sub-optimal cluster solutions over different runs. This paper introduces a novel method that hybridizes genetic algorithm (GA) and expectation maximization algorithms (EM) for clustering gene trajectories with the mixtures of multiple linear regression models (MLRs), with the objective of improving the global optimality and consistency of the clustering performance. The proposed method is applied to cluster the human fibroblasts and the yeast time-course gene expression data based on their trajectory similarities. It outperforms the standard EM method significantly in terms of both clustering accuracy and consistency. The biological implications of the improved clustering performance are demonstrated.

Algorithms↗

PubMedDate not supplied

Text mining biomedical literature for discovering gene-to-gene relationships: a comparative study of algorithms.

Partitioning closely related genes into clusters has become an important element of practically all statistical analyses of microarray data. A number of computer algorithms have been developed for this task. Although these algorithms have demonstrated their usefulness for gene clustering, some basic problems remain. This paper describes our work on extracting functional keywords from MEDLINE for a set of genes that are isolated for further study from microarray experiments based on their differential expression patterns. The sharing of functional keywords among genes is used as a basis for clustering in a new approach called BEA-PARTITION in this paper. Functional keywords associated with genes were extracted from MEDLINE abstracts. We modified the Bond Energy Algorithm (BEA), which is widely accepted in psychology and database design but is virtually unknown in bioinformatics, to cluster genes by functional keyword associations. The results showed that BEA-PARTITION and hierarchical clustering algorithm outperformed k-means clustering and self-organizing map by correctly assigning 25 of 26 genes in a test set of four known gene groups. To evaluate the effectiveness of BEA-PARTITION for clustering genes identified by microarray profiles, 44 yeast genes that are differentially expressed during the cell cycle and have been widely studied in the literature were used as a second test set. Using established measures of cluster quality, the results produced by BEA-PARTITION had higher purity, lower entropy, and higher mutual information than those produced by k-means and self-organizing map. Whereas BEA-PARTITION and the hierarchical clustering produced similar quality of clusters, BEA-PARTITION provides clear cluster boundaries compared to the hierarchical clustering. BEA-PARTITION is simple to implement and provides a powerful approach to clustering genes or to any clustering problem where starting matrices are available from experimental observations.

Abstracting and Indexing↗

PubMed1991

Fuzzy K-nearest neighbor classifiers for ventricular arrhythmia detection.

We report a study of the efficiency of 4 classifiers (the K-nearest-neighbor and single-nearest-prototype algorithms, each as parametrized by both Fuzzy C-Means and Fuzzy Covariance clustering) in the detection of ventricular arrhythmias in ECG traces characterized by 4 features derived from 7 spectral parameters. Principal components analysis was used in conjunction with a cardiologist's deterministic classification of 90 ECG traces to fix the number of trace classes to 5 (ventricular fibrillation/flutter, sinus rhythm, ventricular rhythms with aberrant complexes and 2 classes of artefact). Forty of the 90 traces were then defined as a test set; 5 different learning sets (numbering 25, 30, 35, 40 and 45 traces) were randomly selected from the remaining 50 traces; each learning set was used to parametrize both the classification algorithms using both fuzzy clustering algorithms and the parametrized classification algorithms were then applied to the test set. Optimal K for K-nearest-neighbor algorithms and optimal cluster volumes for Fuzzy Covariance algorithms were sought by trial and error to minimize classification differences with respect to the cardiologist's classification. Fuzzy Covariance clustering afforded significantly better perception of cluster structure than the Fuzzy C-Means algorithm, and the classifiers performed correspondingly with an overall empirical error ratio of just 0.10 for the K-nearest-neighbor algorithm parametrized by Fuzzy Covariance.

Algorithms↗

PubMed2006

Fine mapping of disease genes via haplotype clustering.

We propose an algorithm for analysing SNP-based population association studies, which is a development of that introduced by Molitor et al. [2003: Am J Hum Genet 73:1368-1384]. It uses clustering of haplotypes to overcome the major limitations of many current haplotype-based approaches. We define a between-haplotype score that is simple, yet appears to capture much of the information about evolutionary relatedness of the haplotypes in the vicinity of a (unobserved) putative causal locus. Haplotype clusters can then be defined via a putative ancestral haplotype and a cut-off distance. The number of an individual's two haplotypes that lie within the cluster predicts the individual's genotype at the causal locus. This predicted genotype can then be investigated for association with the phenotype of interest. We implement our approach within a Markov-chain Monte Carlo algorithm that, in effect, searches over locations and ancestral haplotypes to identify large, case-rich clusters. The algorithm successfully fine-maps a causal mutation in a test analysis using real data, and achieves almost 98% accuracy in predicting the genotype at the causal locus. A simulation study indicates that the new algorithm is substantially superior to alternative approaches, and it also allows us to identify situations in which multi-point approaches can substantially improve over single-SNP analyses. Our algorithm runs quickly and there is scope for extension to a wide range of disease models and genomic scales.

Algorithms↗

PubMed1998

Spatial and temporal pattern analysis via spiking neurons.

Spiking neurons, receiving temporally encoded inputs, can compute radial basis functions (RBFs) by storing the relevant information in their delays. In this paper we show how these delays can be learned using exclusively locally available information (basically the time difference between the pre- and postsynaptic spikes). Our approach gives rise to a biologically plausible algorithm for finding clusters in a high-dimensional input space with networks of spiking neurons, even if the environment is changing dynamically. Furthermore, we show that our learning mechanism makes it possible that such RBF neurons can perform some kind of feature extraction where they recognize that only certain input coordinates carry relevant information. Finally we demonstrate that this model allows the recognition of temporal sequences even if they are distorted in various ways.

Action Potentials↗

PubMed2001

Contextual clustering for analysis of functional MRI data.

We present a contextual clustering procedure for statistical parametric maps (SPM) calculated from time varying three-dimensional images. The algorithm can be used for the detection of neural activations from functional magnetic resonance images (fMRI). An important characteristic of SPM is that the intensity distribution of background (nonactive area) is known whereas the distributions of activation areas are not. The developed contextual clustering algorithm divides an SPM into background and activation areas so that the probability of detecting false activations by chance is controlled, i.e., hypothesis testing is performed. Unlike the much used voxel-by-voxel testing, neighborhood information is utilized, an important difference. This is achieved by using a Markov random field prior and iterated conditional modes (ICM) algorithm. However, unlike in the conventional use of ICM algorithm, the classification is based only on the distribution of background. The results from our simulations and human fMRI experiments using visual stimulation demonstrate that a better sensitivity is achieved with a given specificity in comparison to the voxel-by-voxel thresholding technique. The algorithm is computationally efficient and can be used to detect and delineate objects from a noisy background in other applications.

Algorithms↗

PubMed1996

Adaptive motor unit action potential clustering using shape and temporal information.

An adaptive algorithm is described that groups motor unit action potentials (MUAPs), detected in a composite EMG signal during signal decomposition, and creates partial motor unit action potential trains (MUAPTs). Data-driven MUAP shape and motor unit firing-pattern based criteria are used to form the clusters. An algorithm for estimating MUAPT temporal parameters, which provides accurate estimates even for partially defined trains, is used to obtain firing-pattern information. No a priori knowledge is required regarding the number of clusters or the distribution of their template shapes. The clustering algorithm when applied to real concentric-needle detected MUAP data provides accurate and useful clustering results. Compared to a classical leader-based algorithm, it provides more robust performance, is better able to estimate the true number of motor units represented in a set of detected MUAPs, and obtains more complete and accurate MUAPTs.

Action Potentials↗

PubMed2002

Using replicator dynamics for analyzing fMRI data of the human brain.

The understanding of brain networks becomes increasingly the focus of current research. In the context of functional magnetic resonance imagery (fMRI) data of the human brain, networks have been mostly detected using standard clustering approaches. In this work, we present a new method of detecting functional networks using fMRI data. The novelty of this method is that these networks have the property that every network member is closely connected with every other member. This definition might to be better suited to model important aspects of brain activity than standard cluster definitions. The algorithm that we present here is based on a concept from theoretical biology called "replicator dynamics."

Algorithms↗

PubMed2003

AntiClustal: Multiple Sequence Alignment by antipole clustering and linear approximate 1-median computation.

In this paper we present a new Multiple Sequence Alignment (MSA) algorithm called AntiClusAl. The method makes use of the commonly use idea of aligning homologous sequences belonging to classes generated by some clustering algorithm, and then continue the alignment process ina bottom-up way along a suitable tree structure. The final result is then read at the root of the tree. Multiple sequence alignment in each cluster makes use of the progressive alignment with the 1-median (center) of the cluster. The 1-median of set S of sequences is the element of S which minimizes the average distance from any other sequence in S. Its exact computation requires quadratic time. The basic idea of our proposed algorithm is to make use of a simple and natural algorithmic technique based on randomized tournaments which has been successfully applied to large size search problems in general metric spaces. In particular a clustering algorithm called Antipole tree and an approximate linear 1-median computation are used. Our algorithm compared with Clustal W, a widely used tool to MSA, shows a better running time results with fully comparable alignment quality. A successful biological application showing high aminoacid conservation during evolution of Xenopus laevis SOD2 is also cited.

Algorithms↗

PubMedDate not supplied

Global optimization of Lennard-Jones clusters by a parallel fast annealing evolutionary algorithm.

A parallel fast annealing evolutionary algorithm (PFAEA) was presented and applied to optimize Lennard-Jones (LJ) clusters. All the lowest known minima up to LJ(116) with both icosahedral and nonicosahedral structure, including the truncated octahedron of LJ(38), central fcc tetrahedron of LJ(98), the Marks' decahedron of LJ(75)(-)(77), and LJ(102)(-)(104), were located successfully by the unbiased algorithm. PFAEA is a parallel version of fast annealing evolutionary algorithm (FAEA) that combines the aspect of population in genetic algorithm and annealing algorithm with a very fast annealing schedule. A master-slave paradigm is used to parallelize FAEA to improve the efficiency. The performance of PFAEA is studied, and the scaling of execution time with the cluster size is approximately cubic, which is important for larger scale energy minimization systems.

Journal Article↗

PubMed2003

New algorithms for multi-class cancer diagnosis using tumor gene expression signatures.

MOTIVATION: The increasing use of DNA microarray-based tumor gene expression profiles for cancer diagnosis requires mathematical methods with high accuracy for solving clustering, feature selection and classification problems of gene expression data. RESULTS: New algorithms are developed for solving clustering, feature selection and classification problems of gene expression data. The clustering algorithm is based on optimization techniques and allows the calculation of clusters step-by-step. This approach allows us to find as many clusters as a data set contains with respect to some tolerance. Feature selection is crucial for a gene expression database. Our feature selection algorithm is based on calculating overlaps of different genes. The database used, contains over 16 000 genes and this number is considerably reduced by feature selection. We propose a classification algorithm where each tissue sample is considered as the center of a cluster which is a ball. The results of numerical experiments confirm that the classification algorithm in combination with the feature selection algorithm perform slightly better than the published results for multi-class classifiers based on support vector machines for this data set. AVAILABILITY: Available on request from the authors.

Algorithms↗

PubMed2005

A mathematical and computational framework for quantitative comparison and integration of large-scale gene expression data.

Analysis of large-scale gene expression studies usually begins with gene clustering. A ubiquitous problem is that different algorithms applied to the same data inevitably give different results, and the differences are often substantial, involving a quarter or more of the genes analyzed. This raises a series of important but nettlesome questions: How are different clustering results related to each other and to the underlying data structure? Is one clustering objectively superior to another? Which differences, if any, are likely candidates to be biologically important? A systematic and quantitative way to address these questions is needed, together with an effective way to integrate and leverage expression results with other kinds of large-scale data and annotations. We developed a mathematical and computational framework to help quantify, compare, visualize and interactively mine clusterings. We show that by coupling confusion matrices with appropriate metrics (linear assignment and normalized mutual information scores), one can quantify and map differences between clusterings. A version of receiver operator characteristic analysis proved effective for quantifying and visualizing cluster quality and overlap. These methods, plus a flexible library of clustering algorithms, can be called from a new expandable set of software tools called CompClust 1.0 (http://woldlab.caltech.edu/compClust/). CompClust also makes it possible to relate expression clustering patterns to DNA sequence motif occurrences, protein-DNA interaction measurements and various kinds of functional annotations. Test analyses used yeast cell cycle data and revealed data structure not obvious under all algorithms. These results were then integrated with transcription motif and global protein-DNA interaction data to identify G1 regulatory modules.

Algorithms↗

PubMed2004

A graph-theoretic modeling on GO space for biological interpretation of gene clusters.

MOTIVATION: With the advent of DNA microarray technologies, the parallel quantification of genome-wide transcriptions has been a great opportunity to systematically understand the complicated biological phenomena. Amidst the enthusiastic investigations into the intricate gene expression data, clustering methods have been the useful tools to uncover the meaningful patterns hidden in those data. The mathematical techniques, however, entirely based on the numerical expression data, do not show biologically relevant information on the clustering results. RESULTS: We present a novel methodology for biological interpretation of gene clusters. Our graph theoretic algorithm extracts common biological attributes of the genes within a cluster or a group of interest through the modified structure of gene ontology (GO) called GO tree. After genes are annotated with GO terms, the hierarchical nature of GO terms is used to find the representative biological meanings of the gene clusters. In addition, the biological significance of gene clusters can be assessed quantitatively by defining a distance function on the GO tree. Our approach has a complementary meaning to many statistical clustering techniques; we can see clustering problems from a different viewpoint by use of biological ontology. We applied this algorithm to the well-known data set and successfully obtained the biological features of the gene clusters with the quantitative biological assessment of clustering quality through GO Biological Process.

Algorithms↗

PubMed2006

Blue-noise halftoning for hexagonal grids.

In this paper, we closely scrutinize the spatial and spectral properties of aperiodic halftoning schemes on rectangular and hexagonal sampling grids. Traditionally, hexagonal sampling grids have been shunned due to their inability to preserve the high-frequency components of blue-noise dither patterns at gray-levels near one-half, but as will be shown, only through the introduction of diagonal correlations between dots can even rectangular sampling grids preserve these frequencies. And by allowing the sampling grid to constrain the placement of dots, a particular algorithm may introduce visual artifacts just as disturbing as excess energy below the principal frequency. If, instead, the algorithm maintains radial symmetry by introducing a minimum degree of clustering, then that algorithm can maintain its grid defiance illusion fundamental to the spirit of the blue-noise model. As such, this paper shows that hexagonal grids are preferrable because they can support gray-levels near one-half with less required clustering of minority pixels and a higher principal frequency. Along with a thorough Fourier analysis of blue-noise dither patterns on both rectangular and hexagonal sampling grids, this paper also demonstrates the construction of a blue-noise dither array for hexagonal grids.

Algorithms↗

PubMed2001

Clustering protein sequences--structure prediction by transitive homology.

MOTIVATION: It is widely believed that for two proteins Aand Ba sequence identity above some threshold implies structural similarity due to a common evolutionary ancestor. Since this is only a sufficient, but not a necessary condition for structural similarity, the question remains what other criteria can be used to identify remote homologues. Transitivity refers to the concept of deducing a structural similarity between proteins A and C from the existence of a third protein B, such that A and B as well as B and C are homologues, as ascertained if the sequence identity between A and B as well as that between B and C is above the aforementioned threshold. It is not fully understood if transitivity always holds and whether transitivity can be extended ad infinitum. RESULTS: We developed a graph-based clustering approach, where transitivity plays a crucial role. We determined all pair-wise similarities for the sequences in the SwissProt database using the Smith-Waterman local alignment algorithm. This data was transformed into a directed graph, where protein sequences constitute vertices. A directed edge was drawn from vertex A to vertex B if the sequences A and B showed similarity, scaled with respect to the self-similarity of A, above a fixed threshold. Transitivity was important in the clustering process, as intermediate sequences were used, limited though by the requirement of having directed paths in both directions between proteins linked over such sequences. The length dependency-implied by the self-similarity-of the scaling of the alignment scores appears to be an effective criterion to avoid clustering errors due to multi-domain proteins. To deal with the resulting large graphs we have developed an efficient library. Methods include the novel graph-based clustering algorithm capable of handling multi-domain proteins and cluster comparison algorithms. Structural Classification of Proteins (SCOP) was used as an evaluation data set for our method, yielding a 24% improvement over pair-wise comparisons in terms of detecting remote homologues. AVAILABILITY: The software is available to academic users on request from the authors. CONTACT: e.bolten@science-factory.com; schliep@zpr.uni-koeln.de; s.schneckener@science-factory.com; d.schomburg@uni-koeln.de; schrader@zpr.uni-koeln.de. SUPPLEMENTARY INFORMATION: http://www.zaik.uni-koeln.de/~schliep/ProtClust.html.

Algorithms↗