Graph Community Detection from Coarse Measurements: Recovery Conditions for the Coarsened Weighted Stochastic Block Model.
Ontology highlight
ABSTRACT:
SUBMITTER: Ghoroghchian N
PROVIDER: S-EPMC8275009 | biostudies-literature |
REPOSITORIES: biostudies-literature
Similar Datasets
Project description:The anatomical architecture of the mammalian brain can be modeled as the connectivity between functionally distinct areas of cortex and sub-cortex, which we refer to as the connectome. The community structure of the connectome describes how the network can be parsed into meaningful groups of nodes. This process, called community detection, is commonly carried out to find internally densely connected communities-a modular topology. However, other community structure patterns are possible. Here we employ the weighted stochastic block model (WSBM), which can identify a wide range of topologies, to the rat cerebral cortex connectome, to probe the network for evidence of modular, core, periphery, and disassortative organization. Despite its algorithmic flexibility, the WSBM identifies substantial modular and assortative topology throughout the rat cerebral cortex connectome, significantly aligning to the modular approach in some parts of the network. Significant deviations from modular partitions include the identification of communities that are highly enriched in core (rich club) areas. A comparison of the WSBM and modular models demonstrates that the former, when applied as a generative model, more closely captures several nodal network attributes. An analysis of variation across an ensemble of partitions reveals that certain parts of the network participate in multiple topological regimes. Overall, our findings demonstrate the potential benefits of adopting the WSBM, which can be applied to a single weighted and directed matrix such as the rat cerebral cortex connectome, to identify community structure with a broad definition that transcends the common modular approach.
| S-EPMC11220483 | biostudies-literature
Project description:The human brain can be described as a complex network of anatomical connections between distinct areas, referred to as the human connectome. Fundamental characteristics of connectome organization can be revealed using the tools of network science and graph theory. Of particular interest is the network's community structure, commonly identified by modularity maximization, where communities are conceptualized as densely intra-connected and sparsely inter-connected. Here we adopt a generative modeling approach called weighted stochastic block models (WSBM) that can describe a wider range of community structure topologies by explicitly considering patterned interactions between communities. We apply this method to the study of changes in the human connectome that occur across the life span (between 6-85 years old). We find that WSBM communities exhibit greater hemispheric symmetry and are spatially less compact than those derived from modularity maximization. We identify several network blocks that exhibit significant linear and non-linear changes across age, with the most significant changes involving subregions of prefrontal cortex. Overall, we show that the WSBM generative modeling approach can be an effective tool for describing types of community structure in brain networks that go beyond modularity.
| S-EPMC6115421 | biostudies-literature
Project description:The stochastic block model is able to generate random graphs with different types of network partitions, ranging from the traditional assortative structures to the disassortative structures. Since the stochastic block model does not specify which mixing pattern is desired, the inference algorithms discover the locally most likely nodes' partition, regardless of its type. Here we introduce a new model constraining nodes' internal degree ratios in the objective function to guide the inference algorithms to converge to the desired type of structure in the observed network data. We show experimentally that given the regularized model, the inference algorithms, such as Markov chain Monte Carlo, reliably and quickly find the assortative or disassortative structure as directed by the value of a single parameter. In contrast, when the sought-after assortative community structure is not strong in the observed network, the traditional inference algorithms using the degree-corrected stochastic block model tend to converge to undesired disassortative partitions.
| S-EPMC6744415 | biostudies-literature
Project description:The selection of coarse-grained (CG) mapping operators is a critical step for CG molecular dynamics (MD) simulation. It is still an open question about what is optimal for this choice and there is a need for theory. The current state-of-the art method is mapping operators manually selected by experts. In this work, we demonstrate an automated approach by viewing this problem as supervised learning where we seek to reproduce the mapping operators produced by experts. We present a graph neural network based CG mapping predictor called Deep Supervised Graph Partitioning Model (DSGPM) that treats mapping operators as a graph segmentation problem. DSGPM is trained on a novel dataset, Human-annotated Mappings (HAM), consisting of 1180 molecules with expert annotated mapping operators. HAM can be used to facilitate further research in this area. Our model uses a novel metric learning objective to produce high-quality atomic features that are used in spectral clustering. The results show that the DSGPM outperforms state-of-the-art methods in the field of graph segmentation. Finally, we find that predicted CG mapping operators indeed result in good CG MD models when used in simulation.
| S-EPMC8161155 | biostudies-literature
Project description:We propose a universal approach for analysis and fast simulations of stiff stochastic biochemical networks, which rests on elimination of fast chemical species without a loss of information about mesoscopic, non-Poissonian fluctuations of the slow ones. Our approach is similar to the Born-Oppenheimer approximation in quantum mechanics and follows from the stochastic path integral representation of the cumulant generating function of reaction events. In applications with a small number of chemical reactions, it produces analytical expressions for cumulants of chemical fluxes between the slow variables. This allows for a low-dimensional, interpretable representation and can be used for high-accuracy, low-complexity coarse-grained numerical simulations. As an example, we derive the coarse-grained description for a chain of biochemical reactions and show that the coarse-grained and the microscopic simulations agree, but the former is 3 orders of magnitude faster.
| S-EPMC2705573 | biostudies-literature
Project description:pH dependence abounds in biochemical systems; however, many simulation methods used to investigate these systems do not consider this property. Using a modified version of the hybrid non-equilibrium molecular dynamics (MD)/Monte Carlo algorithm, we include a stochastic charge neutralization method, which is particularly suited to the MARTINI force field and enables artifact-free Ewald summation methods in electrostatic calculations. We demonstrate the efficacy of this method by reproducing pH-dependent self-assembly and self-organization behavior previously reported in experimental literature. In addition, we have carried out experimental oleic acid titrations where we report the results in a more relevant way for the comparison with computational methods than has previously been done.
| S-EPMC9109222 | biostudies-literature
Project description:The human leukocyte antigen system (HLA) contains many highly variable genes. HLA genes play an important role in the human immune system, and HLA gene matching is crucial for the success of human organ transplantations. Numerous studies have demonstrated that variation in HLA genes is associated with many autoimmune, inflammatory and infectious diseases. However, typing HLA genes by serology or PCR is time consuming and expensive, which limits large-scale studies involving HLA genes. Since it is much easier and cheaper to obtain single nucleotide polymorphism (SNP) genotype data, accurate computational algorithms to infer HLA gene types from SNP genotype data are in need. To infer HLA types from SNP genotypes, the first step is to infer SNP haplotypes from genotypes. However, for the same SNP genotype data set, the haplotype configurations inferred by different methods are usually inconsistent, and it is often difficult to decide which one is true.In this paper, we design an accurate HLA gene type inference algorithm by utilizing SNP genotype data from pedigrees, known HLA gene types of some individuals and the relationship between inferred SNP haplotypes and HLA gene types. Given a set of haplotypes inferred from the genotypes of a population consisting of many pedigrees, the algorithm first constructs a weighted similarity graph based on a new haplotype similarity measure and derives constraint edges from known HLA gene types. Based on the principle that different HLA gene alleles should have different background haplotypes, the algorithm searches for an optimal labeling of all the haplotypes with unknown HLA gene types such that the total weight among the same HLA gene types is maximized. To deal with ambiguous haplotype solutions, we use a genetic algorithm to select haplotype configurations that tend to maximize the same optimization criterion. Our experiments on a previously typed subset of the HapMap data show that the algorithm is highly accurate, achieving an accuracy of 96% for gene HLA-A, 95% for HLA-B, 97% for HLA-C, 84% for HLA-DRB1, 98% for HLA-DQA1 and 97% for HLA-DQB1 in a leave-one-out test.Our algorithm can infer HLA gene types from neighboring SNP genotype data accurately. Compared with a recent approach on the same input data, our algorithm achieved a higher accuracy. The code of our algorithm is available to the public for free upon request to the corresponding authors.
| S-EPMC3024871 | biostudies-other
Project description:MotivationThe increasing availability of complete genomes demands for models to study genomic variability within entire populations. Pangenome graphs capture the full genomic similarity and diversity between multiple genomes. In order to understand them, we need to see them. For visualization, we need a human readable graph layout: A graph embedding in low (e.g. two) dimensional depictions. Due to a pangenome graph's potential excessive size, this is a significant challenge.ResultsIn response, we introduce a novel graph layout algorithm: the Path-Guided Stochastic Gradient Descent (PG-SGD). PG-SGD uses the genomes, represented in the pangenome graph as paths, as an embedded positional system to sample genomic distances between pairs of nodes. This avoids the quadratic cost seen in previous versions of graph drawing by Stochastic Gradient Descent (SGD). We show that our implementation efficiently computes the low dimensional layouts of gigabase-scale pangenome graphs, unveiling their biological features.AvailabilityWe integrated PG-SGD in ODGI which is released as free software under the MIT open source license. Source code is available at https://github.com/pangenome/odgi.
| S-EPMC10542513 | biostudies-literature
Project description:Oscillations in dynamical systems are widely reported in multiple branches of applied mathematics. Critically, even a non-oscillatory deterministic system can produce cyclic trajectories when it is in a low copy number, stochastic regime. Common methods of finding parameter ranges for stochastically driven resonances, such as direct calculation, are cumbersome for any but the smallest networks. In this paper, we provide a systematic framework to efficiently determine the number of resonant modes and parameter ranges for stochastic oscillations relying on real root counting algorithms and graph theoretic methods. We argue that stochastic resonance is a network property by showing that resonant modes only depend on the squared Jacobian matrix J2, unlike deterministic oscillations which are determined by J By using graph theoretic tools, analysis of stochastic behaviour for larger interaction networks is simplified and stochastic dynamical systems with multiple resonant modes can be identified easily.
| S-EPMC5746565 | biostudies-literature
Project description:Long non-coding RNAs (lncRNAs) are widely concerned because of their close associations with many key biological activities. Though precise functions of most lncRNAs are unknown, research works show that lncRNAs usually exert biological function by interacting with the corresponding proteins. The experimental validation of interactions between lncRNAs and proteins is costly and time-consuming. In this study, we developed a weighted graph-regularized matrix factorization (LPI-WGRMF) method to find unobserved lncRNA-protein interactions (LPIs) based on lncRNA similarity matrix, protein similarity matrix, and known LPIs. We compared our proposed LPI-WGRMF method with five classical LPI prediction methods, that is, LPBNI, LPI-IBNRA, LPIHN, RWR, and collaborative filtering (CF). The results demonstrate that the LPI-WGRMF method can produce high-accuracy performance, obtaining an AUC score of 0.9012 and AUPR of 0.7324. The case study showed that SFPQ, SNHG3, and PRPF31 may associate with Q9NUL5, Q9NUL5, and Q9UKV8 with the highest linking probabilities and need to further experimental validation.
| S-EPMC8322775 | biostudies-literature