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 775 records · Page 43Linked to original sources

PubMed2004

Graph-based clustering for finding distant relationships in a large set of protein sequences.

MOTIVATION: Clustering of protein sequences is widely used for the functional characterization of proteins. However, it is still not easy to cluster distantly-related proteins, which have only regional similarity among their sequences. It is therefore necessary to develop an algorithm for clustering such distantly-related proteins. RESULTS: We have developed a time and space efficient clustering algorithm. It uses a graph representation where its vertices and edges denote proteins and their sequence similarities above a certain cutoff score, respectively. It repeatedly partitions the graph by removing edges that have small weights, which correspond to low sequence similarities. To find the appropriate partitions, we introduce a score combining the normalized cut and a locally minimal cut capacities. Our method is applied to the entire 40,703 human proteins in SWISS-PROT and TrEMBL. The resulting clusters shows a 76% recall (20,529 proteins) of the 26,917 classified by InterPro. It also finds relationships not found by other clustering methods. AVAILABILITY: The complete result of our algorithm for all the human proteins in SWISS-PROT and TrEMBL, and other supplementary information are available at http://motif.ics.es.osaka-u.ac.jp/Ncut-KL/

Algorithms↗

PubMed2005

Robust multi-scale clustering of large DNA microarray datasets with the consensus algorithm.

MOTIVATION: Hierarchical and relocation clustering (e.g. K-means and self-organizing maps) have been successful tools in the display and analysis of whole genome DNA microarray expression data. However, the results of hierarchical clustering are sensitive to outliers, and most relocation methods give results which are dependent on the initialization of the algorithm. Therefore, it is difficult to assess the significance of the results. We have developed a consensus clustering algorithm, where the final result is averaged over multiple clustering runs, giving a robust and reproducible clustering, capable of capturing small signal variations. The algorithm preserves valuable properties of hierarchical clustering, which is useful for visualization and interpretation of the results. RESULTS: We show for the first time that one can take advantage of multiple clustering runs in DNA microarray analysis by collecting re-occurring clustering patterns in a co-occurrence matrix. The results show that consensus clustering obtained from clustering multiple times with Variational Bayes Mixtures of Gaussians or K-means significantly reduces the classification error rate for a simulated dataset. The method is flexible and it is possible to find consensus clusters from different clustering algorithms. Thus, the algorithm can be used as a framework to test in a quantitative manner the homogeneity of different clustering algorithms. We compare the method with a number of state-of-the-art clustering methods. It is shown that the method is robust and gives low classification error rates for a realistic, simulated dataset. The algorithm is also demonstrated for real datasets. It is shown that more biological meaningful transcriptional patterns can be found without conservative statistical or fold-change exclusion of data. AVAILABILITY: Matlab source code for the clustering algorithm ClusterLustre, and the simulated dataset for testing are available upon request from T.G. and O.W.

Algorithms↗

PubMed2006

Linkage identification by fitness difference clustering.

Genetic Algorithms perform crossovers effectively when linkage sets - sets of variables tightly linked to form building blocks - are identified. Several methods have been proposed to detect the linkage sets. Perturbation methods (PMs) investigate fitness differences by perturbations of gene values and Estimation of distribution algorithms (EDAs) estimate the distribution of promising strings. In this paper, we propose a novel approach combining both of them, which detects dependencies of variables by estimating the distribution of strings clustered according to fitness differences. The proposed algorithm, called the Dependency Detection for Distribution Derived from fitness Differences (D(5)), can detect dependencies of a class of functions that are difficult for EDAs, and requires less computational cost than PMs.

Algorithms↗

PubMed1998

Feature extraction and state identification in biomedical signals using hierarchical fuzzy clustering.

