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

PubMed2026

GBSC: graph-based sequence clustering method for similar short tandem repeats in protein sequences.

MOTIVATION: Short tandem repeats (STRs) are abundant in protein sequences and play important role in determining their structures and functions. Strikingly, the unusual compositional characteristics of tandem repeats break classical sequence analysis tools. RESULTS: Here, we establish the first algorithm to effectively identify and cluster STRs: Graph-Based Sequence Clustering (GBSC) features linear time complexity, and clusters protein sequence fragments based on their STRs, while allowing for insertions and mutations and supporting the analysis of imperfect or cryptic repeats. Due to its computational efficacy, our algorithm can be used to systematically scan for patterns in large datasets. We compare our method both to state-of-the-art methods for identifying STRs in proteins and alternative clustering approaches. Unlike existing STR analysis methods, GBSC clusters repeat patterns rather than raw sequences, operating at the level of structural repeat identity, while tolerating biological variations and preventing erroneous merging of structurally and functionally distinct motifs. Whereas functional annotation is typically only available at the protein level, the functions of individual STRs and sequences of adjacent STRs remain largely unknown. On a challenging use case we here demonstrate and discuss how our method can be used to associate previously unannotated repetitive protein fragments with similar ones, allowing the transfer of annotation by similarity. For the first time, GBSC offers a tool that systematically extends this fundamental bioinformatics principle to low-complexity regions across large datasets. AVAILABILITY AND IMPLEMENTATION: GBSC is available at GitHub https://github.com/patryk-jarnot/GBSC and https://doi.org/10.5281/zenodo.18965247. The data and scripts to reproduce the analysis are available at https://doi.org/10.5281/zenodo.16906653.

Microsatellite Repeats↗

PubMed2003

Identification of functional clusters of transcription factor binding motifs in genome sequences: the MSCAN algorithm.

MOTIVATION: The identification of regulatory control regions within genomes is a major challenge. Studies have demonstrated that regulating regions can be described as locally dense clusters or modules of cis-acting transcription factor binding sites (TFBS). For well-described biological contexts, it is possible to train predictive algorithms to discern novel modules in genome sequences. However, utility of module detection methods has been severely limited by insufficient training data. For only a few tissues can one obtain sufficient numbers of literature-derived regulatory modules. RESULTS: We present a novel method, MSCAN, that circumvents the training data problem by measuring the statistical significance of any non-overlapping combination of TFBS in a window. Given a set of transcription factor binding profiles, a significance threshold, and a genomic sequence, MSCAN returns putative regulatory regions. We assess performance on two curated collections of regulatory regions; one each for tissue-specific expression in liver and skeletal muscle cells. The efficiency of MSCAN allows for predictive screens of entire genomes.

Algorithms↗

PubMed2004

Analysis of speedup as function of block size and cluster size for parallel feed-forward neural networks on a Beowulf cluster.

The performance of feed-forward neural networks trained with the backpropagation algorithm on a dedicated Beowulf cluster is analyzed. The concept of training set parallelism is applied. A new model for run time and speedup prediction is developed. With the model the speedup and efficiency of one iteration of the neural networks can be estimated as a function of block size and cluster size. The model is applied to three example problems representing different applications and network architectures. The estimation of the model has a higher accuracy than traditional methods for run time estimation and can be efficiently calculated. Experiments show that speedup of one iteration does not necessarily translate to a shorter training time toward a given error level. To overcome this problem a heuristic extension to training set parallelism called weight averaging is developed. The results show that training in parallel should only be done on clusters with high performance network connections or a multiprocessor machine. A rule of thumb is given for how much network performance of the cluster is needed to achieve speedup of the training time for a neural network.

Cluster Analysis↗

PubMed1998

Categorization of interictal epileptiform potentials using a graph-theoretic method.

