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

PubMed2004

Distance-preserving projection of high-dimensional data for nonlinear dimensionality reduction.

A distance-preserving method is presented to map high-dimensional data sequentially to low-dimensional space. It preserves exact distances of each data point to its nearest neighbor and to some other near neighbors. Intrinsic dimensionality of data is estimated by examining the preservation of interpoint distances. The method has no user-selectable parameter. It can successfully project data when the data points are spread among multiple clusters. Results of experiments show its usefulness in projecting high-dimensional data.

Algorithms↗

PubMedDate not supplied

Prediction of membrane proteins in Mycobacterium tuberculosis using a support vector machine algorithm.

We report our finding of linear clustering of signal sequences at the N-terminus of M.tb membrane proteins, directing membrane localization. Although it is widely accepted that membrane proteins have signal peptides at the N-terminus, statistical ensemble analysis of Support Vector Machine prediction results indicate that M.tb membrane proteins have embedded N-terminal sequence patterns beyond the signal peptides previously identified in E. coli. The additional patterns at the N-terminus of M.tb membrane proteins may have correlations to their unique enzymatic functions and unusual characteristics such as membrane interaction in pathogenes.

Algorithms↗

PubMed1999

Computer identification of musical instruments using pattern recognition with cepstral coefficients as features.

Cepstral coefficients based on a constant Q transform have been calculated for 28 short (1-2 s) oboe sounds and 52 short saxophone sounds. These were used as features in a pattern analysis to determine for each of these sounds comprising the test set whether it belongs to the oboe or to the sax class. The training set consisted of longer sounds of 1 min or more for each of the instruments. A k-means algorithm was used to calculate clusters for the training data, and Gaussian probability density functions were formed from the mean and variance of each of the clusters. Each member of the test set was then analyzed to determine the probability that it belonged to each of the two classes; and a Bayes decision rule was invoked to assign it to one of the classes. Results have been extremely good and are compared to a human perception experiment identifying a subset of these same sounds.

Algorithms↗

PubMed2004

Machine learning based pattern recognition applied to microarray data.

MOTIVATION: Microarrays have allowed the expression level of thousands of genes or proteins to be measured simultaneously. Data sets generated by these arrays consist of a small number of observations (e.g., 20-100 samples) on a very large number of variables (e.g., 10,000 genes or proteins). The observations in these data sets often have other attributes associated with them such as a class label denoting the pathology of the subject. Finding the genes or proteins that are correlated to these attributes is often a difficult task since most of the variables do not contain information about the pathology and as such can mask the identity of the relevant features. We describe a genetic algorithm (GA) that employs both supervised and unsupervised learning to mine gene expression and proteomic data. The pattern recognition GA selects features that increase clustering, while simultaneously searching for features that optimize the separation of the classes in a plot of the two or three largest principal components of the data. Because the largest principal components capture the bulk of the variance in the data, the features chosen by the GA contain information primarily about differences between classes in the data set. The principal component analysis routine embedded in the fitness function of the GA acts as an information filter, significantly reducing the size of the search space since it restricts the search to feature sets whose principal component plots show clustering on the basis of class. The algorithm integrates aspects of artificial intelligence and evolutionary computations to yield a smart one pass procedure for feature selection, clustering, classification, and prediction.

Algorithms↗

PubMed2005

Robust nonrigid registration to capture brain shift from intraoperative MRI.

We present a new algorithm to register 3-D preoperative magnetic resonance (MR) images to intraoperative MR images of the brain which have undergone brain shift. This algorithm relies on a robust estimation of the deformation from a sparse noisy set of measured displacements. We propose a new framework to compute the displacement field in an iterative process, allowing the solution to gradually move from an approximation formulation (minimizing the sum of a regularization term and a data error term) to an interpolation formulation (least square minimization of the data error term). An outlier rejection step is introduced in this gradual registration process using a weighted least trimmed squares approach, aiming at improving the robustness of the algorithm. We use a patient-specific model discretized with the finite element method in order to ensure a realistic mechanical behavior of the brain tissue. To meet the clinical time constraint, we parallelized the slowest step of the algorithm so that we can perform a full 3-D image registration in 35 s (including the image update time) on a heterogeneous cluster of 15 personal computers. The algorithm has been tested on six cases of brain tumor resection, presenting a brain shift of up to 14 mm. The results show a good ability to recover large displacements, and a limited decrease of accuracy near the tumor resection cavity.