Many problems in the field of biomedical signal processing can be reduced to a task of state recognition and event prediction. Examples can be found in tachycardia detection from ECG signals, epileptic seizure or psychotic attack prediction from an EEG signal, and prediction of vehicle drivers falling asleep from both signals. The problem generally treats a set of ordered measurements and asks for the recognition of some patterns of observed elements that will forecast an event or a transition between two different states of the biological system. It is proposed to apply clustering methods to grouping discontinuous related temporal patterns of a continuously sampled measurement. The vague switches from one stationary state to another are naturally treated by means of fuzzy clustering. In such cases, an adaptive selection of the number of clusters (the number of underlying semi-stationary processes) can overcome the general non-stationary nature of biomedical signals and enable the formation of a warning cluster. The algorithm suggested for the clustering is a new recursive algorithm for hierarchical fuzzy partitioning. Each pattern can have a non-zero membership in more than one data subset in the hierarchy. A 'natural' and feasible solution to the cluster validity problem is suggested by combining hierarchical and fuzzy concepts. The algorithm is shown to be effective for a variety of data sets with a wide dynamic range of both covariance matrices and number of members in each class. The new method is applied to state recognition during recovery from exercise using the heart rate signal and to the forecasting of generalised epileptic seizures from the EEG signal.

Algorithms↗

PubMed2002

Using weighted fixed neural networks for unsupervised fuzzy clustering.

A novel algorithm for unsupervised fuzzy clustering is introduced. The algorithm uses a so-called Weighted Fixed Neural Network (WFNN) to store important and useful information about the topological relations in a given data set. The algorithm produces a weighted connected net, of weighted nodes connected by weighted edges, which reflects and preserves the topology of the input data set. The weights of the nodes and the edges in the resulting net are proportional to the local densities of data samples in input space. The connectedness of the net can be changed, and the higher the connectedness of the net is chosen, the fuzzier the system becomes. The new algorithm is computationally efficient when compared to other existing methods for clustering multi-dimensional data, such as color images.

Algorithms↗

PubMed1998

A fuzzy vessel tracking algorithm for retinal images based on fuzzy clustering.

In this paper we present a new unsupervised fuzzy algorithm for vessel tracking that is applied to the detection of the ocular fundus vessels. The proposed method overcomes the problems of initialization and vessel profile modeling that are encountered in the literature and automatically tracks fundus vessels using linguistic descriptions like "vessel" and "nonvessel." The main tool for determining vessel and nonvessel regions along a vessel profile is the fuzzy C-means clustering algorithm that is fed with properly preprocessed data. Additional procedures for checking the validity of the detected vessels and handling junctions and forks are also presented. The application of the proposed algorithm to fundus images and simulated vessels resulted in very good overall performance and consistent estimation of vessel parameters.

Algorithms↗

PubMed2005

Topological side-chain classification of beta-turns: ideal motifs for peptidomimetic development.

Beta-turns are important topological motifs for biological recognition of proteins and peptides. Organic molecules that sample the side chain positions of beta-turns have shown broad binding capacity to multiple different receptors, for example benzodiazepines. Beta-turns have traditionally been classified into various types based on the backbone dihedral angles (phi2, psi2, phi3 and psi3). Indeed, 57-68% of beta-turns are currently classified into 8 different backbone families (Type I, Type II, Type I', Type II', Type VIII, Type VIa1, Type VIa2 and Type VIb and Type IV which represents unclassified beta-turns). Although this classification of beta-turns has been useful, the resulting beta-turn types are not ideal for the design of beta-turn mimetics as they do not reflect topological features of the recognition elements, the side chains. To overcome this, we have extracted beta-turns from a data set of non-homologous and high-resolution protein crystal structures. The side chain positions, as defined by C(alpha)-C(beta) vectors, of these turns have been clustered using the kth nearest neighbor clustering and filtered nearest centroid sorting algorithms. Nine clusters were obtained that cluster 90% of the data, and the average intra-cluster RMSD of the four C(alpha)-C(beta) vectors is 0.36. The nine clusters therefore represent the topology of the side chain scaffold architecture of the vast majority of beta-turns. The mean structures of the nine clusters are useful for the development of beta-turn mimetics and as biological descriptors for focusing combinatorial chemistry towards biologically relevant topological space.

