PubMed Health⌕ Search

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,675 records · Page 93Linked to original sources
PubMed1999

Multiple structural alignment and core detection by geometric hashing.

A Multiple Structural Alignment algorithm is presented. The algorithm accepts an ensemble of protein structures and finds the largest substructure (core) of C alpha atoms whose geometric configuration appear in all the molecules of the ensemble (core). Both the detection of this core and the resulting structural alignment are done simultaneously. Other large enough multistructural superimpositions are detected as well. Our method is based on the Geometric Hashing paradigm and a superimposition clustering technique which represents superimpositions by sets of matching atoms. The algorithm proved to be efficient on real data in a series of experiments. The same method can be applied to any ensemble of molecules (not necessarily proteins) since our basic technique is sequence order independent.

Algorithms↗
PubMed2005

Continuous extremal optimization for Lennard-Jones clusters.

We explore a general-purpose heuristic algorithm for finding high-quality solutions to continuous optimization problems. The method, called continuous extremal optimization (CEO), can be considered as an extension of extremal optimization and consists of two components, one which is responsible for global searching and the other which is responsible for local searching. The CEO's performance proves competitive with some more elaborate stochastic optimization procedures such as simulated annealing, genetic algorithms, and so on. We demonstrate it on a well-known continuous optimization problem: the Lennard-Jones cluster optimization problem.

Journal Article↗
PubMed2003

Exhaustive enumeration of protein domain families.

Domains are considered as the basic units of protein folding, evolution, and function. Decomposing each protein into modular domains is thus a basic prerequisite for accurate functional classification of biological molecules. Here, we present ADDA, an automatic algorithm for domain decomposition and clustering of all protein domain families. We use alignments derived from an all-on-all sequence comparison to define domains within protein sequences based on a global maximum likelihood model. In all, 90% of domain boundaries are predicted within 10% of domain size when compared with the manual domain definitions given in the SCOP database. A representative database of 249,264 protein sequences were decomposed into 450,462 domains. These domains were clustered on the basis of sequence similarities into 33,879 domain families containing at least two members with less than 40% sequence identity. Validation against family definitions in the manually curated databases SCOP and PFAM indicates almost perfect unification of various large domain families while contamination by unrelated sequences remains at a low level. The global survey of protein-domain space by ADDA confirms that most large and universal domain families are already described in PFAM and/or SMART. However, a survey of the complete set of mobile modules leads to the identification of 1479 new interesting domain families which shuffle around in multi-domain proteins. The data are publicly available at ftp://ftp.ebi.ac.uk/pub/contrib/heger/adda.

Algorithms↗
PubMed1999

Rosenbluth chain cluster growth in the study of micelle self-assembly.

A Rosenbluth algorithm [J. Chem. Phys. 23, 356 (1955)] for enumerating clusters of chains is presented. The method is used to undertake a direct enumeration of the cluster partition function for small clusters in a three-dimensional lattice model of a binary mixture of amphiphile and solvent. In this model, the amphiphiles are represented as connected chains on a lattice, with vacant sites representing the solvent. The results from the Rosenbluth method are compared with those obtained by Metropolis Monte Carlo simulations which allow free self-assembly of clusters. The agreement between the two methods allows an unambiguous identification of the packing entropy associated with micelle self-assembly. Results are presented for unbranched chains having two head and four tail segments (H2T4) and also four head and four tail segments (H4T4). Although the cluster enumeration method described in this paper has been developed for micellar systems, it will have applications in a variety of areas including nucleation and percolation.

Journal Article↗
PubMed2004

Exhaustive whole-genome tandem repeats search.

MOTIVATION: Approximate tandem repeats (ATR) occur frequently in the genomes of organisms, and are a source of polymorphisms observed in individuals, and thus are of interest to those studying genetic disorders. Though extensive work has been done in order to identify ATRs, there are inherent limitations with the current approaches in terms of the number of pattern sizes that can be searched or the size of the input length. RESULTS: This paper describes (1) a new algorithm which exhaustively finds all variable-length ATRs in a genomic sequence and (2) a precise description of, and an algorithm to significantly reduce, redundancy in the output. Our ATR definition is parameterized by a mismatch ratio p which allows for more mismatches in longer tandem repeats (and fewer in shorter). Furthermore, our algorithm is embarrassingly parallel and thus can attain near-linear speed-up on Beowulf clusters. We present results of our algorithm applied to sequences of widely differing lengths (from genes to chromosomes). AVAILABILITY: Source and binaries are available on request.

Algorithms↗
PubMed1993

Computational waveform analysis and classification of auditory brainstem evoked potentials.

