Browse
Submit Data
Databases
API
Help

Dataset Information

0 Views

0 Connections

0 Citations

0 Reanalyses

0 Downloads

Omics score: 0

Renyi entropy driven hierarchical graph clustering.

ABSTRACT: This article explores a graph clustering method that is derived from an information theoretic method that clusters points in Rn relying on Renyi entropy, which involves computing the usual Euclidean distance between these points. Two view points are adopted: (1) the graph to be clustered is first embedded into Rd for some dimension d so as to minimize the distortion of the embedding, then the resulting points are clustered, and (2) the graph is clustered directly, using as distance the shortest path distance for undirected graphs, and a variation of the Jaccard distance for directed graphs. In both cases, a hierarchical approach is adopted, where both the initial clustering and the agglomeration steps are computed using Renyi entropy derived evaluation functions. Numerical examples are provided to support the study, showing the consistency of both approaches (evaluated in terms of F-scores).

SUBMITTER: Oggier F

PROVIDER: S-EPMC7959621 | biostudies-literature | 2021

REPOSITORIES: biostudies-literature

ACCESS DATA

Json Xml

Publications

Renyi entropy driven hierarchical graph clustering.

Oggier Frédérique F Datta Anwitaman A

PeerJ. Computer science 20210225

This article explores a graph clustering method that is derived from an information theoretic method that clusters points in R n relying on Renyi entropy, which involves computing the usual Euclidean distance between these points. Two view points are adopted: (1) the graph to be clustered is first embedded into R d for some dimension <i>d</i> so as to minimize the distortion of the embedding, then the resulting points are clustered, and (2) the graph is clustered directly, using as distance ...[more]

PMID: 33817016

Similar Datasets

Analysis and tuning of hierarchical topic models based on Renyi entropy approach.

Project description:Hierarchical topic modeling is a potentially powerful instrument for determining topical structures of text collections that additionally allows constructing a hierarchy representing the levels of topic abstractness. However, parameter optimization in hierarchical models, which includes finding an appropriate number of topics at each level of hierarchy, remains a challenging task. In this paper, we propose an approach based on Renyi entropy as a partial solution to the above problem. First, we introduce a Renyi entropy-based metric of quality for hierarchical models. Second, we propose a practical approach to obtaining the "correct" number of topics in hierarchical topic models and show how model hyperparameters should be tuned for that purpose. We test this approach on the datasets with the known number of topics, as determined by the human mark-up, three of these datasets being in the English language and one in Russian. In the numerical experiments, we consider three different hierarchical models: hierarchical latent Dirichlet allocation model (hLDA), hierarchical Pachinko allocation model (hPAM), and hierarchical additive regularization of topic models (hARTM). We demonstrate that the hLDA model possesses a significant level of instability and, moreover, the derived numbers of topics are far from the true numbers for the labeled datasets. For the hPAM model, the Renyi entropy approach allows determining only one level of the data structure. For hARTM model, the proposed approach allows us to estimate the number of topics for two levels of hierarchy.

| S-EPMC8330431 | biostudies-literature

Dynamic networks from hierarchical bayesian graph clustering.

Project description:Biological networks change dynamically as protein components are synthesized and degraded. Understanding the time-dependence and, in a multicellular organism, tissue-dependence of a network leads to insight beyond a view that collapses time-varying interactions into a single static map. Conventional algorithms are limited to analyzing evolving networks by reducing them to a series of unrelated snapshots.Here we introduce an approach that groups proteins according to shared interaction patterns through a dynamical hierarchical stochastic block model. Protein membership in a block is permitted to evolve as interaction patterns shift over time and space, representing the spatial organization of cell types in a multicellular organism. The spatiotemporal evolution of the protein components are inferred from transcript profiles, using Arabidopsis root development (5 tissues, 3 temporal stages) as an example.The new model requires essentially no parameter tuning, out-performs existing snapshot-based methods, identifies protein modules recruited to specific cell types and developmental stages, and could have broad application to social networks and other similar dynamic systems.

| S-EPMC2799515 | biostudies-literature

Entropy-Based Graph Clustering of PPI Networks for Predicting Overlapping Functional Modules of Proteins.

Project description:Functional modules can be predicted using genome-wide protein-protein interactions (PPIs) from a systematic perspective. Various graph clustering algorithms have been applied to PPI networks for this task. In particular, the detection of overlapping clusters is necessary because a protein is involved in multiple functions under different conditions. graph entropy (GE) is a novel metric to assess the quality of clusters in a large, complex network. In this study, the unweighted and weighted GE algorithm is evaluated to prove the validity of predicting function modules. To measure clustering accuracy, the clustering results are compared to protein complexes and Gene Ontology (GO) annotations as references. We demonstrate that the GE algorithm is more accurate in overlapping clusters than the other competitive methods. Moreover, we confirm the biological feasibility of the proteins that occur most frequently in the set of identified clusters. Finally, novel proteins for the additional annotation of GO terms are revealed.

