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,279 records · Page 71Linked to original sources
PubMed2004

Prediction of cis-regulatory elements of coregulated genes.

We present a computational pipeline to predict cis-regulatory elements composing results based on different algorithms: Clover, Cluster-Buster, an own implementation of human/rat/mouse sequence identity and our ITB algorithm. The procedure uses information from the human genome sequence, NCBI gene annotations, verified eukaryotic promoters (EPD), experimentally proven binding sites (Transfac) and homologies to mouse and rat (HomGL/HomoloGene). We test the approach on 18 upstream regions of experimentally verified AP-1 target genes. About a half of the known sites belong to high-scoring candidates. Three top-scoring elements are confirmed by Cluster-Buster and high homologies. The same analysis we applied to genes found to be up- or downregulated due to mutated RAS. We performed a detailed literature and computational search for promoter regions. Indications of overrepresented Elk-1 and AP-1 motifs are found via a comparison with shuffled sequences. In some promoters consistent predictions of clustered binding sites were obtained.

Animals↗
PubMed2004

Unsupervised fuzzy clustering using Weighted Incremental Neural Networks.

A new more efficient variant of a recently developed algorithm for unsupervised fuzzy clustering is introduced. A Weighted Incremental Neural Network (WINN) is introduced and used for this purpose. The new approach is called FC-WINN (Fuzzy Clustering using WINN). The WINN algorithm produces a net of nodes connected by edges, which reflects and preserves the topology of the input data set. Additional weights, which are proportional to the local densities in input space, are associated with the resulting nodes and edges to store useful information about the topological relations in the given input data set. A fuzziness factor, proportional to the connectedness of the net, is introduced in the system. A watershed-like procedure is used to cluster the resulting net. The number of the resulting clusters is determined by this procedure. Only two parameters must be chosen by the user for the FC-WINN algorithm to determine the resolution and the connectedness of the net. Other parameters that must be specified are those which are necessary for the used incremental neural network, which is a modified version of the Growing Neural Gas algorithm (GNG). The FC-WINN algorithm is computationally efficient when compared to other approaches for clustering large high-dimensional data sets.

Algorithms↗
PubMed2026

Episode clustering in phylogenetic networks.