OBJECTIVES: In patients with epileptic seizures, localization of the source of interictal epileptiform activity is of interest. For correct source localization, a favorable signal to noise ratio is important, and to achieve this, averaging of several epileptiform potentials is often necessary. Before averaging, a careful categorization of epileptiform potentials with different potential distributions is crucial. The aim of this study was to investigate whether a a hierarchic, graph-theoretic algorithm could be used for this categorization. METHODS: In 4 patients, 50-100 sharp waves with different surface distributions were categorized independently with the algorithm, and by visual inspection of the traces. As an independent evaluation of the algorithm, a dipole reconstruction was performed for each sharp wave, and the dipole results for the sharp waves from the different automatically obtained categories were compared. RESULTS: All patients showed a high degree of correspondence between the results of the automatic analysis and the visual estimation. There were clear differences in dipole results between the sharp waves of the different categories obtained from the automatic categorization. CONCLUSION: The results indicate that the graph-theoretic categorization algorithm provides a reliable clustering of interictal epileptiform potentials, and that the method may become a useful tool in the pre-averaging categorization of interictal epileptiform potentials prior to source localization.

Action Potentials↗

PubMed2006

Automatic identification of the left ventricle in cardiac cine-MR images: dual-contrast cluster analysis and scout-geometry approaches.

PURPOSE: To evaluate the technical feasibility of two approaches--dual-contrast (DC) cluster analysis, and scout geometry (SG)--for automatic identification of the left ventricular (LV) cavity in short-axis (SA) cine-MR images. MATERIALS AND METHODS: The DC algorithm uses Fuzzy C-Means (FCM) cluster analysis of SA images from a black-blood double-inversion recovery turbo spin-echo (dual IR TSE) sequence, and bright-blood images from a steady-state free precession (SSFP) sequence. The SG algorithm employs geometric information from scout views (i.e., vertical long-axis (VLA) and four-chamber (4CH) views). Both algorithms incorporate additional geometric continuity constraints along with LV region segmentation to identify the LV. The performance of both algorithms was compared on images of eight healthy volunteers, and the SG algorithm was further evaluated on images of 13 clinical patients. RESULTS: The DC algorithm identified the LV in 89% (72/75 at end-diastole (ED) and 47/59 at end-systole (ES)) of the images from healthy volunteers, compared to 98% (74/75 at ED and 57/59 at ES) by the SG algorithm. Both methods are robust against interslice signal variations and misalignment. The DC method suffers from misregistration between the dual IR TSE and SSFP images near the apex at ES. The SG method identified the LV in 91% (112/122 at ED and 91/102 at ES) of the images from clinical patients. CONCLUSION: The SG method requires no additional scan, is robust and accurate, and performs better than the DC method for automatic identification of the LV.

Adult↗

PubMed2003

CUBIC: identification of regulatory binding sites through data clustering.

Transcription factor binding sites are short fragments in the upstream regions of genes, to which transcription factors bind to regulate the transcription of genes into mRNA. Computational identification of transcription factor binding sites remains an unsolved challenging problem though a great amount of effort has been put into the study of this problem. We have recently developed a novel technique for identification of binding sites from a set of upstream regions of genes, that could possibly be transcriptionally co-regulated and hence might share similar transcription factor binding sites. By utilizing two key features of such binding sites (i.e. their high sequence similarities and their relatively high frequencies compared to other sequence fragments), we have formulated this problem as a cluster identification problem. That is to identify and extract data clusters from a noisy background. While the classical data clustering problem (partitioning a data set into clusters sharing common or similar features) has been extensively studied, there is no general algorithm for solving the problem of identifying data clusters from a noisy background. In this paper, we present a novel algorithm for solving such a problem. We have proved that a cluster identification problem, under our definition, can be rigorously and efficiently solved through searching for substrings with special properties in a linear sequence. We have also developed a method for assessing the statistical significance of each identified cluster, which can be used to rule out accidental data clusters. We have implemented the cluster identification algorithm and the statistical significance analysis method as a computer software CUBIC. Extensive testing on CUBIC has been carried out. We present here a few applications of CUBIC on challenging cases of binding site identification.

Algorithms↗

PubMed2003

Numerical phenetic classification of clinically significant aerobic sporoactinomycetes and related organisms.

