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

Automated intensity descent algorithm for interpretation of complex high-resolution mass spectra.

This paper describes a new automated intensity descent algorithm for analysis of complex high-resolution mass spectra. The algorithm has been successfully applied to interpret Fourier transform mass spectra of proteins; however, it should be generally applicable to complex high-resolution mass spectra of large molecules recorded by other instruments. The algorithm locates all possible isotopic clusters by a novel peak selection method and a robust cluster subtraction technique according to the order of descending peak intensity after global noise level estimation and baseline correction. The peak selection method speeds up charge state determination and isotopic cluster identification. A Lorentzian-based peak subtraction technique resolves overlapping clusters in high peak density regions. A noise flag value is introduced to minimize false positive isotopic clusters. Moreover, correlation coefficients and matching errors between the identified isotopic multiplets and the averagine isotopic abundance distribution are the criteria for real isotopic clusters. The best fitted averagine isotopic abundance distribution of each isotopic cluster determines the charge state and the monoisotopic mass. Three high-resolution mass spectra were interpreted by the program. The results show that the algorithm is fast in computational speed, robust in identification of overlapping clusters, and efficient in minimization of false positives. In approximately 2 min, the program identified 611 isotopic clusters for a plasma ECD spectrum of carbonic anhydrase. Among them, 50 new identified isotopic clusters, which were missed previously by other methods, have been discovered in the high peak density regions or as weak clusters by this algorithm. As a result, 18 additional new bond cleavages have been identified from the 50 new clusters of carbonic anhydrase.

Algorithms↗

Structural unit analysis identifies lead series and facilitates scaffold hopping in combinatorial chemistry.

Combinatorial chemistry and high-throughput screening technologies produce huge amounts of data on a regular basis. Sieving through these libraries of compounds and their associated assay data to identify appropriate series for follow-up is a daunting task, which has created a need for computational techniques that can find coherent islands of structure-activity relationships in this sea. Structural unit analysis (SUA) examines an entire data set so as to identify the molecular substructures or fragments that distinguish compounds with high activity from those with average activity. The algorithm is iterative and follows set heuristics in order to generate the structural units. It produces graphs that represent a set of units, which become SUA rules. Finding all of the input structures that match these graphs generates clusters. The Apriori algorithm for association rule mining is adapted to explore all of the combinations of structural units that define useful series. User-defined constraints are applied toward series selection and the refinement of rules. The significance of a series is determined by applying statistical methods appropriate to each data set. Application to the NCI-H23 (DTP Human Tumor Cell Line Screen) database serves to illustrate the process by which structural series are identified. An application of the method to scaffold hopping is then discussed in connection with proprietary screening data from a lead optimization project directed toward the treatment of respiratory tract infections at Bayer Healthcare. SUA was able to successfully identify promising alternative core structures in addition to identifying compounds with above-average activity and selectivity.

Cell Line, Tumor↗

Gene selection and clustering for time-course and dose-response microarray experiments using order-restricted inference.

We propose an algorithm for selecting and clustering genes according to their time-course or dose-response profiles using gene expression data. The proposed algorithm is based on the order-restricted inference methodology developed in statistics. We describe the methodology for time-course experiments although it is applicable to any ordered set of treatments. Candidate temporal profiles are defined in terms of inequalities among mean expression levels at the time points. The proposed algorithm selects genes when they meet a bootstrap-based criterion for statistical significance and assigns each selected gene to the best fitting candidate profile. We illustrate the methodology using data from a cDNA microarray experiment in which a breast cancer cell line was stimulated with estrogen for different time intervals. In this example, our method was able to identify several biologically interesting genes that previous analyses failed to reveal.

Algorithms↗

Information-based clustering.

In an age of increasingly large data sets, investigators in many different disciplines have turned to clustering as a tool for data analysis and exploration. Existing clustering methods, however, typically depend on several nontrivial assumptions about the structure of data. Here, we reformulate the clustering problem from an information theoretic perspective that avoids many of these assumptions. In particular, our formulation obviates the need for defining a cluster "prototype," does not require an a priori similarity metric, is invariant to changes in the representation of the data, and naturally captures nonlinear relations. We apply this approach to different domains and find that it consistently produces clusters that are more coherent than those extracted by existing algorithms. Finally, our approach provides a way of clustering based on collective notions of similarity rather than the traditional pairwise measures.

Algorithms↗

Support vector machine implementations for classification & clustering.