MOTIVATION: The classical duplication episode clustering (EC) model introduced by Guigó et al. in the 1990s provides a foundational approach for inferring genomic duplication events crucial to understanding genome evolution. This model clusters single gene duplications from a collection of gene trees at locations in the species tree to minimize the total number of such locations, called duplication episodes. However, it does not capture reticulate evolutionary histories. RESULTS: Here, we introduce NetEC, a novel extension of this problem to phylogenetic networks. To solve NetEC, we first develop a polynomial-time dynamic programming (DP) algorithm for testing whether a given set of network nodes can serve as episode locations. We then propose a main inference algorithm that utilizes this DP component to optimize the episode count; while the feasibility test runs in polynomial time, the full optimization has exponential worst-case complexity, and an optional heuristic mode is provided for larger instances. We also propose an extended episode analysis procedure that identifies additional genomic duplication candidates below reticulation nodes, complementing the main algorithm by resolving potential upward clustering of duplications induced by reticulation. We evaluate our method on simulated data and on an empirical Pandanales dataset comprising over 29 000 gene trees, demonstrating exact and accurate inference of genomic duplication events even in the presence of multiple reticulations. AVAILABILITY AND IMPLEMENTATION: All experiments were conducted using the NetEC tool (https://github.com/ppgorecki/netec), with all input data, scripts, and parameter settings for reproduction available in the same repository.

Phylogeny↗
PubMed2001

Cell image segmentation with kernel-based dynamic clustering and an ellipsoidal cell shape model.

In this paper, we propose a novel approach to cell image segmentation under severe noise conditions by combining kernel-based dynamic clustering and a genetic algorithm. Our method incorporates a priori knowledge about cell shape. That is, an elliptical cell contour model is introduced to describe the boundary of the cell. Our method consists of the following components: (1) obtain the gradient image; (2) use the gradient image to obtain points which possibly belong to cell boundaries; (3) adjust the parameters of the elliptical cell boundary model to match the cell contour using a genetic algorithm. The method is tested on images of noisy human thyroid and small intestine cells.

Algorithms↗
PubMed2004

Unsupervised learning of an atlas from unlabeled point-sets.

One of the key challenges in deformable shape modeling is the problem of estimating a meaningful average or mean shape from a set of unlabeled shapes. We present a new joint clustering and matching algorithm that is capable of computing such a mean shape from multiple shape samples which are represented by unlabeled point-sets. An iterative bootstrap process is used wherein multiple shape sample point-sets are nonrigidly deformed to the emerging mean shape, with subsequent estimation of the mean shape based on these nonrigid alignments. The process is entirely symmetric with no bias toward any of the original shape sample point-sets. We believe that this method can be especially useful for creating atlases of various shapes present in medical images. We have applied the method to create mean shapes from nine hand-segmented 2D corpus callosum data sets and 10 hippocampal 3D point-sets.

Algorithms↗
PubMed2024

The prognostic significance of ubiquitination-related genes in multiple myeloma by bioinformatics analysis.

BACKGROUND: Immunoregulatory drugs regulate the ubiquitin-proteasome system, which is the main treatment for multiple myeloma (MM) at present. In this study, bioinformatics analysis was used to construct the risk model and evaluate the prognostic value of ubiquitination-related genes in MM. METHODS AND RESULTS: The data on ubiquitination-related genes and MM samples were downloaded from The Cancer Genome Atlas (TCGA) and Gene Expression Omnibus (GEO) databases. The consistent cluster analysis and ESTIMATE algorithm were used to create distinct clusters. The MM prognostic risk model was constructed through single-factor and multiple-factor analysis. The ROC curve was plotted to compare the survival difference between high- and low-risk groups. The nomogram was used to validate the predictive capability of the risk model. A total of 87 ubiquitination-related genes were obtained, with 47 genes showing high expression in the MM group. According to the consistent cluster analysis, 4 clusters were determined. The immune infiltration, survival, and prognosis differed significantly among the 4 clusters. The tumor purity was higher in clusters 1 and 3 than in clusters 2 and 4, while the immune score and stromal score were lower in clusters 1 and 3. The proportion of B cells memory, plasma cells, and T cells CD4 naïve was the lowest in cluster 4. The model genes KLHL24, HERC6, USP3, TNIP1, and CISH were highly expressed in the high-risk group. AICAr and BMS.754,807 exhibited higher drug sensitivity in the low-risk group, whereas Bleomycin showed higher drug sensitivity in the high-risk group. The nomogram of the risk model demonstrated good efficacy in predicting the survival of MM patients using TCGA and GEO datasets. CONCLUSIONS: The risk model constructed by ubiquitination-related genes can be effectively used to predict the prognosis of MM patients. KLHL24, HERC6, USP3, TNIP1, and CISH genes in MM warrant further investigation as therapeutic targets and to combat drug resistance.

Humans↗
PubMed2003

A memetic-aided approach to hierarchical clustering from distance matrices: application to gene expression clustering and phylogeny.

We propose a heuristic approach to hierarchical clustering from distance matrices based on the use of memetic algorithms (MAs). By using MAs to solve some variants of the Minimum Weight Hamiltonian Path Problem on the input matrix, a sequence of the individual elements to be clustered (referred to as patterns) is first obtained. While this problem is also NP-hard, a probably optimal sequence is easy to find with the current advances for this problem and helps to prune the space of possible solutions and/or to guide the search performed by an actual clustering algorithm. This technique has been successfully applied to both a Branch-and-Bound algorithm, and to evolutionary algorithms and MAs. Experimental results are given in the context of phylogenetic inference and in the hierarchical clustering of gene expression data.

Algorithms↗
PubMed2001

Efficiency of parallel direct optimization.

Tremendous progress has been made at the level of sequential computation in phylogenetics. However, little attention has been paid to parallel computation. Parallel computing is particularly suited to phylogenetics because of the many ways large computational problems can be broken into parts that can be analyzed concurrently. In this paper, we investigate the scaling factors and efficiency of random addition and tree refinement strategies using the direct optimization software, POY, on a small (10 slave processors) and a large (256 slave processors) cluster of networked PCs running LINUX. These algorithms were tested on several data sets composed of DNA and morphology ranging from 40 to 500 taxa. Various algorithms in POY show fundamentally different properties within and between clusters. All algorithms are efficient on the small cluster for the 40-taxon data set. On the large cluster, multibuilding exhibits excellent parallel efficiency, whereas parallel building is inefficient. These results are independent of data set size. Branch swapping in parallel shows excellent speed-up for 16 slave processors on the large cluster. However, there is no appreciable speed-up for branch swapping with the further addition of slave processors (>16). This result is independent of data set size. Ratcheting in parallel is efficient with the addition of up to 32 processors in the large cluster. This result is independent of data set size.

Algorithms↗
PubMed2005

Tight clustering: a resampling-based approach for identifying stable and tight patterns in data.

In this article, we propose a method for clustering that produces tight and stable clusters without forcing all points into clusters. The methodology is general but was initially motivated from cluster analysis of microarray experiments. Most current algorithms aim to assign all genes into clusters. For many biological studies, however, we are mainly interested in identifying the most informative, tight, and stable clusters of sizes, say, 20-60 genes for further investigation. We want to avoid the contamination of tightly regulated expression patterns of biologically relevant genes due to other genes whose expressions are only loosely compatible with these patterns. "Tight clustering" has been developed specifically to address this problem. It applies K-means clustering as an intermediate clustering engine. Early truncation of a hierarchical clustering tree is used to overcome the local minimum problem in K-means clustering. The tightest and most stable clusters are identified in a sequential manner through an analysis of the tendency of genes to be grouped together under repeated resampling. We validated this method in a simulated example and applied it to analyze a set of expression profiles in the study of embryonic stem cells.

Algorithms↗
PubMed2005

Computational cluster validation in post-genomic data analysis.

MOTIVATION: The discovery of novel biological knowledge from the ab initio analysis of post-genomic data relies upon the use of unsupervised processing methods, in particular clustering techniques. Much recent research in bioinformatics has therefore been focused on the transfer of clustering methods introduced in other scientific fields and on the development of novel algorithms specifically designed to tackle the challenges posed by post-genomic data. The partitions returned by a clustering algorithm are commonly validated using visual inspection and concordance with prior biological knowledge--whether the clusters actually correspond to the real structure in the data is somewhat less frequently considered. Suitable computational cluster validation techniques are available in the general data-mining literature, but have been given only a fraction of the same attention in bioinformatics. RESULTS: This review paper aims to familiarize the reader with the battery of techniques available for the validation of clustering results, with a particular focus on their application to post-genomic data analysis. Synthetic and real biological datasets are used to demonstrate the benefits, and also some of the perils, of analytical clustervalidation. AVAILABILITY: The software used in the experiments is available at http://dbkweb.ch.umist.ac.uk/handl/clustervalidation/. SUPPLEMENTARY INFORMATION: Enlarged colour plots are provided in the Supplementary Material, which is available at http://dbkweb.ch.umist.ac.uk/handl/clustervalidation/.

Algorithms↗
PubMed2005

Evaluation of Glycine max mRNA clusters.

BACKGROUND: Clustering the ESTs from a large dataset representing a single species is a convenient starting point for a number of investigations into gene discovery, genome evolution, expression patterns, and alternatively spliced transcripts. Several methods have been developed to accomplish this, the most widely available being UniGene, a public domain collection of gene-oriented clusters for over 45 different species created and maintained by NCBI. The goal is for each cluster to represent a unique gene, but currently it is not known how closely the overall results represent that reality. UniGene's build procedure begins with initial mRNA clusters before joining ESTs. UniGene's results for soybean indicate a significant amount of redundancy among some sequences reported to be unique mRNAs. To establish a valid non-redundant known gene set for Glycine max we applied our algorithm to the clustering of only mRNA sequences. The mRNA dataset was run through the algorithm using two different matching stringencies. The resulting cluster compositions were compared to each other and to UniGene. Clusters exhibiting differences among the three methods were analyzed by 1) nucleotide and amino acid alignment and 2) submitting authors conclusions to determine whether members of a single cluster represented the same gene or not. RESULTS: Of the 12 clusters that were examined closely most contained examples of sequences that did not belong in the same cluster. However, neither the two stringencies of PECT nor UniGene had a significantly greater record of accuracy in placing paralogs into separate clusters. CONCLUSION: Our results reveal that, although each method produces some errors, using multiple stringencies for matching or a sequential hierarchical method of increasing stringencies can provide more reliable results and therefore allow greater confidence in the vast majority of clusters that contain only ESTs and no mRNA sequences.

