Multiscale Graph Grammars Can Generate Cayley Graphs of Groups and Monoids
Ontology highlight
ABSTRACT:
SUBMITTER: Gadducci F
PROVIDER: S-EPMC7314706 | biostudies-literature | 2020 May
REPOSITORIES: biostudies-literature
Similar Datasets
Project description:BACKGROUND AND AIMS: Functional-structural plant models (FSPMs) simulate biological processes at different spatial scales. Methods exist for multiscale data representation and modification, but the advantages of using multiple scales in the dynamic aspects of FSPMs remain unclear. Results from multiscale models in various other areas of science that share fundamental modelling issues with FSPMs suggest that potential advantages do exist, and this study therefore aims to introduce an approach to multiscale modelling in FSPMs. METHODS: A three-part graph data structure and grammar is revisited, and presented with a conceptual framework for multiscale modelling. The framework is used for identifying roles, categorizing and describing scale-to-scale interactions, thus allowing alternative approaches to model development as opposed to correlation-based modelling at a single scale. Reverse information flow (from macro- to micro-scale) is catered for in the framework. The methods are implemented within the programming language XL. KEY RESULTS: Three example models are implemented using the proposed multiscale graph model and framework. The first illustrates the fundamental usage of the graph data structure and grammar, the second uses probabilistic modelling for organs at the fine scale in order to derive crown growth, and the third combines multiscale plant topology with ozone trends and metabolic network simulations in order to model juvenile beech stands under exposure to a toxic trace gas. CONCLUSIONS: The graph data structure supports data representation and grammar operations at multiple scales. The results demonstrate that multiscale modelling is a viable method in FSPM and an alternative to correlation-based modelling. Advantages and disadvantages of multiscale modelling are illustrated by comparisons with single-scale implementations, leading to motivations for further research in sensitivity analysis and run-time efficiency for these models.
| S-EPMC4156127 | biostudies-other
Project description:A new approach, graph-grammars, to encode RNA tertiary structure patterns is introduced and exemplified with the classical sarcin-ricin motif. The sarcin-ricin motif is found in the stem of the crucial ribosomal loop E (also referred to as the sarcin-ricin loop), which is sensitive to the alpha-sarcin and ricin toxins. Here, we generate a graph-grammar for the sarcin-ricin motif and apply it to derive putative sequences that would fold in this motif. The biological relevance of the derived sequences is confirmed by a comparison with those found in known sarcin-ricin sites in an alignment of over 800 bacterial 23S ribosomal RNAs. The comparison raised alternative alignments in few sarcin-ricin sites, which were assessed using tertiary structure predictions and 3D modeling. The sarcin-ricin motif graph-grammar was built with indivisible nucleotide interaction cycles that were recently observed in structured RNAs. A comparison of the sequences and 3D structures of each cycle that constitute the sarcin-ricin motif gave us additional insights about RNA sequence-structure relationships. In particular, this analysis revealed the sequence space of an RNA motif depends on a structural context that goes beyond the single base pairing and base-stacking interactions.
| S-EPMC1865062 | biostudies-literature
Project description:The parsing problem is one of the key problems of graph grammars. The typical parsing algorithm uses the bottom-up method. The time-complexity of this method is high, and it is difficult to apply. In order to reduce the time-complexity, this paper uses the top-down method for parsing. This method avoids the subgraph isomorphism judgment and selects the productions specifically, so that the time-complexity is greatly reduced.
| S-EPMC4664237 | biostudies-literature
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
Project description:Genome graphs allow very general representations of genetic variation; depending on the model and implementation, variation at different length-scales (single nucleotide polymorphisms (SNPs), structural variants) and on different sequence backgrounds can be incorporated with different levels of transparency. We implement a model which handles this multiscale variation and develop a JSON extension of VCF (jVCF) allowing for variant calls on multiple references, both implemented in our software gramtools. We find gramtools outperforms existing methods for genotyping SNPs overlapping large deletions in M. tuberculosis and is able to genotype on multiple alternate backgrounds in P. falciparum, revealing previously hidden recombination.
| S-EPMC8420074 | biostudies-literature
Project description:Lignin is an aromatic biopolymer found in ubiquitous sources of woody biomass. Designing and optimizing lignin valorization processes requires a fundamental understanding of lignin structures. Experimental characterization techniques, such as 2D-heteronuclear single quantum coherence (HSQC) nuclear magnetic resonance (NMR) spectra, could elucidate the global properties of the polymer molecules. Computer models could extend the resolution of experiments by representing structures at the molecular and atomistic scales. We introduce a graph-based multiscale modeling framework for lignin structure generation and visualization. The framework employs accelerated rejection-free polymerization and hierarchical Metropolis Monte Carlo optimization algorithms. We obtain structure libraries for various lignin feedstocks based on literature and new experimental NMR data for poplar wood, pinewood, and herbaceous lignin. The framework could guide researchers towards feasible lignin structures, efficient space exploration, and future kinetics modeling. Its software implementation in Python, LigninGraphs, is open-source and available on GitHub.
| S-EPMC9261032 | biostudies-literature
Project description:Trillions of chemical reactions occur in the human body every second, where the generated products are not only consumed locally but also transported to various locations in a systematic manner to sustain homeostasis. Current solutions to model these biological phenomena are restricted in computability and scalability due to the use of continuum approaches in which it is practically impossible to encapsulate the complexity of the physiological processes occurring at diverse scales. Here, we present a discrete modeling framework defined on an interacting graph that offers the flexibility to model multiscale systems by translating the physical space into a metamodel. We discretize the graph-based metamodel into functional units composed of well-mixed volumes with vascular and cellular subdomains; the operators defined over these volumes define the transport dynamics. We predict glucose drift governed by advective-dispersive transport in the vascular subdomains of an islet vasculature and cross-validate the flow and concentration fields with finite-element-based COMSOL simulations. Vascular and cellular subdomains are coupled to model the nutrient exchange occurring in response to the gradient arising out of reaction and perfusion dynamics. The application of our framework for modeling biologically relevant test systems shows how our approach can assimilate both multi-omics data from in vitro-in vivo studies and vascular topology from imaging studies for examining the structure-function relationship of complex vasculatures. The framework can advance simulation of whole-body networks at user-defined levels and is expected to find major use in personalized medicine and drug discovery.
| S-EPMC10013063 | biostudies-literature
Project description:Traditional classification tasks learn to assign samples to given classes based solely on sample features. This paradigm is evolving to include other sources of information, such as known relations between samples. Here, we show that, even if additional relational information is not available in the dataset, one can improve classification by constructing geometric graphs from the features themselves, and using them within a Graph Convolutional Network. The improvement in classification accuracy is maximized by graphs that capture sample similarity with relatively low edge density. We show that such feature-derived graphs increase the alignment of the data to the ground truth while improving class separation. We also demonstrate that the graphs can be made more efficient using spectral sparsification, which reduces the number of edges while still improving classification performance. We illustrate our findings using synthetic and real-world datasets from various scientific domains.
| S-EPMC8085612 | biostudies-literature
Project description:Undergraduate biology education reform aims to engage students in scientific practices such as experimental design, experimentation, and data analysis and communication. Graphs are ubiquitous in the biological sciences, and creating effective graphical representations involves quantitative and disciplinary concepts and skills. Past studies document student difficulties with graphing within the contexts of classroom or national assessments without evaluating student reasoning. Operating under the metarepresentational competence framework, we conducted think-aloud interviews to reveal differences in reasoning and graph quality between undergraduate biology students, graduate students, and professors in a pen-and-paper graphing task. All professors planned and thought about data before graph construction. When reflecting on their graphs, professors and graduate students focused on the function of graphs and experimental design, while most undergraduate students relied on intuition and data provided in the task. Most undergraduate students meticulously plotted all data with scaled axes, while professors and some graduate students transformed the data, aligned the graph with the research question, and reflected on statistics and sample size. Differences in reasoning and approaches taken in graph choice and construction corroborate and extend previous findings and provide rich targets for undergraduate and graduate instruction.
| S-EPMC5589433 | biostudies-literature
Project description:Objective.Image texture features, such as those derived by Haralicket al, are a powerful metric for image classification and are used across fields including cancer research. Our aim is to demonstrate how analogous texture features can be derived for graphs and networks. We also aim to illustrate how these new metrics summarize graphs, may aid comparative graph studies, may help classify biological graphs, and might assist in detecting dysregulation in cancer.Approach.We generate the first analogies of image texture for graphs and networks. Co-occurrence matrices for graphs are generated by summing over all pairs of neighboring nodes in the graph. We generate metrics for fitness landscapes, gene co-expression and regulatory networks, and protein interaction networks. To assess metric sensitivity we varied discretization parameters and noise. To examine these metrics in the cancer context we compare metrics for both simulated and publicly available experimental gene expression and build random forest classifiers for cancer cell lineage.Main results.Our novel graph 'texture' features are shown to be informative of graph structure and node label distributions. The metrics are sensitive to discretization parameters and noise in node labels. We demonstrate that graph texture features vary across different biological graph topologies and node labelings. We show how our texture metrics can be used to classify cell line expression by lineage, demonstrating classifiers with 82% and 89% accuracy.Significance.New metrics provide opportunities for better comparative analyzes and new models for classification. Our texture features are novel second-order graph features for networks or graphs with ordered node labels. In the complex cancer informatics setting, evolutionary analyses and drug response prediction are two examples where new network science approaches like this may prove fruitful.
| S-EPMC10598684 | biostudies-literature