Introducing a graph topology for robust cooperation.
Ontology highlight
ABSTRACT:
SUBMITTER: Locodi AM
PROVIDER: S-EPMC8097208 | biostudies-literature |
REPOSITORIES: biostudies-literature
Similar Datasets
Project description:MotivationSince the amount of published biological sequencing data is growing exponentially, efficient methods for storing and indexing this data are more needed than ever to truly benefit from this invaluable resource for biomedical research. Labeled de Bruijn graphs are a frequently-used approach for representing large sets of sequencing data. While significant progress has been made to succinctly represent the graph itself, efficient methods for storing labels on such graphs are still rapidly evolving.ResultsIn this article, we present RowDiff, a new technique for compacting graph labels by leveraging expected similarities in annotations of vertices adjacent in the graph. RowDiff can be constructed in linear time relative to the number of vertices and labels in the graph, and in space proportional to the graph size. In addition, construction can be efficiently parallelized and distributed, making the technique applicable to graphs with trillions of nodes. RowDiff can be viewed as an intermediary sparsification step of the original annotation matrix and can thus naturally be combined with existing generic schemes for compressed binary matrices. Experiments on 10 000 RNA-seq datasets show that RowDiff combined with multi-BRWT results in a 30% reduction in annotation footprint over Mantis-MST, the previously known most compact annotation representation. Experiments on the sparser Fungi subset of the RefSeq collection show that applying RowDiff sparsification reduces the size of individual annotation columns stored as compressed bit vectors by an average factor of 42. When combining RowDiff with a multi-BRWT representation, the resulting annotation is 26 times smaller than Mantis-MST.Availability and implementationRowDiff is implemented in C++ within the MetaGraph framework. The source code and the data used in the experiments are publicly available at https://github.com/ratschlab/row_diff.
| S-EPMC8346655 | biostudies-literature
Project description:Graph embedding methods are useful for a wide range of graph analysis tasks including link prediction and node classification. Most graph embedding methods learn only the topological structure of graphs. Nevertheless, it has been shown that the incorporation of node attributes is beneficial in improving the expressive power of node embeddings. However, real-world graphs are often noisy in terms of structure and/or attributes (missing and/or erroneous edges/attributes). Most existing graph embedding methods are susceptible to this noise, as they do not consider uncertainty during the modelling process. In this paper, we introduce RASE, a Robust Attribute and Structure preserving graph Embedding model. RASE is a novel graph representation learning model which effectively preserves both graph structure and node attributes through a unified loss function. To be robust, RASE uses a denoising attribute auto-encoder to deal with node attribute noise, and models uncertainty in the embedding space as Gaussians to cope with graph structure noise. We evaluate the performance of RASE through an extensive experimental study on various real-world datasets. Results demonstrate that RASE outperforms state-of-the-art embedding methods on multiple graph analysis tasks and is robust to both structure and attribute noise.
| S-EPMC7206273 | biostudies-literature
Project description:A gene regulatory network can be described at a high level by a directed graph with signed edges, and at a more detailed level by a system of ordinary differential equations (ODEs). The former qualitatively models the causal regulatory interactions between ordered pairs of genes, while the latter quantitatively models the time-varying concentrations of mRNA and proteins. This paper clarifies the connection between the two types of models. We propose a property, called the constant sign property, for a general class of ODE models. The constant sign property characterizes the set of conditions (system parameters, external signals, or internal states) under which an ODE model is consistent with a signed, directed graph. If the constant sign property for an ODE model holds globally for all conditions, then the ODE model has a single signed, directed graph. If the constant sign property for an ODE model only holds locally, which may be more typical, then the ODE model corresponds to different graphs under different sets of conditions. In addition, two versions of constant sign property are given and a relationship between them is proved. As an example, the ODE models that capture the effect of cis-regulatory elements involving protein complex binding, based on the model in the GeneNetWeaver source code, are described in detail and shown to satisfy the global constant sign property with a unique consistent gene regulatory graph. Even a single gene regulatory graph is shown to have many ODE models of GeneNetWeaver type consistent with it due to combinatorial complexity and continuous parameters. Finally the question of how closely data generated by one ODE model can be fit by another ODE model is explored. It is observed that the fit is better if the two models come from the same graph.
| S-EPMC7326199 | biostudies-literature
Project description:Neuroimaging studies of functional connectivity using graph theory have furthered our understanding of the network structure in temporal lobe epilepsy (TLE). Brain network effects of anti-epileptic drugs could influence such studies, but have not been systematically studied. Resting-state functional MRI was analyzed in 25 patients with TLE using graph theory analysis. Patients were divided into two groups based on anti-epileptic medication use: those taking carbamazepine/oxcarbazepine (CBZ/OXC) (n=9) and those not taking CBZ/OXC (n=16) as a part of their medication regimen. The following graph topology metrics were analyzed: global efficiency, betweenness centrality (BC), clustering coefficient, and small-world index. Multiple linear regression was used to examine the association of CBZ/OXC with graph topology. The two groups did not differ from each other based on epilepsy characteristics. Use of CBZ/OXC was associated with a lower BC. Longer epilepsy duration was also associated with a lower BC. These findings can inform graph theory-based studies in patients with TLE. The changes observed are discussed in relation to the anti-epileptic mechanism of action and adverse effects of CBZ/OXC.
| S-EPMC4490704 | biostudies-literature
Project description:BackgroundBreast cancer is currently one of the cancers with a higher mortality rate in the world. The biological research on anti-breast cancer drugs focuses on the activity of estrogen receptors alpha (ER[Formula: see text]), the pharmacokinetic properties and the safety of the compounds, which, however, is an expensive and time-consuming process. Developments of deep learning bring potential to efficiently facilitate the candidate drug selection against breast cancer.MethodsIn this paper, we propose an Anti-Breast Cancer Drug selection method utilizing Gated Graph Neural Networks (ABCD-GGNN) to topologically enhance the molecular representation of candidate drugs. By constructing atom-level graphs through atomic descriptors for each distinct compound, ABCD-GGNN can topologically learn both the implicit structure and substructure characteristics of a candidate drug and then integrate the representation with explicit discrete molecular descriptors to generate a molecule-level representation. As a result, the representation of ABCD-GGNN can inductively predict the ER[Formula: see text], the pharmacokinetic properties and the safety of each candidate drug. Finally, we design a ranking operator whose inputs are the predicted properties so as to statistically select the appropriate drugs against breast cancer.ResultsExtensive experiments conducted on our collected anti-breast cancer candidate drug dataset demonstrate that our proposed method outperform all the other representative methods in the tasks of predicting ER[Formula: see text], and the pharmacokinetic properties and safety of the compounds. Extended result analysis demonstrates the efficiency and biological rationality of the operator we design to calculate the candidate drug ranking from the predicted properties.ConclusionIn this paper, we propose the ABCD-GGNN representation method to efficiently integrate the topological structure and substructure features of the molecules with the discrete molecular descriptors. With a ranking operator applied, the predicted properties efficiently facilitate the candidate drug selection against breast cancer.
| S-EPMC9484163 | biostudies-literature
Project description:Artifacts in biomedical signal recordings, such as gene expression, sonar image and electroencephalogram, have a great influence on the related research because the artifacts with large value usually break the neighbor structure in the datasets. However, the conventional graph embedding (GE) used for dimension reduction such as linear discriminant analysis, principle component analysis and locality preserving projections is essentially defined in the L2 norm space and is prone to the presence of artifacts, resulting in biased sub-structural features. In this work, we defined graph embedding in the L1 norm space and used the maximization strategy to solve this model with the aim of restricting the influence of outliers on the dimension reduction of signals. The quantitative evaluation with different outlier conditions demonstrates that an L1 norm-based GE structure can estimate hyperplanes, which are more stable than those of conventional GE-based methods. The applications to a variety of datasets also show that the proposed L1 GE is more robust to outlier influence with higher classification accuracy estimated. The proposed L1 GE may be helpful for capturing reliable mapping information from the datasets that have been contaminated with outliers.
| S-EPMC5844917 | biostudies-literature
Project description:Early and accurate diagnoses of cancer can significantly improve the design of personalized therapy and enhance the success of therapeutic interventions. Histopathological approaches, which rely on microscopic examinations of malignant tissue, are not conducive to timely diagnoses. High throughput genomics offers a possible new classification of cancer subtypes. Unfortunately, most clustering algorithms have not been proven sufficiently robust. We propose a novel approach that relies on the use of statistical invariants and persistent homology, one of the most exciting recent developments in topology. It identifies a sufficient but compact set of genes for the analysis as well as a core group of tightly correlated patient samples for each subtype. Partitioning occurs hierarchically and allows for the identification of genetically similar subtypes. We analyzed the gene expression profiles of 202 tumors of the brain cancer glioblastoma multiforme (GBM) given at the Cancer Genome Atlas (TCGA) site. We identify core patient groups associated with the classical, mesenchymal, and proneural subtypes of GBM. In our analysis, the neural subtype consists of several small groups rather than a single component. A subtype prediction model is introduced which partitions tumors in a manner consistent with clustering algorithms but requires the genetic signature of only 59 genes.
| S-EPMC4393071 | biostudies-literature
Project description:In this Letter we investigate a direct relationship between a graph's topology and the free energy of a spin system on the graph. We develop a method of separating topological and energetic contributions to the free energy, and find that considering the topology is sufficient to qualitatively compare the free energies of different graph systems at high temperature, even when the energetics are not fully known. This method was applied to the metal lattice system with defects, and we found that it partially explains why point defects are more stable than high-dimensional defects. Given the energetics, we can even quantitatively compare free energies of different graph structures via a closed form of linear graph contributions. The closed form is applied to predict the sequence-space free energy of lattice proteins, which is a key factor determining the designability of a protein structure.
| S-EPMC5668130 | biostudies-literature
Project description:It has been shown that natural selection favors cooperation in a homogenous graph if the benefit-to-cost ratio exceeds the degree of the graph. However, most graphs related to interactions in real populations are heterogeneous, in which some individuals have many more neighbors than others. In this paper, we introduce a new state variable to measure the time evolution of cooperation in a heterogeneous graph. Based on the diffusion approximation, we find that the fixation probability of a single cooperator depends crucially on the number of its neighbors. Under weak selection, a cooperator with more neighbors has a larger probability of fixation in the population. We then investigate the average fixation probability of a randomly chosen cooperator. If a cooperator pays a cost for each of its neighbors (the so called fixed cost per game case), natural selection favors cooperation if the benefit-to-cost ratio is larger than the average degree. In contrast, if a cooperator pays a fixed cost and all its neighbors share the benefit (the fixed cost per individual case), cooperation is favored if the benefit-to-cost ratio is larger than the harmonic mean of the degree distribution. Moreover, increasing the graph heterogeneity will reduce the effect of natural selection.
| S-EPMC3688584 | biostudies-literature
Project description:Bacteria commonly form dense biofilms encased in extracellular polymeric substances (EPS). Biofilms are often extremely tolerant to antimicrobials but their reliance on shared EPS may also be a weakness as social evolution theory predicts that inhibiting shared traits can select against resistance. Here we show that EPS of Salmonella biofilms is a cooperative trait whose benefit is shared among cells, and that EPS inhibition reduces both cell attachment and antimicrobial tolerance. We then compare an EPS inhibitor to conventional antimicrobials in an evolutionary experiment. While resistance against conventional antimicrobials rapidly evolves, we see no evolution of resistance to EPS inhibition. We further show that a resistant strain is outcompeted by a susceptible strain under EPS inhibitor treatment, explaining why resistance does not evolve. Our work suggests that targeting cooperative traits is a viable solution to the problem of antimicrobial resistance.
| S-EPMC6952394 | biostudies-literature