Cluster Analysis↗
PubMed2006

Clustering microarray data.

Even a simple, small-scale, microarray experiment generates thousands to millions of data points. Clearly, spreadsheets or plotting programs do not suffice for analysis of such large volumes of data, and comprehensive analysis requires systematic methods for selection and organization of data. This chapter focuses on the concepts and algorithms of hierarchical clustering and the most commonly employed methods of partitioning or organizing microarray data, and freely available software that implements these algorithms.

Animals↗
PubMed2005

Ab-initio coupled-cluster study of 16O.

We report converged results for the ground and excited states and matter density of 16O using realistic two-body nucleon-nucleon interactions and coupled-cluster methods and algorithms developed in quantum chemistry. Most of the binding is obtained with the coupled-cluster singles and doubles approach. Additional binding due to three-body clusters (triples) is minimal. The coupled-cluster method with singles and doubles provides a good description of the matter density, charge radius, charge form factor, and excited states of a one-particle, one-hole nature, but it cannot describe the first-excited 0(+) state. Incorporation of triples has no effect on the latter finding.

Journal Article↗
PubMed2004

Towards realistic description of collective motions in the lattice protein folding models.

Collective motions and the formation of clusters of residues play an important role in the folding of real proteins. However, existing Monte Carlo (MC) techniques of the protein folding simulations based on highly popular lattice models provide only a schematic representation of collective motions, which is rather far from physical reality. The Clustering Monte Carlo (CMC) algorithm was developed with particular aim to provide a realistic description of collective motions on the lattice. CMC allows modeling the cluster dynamics and the effects of the solvent viscosity, which is impossible in conventional algorithms. In this study two 2D lattice peptides, with the ground states of hierarchical and non-hierarchical design, were investigated comparatively using three methods: Metropolis MC with the local move set, Metropolis MC with unspecific rigid rotations and the CMC algorithm. We present evidence that the folding pathways and kinetics of hierarchically folding clustered sequence are not adequately described in conventional MC simulations, and the account for cluster dynamics provided by CMC allows to capture essential features of the folding process. Our data suggest that the methods, which enable specific cluster motions, such as CMC, should be used for a more realistic description of protein folding.