| S-EPMC8534328 | biostudies-literature

Discrimination of emotional states from scalp- and intracranial EEG using multiscale Renyi entropy.

Project description:A data-adaptive, multiscale version of Rényi's quadratic entropy (RQE) is introduced for emotional state discrimination from EEG recordings. The algorithm is applied to scalp EEG recordings of 30 participants watching 4 emotionally-charged video clips taken from a validated public database. Krippendorff's inter-rater statistic reveals that multiscale RQE of the mid-frontal scalp electrodes best discriminates between five emotional states. Multiscale RQE is also applied to joint scalp EEG, amygdala- and occipital pole intracranial recordings of an implanted patient watching a neutral and an emotionally charged video clip. Unlike for the neutral video clip, the RQEs of the mid-frontal scalp electrodes and the amygdala-implanted electrodes are observed to coincide in the time range where the crux of the emotionally-charged video clip is revealed. In addition, also during this time range, phase synchrony between the amygdala and mid-frontal recordings is maximal, as well as our 30 participants' inter-rater agreement on the same video clip. A source reconstruction exercise using intracranial recordings supports our assertion that amygdala could contribute to mid-frontal scalp EEG. On the contrary, no such contribution was observed for the occipital pole's intracranial recordings. Our results suggest that emotional states discriminated from mid-frontal scalp EEG are likely to be mirrored by differences in amygdala activations in particular when recorded in response to emotionally-charged scenes.

| S-EPMC5669426 | biostudies-literature

Hierarchical clustering of PDAC cell lines

Project description:Hierarchical clustering of pancreatic cancer cell lines based on differentially regulated genes between mesenchymal and epithelial PDAC cells derived from primary tumours and metastases from KrasG12D-driven mouse models of pancreatic cancer.

2022-11-19 | E-MTAB-8173 | biostudies-arrayexpress

Adjusting protein graphs based on graph entropy.

Project description:Measuring protein structural similarity attempts to establish a relationship of equivalence between polymer structures based on their conformations. In several recent studies, researchers have explored protein-graph remodeling, instead of looking a minimum superimposition for pairwise proteins. When graphs are used to represent structured objects, the problem of measuring object similarity become one of computing the similarity between graphs. Graph theory provides an alternative perspective as well as efficiency. Once a protein graph has been created, its structural stability must be verified. Therefore, a criterion is needed to determine if a protein graph can be used for structural comparison. In this paper, we propose a measurement for protein graph remodeling based on graph entropy. We extend the concept of graph entropy to determine whether a graph is suitable for representing a protein. The experimental results suggest that when applied, graph entropy helps a conformational on protein graph modeling. Furthermore, it indirectly contributes to protein structural comparison if a protein graph is solid.

| S-EPMC4271566 | biostudies-literature

Hierarchical Graph Representation of Pharmacophore Models.

Project description:For the investigation of protein-ligand interaction patterns, the current accessibility of a wide variety of sampling methods allows quick access to large-scale data. The main example is the intensive use of molecular dynamics simulations applied to crystallographic structures which provide dynamic information on the binding interactions in protein-ligand complexes. Chemical feature interaction based pharmacophore models extracted from these simulations, were recently used with consensus scoring approaches to identify potentially active molecules. While this approach is rapid and can be fully automated for virtual screening, additional relevant information from such simulations is still opaque and so far the full potential has not been entirely exploited. To address these aspects, we developed the hierarchical graph representation of pharmacophore models (HGPM). This single graph representation enables an intuitive observation of numerous pharmacophore models from long MD trajectories and further emphasizes their relationship and feature hierarchy. The resulting interactive depiction provides an easy-to-apprehend tool for the selection of sets of pharmacophores as well as visual support for analysis of pharmacophore feature composition and virtual screening results. Furthermore, the representation can be adapted to include information involving interactions between the same protein and multiple different ligands. Herein, we describe the generation, visualization and use of HGPMs generated from MD simulations of two x-ray crystallographic derived structures of the human glucokinase protein in complex with allosteric activators. The results demonstrate that a large number of pharmacophores and their relationships can be visualized in an interactive, efficient manner, unique binding modes identified and a combination of models derived from long MD simulations can be strategically prioritized for VS campaigns.

| S-EPMC7793842 | biostudies-literature

