Search PubMed⌕ Search

SEARCH · Search PubMed

Results for “Clustering Algorithms”

Search indexed PubMed citations on genomics, clinical trials, systematic reviews and public health. Explore titles, authors and supplied subject terms, then open the PubMed record.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 55 records · Page 3Linked to original sources
PubMed2001

Cluster algorithms for general-S quantum spin systems.

We present a general strategy to extend quantum cluster algorithms for S = 1 / 2 spin systems, such as the loop algorithm, to those with an arbitrary size of spins. The partition function of a high- S spin system is generally represented by the path integral of a S = 1 / 2 model with special boundary conditions in the imaginary-time direction. We introduce additional graphs for the boundary part and give the labeling probability explicitly, which completes the algorithm together with an existing S = 1 / 2 algorithm. As a demonstration, we simulate the integer-spin antiferromagnetic Heisenberg chains. The magnitude of the first excitation gap is estimated to be 0.41048(6), 0.08917(4), and 0.01002(3) for S = 1, 2, and 3, respectively.

Journal Article↗
PubMed2005

Spectral clustering algorithms for ultrasound image segmentation.

Image segmentation algorithms derived from spectral clustering analysis rely on the eigenvectors of the Laplacian of a weighted graph obtained from the image. The NCut criterion was previously used for image segmentation in supervised manner. We derive a new strategy for unsupervised image segmentation. This article describes an initial investigation to determine the suitability of such segmentation techniques for ultrasound images. The extension of the NCut technique to the unsupervised clustering is first described. The novel segmentation algorithm is then performed on simulated ultrasound images. Tests are also performed on abdominal and fetal images with the segmentation results compared to manual segmentation. Comparisons with the classical NCut algorithm are also presented. Finally, segmentation results on other types of medical images are shown.

Algorithms↗
PubMed2003

A clustering algorithm using DNA marker information for sub-pedigree reconstruction.

In a mass disaster scenario in which many people are dead, it may be that small family groups are among the dead, and investigators may need to identify such groups, e.g., to return bodies to living relatives for burial. We consider the problem of identifying small groups of closely related people within a large group of people through the use of DNA marker information. We propose a likelihood-ratio-based distance measure of the relatedness between pairs of individuals and use an estimate of this measure as a means of clustering related people into groups. We show the effectiveness of our approach on real examples and through simulations, which suggest that the method is quite reliable for identifying very close relationships. We discuss the use of our clustering algorithm in a two-stage pedigree reconstruction procedure and suggest directions in which the analysis could be extended. Applications include the identification of family groups among bodies found in mass graves and identification of family groups in animal populations.

Algorithms↗
PubMed1998

Enhancing the detection of seizures with a clustering algorithm.

Automated detection algorithms of EEG seizures or similar clinical events typically analyze a finite epoch a given channel at a time, producing a probability or a weight estimating how likely it is for the event to resemble a clinical pattern. Epochs are normally shorter than the duration of a seizure, which may spread to more than one electrode. This may result in a weak correspondence between the seizure pattern in the record and its calculated detector event counterpart. As a result, such algorithms suffer from a high rate of false detections. We show that the weights/probabilities of a generic detector can be described as a weight function embedded in a directed graph (digraph). Extended objects such as seizures therefore correspond to the connected components of the digraph. We introduce a clustering algorithm that accounts for the shortcomings of a generic detector of the type described above. By correlating detector results with respect to both time and channel, we effectively extend the detection to an unlimited number of electrodes over an indefinite time. The algorithm is fast (linear - O(m)) and may be implemented in real time. We argue that the algorithm enhances the detection of seizure onset and lowers the rate of false detections. Preliminary results demonstrate a strong correlation between the seizure and the cluster's boundaries and over 50% reduction of false detection rate.

Algorithms↗
PubMed2006

Evaluation of clustering algorithms for protein-protein interaction networks.