Clinically significant aerobic sporoactinomycetes, notably agents of mycetoma, were examined for a balanced set of unit characters and the resultant data analysed using standard numerical taxonomic procedures. All save two of the one hundred and seventy three tested strains were assigned to three multimembered cluster-groups, which encompassed sixteen major (4-7 strains), ten minor (2-3 strains) and forty single membered clusters, in an analysis based on the simple matching coefficient and unweighted pair group method with arithmetic averages algorithm. The three cluster-groups were equated with the genus Actinomadura (including Actinocorallia and Streptomyces somaliensis strains), and the genera Nocardiopsis and Streptomyces, and Thermobifida and Thermomonospora, respectively. In a corresponding principal co-ordinates analysis four multimembered groups corresponding to the genera Actinomadura, Nocardiopsis, Streptomyces, and Thermobifida and Thermomonospora were recognised. The causal agents of actinomycetoma were not only assigned to established taxa, notably, to Actinomadura latina, Actinomadura madurae, Actinomadura pelletieri and Streptomyces somaliensis, but also to additional centres of taxonomic variation which were equated with the rank of species. Most of the streptomycetes isolated from clinical material were assigned to clusters equated with the species Streptomyces albus and Streptomyces anulatus. The numerical taxonomic data were used to generate a frequency matrix designed to facilitate the identification of clinically significant Actinomadura, Nocardiopsis and Streptomyces strains to the species level; rapid enzyme tests accounted for eleven out of the twenty-one diagnostic tests.

Actinomycetales↗

PubMed2002

Analysis of DNA microarrays using algorithms that employ rule-based expert knowledge.

The ability to investigate the transcription of thousands of genes concurrently by using DNA microarrays offers both major scientific opportunities and significant analytical challenges. Here we describe GABRIEL, a rule-based system of computer programs designed to apply domain-specific and procedural knowledge systematically and uniformly for the analysis and interpretation of data from DNA microarrays. GABRIEL'S problem-solving rules direct stereotypical tasks, whereas domain-specific knowledge pertains to gene functions and relationships or to experimental conditions. Additionally, GABRIEL can learn novel rules through genetic algorithms, which define patterns that best match the data being analyzed and can identify groupings in gene expression profiles preordered by chromosomal position or by a nonsupervised algorithm such as hierarchical clustering. GABRIEL subsystems explain the logic that underlies conclusions and provide a graphical interface and interactive platform for the acquisition of new knowledge. The present report compares GABRIEL'S output with published findings in which expert knowledge has been applied post hoc to microarray groupings generated by hierarchical clustering.

Algorithms↗

PubMed2001

Pharmacogenomics of cystic fibrosis.

Pharmacogenomics is becoming a frontline instrument of drug discovery, where the drug-dependent patterns of global gene expression are employed as biologically relevant end points. In the case of cystic fibrosis (CF), cells and tissues from CF patients provide the starting points of genomic analysis. The end points for drug discovery are proposed to reside in gene expression patterns of CF cells that have been corrected by gene therapy. A case is made here that successful drug therapy and gene therapy should, hypothetically, converge at a common end point. In response to a virtual tidal wave of genomic data, bioinformatics algorithms are needed to identify those genes that truly reveal drug efficacy. As examples, we describe the hierarchical clustering, GRASP, and GENESAVER algorithms, particularly within a hypothesis-driven context that focuses on data for a CF candidate drug. Pharmacogenomic approaches to CF, and other similar diseases, may eventually give us the opportunity to create drugs that work in a patient- or mutation-specific manner.

Algorithms↗

PubMed2003

Identification of regulatory binding sites using minimum spanning trees.

Recognition of protein-binding sites from the upstream regions of genes is a highly important and unsolved problem. In this paper, we present a new approach for studying this challenging issue. We formulate the binding-site recognition problem as a cluster identification problem, i.e., to identify clusters in a data set that exhibit significantly different features (e.g., density) than the overall background of the data set. We have developed a general framework for solving such a cluster identification problem. The foundation of the framework is a rigorous relationship between data clusters and subtrees of a minimum spanning tree (MST) representation of a data set. We have proposed a formal and general definition of clusters, and have demonstrated that a cluster is always represented as a connected component of the MST, and further it corresponds to a substring of a linear representation of the MST. Hence a cluster identification problem is reduced to a problem of finding substrings with certain features, for which algorithms have been developed. We have applied this MST-based cluster identification algorithm to a number of binding site identification problems. The results are highly encouraging.

Algorithms↗

PubMed2006

Competing populations on fragmented landscapes with spatially structured heterogeneities: improved landscape generation and mixed dispersal strategies.