Algorithms↗
PubMed1993

Automatic lineage assignment of acute leukemias by flow cytometry.

A method for automatic lineage assignment of acute leukemias was developed. Input are eight list mode data files acquired with a FACScan flow cytometer. For each cell, four parameters are measured: forward light scatter, orthogonal light scatter, fluorescein fluorescence, and phycoerythrin fluorescence. Eight data files are acquired in the following sequence: unstained, isotype controls, CD10/CD19, CD20/CD5, CD3/CD22, CD7/CD33, HLADR/CD13, and CD34/CD38. First, each of the data files 3 to 8 are clustered independently employing an algorithm based on nearest neighbors. Next, the clusters are associated across the data files to form cell populations, using the assumption of light scatter invariance across tubes for each population. The mean positions of each cell population are fed into a decision tree. The decision tree first identifies normal cell populations, i.e., monocytes, neutrophils, eosinophils, basophils, NK cells, T-lymphocytes, and B-lymphocytes. After elimination of the normal cell populations from the data space, the residual cell populations are classified as B-lineage ALL, T-lineage ALL, AML, AUL, B-CLL, or unknown. The effectiveness of this novel approach is shown with case studies of B-lymphoid, T-lymphoid, and Myeloid acute leukemias.

Antigens, CD↗
PubMed1991

Automatic segmentation and classification of ionic-channel signals.

Identification of ionic-channel types and their selectivity depends critically on the open channel current that can be resolved. In this paper, an automatic channel detection algorithm is proposed that is based on sequential minimization of an index which is usually used in cluster analysis. The algorithm consists of two stages, namely segmentation and classification. In the first stage, the signal samples are segmented based on the assumption that the samples in each segment should be sequentially connected. In the second stage, the resultant segments are classified with no regard to their connectivities. Results on synthetic and real channel currents are very encouraging and they suggest that this algorithm will substantially increase the productivity of many laboratories involved in ionic-channel research.

Algorithms↗
PubMed1980

Use of a monthly health review to ascertain illness and injuries.

A Monthly Health Review was developed to monitor symptoms, illnesses and injuries among Air Traffic Controllers. Return rate of the mailed check-list exceeded 90 per cent. Diagnoses were generated from symptom clusters by computer algorithms. Telephone interview by physicians, laboratory analyses for serum pepsinogen I, and analyses of relations between symptom clusters and degree of disability all served to support the validity of the methodology. Such a system can provide inexpensive surveillance of morbidity in suitable populations.

Adult↗