The widely used quantitative descriptors of amplitude and latency of evoked potentials, for peaks and troughs along the waveform, relate to only a limited number of points along the waveform, ignoring the interposed data. Moreover, these descriptors are typically determined manually, rendering them susceptible to user bias. We propose and demonstrate a machine-scoring algorithm for the identification and measurement of Auditory Brainstem Evoked Potentials (ABEP) peaks I, III and V. We further introduce an algorithm for the quantitative analysis of ABEP by waveform, and for clustering records according to waveform characteristics. The results of computerized peak identification and measurement, without user intervention, were correlated with manual measurements of the same peaks in a large number of waveforms. The waveform analysis and classification procedure differentiated waveforms to monaural left, monaural right and binaural stimulation, as well as according to the recording montage. These results underscore the advantages of using information in the waveform of ABEP, which has so far been overlooked. The automated algorithms for evaluation of ABEP by waveform hold the promise of a more comprehensive and consistent evaluation, and hence improved sensitivity.

Adult↗
PubMed2001

Volume learning algorithm artificial neural networks for 3D QSAR studies.

The current study introduces a new method, the volume learning algorithm (VLA), for the investigation of three-dimensional quantitative structure-activity relationships (QSAR) of chemical compounds. This method incorporates the advantages of comparative molecular field analysis (CoMFA) and artificial neural network approaches. VLA is a combination of supervised and unsupervised neural networks applied to solve the same problem. The supervised algorithm is a feed-forward neural network trained with a back-propagation algorithm while the unsupervised network is a self-organizing map of Kohonen. The use of both of these algorithms makes it possible to cluster the input CoMFA field variables and to use only a small number of the most relevant parameters to correlate spatial properties of the molecules with their activity. The statistical coefficients calculated by the proposed algorithm for cannabimimetic aminoalkyl indoles were comparable to, or improved, in comparison to the original study using the partial least squares algorithm. The results of the algorithm can be visualized and easily interpreted. Thus, VLA is a new convenient tool for three-dimensional QSAR studies.

Algorithms↗
PubMed2004

Constrained clusters of gene expression profiles with pathological features.

MOTIVATION: Gene expression profiles should be useful in distinguishing variations in disease, since they reflect accurately the status of cells. The primary clustering of gene expression reveals the genotypes that are responsible for the proximity of members within each cluster, while further clustering elucidates the pathological features of the individual members of each cluster. However, since the first clustering process and the second classification step, in which the features are associated with clusters, are performed independently, the initial set of clusters may omit genes that are associated with pathologically meaningful features. Therefore, it is important to devise a way of identifying gene expression clusters that are associated with pathological features. RESULTS: We present the novel technique of 'itemset constrained clustering' (IC-Clustering), which computes the optimal cluster that maximizes the interclass variance of gene expression between groups, which are divided according to the restriction that only divisions that can be expressed using common features are allowed. This constraint automatically labels each cluster with a set of pathological features which characterize that cluster. When applied to liver cancer datasets, IC-Clustering revealed informative gene expression clusters, which could be annotated with various pathological features, such as 'tumor' and 'man', or 'except tumor' and 'normal liver function'. In contrast, the k-means method overlooked these clusters.

Algorithms↗
PubMed2006

Evaluation and comparison of gene clustering methods in microarray analysis.

MOTIVATION: Microarray technology has been widely applied in biological and clinical studies for simultaneous monitoring of gene expression in thousands of genes. Gene clustering analysis is found useful for discovering groups of correlated genes potentially co-regulated or associated to the disease or conditions under investigation. Many clustering methods including hierarchical clustering, K-means, PAM, SOM, mixture model-based clustering and tight clustering have been widely used in the literature. Yet no comprehensive comparative study has been performed to evaluate the effectiveness of these methods. RESULTS: In this paper, six gene clustering methods are evaluated by simulated data from a hierarchical log-normal model with various degrees of perturbation as well as four real datasets. A weighted Rand index is proposed for measuring similarity of two clustering results with possible scattered genes (i.e. a set of noise genes not being clustered). Performance of the methods in the real data is assessed by a predictive accuracy analysis through verified gene annotations. Our results show that tight clustering and model-based clustering consistently outperform other clustering methods both in simulated and real data while hierarchical clustering and SOM perform among the worst. Our analysis provides deep insight to the complicated gene clustering problem of expression profile and serves as a practical guideline for routine microarray cluster analysis.

Algorithms↗
PubMed2005

Pattern vectors from algebraic graph theory.