BACKGROUND: We describe Support Vector Machine (SVM) applications to classification and clustering of channel current data. SVMs are variational-calculus based methods that are constrained to have structural risk minimization (SRM), i.e., they provide noise tolerant solutions for pattern recognition. The SVM approach encapsulates a significant amount of model-fitting information in the choice of its kernel. In work thus far, novel, information-theoretic, kernels have been successfully employed for notably better performance over standard kernels. Currently there are two approaches for implementing multiclass SVMs. One is called external multi-class that arranges several binary classifiers as a decision tree such that they perform a single-class decision making function, with each leaf corresponding to a unique class. The second approach, namely internal-multiclass, involves solving a single optimization problem corresponding to the entire data set (with multiple hyperplanes). RESULTS: Each SVM approach encapsulates a significant amount of model-fitting information in its choice of kernel. In work thus far, novel, information-theoretic, kernels were successfully employed for notably better performance over standard kernels. Two SVM approaches to multiclass discrimination are described: (1) internal multiclass (with a single optimization), and (2) external multiclass (using an optimized decision tree). We describe benefits of the internal-SVM approach, along with further refinements to the internal-multiclass SVM algorithms that offer significant improvement in training time without sacrificing accuracy. In situations where the data isn't clearly separable, making for poor discrimination, signal clustering is used to provide robust and useful information--to this end, novel, SVM-based clustering methods are also described. As with the classification, there are Internal and External SVM Clustering algorithms, both of which are briefly described.

Algorithms↗

Cluster analysis for automatic image segmentation in dynamic scintigraphies.

An original and entirely automatic algorithm is proposed to select regions of interest (ROIs) on dynamic scintigrams. This algorithm is based on factor analysis and on cluster analysis. It consists of first extracting the orthogonal factor images of the series using factor analysis of correspondence. These factor images are then automatically segmented in ROIs using a hierarchical ascendant classification procedure. The distance used for the classification is the 'minimum added intra-class variance' distance. This algorithm has been implemented on a fast computer dedicated to nuclear medicine (Nodecrest Micas V system). The time of calculation on 1000 pixels from 40 images is less than 5 min when three factor images are used. This algorithm is validated using a numerical phantom and is illustrated using renal (99Tcm DTPA) and cardiac (equilibrium gated angiography) dynamic scintigraphies. The results show that the algorithm is able to recognize the bladder, the renal cavities and the renal parenchyma on the renal series, and the ventricules and the atria on the cardiac series.

Algorithms↗

Identification and handling of artifactual gene expression profiles emerging in microarray hybridization experiments.

Mathematical methods of analysis of microarray hybridizations deal with gene expression profiles as elementary units. However, some of these profiles do not reflect a biologically relevant transcriptional response, but rather stem from technical artifacts. Here, we describe two technically independent but rationally interconnected methods for identification of such artifactual profiles. Our diagnostics are based on detection of deviations from uniformity, which is assumed as the main underlying principle of microarray design. Method 1 is based on detection of non-uniformity of microarray distribution of printed genes that are clustered based on the similarity of their expression profiles. Method 2 is based on evaluation of the presence of gene-specific microarray spots within the slides' areas characterized by an abnormal concentration of low/high differential expression values, which we define as 'patterns of differentials'. Applying two novel algorithms, for nested clustering (method 1) and for pattern detection (method 2), we can make a dual estimation of the profile's quality for almost every printed gene. Genes with artifactual profiles detected by method 1 may then be removed from further analysis. Suspicious differential expression values detected by method 2 may be either removed or weighted according to the probabilities of patterns that cover them, thus diminishing their input in any further data analysis.

Algorithms↗

Fast algorithm and implementation of dissimilarity self-organizing maps.

In many real-world applications, data cannot be accurately represented by vectors. In those situations, one possible solution is to rely on dissimilarity measures that enable a sensible comparison between observations. Kohonen's self-organizing map (SOM) has been adapted to data described only through their dissimilarity matrix. This algorithm provides both nonlinear projection and clustering of nonvector data. Unfortunately, the algorithm suffers from a high cost that makes it quite difficult to use with voluminous data sets. In this paper, we propose a new algorithm that provides an important reduction in the theoretical cost of the dissimilarity SOM without changing its outcome (the results are exactly the same as those obtained with the original algorithm). Moreover, we introduce implementation methods that result in very short running times. Improvements deduced from the theoretical cost model are validated on simulated and real-world data (a word list clustering problem). We also demonstrate that the proposed implementation methods reduce the running time of the fast algorithm by a factor up to three over a standard implementation.

Algorithms↗

Fast optimal leaf ordering for hierarchical clustering.

We present the first practical algorithm for the optimal linear leaf ordering of trees that are generated by hierarchical clustering. Hierarchical clustering has been extensively used to analyze gene expression data, and we show how optimal leaf ordering can reveal biological structure that is not observed with an existing heuristic ordering method. For a tree with n leaves, there are 2(n-1) linear orderings consistent with the structure of the tree. Our optimal leaf ordering algorithm runs in time O(n(4)), and we present further improvements that make the running time of our algorithm practical.