Algorithms↗

PubMed2006

A cost-function approach to rival penalized competitive learning (RPCL).

Rival penalized competitive learning (RPCL) has been shown to be a useful tool for clustering on a set of sample data in which the number of clusters is unknown. However, the RPCL algorithm was proposed heuristically and is still in lack of a mathematical theory to describe its convergence behavior. In order to solve the convergence problem, we investigate it via a cost-function approach. By theoretical analysis, we prove that a general form of RPCL, called distance-sensitive RPCL (DSRPCL), is associated with the minimization of a cost function on the weight vectors of a competitive learning network. As a DSRPCL process decreases the cost to a local minimum, a number of weight vectors eventually fall into a hypersphere surrounding the sample data, while the other weight vectors diverge to infinity. Moreover, it is shown by the theoretical analysis and simulation experiments that if the cost reduces into the global minimum, a correct number of weight vectors is automatically selected and located around the centers of the actual clusters, respectively. Finally, we apply the DSRPCL algorithms to unsupervised color image segmentation and classification of the wine data.

Algorithms↗

PubMed1996

An iterative algorithm for cell segmentation using short-time Fourier transform.

In this paper, an iterative cell image segmentation algorithm using short-time Fourier transform magnitude vectors as class features is presented. The cluster centroids of the magnitude vectors are obtained by the K-means clustering method and used as representative class features. The initial image segmentation classifies only those image pixels whose surrounding closely matches a class centroid. The subsequent procedure iteratively classifies the remaining image pixels by combining their spatial distance from the regions already segmented and the similarities between their corresponding magnitude vectors and the cluster centroids. Experimental results of the proposed algorithm for segmenting real cell images are provided.

Algorithms↗

PubMed2004

Karyometry detects subvisual differences in chromatin organisation state between non-recurrent and recurrent papillary urothelial neoplasms of low malignant potential.

AIM: To analyse nuclear chromatin texture in non-recurrent and recurrent papillary urothelial neoplasms of low malignant potential (PUNLMPs). MATERIALS: Ninety three karyometric features were analysed on haematoxylin and eosin stained sections from 20 PUNLMP cases: 10 from patients with a solitary PUNLMP lesion, who were disease free during at least eight years' follow up, and 10 from patients with unifocal PUNLMP, one or more recurrences being seen during follow up. RESULTS: Kruskal-Wallis analysis was used to search for features showing significant differences between recurrent and non-recurrent cases. Significance was better than p<0.005 for more than 20 features. Based on significance, six texture features were selected for discriminant analysis. Stepwise linear discriminant analysis reduced Wilk's lambda to 0.87, indicating a highly significant difference between the two multivariate data sets, but only modest ability to discriminate (70% correct case classification). A box sequential classifier was used based on data derived from discriminant analysis. The classifier took three classification steps and classified 19 of the 20 cases correctly (95% correct case classification). To determine whether significant case grouping could also be obtained based on an objective criterion, the merged data sets of non-recurrent and recurrent cases were submitted to the unsupervised learning algorithm P-index. Two clusters were formed with significant differences. The subsequent application of a Cooley/Lohnes classifier resulted in an overall correct case classification rate of 85%. CONCLUSIONS: Karyometry and multivariate analyses detect subvisual differences in chromatin organisation state between non-recurrent and recurrent PUNLMPs, thus allowing identification of lesions that do or do not recur.

Algorithms↗

PubMed2003

Automated fiducial marker detection for patient registration in image-guided neurosurgery.