BACKGROUND: Protein interactions are crucial components of all cellular processes. Recently, high-throughput methods have been developed to obtain a global description of the interactome (the whole network of protein interactions for a given organism). In 2002, the yeast interactome was estimated to contain up to 80,000 potential interactions. This estimate is based on the integration of data sets obtained by various methods (mass spectrometry, two-hybrid methods, genetic studies). High-throughput methods are known, however, to yield a non-negligible rate of false positives, and to miss a fraction of existing interactions. The interactome can be represented as a graph where nodes correspond with proteins and edges with pairwise interactions. In recent years clustering methods have been developed and applied in order to extract relevant modules from such graphs. These algorithms require the specification of parameters that may drastically affect the results. In this paper we present a comparative assessment of four algorithms: Markov Clustering (MCL), Restricted Neighborhood Search Clustering (RNSC), Super Paramagnetic Clustering (SPC), and Molecular Complex Detection (MCODE). RESULTS: A test graph was built on the basis of 220 complexes annotated in the MIPS database. To evaluate the robustness to false positives and false negatives, we derived 41 altered graphs by randomly removing edges from or adding edges to the test graph in various proportions. Each clustering algorithm was applied to these graphs with various parameter settings, and the clusters were compared with the annotated complexes. We analyzed the sensitivity of the algorithms to the parameters and determined their optimal parameter values. We also evaluated their robustness to alterations of the test graph. We then applied the four algorithms to six graphs obtained from high-throughput experiments and compared the resulting clusters with the annotated complexes. CONCLUSION: This analysis shows that MCL is remarkably robust to graph alterations. In the tests of robustness, RNSC is more sensitive to edge deletion but less sensitive to the use of suboptimal parameter values. The other two algorithms are clearly weaker under most conditions. The analysis of high-throughput data supports the superiority of MCL for the extraction of complexes from interaction networks.

Algorithms↗
PubMed2003

Expression profiling of 68 glycosyltransferase genes in 27 different human tissues by the systematic multiplex reverse transcription-polymerase chain reaction method revealed clustering of sexually related tissues in hierarchical clustering algorithm analysis.

We have developed an experimental system to study the expression of 68 human glycosyltransferase genes. Using this system, we examined the expression of those genes in 27 different tissues by the technique which we named systematic multiplex reverse transcription-polymerase chain reaction (SM RT-PCR). The panoramic view of a total of 1836 (68 x 27) expression data demonstrates that some glycosyltransferase genes are differentially expressed whereas some others are ubiquitously expressed. The data gathered provide more information on glycosyltransferase gene expression in tissues than any other paper published, and surpass in quantity all the information combined from previous publications. Although the expression profiling of glycosyltransferase genes alone may not directly explain the repertoires of oligosaccharides synthesized, it is an important step toward a better understanding of the gene expression network involved in oligosaccharide synthesis/degradation. Our modestly high-throughput gene expression study and the data analysis using a hierarchical clustering algorithm have allowed us to investigate the correlation between tissues and glycosyltransferase gene expression. Similar patterns of glycosyltransferase gene expression were observed in functionally and anatomically related tissues. All, but one, sexually related tissues formed a cluster in a tissue dendrogram, suggesting the involvement of sex hormones in the transcriptional control of many glycosyltransferase genes. Once established, the SM RT-PCR is cost- and time-efficient and requires small amounts of RNA as template. It is especially useful for the simultaneous analyses of multiple samples. Because of its simple design, the SM RT-PCR may offer an easy alternative in studying the expression of many other families of genes, as well as groups of related/unrelated genes, in various biological phenomena.

Algorithms↗
PubMed2000

On the convergence of a clustering algorithm for protein-coding regions in microbial genomes.

MOTIVATION: As the number of fully sequenced prokaryotic genomes continues to grow rapidly, computational methods for reliably detecting protein-coding regions become even more important. Audic and Claverie (1998) Proc. Natl Acad. Sci. USA, 95, 10026-10031, have proposed a clustering algorithm for protein-coding regions in microbial genomes. The algorithm is based on three Markov models of order k associated with subsequences extracted from a given genome. The parameters of the three Markov models are recursively updated by the algorithm which, in simulations, always appear to converge to a unique stable partition of the genome. The partition corresponds to three kinds of regions: (1) coding on the direct strand, (2) coding on the complementary strand, (3) non-coding. RESULTS: Here we provide an explanation for the convergence of the algorithm by observing that it is essentially a form of the expectation maximization (EM) algorithm applied to the corresponding mixture model. We also provide a partial justification for the uniqueness of the partition based on identifiability. Other possible variations and improvements are briefly discussed.

Algorithms↗
PubMed2002

Segmentation of fat and muscle from MR images of the thigh by a possibilistic clustering algorithm.