Algorithms↗

PubMed1995

Automatic analysis of protein conformational changes by multiple linkage clustering.

An automatic algorithm is presented for analyzing protein conformational changes such as those occurring upon substrate binding or in different crystal forms of the same protein. Using, as sole information, the atomic coordinates of a pair of protein structures, the procedure first generates structure alignments, which optimize the root-mean-square deviation of the backbone atoms. To this end, equivalent secondary structures and/or loops from both proteins are combined by a multiple linkage hierarchic clustering algorithm, which generates several intertwined clustering trees. Automatic analysis of these clustering trees is used to dissect the mechanism of the conformational change. It allows the identification of the static core, representing the collection of secondary structures which undergo no structural changes, as well as other entities which move like rigid bodies. It also permits the description of the movement of secondary structures or loops relative to this core or entities. USing this information, it can be inferred whether a particular conformational change involves shear or hinge motion, or components of both. The algorithm is applied to the analysis of the conformational changes of citrate synthase, lactate dehydrogenase, lactoferrin and beta-glucosyltransferase, representing typical examples of shear- and hinge-type mechanisms, and a varied range in movement size. The results are shown to be in excellent agreement with previous analyses, and to provide additional information which gives a more complete and objective picture of the conformational change. Using our automatic algorithm, we find that any conformational change may be viewed as having components of both shear- and hinge-type motion. Determining which of these is most appropriate requires the combination of the information provided by our procedure with detailed knowledge of the protein tertiary structures.

Algorithms↗

PubMed2005

CLAGen: a tool for clustering and annotating gene sequences using a suffix tree algorithm.

Most multiple gene sequence alignment methods rely on conventions regarding the score of a multiple alignment in pairwise fashion. Therefore, as the number of sequences increases, the runtime of sequencing expands exponentially. In order to solve the problem, this paper presents a multiple sequence alignment method using a linear-time suffix tree algorithm to cluster similar sequences at one time without pairwise alignment. After searching for common subsequences, cross-matching common subsequences were generated, and sometimes inexact matching was found. So, a procedure aimed at masking the inexact cross-matching pairs was suggested here. In addition, BLAST was combined with a clustering tool in order to annotate the clusters generated by suffix tree clustering. The proposed method for clustering and annotating genes consists of the following steps: (1) construction of a suffix tree; (2) searching and overlapping common subsequences; (3) grouping subsequence pairs; (4) masking cross-matching pairs; (5) clustering gene sequences; (6) annotating gene clusters by the BLAST search. The performance of the proposed system, CLAGen, was successfully evaluated with 42 gene sequences in a TCA cycle (a citrate cycle) of bacteria. The system generated 11 clusters and found the longest subsequences of each cluster, which are biologically significant.

Algorithms↗

PubMed2003

Genetic algorithms applied to multi-class clustering for gene expression data.

A hybrid GA (genetic algorithm)-based clustering (HGACLUS) schema, combining merits of the Simulated Annealing, was described for finding an optimal or near-optimal set of medoids. This schema maximized the clustering success by achieving internal cluster cohesion and external cluster isolation. The performance of HGACLUS and other methods was compared by using simulated data and open microarray gene-expression datasets. HGACLUS was generally found to be more accurate and robust than other methods discussed in this paper by the exact validation strategy and the explicit cluster number.

Algorithms↗

PubMed2002

An efficient algorithm for large-scale detection of protein families.

Detection of protein families in large databases is one of the principal research objectives in structural and functional genomics. Protein family classification can significantly contribute to the delineation of functional diversity of homologous proteins, the prediction of function based on domain architecture or the presence of sequence motifs as well as comparative genomics, providing valuable evolutionary insights. We present a novel approach called TRIBE-MCL for rapid and accurate clustering of protein sequences into families. The method relies on the Markov cluster (MCL) algorithm for the assignment of proteins into families based on precomputed sequence similarity information. This novel approach does not suffer from the problems that normally hinder other protein sequence clustering algorithms, such as the presence of multi-domain proteins, promiscuous domains and fragmented proteins. The method has been rigorously tested and validated on a number of very large databases, including SwissProt, InterPro, SCOP and the draft human genome. Our results indicate that the method is ideally suited to the rapid and accurate detection of protein families on a large scale. The method has been used to detect and categorise protein families within the draft human genome and the resulting families have been used to annotate a large proportion of human proteins.