OBJECTIVE: The registration of applied fiducial markers within the preoperative data is often left to the surgeon, who has to identify and tag the center of each marker. This is both time-consuming and a potential source of error. For this reason, the development of an automated procedure was desirable. In this study, we have investigated the accuracy of a software algorithm for detecting fiducial markers within the navigation data set. The influence of adjustable values for accuracy and threshold on the sensitivity and specificity of the detection process, as well as the time gain, was investigated. PATIENTS AND METHODS: One hundred MP-RAGE MRI data sets of patients with different pathologies who were scheduled for image-guided surgery were used in this study. A total of 591 applied fiducial markers were to be detected using the algorithm of the software VVPlanning 1.3 (BrainLAB, Heimstetten, Germany) on a Pentium II standard PC. The size value of a marker in the y-direction is called "accuracy" and depends on the slice thickness. "Threshold" describes the gray level above which the algorithm starts searching for pixel clusters. The threshold value was changed stepwise on the basis of a constant "accuracy" value. The "accuracy" value was changed on the basis of that threshold value at which all markers were detected correctly. RESULTS: The time needed for automatic detection varied between 12 s and 25 s. An optimum value for adjustable marker size was found to be 1.1 mm, with 8 undetected markers (1.35%) and 7 additionally detected structures (1.18%) out of 591. The mean gray level (Threshold) for all data sets above which marker detection was correct was 248.9. The automatic detection of markers was good for higher gray levels, with 11 missed markers (1.86%). Starting the algorithm at lower gray levels led to a decreased incidence of missed markers (0.17%), but increased the incidence of additionally detected structures to 27.92%. CONCLUSION: The automatic marker-detection algorithm is a robust, fast and objective instrument for reliable fiducial marker registration when used with optimum settings for both threshold and accuracy.

Adolescent↗

PubMed2003

Parallelization of four-component calculations. II. Symmetry-driven parallelization of the 4-Spinor CCSD algorithm.

Given the importance of the Coupled-cluster (CC) method as an efficient and accurate way to take electron correlation into account, we extend the parallelization technique in the second part of this series also to the 4-Spinor CCSD algorithm implemented in the Dirac-Fock packages DIRAC and MOLFDIR. The present implementation is based on the availability of the transformed molecular two-electron integrals on an external storage medium. The linearity of the CC equations in these two-electron integrals is used in a parallelization strategy that is based on distribution of the two largest integral classes that carry three or four virtual spinor indices. The corresponding partial contributions to the T(1) and T(2) amplitudes are calculated on each node and added using Message Passing Interface (MPI) library calls. Although we did not employ a master/slave principle, one specific node was assigned to also perform the remaining serial parts of the algorithm. In the critical sections considerable savings in storage requirements and computer time could be achieved, and this allows for computations on larger systems in the framework of four-component theory.

Journal Article↗

PubMed2003

A unified non-rigid feature registration method for brain mapping.

This paper describes the design, implementation and results of a unified non-rigid feature registration method for the purposes of anatomical MRI brain registration. An important characteristic of the method is its ability to fuse different types of anatomical features into a single point-set representation. We demonstrate the application of the method using two different types of features: the outer cortical surface and major sulcal ribbons. Non-rigid registration of the combined feature point-sets is then performed using a new robust non-rigid point matching algorithm. The point matching algorithm implements an iterative joint clustering and matching (JCM) strategy which effectively reduces the computational complexity without sacrificing accuracy. We have conducted carefully designed synthetic experiments to gauge the effect of using different types of features either separately or together. A validation study examining the accuracy of non-rigid alignment of many brain structures is also presented. Finally, we present anecdotal results on the alignment of two subject MRI brain data.

Algorithms↗

PubMed2006

On the ancestral compatibility of two phylogenetic trees with nested taxa.

Compatibility of phylogenetic trees is the most important concept underlying widely-used methods for assessing the agreement of different phylogenetic trees with overlapping taxa and combining them into common supertrees to reveal the tree of life. The notion of ancestral compatibility of phylogenetic trees with nested taxa was recently introduced. In this paper we analyze in detail the meaning of this compatibility from the points of view of the local structure of the trees, of the existence of embeddings into a common supertree, and of the joint properties of their cluster representations. Our analysis leads to a very simple polynomial-time algorithm for testing this compatibility, which we have implemented and is freely available for download from the BioPerl collection of Perl modules for computational biology.