Physical training is proved to induce changes in physical capacity and body composition. We propose in this article a fast, unsupervised and fully three-dimensional automatic method to extract muscle and fat volumes from magnetic resonance images of thighs in order to assess these changes. The technique relies on the use of a fuzzy clustering algorithm and post-processings to accurately process the body composition of thighs. Results are compared on 11 healthy voluntary elderly people with those provided on the same data by a validated method already published, and its reliability is assessed on repeated measures on three subjects. The two methods statistically agree when computing muscle and fat volumes, and clinical implications of this fully automatic method are important for medicine, physical conditioning, weight-loss programs and predictions of optimal body weight.

Algorithms↗
PubMed2006

Clustering algorithm for determining community structure in large networks.

We propose an algorithm to find the community structure in complex networks based on the combination of spectral analysis and modularity optimization. The clustering produced by our algorithm is as accurate as the best algorithms on the literature of modularity optimization; however, the main asset of the algorithm is its efficiency. The best match for our algorithm is Newman's fast algorithm, which is the reference algorithm for clustering in large networks due to its efficiency. When both algorithms are compared, our algorithm outperforms the fast algorithm both in efficiency and accuracy of the clustering, in terms of modularity. Thus, the results suggest that the proposed algorithm is a good choice to analyze the community structure of medium and large networks in the range of tens and hundreds of thousand vertices.

Journal Article↗
PubMed2001

Crossover and self-averaging in the two-dimensional site-diluted Ising model: application of probability-changing cluster algorithm.

Using the newly proposed probability-changing cluster (PCC) Monte Carlo algorithm, we simulate the two-dimensional (2D) site-diluted Ising model. Since we can tune the critical point of each random sample automatically with the PCC algorithm, we succeed in studying the sample-dependent T(c)(L) and the sample average of physical quantities at each T(c)(L) systematically. Using the finite-size scaling (FSS) analysis for T(c)(L), we discuss the importance of corrections to FSS both in the strong-dilution and weak-dilution regions. The critical phenomena of the 2D site-diluted Ising model are shown to be controlled by the pure fixed point. The crossover from the percolation fixed point to the pure Ising fixed point with the system size is explicitly demonstrated by the study of the Binder parameter. We also study the distribution of critical temperature T(c)(L). Its variance shows the power-law L dependence, L(-n), and the estimate of the exponent n is consistent with the prediction of Aharony and Harris [Phys. Rev. Lett. 77, 3700 (1996)]. Calculating the relative variance of critical magnetization at the sample-dependent T(c)(L), we show that the 2D site-diluted Ising model exhibits weak self-averaging.

Journal Article↗
PubMed2025

Tumor-immune partitioning and clustering algorithm for identifying tumor-immune cell spatial interaction signatures within the tumor microenvironment.

BACKGROUND: Growing evidence supports the importance of characterizing the organizational patterns of various cellular constituents in the tumor microenvironment in precision oncology. Most existing data on immune cell infiltrates in tumors, which are based on immune cell counts or nearest neighbor-type analyses, have failed to fully capture the cellular organization and heterogeneity. METHODS: We introduce a computational algorithm, termed Tumor-Immune Partitioning and Clustering (TIPC), that jointly measures immune cell partitioning between tumor epithelial and stromal areas and immune cell clustering versus dispersion. As proof-of-principle, we applied TIPC to a prospective cohort incident tumor biobank containing 931 colorectal carcinoma cases. TIPC identified tumor subtypes with unique spatial patterns between tumor cells and T lymphocytes linked to certain molecular pathologic and prognostic features. T lymphocyte identification and phenotyping were achieved using multiplexed (multispectral) immunofluorescence. In a separate hepatocellular carcinoma cohort, we replaced the stromal component with specific immune cell types-CXCR3+CD68+ or CD8+-to profile their spatial relationships with CXCL9+CD68+ cells. RESULTS: Six unsupervised TIPC subtypes based on T lymphocyte distribution patterns were identified, comprising two cold and four hot subtypes. Three of the four hot subtypes were associated with significantly longer colorectal cancer (CRC)-specific survival compared to a reference cold subtype. Our analysis showed that variations in T-cell densities among the TIPC subtypes did not strictly correlate with prognostic benefits, underscoring the prognostic significance of immune cell spatial patterns. Additionally, TIPC revealed two spatially distinct and cell density-specific subtypes among microsatellite instability-high colorectal cancers, indicating its potential to upgrade tumor subtyping. TIPC was also applied to additional immune cell types, eosinophils and neutrophils, identified using morphology and supervised machine learning; here two tumor subtypes with similarly low densities, namely 'cold, tumor-rich' and 'cold, stroma-rich', exhibited differential prognostic associations. Lastly, we validated our methods and results using The Cancer Genome Atlas colon and rectal adenocarcinoma data (n = 570). Moreover, applying TIPC to hepatocellular carcinoma cases (n = 27) highlighted critical cell interactions like CXCL9-CXCR3 and CXCL9-CD8. CONCLUSIONS: Unsupervised discoveries of microgeometric tissue organizational patterns and novel tumor subtypes using the TIPC algorithm can deepen our understanding of the tumor immune microenvironment and likely inform precision cancer immunotherapy.