Non-supervised hierarchical clustering of gene expression data

Project description:Despite the frequent detection of circulating tumor antigen-specific T cells, either spontaneously or following active immunization or adoptive transfer, immune-mediated cancer regression occurs only in the minority of patients. One theoretical rate-limiting step is whether effector T cells successfully migrate into metastatic tumor sites. Affymetrix gene expression profiling performed on a series of metastatic melanoma biopsies revealed a major segregation of samples based on the presence or absence of T cell-associated transcripts. The presence of lymphocytes correlated with the expression of defined chemokine genes. A subset of 6 chemokines (CCL2, CCL3, CCL4, CCL5, CXCL9, and CXCL10) was confirmed by protein array and/or quantitative RT-PCR to be preferentially expressed in tumors that contained T cells. Corresponding chemokine receptors were found to be upregulated on human CD8+ effector T cells, and transwell migration assays confirmed the ability of each of these chemokines to promote migration of CD8+ effector cells in vitro. Screening by chemokine protein array identified a subset of melanoma cell lines produced a similar broad array of chemokines. These melanoma cells more effectively recruited human CD8+ effector T cells when implanted as xenografts in NOD/scid mice in vivo. Chemokine blockade with specific antibodies inhibited migration of CD8+ T cells. Our results suggest that lack of critical chemokines in a subset of melanoma metastases may limit the migration of activated T cells, which in turn could limit the effectiveness of anti-tumor immunity. Keywords: Tumor sample microarray

2008-08-30 | GSE12627 | GEO

Communication-Optimal Distributed Dynamic Graph Clustering.

Project description:We consider the problem of clustering graph nodes over large-scale dynamic graphs, such as citation networks, images and web networks, when graph updates such as node/edge insertions/deletions are observed distributively. We propose communication-efficient algorithms for two well-established communication models namely the message passing and the blackboard models. Given a graph with n nodes that is observed at s remote sites over time [1, t], the two proposed algorithms have communication costs Õ(ns) and Õ(n + s) (Õ hides a polylogarithmic factor), almost matching their lower bounds, Ω(ns) and Ω (n + s), respectively, in the message passing and the blackboard models. More importantly, we prove that at each time point in [1, t] our algorithms generate clustering quality nearly as good as that of centralizing all updates up to that time and then applying a standard centralized clustering algorithm. We conducted extensive experiments on both synthetic and real-life datasets which confirmed the communication efficiency of our approach over baseline algorithms while achieving comparable clustering results.

| S-EPMC9275443 | biostudies-literature

Divisive hierarchical maximum likelihood clustering.

Project description:BACKGROUND:Biological data comprises various topologies or a mixture of forms, which makes its analysis extremely complicated. With this data increasing in a daily basis, the design and development of efficient and accurate statistical methods has become absolutely necessary. Specific analyses, such as those related to genome-wide association studies and multi-omics information, are often aimed at clustering sub-conditions of cancers and other diseases. Hierarchical clustering methods, which can be categorized into agglomerative and divisive, have been widely used in such situations. However, unlike agglomerative methods divisive clustering approaches have consistently proved to be computationally expensive. RESULTS:The proposed clustering algorithm (DRAGON) was verified on mutation and microarray data, and was gauged against standard clustering methods in the literature. Its validation included synthetic and significant biological data. When validated on mixed-lineage leukemia data, DRAGON achieved the highest clustering accuracy with data of four different dimensions. Consequently, DRAGON outperformed previous methods with 3-,4- and 5-dimensional acute leukemia data. When tested on mutation data, DRAGON achieved the best performance with 2-dimensional information. CONCLUSIONS:This work proposes a computationally efficient divisive hierarchical clustering method, which can compete equally with agglomerative approaches. The proposed method turned out to correctly cluster data with distinct topologies. A MATLAB implementation can be extraced from http://www.riken.jp/en/research/labs/ims/med_sci_math/ or http://www.alok-ai-lab.com.

| S-EPMC5751574 | biostudies-literature

OmicsDI is part of the ELIXIR infrastructure

OmicsDI is an Elixir interoperability service. Learn more ›

Tweets

OmicsDI Databases

PRIDE
PeptideAtlas
MassIVE
JPOST Repository
Physiome Model Repository

EGA
EVA
ENA
LINCS
PAXDB
Cell Collective

MetaboLights
Metabolomics Workbench
MetabolomeExpress
GNPS
BioModels
FAIRDOMHub

ArrayExpress
dbGaP
ExpressionAtlas
GEO
NODE

Information

Databases
Help
API
Contact us
Code on GitHub
Terms of use
Submit Data