Graph structures have proven computationally cumbersome for pattern analysis. The reason for this is that, before graphs can be converted to pattern vectors, correspondences must be established between the nodes of structures which are potentially of different size. To overcome this problem, in this paper, we turn to the spectral decomposition of the Laplacian matrix. We show how the elements of the spectral matrix for the Laplacian can be used to construct symmetric polynomials that are permutation invariants. The coefficients of these polynomials can be used as graph features which can be encoded in a vectorial manner. We extend this representation to graphs in which there are unary attributes on the nodes and binary attributes on the edges by using the spectral decomposition of a Hermitian property matrix that can be viewed as a complex analogue of the Laplacian. To embed the graphs in a pattern space, we explore whether the vectors of invariants can be embedded in a low-dimensional space using a number of alternative strategies, including principal components analysis (PCA), multidimensional scaling (MDS), and locality preserving projection (LPP). Experimentally, we demonstrate that the embeddings result in well-defined graph clusters. Our experiments with the spectral representation involve both synthetic and real-world data. The experiments with synthetic data demonstrate that the distances between spectral feature vectors can be used to discriminate between graphs on the basis of their structure. The real-world experiments show that the method can be used to locate clusters of graphs.

Algorithms↗
PubMed1994

Automatic detection of clustered, fluorescent-stained nuclei by digital image-based cytometry.

Automatic image-based cytometry (IC) can conveniently quantify the distributions of several specific, fluorescence-labeled molecules within individual, isolated cells of slide- or tissue-based specimens. However, many specimens contain clusters of cells or nuclei that are not detected as individual entities by existing automatic methods. We have developed analysis algorithms which detected individual nuclei occurring in clusters or as isolated nuclei. Specimens were labeled with a fluorescent DNA stain, imaged and the images were segmented into regions of nuclei and background. Clusters of nuclei, identified by their size and shape, were divided into individual nuclei by searching for dividing paths between nuclei. The paths, which need not be straight, possessed the highest average gradient per pixel. In addition, both high- and low-pass filtered images of the original image were analyzed. For each individual nucleus, one of the three segmented regions representing the nucleus (from either the original or one of two filtered images) was chosen as the final result, based on the closeness of the regions to average nuclear morphology. The algorithms correctly detected a high proportion of isolated (328/333) and clustered (254/271) nuclei when applied to images of 2 microns prostate and breast cancer sections. Thus, these algorithms should enable much more accurate detection and analyses of nuclei in intact specimens.

Algorithms↗
PubMed1997

Fuzzy clustering of children with cerebral palsy based on temporal-distance gait parameters.

Temporal-distance parameters for 88 children with the spastic diplegia form of cerebral palsy (CP) are grouped using the fuzzy clustering paradigm. The two features chosen for clustering are stride length and cadence which are normalized for age and leg length using a model based on a population of 68 neurologically intact children. Using information provided by the neurologically intact population and cluster validity techniques, five clusters for the children with cerebral palsy are identified. The five cluster centers represent distinct walking strategies adopted by children with cerebral palsy. Utilizing just four easily obtained parameters--stride length, cadence, leg length and age--and a small number of simple equations, it is possible to classify any child with spastic diplegia and to generate an individual's membership values for each of the five clusters. The clinical utility of the fuzzy clustering approach is demonstrated with pre- and post-operative test data for subjects with cerebral palsy (one neurosurgical and one orthopaedic) where changes in membership of the five clusters provide an objective technique for measuring improvement. This approach can be adopted to study other clinical entities where different cluster centers would be established using the algorithm provided here.

Adolescent↗
PubMedDate not supplied

[Application of neural networks using the volume learning algorithm for the study of structure-activity relationship in chemical compounds].

A volume learning algorithm for artificial neural networks was developed to quantitatively describe the three-dimensional structure-activity relationships using as an example N-benzylpiperidine derivatives. The new algorithm combines two types of neural networks, the Kohonen and the feed-forward artificial neural networks, which are used to analyze the input grid data generated by the comparative molecular field approach. Selection of the most informative parameters using the algorithm helped to reveal the most important spatial properties of the molecules, which affect their biological activities. Cluster regions determined using the new algorithm adequately predicted the activity of molecules from a control data set.

Algorithms↗
PubMedDate not supplied

Alkyl- and alkenylresorcinols of wheat grains and their chemotaxonomic significance.