Humans↗
PubMed1997

A Comparative Study of Self-organizing Clustering Algorithms Dignet and ART2.

A comparative study of two self-organizing clustering neural network algorithms, Dignet and ART2, has been conducted. The differences in architecture and learning procedures between the two models are compared. Comparative computer simulations on data clustering and signal detection problems with Gaussian noise were used for investigating the performance of Dignet and "fast learning" ART2. The study shows that Dignet, with a simple architecture and straightforward dynamics, is more flexible with the choice of different metrics for the measure of similarity. The system parameters in Dignet can be analytically determined from a self-adjusting process; moreover, the initial threshold value used in Dignet is directly determined from a lower-bound of the desirable operational signal-to-noise ratio. Simulations show that Dignet generally exhibits faster learning and better clustering performance on statistical pattern recognition problems. A simplified ART2 model (SART2) is derived by adopting the structural concepts from Dignet. SART2 exhibits faster learning and eliminates a "false conviction" problem that exists in the "fast learning" ART2. The comparative study is benchmarked against statistical data clustering and signal detection problems. Copyright 1997 Elsevier Science Ltd.

Journal Article↗
PubMed2001

The enhanced LBG algorithm.

Clustering applications cover several fields such as audio and video data compression, pattern recognition, computer vision, medical image recognition, etc. In this paper, we present a new clustering algorithm called Enhanced LBG (ELBG). It belongs to the hard and K-means vector quantization groups and derives directly from the simpler LBG. The basic idea we have developed is the concept of utility of a codeword, a powerful instrument to overcome one of the main drawbacks of clustering algorithms: generally, the results achieved are not good in the case of a bad choice of the initial codebook. We will present our experimental results showing the ELBG is able to find better codebooks than previous clustering techniques and the computational complexity is virtually the same as the simpler LBG.

Algorithms↗
PubMed2004

Automated morphometric analysis of the cat retinal alpha/Y, beta/X and delta ganglion cells using wavelet statistical moment and clustering algorithms.

Computational morphological analysis comprises the development of measures (indicators) that describe different form attributes of a neuron and provides additional parameters for classification algorithms. Our work addressed the problem of small group sizes often encountered in neuromorphological and neurophysiological research, automated classification tasks (unsupervised learning) and introduced a new morphological measure: the wavelet statistical moment. We analysed cat alpha/Y, beta/X and delta Golgi-stained retinal ganglion cells using six different shape features (circularity, 2(nd) statistical moment and entropy of Gaussian blurred images, wavelet statistical moment, number of terminations and the fractal dimension). This allowed us to compare the sensitivity of the methods in uniquely describing morphological attributes of these cells.

Algorithms↗
PubMed2006

Haplotype-based quantitative trait mapping using a clustering algorithm.