Algorithms↗

Multimodal function optimization using minimal representation size clustering and its application to planning multipaths.

A novel genetic algorithm (GA) using minimal representation size cluster (MRSC) analysis is designed and implemented for solving multimodal function optimization problems. The problem of multimodal function optimization is framed within a hypothesize-and-test paradigm using minimal representation size (minimal complexity) for species formation and a GA. A multiple-population GA is developed to identify different species. The number of populations, thus the number of different species, is determined by the minimal representation size criterion. Therefore, the proposed algorithm reveals the unknown structure of the multimodal function when a priori knowledge about the function is unknown. The effectiveness of the algorithm is demonstrated on a number of multimodal test functions. The proposed scheme results in a highly parallel algorithm for finding multiple local minima. In this paper, a path-planning algorithm is also developed based on the MRSC_GA algorithm. The algorithm utilizes MRSC_GA for planning paths for mobile robots, piano-mover problems, and N-link manipulators. The MRSC_GA is used for generating multipaths to provide alternative solutions to the path-planning problem. The generation of alternative solutions is especially important for planning paths in dynamic environments. A novel iterative multiresolution path representation is used as a basis for the GA coding. The effectiveness of the algorithm is demonstrated on a number of two-dimensional path-planning problems.

Algorithms↗

Simultaneous gene clustering and subset selection for sample classification via MDL.

MOTIVATION: The microarray technology allows for the simultaneous monitoring of thousands of genes for each sample. The high-dimensional gene expression data can be used to study similarities of gene expression profiles across different samples to form a gene clustering. The clusters may be indicative of genetic pathways. Parallel to gene clustering is the important application of sample classification based on all or selected gene expressions. The gene clustering and sample classification are often undertaken separately, or in a directional manner (one as an aid for the other). However, such separation of these two tasks may occlude informative structure in the data. Here we present an algorithm for the simultaneous clustering of genes and subset selection of gene clusters for sample classification. We develop a new model selection criterion based on Rissanen's MDL (minimum description length) principle. For the first time, an MDL code length is given for both explanatory variables (genes) and response variables (sample class labels). The final output of the proposed algorithm is a sparse and interpretable classification rule based on cluster centroids or the closest genes to the centroids. RESULTS: Our algorithm for simultaneous gene clustering and subset selection for classification is applied to three publicly available data sets. For all three data sets, we obtain sparse and interpretable classification models based on centroids of clusters. At the same time, these models give competitive test error rates as the best reported methods. Compared with classification models based on single gene selections, our rules are stable in the sense that the number of clusters has a small variability and the centroids of the clusters are well correlated (or consistent) across different cross validation samples. We also discuss models where the centroids of clusters are replaced with the genes closest to the centroids. These models show comparable test error rates to models based on single gene selection, but are more sparse as well as more stable. Moreover, we comment on how the inclusion of a classification criterion affects the gene clustering, bringing out class informative structure in the data. AVAILABILITY: The methods presented in this paper have been implemented in the R language. The source code is available from the first author.

Algorithms↗

The URMS-RMS hybrid algorithm for fast and sensitive local protein structure alignment.

We present an efficient and sensitive hybrid algorithm for local structure alignment of a pair of 3D protein structures. The hybrid algorithm employs both the URMS (unit-vector root mean squared) metric and the RMS metric. Our algorithm searches efficiently the transformation space using a fast screening protocol; initial transformations (rotations) are identified using the URMS algorithm. These rotations are then clustered and an RMS-based dynamic programming algorithm is invoked to find the maximal local similarities for representative rotations of the clusters. Statistical significance of the alignments is estimated using a model that accounts for both the score of the match and the RMS. We tested our algorithm over the SCOP classification of protein domains. Our algorithm performs very well; its main advantages are that (1) it combines the advantages of the RMS and the URMS metrics, (2) it searches extensively the transformation space, (3) it detects complex similarities and structural repeats, and (4) its results are symmetric. The software is available for download at biozon.org/ftp/software/urms/.

Algorithms↗

Dilute Potts model in two dimensions.

We study the two-dimensional dilute q-state Potts model by means of transfer-matrix and Monte Carlo methods. Using the random-cluster representation, we include noninteger values of q. We locate phase transitions in the three-dimensional parameter space of q, the Potts coupling K>>0, and the chemical potential of the vacancies. The critical plane is found to contain a line of fixed points that divides into a critical branch and a tricritical one, just as predicted by the renormalization scenario formulated by Nienhuis et al for the dilute Potts model. The universal properties along the line of fixed points agree with the theoretical predictions. We also determine the density of the vacancies along these branches. For q=2-squareroot of 2 we obtain the phase diagram in a three-dimensional parameter space that also includes a coupling V> or = 0 between the vacancies. For q=2, the latter space contains the Blume-Capel model as a special case. We include a determination of the tricritical point of this model, as well as an analysis of percolation clusters constructed on tricritical Potts configurations for noninteger q. This percolation study is based on Monte Carlo algorithms that include local updates flipping between Potts sites and vacancies. The bond updates are performed locally for and by means of a cluster algorithm for q>1. The updates for q>1 use a number of operations per site independent of the system size.