Resorcinolic lipid contents and homologue compositions in extracts isolated from soft winter, soft spring and hard (durum) wheat grains were evaluated by both instrumental and chromatography means. Resorcinol concentrations determined in wheat were diverse and varied in samples harvested within two consecutive vegetative years, whereas their homologue profiles were found to be rather invariable. The predominant alkylresorcinols identified in wheat grains were saturated 1,3-dihydroxy-5-n-heneicosylbenzene and 1,3-dihydroxy-5-n-nonadecylbenzene. 1,3-Dihydroxy-5-n-heptadecylbenzene and 1,3-dihydroxy-5-n-tricosylbenzene were also determined, whereas 1,3-dihydroxy-5-n-pentadecylbenzene and 1,3-dihydroxy-5-n-pentacosylbenzene were present in these extracts only in spurious amounts. Furthermore, our results show that alk(en)ylresorcinols may be useful as chemotaxonomic markers for a distinction between soft and hard wheat plants. Cluster analysis with Ward's amalgamation algorithm and five different distance linkage types clearly discriminated particular wheats into species- and cultivar-specific clusters, whereas the use of principal component analysis allowed us to specify, which of the variables analysed were decisive. This approach may be useful for both plant breeders and taxonomists to classify wheat species/cultivars.

Phylogeny↗
PubMed2002

[Review: Segmentation and classification methods of 3D medical images].

This paper presents a survey of recent publications (published in 1990 or later) concerning segmentation and classification of medical images. These methods will be classified into six types: cluster (threshold), statistics methods, deformable contour, region growing, mathematics morphology, nonlinear methods (fuzzy segmentation, neural networks, genetic algorithm) and 3D model. Each of the major classes of image segmentation and classification techniques and several specific examples of each class of algorithm are described respectively in detail. At last, the developing trend of 3D medical image is also discussed.

Algorithms↗
PubMed2000

Anatomical connectivity defines the organization of clusters of cortical areas in the macaque monkey and the cat.

The number of different cortical structures in mammalian brains and the number of extrinsic fibres linking these regions are both large. As with any complex system, systematic analysis is required to draw reliable conclusions about the organization of the complex neural networks comprising these numerous elements. One aspect of organization that has long been suspected is that cortical networks are organized into 'streams' or 'systems'. Here we report computational analyses capable of showing whether clusters of strongly interconnected areas are aspects of the global organization of cortical systems in macaque and cat. We used two different approaches to analyse compilations of corticocortical connection data from the macaque and the cat. The first approach, optimal set analysis, employed an explicit definition of a neural 'system' or 'stream', which was based on differential connectivity. We defined a two-component cost function that described the cost of the global cluster arrangement of areas in terms of the areas' connectivity within and between candidate clusters. Optimal cluster arrangements of cortical areas were then selected computationally from the very many possible arrangements, using an evolutionary optimization algorithm. The second approach, non-parametric cluster analysis (NPCA), grouped cortical areas on the basis of their proximity in multidimensional scaling representations. We used non-metric multidimensional scaling to represent the cortical connectivity structures metrically in two and five dimensions. NPCA then analysed these representations to determine the nature of the clusters for a wide range of different cluster shape parameters. The results from both approaches largely agreed. They showed that macaque and cat cortices are organized into densely intra-connected clusters of areas, and identified the constituent members of the clusters. These clusters reflected functionally specialized sets of cortical areas, suggesting that structure and function are closely linked at this gross, systems level.

Algorithms↗
PubMed2005

Generalizing Swendsen-Wang to sampling arbitrary posterior probabilities.

Many vision tasks can be formulated as graph partition problems that minimize energy functions. For such problems, the Gibbs sampler provides a general solution but is very slow, while other methods, such as Ncut and graph cuts are computationally effective but only work for specific energy forms and are not generally applicable. In this paper, we present a new inference algorithm that generalizes the Swendsen-Wang method to arbitrary probabilities defined on graph partitions. We begin by computing graph edge weights, based on local image features. Then, the algorithm iterates two steps. 1) Graph clustering: It forms connected components by cutting the edges probabilistically based on their weights. 2) Graph relabeling: It selects one connected component and flips probabilistically, the coloring of all vertices in the component simultaneously. Thus, it realizes the split, merge, and regrouping of a "chunk" of the graph, in contrast to Gibbs sampler that flips a single vertex. We prove that this algorithm simulates ergodic and reversible Markov chain jumps in the space of graph partitions and is applicable to arbitrary posterior probabilities or energy functions defined on graphs. We demonstrate the algorithm on two typical problems in computer vision--image segmentation and stereo vision. Experimentally, we show that it is 100-400 times faster in CPU time than the classical Gibbs sampler and 20-40 times faster then the DDMCMC segmentation algorithm. For stereo, we compare performance with graph cuts and belief propagation. We also show that our algorithm can automatically infer generative models and obtain satisfactory results (better than the graphic cuts or belief propagation) in the same amount of time.

Algorithms↗