Algorithms↗

PubMed2002

Geometry optimisation of aluminium clusters using a genetic algorithm.

The application of a Genetic Algorithm, for optimising the geometry of aluminium clusters with 21-55 atoms bound by the many-body Murrell-Mottram potential, is described. In this size regime, a number of different structural motifs are identified--face-centred cubic, hexagonal close packed, decahedral and icosahedral structures. The larger clusters consist of hollow icosahedral geometric shells, with Al55 having a centred icosahedral structure. Evolutionary Progress Plots for Al19 and Al38 reveal how the best structure evolves from generation to generation upon operation of the Genetic Algorithm.

Journal Article↗

PubMed2001

CLIFF: clustering of high-dimensional microarray data via iterative feature filtering using normalized cuts.

We present CLIFF, an algorithm for clustering biological samples using gene expression microarray data. This clustering problem is difficult for several reasons, in particular the sparsity of the data, the high dimensionality of the feature (gene) space, and the fact that many features are irrelevant or redundant. Our algorithm iterates between two computational processes, feature filtering and clustering. Given a reference partition that approximates the correct clustering of the samples, our feature filtering procedure ranks the features according to their intrinsic discriminability, relevance to the reference partition, and irredundancy to other relevant features, and uses this ranking to select the features to be used in the following round of clustering. Our clustering algorithm, which is based on the concept of a normalized cut, clusters the samples into a new reference partition on the basis of the selected features. On a well-studied problem involving 72 leukemia samples and 7130 genes, we demonstrate that CLIFF outperforms standard clustering approaches that do not consider the feature selection issue, and produces a result that is very close to the original expert labeling of the sample set.

Algorithms↗

PubMed2005

3-D reconstruction of microcalcification clusters using stereo imaging: algorithm and mammographic unit calibration.

The three-dimensional (3-D) shape of microcalcification clusters is an important indicator in early breast cancer detection. In fact, there is a relationship between the cluster topology and the type of lesion (malignant or benign). This paper presents a 3-D reconstruction method for such clusters using two 2-D views acquired during standard mammographic examinations. For this purpose, the mammographic unit was modeled using a camera with virtual optics. This model was used to calibrate the acquisition unit and then to reconstruct the clusters in the 3-D space after microcalcification segmentation and matching. The proposed model is hardware independent since it is suitable for digital mammographic units with different geometries and with various physical acquisition principles. Three-dimensional reconstruction results are presented here to prove the validity of the method. Tests were first performed using a phantom with a well-known geometry. The latter contained X-ray opaque glass balls representing microcalcifications. The positions of these balls were reconstructed with a 16.25-microm mean accuracy. This very high inherent algorithm accuracy is more than enough for a precise 3-D cluster representation. Further validation tests were carried out using a second phantom including a spherical cluster. This phantom was built with materials simulating the behavior of both mammary tissue and microcalcifications toward Xrays. The reconstructed shape was effectively spherical. Finally, reconstructions were carried out for real clusters and their results are also presented.

Algorithms↗

PubMed2003

Analysing gene expressions with GRANK.

UNLABELLED: Unravelling overlapping clusters of functionally linked genes is a major challenge to current clustering programs. Algorithm GRANK permits systematic study of overlap between clusters of genes of a similar expression profile and large variation across a series of microarrays. AVAILABILITY: GRANK is freely available from http://www.bio.vu.nl/microb/research/tumor.html provided one adheres to the end-user license agreement in the associated manual. SUPPLEMENTARY INFORMATION: Above website also supplies the in- and output files used in the example run.

Algorithms↗