Interactions between two species competing for space were studied using stochastic spatially explicit lattice-based simulations as well as pair approximations. The two species differed only in their dispersal strategies, which were characterized by the proportion of reproductive effort allocated to long-distance (far) dispersal versus short-distance (near) dispersal to adjacent sites. All population dynamics took place on landscapes with spatially clustered distributions of suitable habitat, described by two parameters specifying the amount and the local spatial autocorrelation of suitable habitat. Whereas previous results indicated that coexistence between pure near and far dispersers was very rare, taking place over only a very small region of the landscape parameter space, when mixed strategies are allowed, multiple strategies can coexist over a much wider variety of landscapes. On such spatially structured landscapes, the populations can partition the habitat according to local conditions, with one species using pure near dispersal to exploit large contiguous patches of suitable habitat, and another species using mixed dispersal to colonize isolated smaller patches (via far dispersal) and then rapidly exploit those patches (via near dispersal). An improved mean-field approximation which incorporates the spatially clustered habitat distribution is developed for modeling a single species on these landscapes, along with an improved Monte Carlo algorithm for generating spatially clustered habitat distributions.

Computer Simulation↗

PubMed2006

Estimating the number of clusters in DNA microarray data.

OBJECTIVES: The main objective of the research is an application of the clustering and cluster validity methods to estimate the number of clusters in cancer tumor datasets. A weighed voting technique is going to be used to improve the prediction of the number of clusters based on different data mining techniques. These tools may be used for the identification of new tumour classes using DNA microarray datasets. This estimation approach may perform a useful tool to support biological and biomedical knowledge discovery. METHODS: Three clustering and two validation algorithms were applied to two cancer tumor datasets. Recent studies confirm that there is no universal pattern recognition and clustering model to predict molecular profiles across different datasets. Thus, it is useful not to rely on one single clustering or validation method, but to apply a variety of approaches. Therefore, combination of these methods may be successfully used for the estimation of the number of clusters. RESULTS: The methods implemented in this research may contribute to the validation of clustering results and the estimation of the number of clusters. The results show that this estimation approach may represent an effective tool to support biomedical knowledge discovery and healthcare applications. CONCLUSION: The methods implemented in this research may be successfully used for the estimation of the number of clusters. The methods implemented in this research may contribute to the validation of clustering results and the estimation of the number of clusters. These tools may be used for the identification of new tumour classes using gene expression profiles.

Central Nervous System Neoplasms↗

PubMed1998

Automated classification of antibody complementarity determining region 3 of the heavy chain (H3) loops into canonical forms and its application to protein structure prediction.

A computer-based algorithm was used to cluster the loops forming the complementarity determining region (CDR) 3 of the heavy chain (H3) into canonical classes. Previous analyses of the three-dimensional structures of CDR loops (also known as the hypervariable regions) within antibody immunoglobulin variable domains have shown that for five of the six CDRs there are only a few main-chain conformations (known as canonical forms) that show clear relationships between sequence and structure. However, the larger variation in length and conformation of loops within H3 has limited the classification of these loops into canonical forms. The clustering procedure presented here is based on aligning the Ramachandran-coded main-chain conformation of the residues using a dynamic algorithm that allows the insertion of gaps to obtain an optimum alignment. A total of 41 H3 loops out of 62 non-identical loops, extracted from the Brookhaven Protein Data Bank, have been automatically grouped into 22 clusters. Inspection of the clusters for consensus sequences or intra-loop interactions or invariant conformation led to the proposal of 13 canonical forms representing 31 loops. These canonical forms include a consideration of the geometry of both the take-off region adjacent to the bracing beta-strands and the remaining loop apex. Subsequently a new set of 15 H3 loops not included in the initial analysis was considered. The clustering procedure was repeated and nine of these 15 loops could be assigned to original clusters, including seven to canonical forms. A sequence profile was generated for each canonical form from the original set of loops and matched against the sequences of the new H3 loops. For five out of the seven new H3 loops that were in a canonical form, the correct form was identified at first rank by this predictive scheme.

Amino Acid Sequence↗

PubMed2000

Improved rosenbluth monte carlo scheme for cluster counting and lattice animal enumeration

We describe an algorithm for the Rosenbluth Monte Carlo enumeration of clusters and lattice animals. The method may also be used to calculate associated properties such as moments or perimeter multiplicities of the clusters. The scheme is an extension of the Rosenbluth method for growing polymer chains and is a simplification of a scheme reported earlier by one of the authors. The algorithm may be used to obtain a Monte Carlo estimate of the number of distinct lattice animals on any lattice topology. The method is validated against exact and Monte Carlo enumerations for clusters up to size 50, on a two dimensional square lattice and three dimensional simple cubic lattice. The method may be readily adapted to yield Boltzmann weighted averages over clusters.