Algorithms↗

PubMed2001

TOUCHSTONE: an ab initio protein structure prediction method that uses threading-based tertiary restraints.

The successful prediction of protein structure from amino acid sequence requires two features: an efficient conformational search algorithm and an energy function with a global minimum in the native state. As a step toward addressing both issues, a threading-based method of secondary and tertiary restraint prediction has been developed and applied to ab initio folding. Such restraints are derived by extracting consensus contacts and local secondary structure from at least weakly scoring structures that, in some cases, can lack any global similarity to the sequence of interest. Furthermore, to generate representative protein structures, a reduced lattice-based protein model is used with replica exchange Monte Carlo to explore conformational space. We report results on the application of this methodology, termed TOUCHSTONE, to 65 proteins whose lengths range from 39 to 146 residues. For 47 (40) proteins, a cluster centroid whose rms deviation from native is below 6.5 (5) A is found in one of the five lowest energy centroids. The number of correctly predicted proteins increases to 50 when atomic detail is added and a knowledge-based atomic potential is combined with clustered and nonclustered structures for candidate selection. The combination of the ratio of the relative number of contacts to the protein length and the number of clusters generated by the folding algorithm is a reliable indicator of the likelihood of successful fold prediction, thereby opening the way for genome-scale ab initio folding.

Algorithms↗

PubMed2005

Automated generation of coupled-cluster diagrams: implementation in the multireference state-specific coupled-cluster approach with the complete-active-space reference.

An algorithm for generation of the spin-orbital diagrammatic representation, the corresponding algebraical formulas, and the computer code of the coupled-cluster (CC) method with an arbitrary level of the electronic excitations has been developed. The method was implemented in the general case as well as for specific application in the state-specific multireference coupled-cluster theory (SSMRCC) based on the concept of a "formal reference state." The algorithm was tested in SSMRCC calculations describing dissociation of a single bond and in calculations describing simultaneous dissociation of two single bonds--the problem requiring up to six-particle excitations in the CC operator.

Journal Article↗

PubMed1997

Modelling antibody side chain conformations using heuristic database search.

We have developed a knowledge-based system which models the side chain conformations of residues in the variable domains of antibody Fv fragments. The system is written in Prolog and uses an object-oriented database of aligned antibody structures in conjunction with a side chain rotamer library. The antibody database provides 3-dimensional clusters of side chain conformations which can be copied en masse into the model structure. The object-oriented database architecture facilitates a navigational style of database access, necessary to assemble side chains clusters. Around 60% of the model is built using side chain clusters and this eliminates much of the combinatorial complexity associated with many other side chain placement algorithms. Construction and placement of side chain clusters is guided by a heuristic cost function based on a simple model of side chain packing interactions. Even with a simple model, we find that a large proportion of side chain conformations are modelled accurately. We expect our approach could be used with other homologous protein families, in addition to antibodies, both to improve the quality of model structures and to give a "smart start" to the side chain placement problem.

Algorithms↗

PubMedDate not supplied

Pattern of echocardiographic abnormalities with acute cardiac allograft rejection in adults: correlation with endomyocardial biopsy.

