Unsupervised Cryo-EM Data Clustering through Adaptively Constrained K-Means Algorithm.
Ontology highlight
ABSTRACT:
SUBMITTER: Xu Y
PROVIDER: S-EPMC5154524 | biostudies-literature |
REPOSITORIES: biostudies-literature
Similar Datasets
Project description:Structural heterogeneity in single-particle cryo-electron microscopy (cryo-EM) data represents a major challenge for high-resolution structure determination. Unsupervised classification may serve as the first step in the assessment of structural heterogeneity. However, traditional algorithms for unsupervised classification, such as K-means clustering and maximum likelihood optimization, may classify images into wrong classes with decreasing signal-to-noise-ratio (SNR) in the image data, yet demand increased computational costs. Overcoming these limitations requires further development of clustering algorithms for high-performance cryo-EM data processing. Here we introduce an unsupervised single-particle clustering algorithm derived from a statistical manifold learning framework called generative topographic mapping (GTM). We show that unsupervised GTM clustering improves classification accuracy by about 40% in the absence of input references for data with lower SNRs. Applications to several experimental datasets suggest that our algorithm can detect subtle structural differences among classes via a hierarchical clustering strategy. After code optimization over a high-performance computing (HPC) environment, our software implementation was able to generate thousands of reference-free class averages within hours in a massively parallel fashion, which allows a significant improvement on ab initio 3D reconstruction and assists in the computational purification of homogeneous datasets for high-resolution visualization.
| S-EPMC5546606 | biostudies-literature
Project description:Heterogeneous three-dimensional (3D) reconstruction in single-particle cryo-electron microscopy (cryo-EM) is an important but very challenging technique for recovering the conformational heterogeneity of flexible biological macromolecules such as proteins in different functional states. Heterogeneous projection image classification is a feasible solution to solve the structural heterogeneity problem in single-particle cryo-EM. The majority of heterogeneous projection image classification methods are developed using supervised learning technology or require a large amount of a priori knowledge, such as the orientations or common lines of the projection images, which leads to certain limitations in their practical applications. In this paper, an unsupervised heterogeneous cryo-EM projection image classification algorithm based on autoencoders is proposed, which only needs to know the number of heterogeneous 3D structures in the dataset and does not require any labeling information of the projection images or other a priori knowledge. A simple autoencoder with multi-layer perceptrons trained in iterative mode and a complex autoencoder with residual networks trained in one-pass learning mode are implemented to convert heterogeneous projection images into latent variables. The extracted high-dimensional features are reduced to two dimensions using the uniform manifold approximation and projection dimensionality reduction algorithm, and then clustered using the spectral clustering algorithm. The proposed algorithm is applied to two heterogeneous cryo-EM datasets for heterogeneous 3D reconstruction. Experimental results show that the proposed algorithm can effectively extract category features of heterogeneous projection images and achieve high classification and reconstruction accuracy, indicating that the proposed algorithm is effective for heterogeneous 3D reconstruction in single-particle cryo-EM.
| S-EPMC10179202 | biostudies-literature
Project description:BackgroundSearching for similarities in a set of biological data is intrinsically difficult due to possible data points that should not be clustered, or that should group within several clusters. Under these hypotheses, hierarchical agglomerative clustering is not appropriate. Moreover, if the dataset is not known enough, like often is the case, supervised classification is not appropriate either.ResultsCLAG (for CLusters AGgregation) is an unsupervised non hierarchical clustering algorithm designed to cluster a large variety of biological data and to provide a clustered matrix and numerical values indicating cluster strength. CLAG clusterizes correlation matrices for residues in protein families, gene-expression and miRNA data related to various cancer types, sets of species described by multidimensional vectors of characters, binary matrices. It does not ask to all data points to cluster and it converges yielding the same result at each run. Its simplicity and speed allows it to run on reasonably large datasets.ConclusionsCLAG can be used to investigate the cluster structure present in biological datasets and to identify its underlying graph. It showed to be more informative and accurate than several known clustering methods, as hierarchical agglomerative clustering, k-means, fuzzy c-means, model-based clustering, affinity propagation clustering, and not to suffer of the convergence problem proper to this latter.
| S-EPMC3519615 | biostudies-literature
Project description:Brains perform complex tasks using a fraction of the power that would be required to do the same on a conventional computer. New neuromorphic hardware systems are now becoming widely available that are intended to emulate the more power efficient, highly parallel operation of brains. However, to use these systems in applications, we need "neuromorphic algorithms" that can run on them. Here we develop a spiking neural network model for neuromorphic hardware that uses spike timing-dependent plasticity and lateral inhibition to perform unsupervised clustering. With this model, time-invariant, rate-coded datasets can be mapped into a feature space with a specified resolution, i.e., number of clusters, using exclusively neuromorphic hardware. We developed and tested implementations on the SpiNNaker neuromorphic system and on GPUs using the GeNN framework. We show that our neuromorphic clustering algorithm achieves results comparable to those of conventional clustering algorithms such as self-organizing maps, neural gas or k-means clustering. We then combine it with a previously reported supervised neuromorphic classifier network to demonstrate its practical use as a neuromorphic preprocessing module.
| S-EPMC6658584 | biostudies-literature
Project description:Random spherically-constrained (RSC) reconstruction is a new form of single particle reconstruction (SPR) using cryo-EM images of membrane proteins embedded in spherical lipid vesicles to generate a 3D protein structure. The method has many advantages over conventional SPR, including a more native environment for protein particles and an initial estimate of the particle's angular orientation. These advances allow us to determine structures of membrane proteins such as ion channels and derive more reliable structure estimates. We present an algorithm that relates conventional SPR to the RSC model, and generally, to projection images of particles embedded with an axis parallel to the local normal of a general 2D manifold. We illustrate the performance of this algorithm in the spherical system using synthetic data.
| S-EPMC3903049 | biostudies-literature
Project description:A critical step in cryogenic electron microscopy (cryo-EM) image analysis is to calculate the average of all images aligned to a projection direction. This average, called the class mean, improves the signal-to-noise ratio in single-particle reconstruction. The averaging step is often compromised because of the outlier images of ice, contaminants, and particle fragments. Outlier detection and rejection in the majority of current cryo-EM methods are done using cross-correlation with a manually determined threshold. Empirical assessment shows that the performance of these methods is very sensitive to the threshold. This paper proposes an alternative: a w-estimator of the average image, which is robust to outliers and which does not use a threshold. Various properties of the estimator, such as consistency and influence function are investigated. An extension of the estimator to images with different contrast transfer functions is also provided. Experiments with simulated and real cryo-EM images show that the proposed estimator performs quite well in the presence of outliers.
| S-EPMC4871777 | biostudies-literature
Project description:Recent progress in bioinformatics research has led to the accumulation of huge quantities of biological data at various data sources. The DNA microarray technology makes it possible to simultaneously analyze large number of genes across different samples. Clustering of microarray data can reveal the hidden gene expression patterns from large quantities of expression data that in turn offers tremendous possibilities in functional genomics, comparative genomics, disease diagnosis and drug development. The k- ¬means clustering algorithm is widely used for many practical applications. But the original k-¬means algorithm has several drawbacks. It is computationally expensive and generates locally optimal solutions based on the random choice of the initial centroids. Several methods have been proposed in the literature for improving the performance of the k-¬means algorithm. A meta-heuristic optimization algorithm named harmony search helps find out near-global optimal solutions by searching the entire solution space. Low clustering accuracy of the existing algorithms limits their use in many crucial applications of life sciences. In this paper we propose a novel Harmony Search-K means Hybrid (HSKH) algorithm for clustering the gene expression data. Experimental results show that the proposed algorithm produces clusters with better accuracy in comparison with the existing algorithms.
| S-EPMC3563403 | biostudies-literature
Project description:Single-cell RNA sequencing technologies have enabled us to study tissue heterogeneity at cellular resolution. Fast-developing sequencing platforms like droplet-based sequencing make it feasible to parallel process thousands of single cells effectively. Although a unique molecular identifier (UMI) can remove bias from amplification noise to a certain extent, clustering for such sparse and high-dimensional large-scale discrete data remains intractable and challenging. Most existing deep learning-based clustering methods utilize the mean square error or negative binomial distribution with or without zero inflation to denoise single-cell UMI count data, which may underfit or overfit the gene expression profiles. In addition, neglecting the molecule sampling mechanism and extracting representation by simple linear dimension reduction with a hard clustering algorithm may distort data structure and lead to spurious analytical results. In this paper, we combined the deep autoencoder technique with statistical modeling and developed a novel and effective clustering method, scDMFK, for single-cell transcriptome UMI count data. ScDMFK utilizes multinomial distribution to characterize data structure and draw support from neural network to facilitate model parameter estimation. In the learned low-dimensional latent space, we proposed an adaptive fuzzy k-means algorithm with entropy regularization to perform soft clustering. Various simulation scenarios and the analysis of 10 real datasets have shown that scDMFK outperforms other state-of-the-art methods with respect to data modeling and clustering algorithms. Besides, scDMFK has excellent scalability for large-scale single-cell datasets.
| S-EPMC7180207 | biostudies-literature
Project description:Drug repositioning is the process of identifying new uses for existing drugs. Computational drug repositioning methods can reduce the time, costs and risks of drug development by automating the analysis of the relationships in pharmacology networks. Pharmacology networks are large and heterogeneous. Clustering drugs into small groups can simplify large pharmacology networks, these subgroups can also be used as a starting point for repositioning drugs. In this paper, we propose a two-tiered drug-centric unsupervised clustering approach for drug repositioning, integrating heterogeneous drug data profiles: drug-chemical, drug-disease, drug-gene, drug-protein and drug-side effect relationships.The proposed drug repositioning approach is threefold; (i) clustering drugs based on their homogeneous profiles using the Growing Self Organizing Map (GSOM); (ii) clustering drugs based on drug-drug relation matrices based on the previous step, considering three state-of-the-art graph clustering methods; and (iii) inferring drug repositioning candidates and assigning a confidence value for each identified candidate. In this paper, we compare our two-tiered clustering approach against two existing heterogeneous data integration approaches with reference to the Anatomical Therapeutic Chemical (ATC) classification, using GSOM. Our approach yields Normalized Mutual Information (NMI) and Standardized Mutual Information (SMI) of 0.66 and 36.11, respectively, while the two existing methods yield NMI of 0.60 and 0.64 and SMI of 22.26 and 33.59. Moreover, the two existing approaches failed to produce useful cluster separations when using graph clustering algorithms while our approach is able to identify useful clusters for drug repositioning. Furthermore, we provide clinical evidence for four predicted results (Chlorthalidone, Indomethacin, Metformin and Thioridazine) to support that our proposed approach can be reliably used to infer ATC code and drug repositioning.The proposed two-tiered unsupervised clustering approach is suitable for drug clustering and enables heterogeneous data integration. It also enables identifying reliable repositioning drug candidates with reference to ATC therapeutic classification. The repositioning drug candidates identified consistently by multiple clustering algorithms and with high confidence have a higher possibility of being effective repositioning candidates.
| S-EPMC5896044 | biostudies-other
Project description:Recent experimental advances in producing density maps from cryo-electron microscopy (cryo-EM) have challenged theorists to develop improved techniques to provide structural models that are consistent with the data and that preserve all the local stereochemistry associated with the biomolecule. We develop a new technique that maintains the local geometry and chemistry at each stage of the fitting procedure. A geometric simulation is used to drive the structure from some appropriate starting point (a nearby experimental structure or a modeled structure) toward the experimental density, via a set of small incremental motions. Structural motifs such as alpha-helices can be held rigid during the fitting procedure as the starting structure is brought into alignment with the experimental density. After validating this procedure on simulated data for adenylate kinase and lactoferrin, we show how cryo-EM data for two different GroEL structures can be fit using a starting x-ray crystal structure. We show that by incorporating the correct local stereochemistry in the modeling, structures can be obtained with effective resolution that is significantly higher than might be expected from the nominal cryo-EM resolution.
| S-EPMC2242741 | biostudies-literature