Journal Article↗

PubMed1995

Fuzzy cluster analysis of simple physicochemical properties of amino acids for recognizing secondary structure in proteins.

Fuzzy cluster analysis has been applied to the 20 amino acids by using 65 physicochemical properties as a basis for classification. The clustering products, the fuzzy sets (i.e., classical sets with associated membership functions), have provided a new measure of amino acid similarities for use in protein folding studies. This work demonstrates that fuzzy sets of simple molecular attributes, when assigned to amino acid residues in a protein's sequence, can predict the secondary structure of the sequence with reasonable accuracy. An approach is presented for discriminating standard folding states, using near-optimum information splitting in half-overlapping segments of the sequence of assigned membership functions. The method is applied to a nonredundant set of 252 proteins and yields approximately 73% matching for correctly predicted and correctly rejected residues with approximately 60% overall success rate for the correctly recognized ones in three folding states: alpha-helix, beta-strand, and coil. The most useful attributes for discriminating these states appear to be related to size, polarity, and thermodynamic factors. Van der Waals volume, apparent average thickness of surrounding molecular free volume, and a measure of dimensionless surface electron density can explain approximately 95% of prediction results. hydrogen bonding and hydrophobicity induces do not yet enable clear clustering and prediction.

Algorithms↗

PubMedDate not supplied

Biomedical simulation of heat transfer in a human heart.

Theory and practical experiences from numerical simulations of heat transfer in the field of medicine are presented in this paper. The cooling of a human heart during surgery was taken as an illustrative example. All phases of the simulation process are described starting with the construction of an irregularly shaped 3-dimensional model. The mathematical model is based on diffusion and Navier-Stokes equations. The system of partial differential equations is solved by finite difference approximation using an explicit time-stepping scheme to obtain the time evolution of the solution for the complete simulated interval, which is typically 1 h. A typical domain is composed of several million voxels; therefore, the program was parallelized to speed up the simulation. A speed-up of 8.2 was obtained on 16 processors in a Linux cluster.

Algorithms↗

PubMed2004

Clustering binary data in the presence of masking variables.

A number of important applications require the clustering of binary data sets. Traditional nonhierarchical cluster analysis techniques, such as the popular K-means algorithm, can often be successfully applied to these data sets. However, the presence of masking variables in a data set can impede the ability of the K-means algorithm to recover the true cluster structure. The author presents a heuristic procedure that selects an appropriate subset from among the set of all candidate clustering variables. Specifically, this procedure attempts to select only those variables that contribute to the definition of true cluster structure while eliminating variables that can hide (or mask) that true structure. Experimental testing of the proposed variable-selection procedure reveals that it is extremely successful at accomplishing this goal.

Cluster Analysis↗

PubMed2003

Genomic profiles and predictive biological networks in oxidant-induced atherogenesis.

Atherogenic stimuli trigger complex responses in vascular smooth muscle cells (VSMCs) that culminate in activation/repression of overlapping signal transduction cascades involving oxidative stress. In the case of benzo[a]pyrene (BaP), a polycyclic aromatic hydrocarbon present in tobacco smoke, the atherogenic response involves interference with redox homeostasis by oxidative intermediates of BaP metabolism. The present studies were conducted to define genomic profiles and predictive gene biological networks associated with the atherogenic response of murine (aortic) VSMCs to BaP. A combined oxidant-antioxidant treatment regimen was used to identify redox-sensitive targets during the early course of the atherogenic response. Gene expression profiles were defined using cDNA microarrays coupled to analysis of variance and several clustering methodologies. A predictor algorithm was then applied to gain insight into critical gene-gene interactions during atherogenesis. Supervised and nonsupervised analyses identified clones highly regulated by BaP, unaffected by antioxidant, and neutralized by combined chemical treatments. Lymphocyte antigen-6 complex, histocompatibility class I component factors, secreted phosphoprotein, and several interferon-inducible proteins were identified as novel redox-regulated targets of BaP. Predictor analysis confirmed these relationships and identified immune-related genes as critical molecular targets of BaP. Redox-dependent patterns of gene deregulation indicate that oxidative stress plays a prominent role during the early stages of BaP-induced atherogenesis.

Algorithms↗