In patients who have undergone successful orthotopic heart transplantation, a noninvasive method for rejection surveillance would reduce the frequency of endomyocardial biopsy, guide the timing of biopsies, and allow for more frequent monitoring. This study identified the pattern of change in echocardiographically determined indexes of left ventricular mass, volume, and function that characterized biopsy-positive acute rejection in adult heart transplant patients receiving triple-drug immunosuppressive therapy and describes a simple computer-driven algorithm capable of identifying rejection with high sensitivity and specificity. Two-dimensional and M-mode echocardiography and Doppler color flow analyses were performed within 24 hours of endomyocardial biopsy. M-mode echocardiograms of the left ventricle were digitized and analyzed blinded to the biopsy interpretation, using a computer-assisted measurement format, for size, mass, and wall motion in systole and diastole. Twenty-nine studies were retrospectively analyzed to define the echocardiographic pattern characteristic for rejection. Left ventricular chamber size decreased, and indexes of diastolic function were significantly depressed in patients with biopsy evidence of moderate or severe rejection. However, no single parameter was sufficiently sensitive to detect all episodes of rejection partly because of differences between patients in the echocardiographic manifestations of acute rejection. To accommodate this patient variability, multiple echocardiographic parameters were clustered into a unique scoring algorithm (ECHO score). When applied prospectively to 49 studies, the likelihood that a patient would have an ECHO score not indicative of rejection but with moderate/severe rejection on biopsy was low (less than 3%) or a negative predictive value of 97.4%.(ABSTRACT TRUNCATED AT 250 WORDS)

Acute Disease↗

PubMed2025

scACCorDiON: a clustering approach for explainable patient level cell-cell communication graph analysis.

MOTIVATION: Combining single-cell sequencing with ligand-receptor (LR) analysis paves the way for the characterization of cell communication events in complex tissues. In particular, directed weighted graphs naturally represent cell-cell communication events. However, current computational methods cannot yet analyze sample-specific cell-cell communication events, as measured in single-cell data produced in large patient cohorts. Cohort-based cell-cell communication analysis presents many challenges, such as the nonlinear nature of cell-cell communication and the high variability given by the patient-specific single-cell RNAseq datasets. RESULTS: Here, we present scACCorDiON (single-cell Analysis of Cell-Cell Communication in Disease clusters using Optimal transport in Directed Networks), an optimal transport algorithm exploring node distances on the Markov Chain as the ground metric between directed weighted graphs. Benchmarking indicates that scACCorDiON performs a better clustering of samples according to their disease status than competing methods that use undirected graphs. We provide a case study of pancreas adenocarcinoma, where scACCorDion detects a sub-cluster of disease samples associated with changes in the tumor microenvironment. Our study case corroborates that clusters provide a robust and explainable representation of cell-cell communication events and that the expression of detected LR pairs is predictive of pancreatic cancer survival. AVAILABILITY AND IMPLEMENTATION: The code of scACCorDiON is available at https://scaccordion.readthedocs.io/en/latest/. and https://doi.org/10.5281/zenodo.15267648. The survival analysis package can be found at https://github.com/CostaLab/scACCorDiON.su.

Humans↗

PubMed1999

Segmentation of confocal microscope images of cell nuclei in thick tissue sections.

Segmentation of intact cell nuclei from three-dimensional (3D) images of thick tissue sections is an important basic capability necessary for many biological research studies. However, segmentation is often difficult because of the tight clustering of nuclei in many specimen types. We present a 3D segmentation approach that combines the recognition capabilities of the human visual system with the efficiency of automatic image analysis algorithms. The approach first uses automatic algorithms to separate the 3D image into regions of fluorescence-stained nuclei and unstained background. This includes a novel step, based on the Hough transform and an automatic focusing algorithm to estimate the size of nuclei. Then, using an interactive display, each nuclear region is shown to the analyst, who classifies it as either an individual nucleus, a cluster of multiple nuclei, partial nucleus or debris. Next, automatic image analysis based on morphological reconstruction and the watershed algorithm divides clusters into smaller objects, which are reclassified by the analyst. Once no more clusters remain, the analyst indicates which partial nuclei should be joined to form complete nuclei. The approach was assessed by calculating the fraction of correctly segmented nuclei for a variety of tissue types: Caenorhabditis elegans embryos (839 correct out of a total of 848), normal human skin (343/362), benign human breast tissue (492/525), a human breast cancer cell line grown as a xenograft in mice (425/479) and invasive human breast carcinoma (260/335). Furthermore, due to the analyst's involvement in the segmentation process, it is always known which nuclei in a population are correctly segmented and which not, assuming that the analyst's visual judgement is correct.

Animals↗