PubMed2003

High concentrations of long interspersed nuclear element sequence distinguish monoallelically expressed genes.

Genes subject to monoallelic expression are expressed from only one of the two alleles either selected at random (random monoallelic genes) or in a parent-of-origin specific manner (imprinted genes). Because high densities of long interspersed nuclear element (LINE)-1 transposon sequence have been implicated in X-inactivation, we asked whether monoallelically expressed autosomal genes are also flanked by high densities of LINE-1 sequence. A statistical analysis of repeat content in the regions surrounding monoallelically and biallelically expressed genes revealed that random monoallelic genes were flanked by significantly higher densities of LINE-1 sequence, evolutionarily more recent and less truncated LINE-1 elements, fewer CpG islands, and fewer base-pairs of short interspersed nuclear elements (SINEs) sequence than biallelically expressed genes. Random monoallelic and imprinted genes were pooled and subjected to a clustering analysis algorithm, which found two clusters on the basis of aforementioned sequence characteristics. Interestingly, these clusters did not follow the random monoallelic vs. imprinted classifications. We infer that chromosomal sequence context plays a role in monoallelic gene expression and may involve the recognition of long repeats or other features. The sequence characteristics that distinguished the high-LINE-1 category were used to identify more than 1,000 additional genes from the human and mouse genomes as candidate genes for monoallelic expression.

Algorithms↗

PubMed1994

Receiver-operated characteristic curve analysis of two algorithms assessing human growth hormone pulsatile secretion (PULSAR, CLUSTER): comparison of peak detection efficacy.

Computer-based peak identification algorithms reduce observer bias in the analysis of pulsatile hormone secretion. With increasing peak detection stringency, an algorithm will detect varying proportions of true-positive and false-positive peaks, determining its receiver-operated characteristics (ROC). To demonstrate that ROC curve analysis can characterize algorithm performance, we analyzed growth hormone (hGH) profiles from 94 children obtained with different hGH assay techniques [radioimmunoassay (RIA), immunoradiometric assay (IRMA)] at different sampling intervals (group A: 1 h/RIA; group B: 1 h/IRMA; group C: 20 min/RIA; group D: 20 min/IRMA), using the PULSAR and CLUSTER algorithms. The area under the ROC curve (AUC) was taken to compare the efficacy of both algorithms over a range of peak recognition stringency thresholds kept constant between algorithms, using hGH noise series for threshold calibration and the results of multiple visual inspection as reference standards. AUC by PULSAR ranged from 0.926 (group C) to 0.961 (group A), indicating good algorithm performance. AUC by CLUSTER ranged from 0.869 (group B) to 0.916 (group D) in the 20-min series, decreasing to 0.756 (group C) and 0.868 (group A) in the 1-hour series. At lower sampling intensity, significant discordant sensitivity existed between algorithms for RIA (p < 0.001) and IRMA (p < 0.0026). When adjusted to a high, assay-specific, comparable stringency, and employed on 20-min sampling hGH data, both the CLUSTER and PULSAR algorithm operated at a similarly high peak detection efficacy. The PULSAR algorithm appears to be more robust when hGH series with lower sampling intensities are analyzed.(ABSTRACT TRUNCATED AT 250 WORDS)

Algorithms↗

PubMed2003

Automatic landmark extraction from image data using modified growing neural gas network.

A new method for automatic landmark extraction from MR brain images is presented. In this method, landmark extraction is accomplished by modifying growing neural gas (GNG), which is a neural-network-based cluster-seeking algorithm. Using modified GNG (MGNG) corresponding dominant points of contours extracted from two corresponding images are found. These contours are borders of segmented anatomical regions from brain images. The presented method is compared to: 1) the node splitting-merging Kohonen model and 2) the Teh-Chin algorithm (a well-known approach for dominant points extraction of ordered curves). It is shown that the proposed algorithm has lower distortion error, ability of extracting landmarks from two corresponding curves simultaneously, and also generates the best match according to five medical experts.

Algorithms↗