BACKGROUND: With the availability of large-scale, high-density single-nucleotide polymorphism (SNP) markers, substantial effort has been made in identifying disease-causing genes using linkage disequilibrium (LD) mapping by haplotype analysis of unrelated individuals. In addition to complex diseases, many continuously distributed quantitative traits are of primary clinical and health significance. However the development of association mapping methods using unrelated individuals for quantitative traits has received relatively less attention. RESULTS: We recently developed an association mapping method for complex diseases by mining the sharing of haplotype segments (i.e., phased genotype pairs) in affected individuals that are rarely present in normal individuals. In this paper, we extend our previous work to address the problem of quantitative trait mapping from unrelated individuals. The method is non-parametric in nature, and statistical significance can be obtained by a permutation test. It can also be incorporated into the one-way ANCOVA (analysis of covariance) framework so that other factors and covariates can be easily incorporated. The effectiveness of the approach is demonstrated by extensive experimental studies using both simulated and real data sets. The results show that our haplotype-based approach is more robust than two statistical methods based on single markers: a single SNP association test (SSA) and the Mann-Whitney U-test (MWU). The algorithm has been incorporated into our existing software package called HapMiner, which is available from our website at http://www.eecs.case.edu/~jxl175/HapMiner.html. CONCLUSION: For QTL (quantitative trait loci) fine mapping, to identify QTNs (quantitative trait nucleotides) with realistic effects (the contribution of each QTN less than 10% of total variance of the trait), large samples sizes (>or= 500) are needed for all the methods. The overall performance of HapMiner is better than that of the other two methods. Its effectiveness further depends on other factors such as recombination rates and the density of typed SNPs. Haplotype-based methods might provide higher power than methods based on a single SNP when using tag SNPs selected from a small number of samples or some other sources (such as HapMap data). Rank-based statistics usually have much lower power, as shown in our study.

Algorithms↗
PubMed1998

Multiresolution texture based adaptive clustering algorithm for breast lesion segmentation.

OBJECTIVE: A specific algorithm is presented for the automatic extraction of breast tumors in ultrasonic imaging. METHOD: The algorithm involves two-dimensional adaptive K-means clustering of the gray scale and textural feature images. The segmentation problem is formulated as a maximum a posteriori (MAP) estimation problem. The MAP estimation is achieved using Besag's iterated conditional modes algorithm for the minimization of an energy function. This function has three components: the first constrains the region to be close to the data; the second imposes spatial continuity; and the third takes into consideration the texture of the various regions. A multiresolution implementation of the algorithm is performed using a waveless basis. RESULTS: Experiments were carried out on synthetic images and on in vivo breast ultrasound images. Various parameters involved in the algorithm are discussed to evaluate the robustness and accuracy of the segmentation method. CONCLUSION: Including textural features in the segmentation of ultrasonic data improves the robustness of the algorithm and makes the segmentation result less parameter dependent.

Adenocarcinoma↗
PubMed2006

A near linear-scaling smooth local coupled cluster algorithm for electronic structure.

We demonstrate near linear scaling of a new algorithm for computing smooth local coupled-cluster singles-doubles (LCCSD) correlation energies of quantum mechanical systems. The theory behind our approach has been described previously, [J. Subotnik and M. Head-Gordon, J. Chem. Phys. 123, 064108 (2005)], and requires appropriately multiplying standard iterative amplitude equations by a bump function, creating local amplitude equations (which are smooth according to the implicit function theorem). Here, we provide an example that this theory works in practice: we show that our algorithm leads to smooth potential energy surfaces and yields large computational savings. As an example, we apply our LCCSD approach to measure the post-MP2 correction to the energetic gap between two different alanine tetrapeptide conformations.

Algorithms↗
PubMed2006

A simple clustering algorithm can be accurate enough for use in calculations of pKs in macromolecules.

Structure and function of macromolecules depend critically on the ionization states of their acidic and basic groups. Most current structure-based theoretical methods that predict pK of ionizable groups in macromolecules include, as one of the key steps, a computation of the partition sum (Boltzmann average) over all possible protonation microstates. As the number of these microstates depends exponentially on the number of ionizable groups present in the molecule, direct computation of the sum is not realistically feasible for many typical proteins that may have tens or even hundreds of ionizable groups. We have tested a simple and robust approximate algorithm for computing these partition sums for macromolecules. The method subdivides the interacting sites into independent clusters, based upon the strength of site-site electrostatic interaction. The resulting partition function is factorizable into computationally manageable components. Two variants of the approach are presented and validated on a representative test set of 602 proteins, by comparing the pK(1/2) values computed by the proposed method with those obtained by the standard Monte Carlo approach used as a reference. With 95% confidence, the relative error introduced by the more accurate of the two methods is less than 0.25 pK units. The algorithms are one to two orders of magnitude faster than the Monte Carlo method, with the typical settings. A graphical representation is introduced that visualizes the clusters of strong site-site interactions in the context of the three-dimensional (3D) structure of the macromolecule, facilitating identification of functionally important clusters of ionizable groups; the approach is exemplified on two proteins, bacteriorhodopsin and myoglobin.

Algorithms↗