Journal Article↗

The structure of 4-methylphenol and its water cluster revealed by rotationally resolved UV spectroscopy using a genetic algorithm approach.

The structure of 4-methylphenol (p-cresol) and its binary water cluster have been elucidated by rotationally resolved laser-induced fluorescence spectroscopy. The electronic origins of the monomer and the cluster are split into four sub-bands by the internal rotation of the methyl group and of the hydroxy group in case of the monomer, and the water moiety in case of the cluster. From the rotational constants of the monomer the structure in the S1 state could be determined to be distorted quinoidally. The structure of the p-cresol-water cluster is determined to be trans linear, with a O-O hydrogen bond length of 290 pm in the electronic ground state and of 285 pm in the electronically excited state. The S1-state lifetime of p-cresol, p-cresol-d1, and the binary water cluster have been determined to be 1.6, 9.7, and 3.8 ns, respectively.

Journal Article↗

Operation and performance of an automatic metaphase finder based on the MRC fast interval processor.

The Medical Research Council's fast interval processor (FIP) has been adapted for metaphase finding and selection. This article summarizes recent improvements to the hardware, and describes the selection of image features. The system uses a highly simplified but effective clustering procedure to reduce computation time, and incorporates a ranking algorithm based on computed cluster features so that high-quality metaphases can be preferentially selected. Experimental results indicate that the system can detect high-quality metaphases rapidly in "rich" material and a high proportion of the available metaphases in "sparse" material. It can handle a wide range of material with good repeatability of performance.

Automation↗

Shape and dynamics of thermoregulating honey bee clusters.

A model of simple algorithmic "agents" acting in a discrete temperature field is used to investigate the movement of individuals in thermoregulating honey bee (Apis mellifera) clusters. Thermoregulation in over-wintering clusters is thought to be the result of individual bees attempting to regulate their own body temperatures. At ambient temperatures above 0( degrees )C, a clustering bee will move relative to its neighbours so as to put its local temperature within some ideal range. The proposed model incorporates this behaviour into an algorithm for bee agents moving on a two-dimensional lattice. Heat transport on the lattice is modelled by a discrete diffusion process. Computer simulation of this model demonstrates qualitative behaviour which agrees with that of real honey bee clusters. In particular, we observe the formation of both disc- and ring-like cluster shapes. The simulation also suggests that at lower ambient temperatures, clusters do not always have a stable shape but can oscillate between insulating rings of different sizes and densities.

Algorithms↗

Distinct methylation patterns of benign and malignant liver tumors revealed by quantitative methylation profiling.

PURPOSE: A comparative quantitative methylation profiling of hepatocellular carcinoma and the most frequent benign liver tumor, hepatocellular adenoma, was set up for the identification of tumor-specific methylation patterns. EXPERIMENTAL DESIGN: The quantitative methylation levels of nine genes (RASSF1A, cyclinD2, p16INK4a, DAP-K, APC, RIZ-1, HIN-1, GSTpi1, SOCS-1) were analyzed in hepatocellular carcinoma and adjacent normal tissue (n = 41), hepatocellular adenoma and adjacent normal tissue (n = 26), focal nodular hyperplasia (n = 10), and unrelated normal liver tissue (n = 28). Accumulated methylation data were analyzed using various statistical algorithms, including hierarchical clustering, to detect tumor-specific methylation patterns. RESULTS: Cluster analysis revealed that hepatocellular adenoma displays a methylation profile much more similar to that found in normal liver tissue and focal nodular hyperplasia than to that found in hepatocellular carcinoma. Many characteristic differences were not detected when using mere qualitative methylation assays. The cyclinD2 gene was identified as a new and frequent target for aberrant hypermethylation in hepatocellular carcinoma (68%). In the control group of 28 liver specimens from healthy donors, a clear correlation between age of patient and frequency and level of aberrant methylation was seen, which could not be detected in the group of hepatocellular carcinoma specimens. CONCLUSIONS: Methylation profiling can clearly contribute to the unequivocal classification of suspicious lesions, but only if done in a quantitative manner applying cell type and gene-specific thresholds. In hepatocellular carcinoma, the altered methylation patterns accompanying malignant transformation override the age-dependent increase in gene methylation.

Adenoma, Liver Cell↗