Research on the Top-Down Parsing Method for Context-Sensitive Graph Grammars.
Ontology highlight
ABSTRACT:
SUBMITTER: Wang Y
PROVIDER: S-EPMC4664237 | biostudies-literature | 2015
REPOSITORIES: biostudies-literature
Publications
Research on the Top-Down Parsing Method for Context-Sensitive Graph Grammars.
Wang Yi Y Zeng XiaoQin X Ding Han H
PloS one 20151130 11
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. ...[more]
Similar Datasets
Project description:BackgroundHuman populations are structured by social networks, in which individuals tend to form relationships based on shared attributes. Certain attributes that are ambiguous, stigmatized or illegal can create a OhiddenO population, so-called because its members are difficult to identify. Many hidden populations are also at an elevated risk of exposure to infectious diseases. Consequently, public health agencies are presently adopting modern survey techniques that traverse social networks in hidden populations by soliciting individuals to recruit their peers, e.g., respondent-driven sampling (RDS). The concomitant accumulation of network-based epidemiological data, however, is rapidly outpacing the development of computational methods for analysis. Moreover, current analytical models rely on unrealistic assumptions, e.g., that the traversal of social networks can be modeled by a Markov chain rather than a branching process.Methodology/principal findingsHere, we develop a new methodology based on stochastic context-free grammars (SCFGs), which are well-suited to modeling tree-like structure of the RDS recruitment process. We apply this methodology to an RDS case study of injection drug users (IDUs) in Tijuana, México, a hidden population at high risk of blood-borne and sexually-transmitted infections (i.e., HIV, hepatitis C virus, syphilis). Survey data were encoded as text strings that were parsed using our custom implementation of the inside-outside algorithm in a publicly-available software package (HyPhy), which uses either expectation maximization or direct optimization methods and permits constraints on model parameters for hypothesis testing. We identified significant latent variability in the recruitment process that violates assumptions of Markov chain-based methods for RDS analysis: firstly, IDUs tended to emulate the recruitment behavior of their own recruiter; and secondly, the recruitment of like peers (homophily) was dependent on the number of recruits.ConclusionsSCFGs provide a rich probabilistic language that can articulate complex latent structure in survey data derived from the traversal of social networks. Such structure that has no representation in Markov chain-based models can interfere with the estimation of the composition of hidden populations if left unaccounted for, raising critical implications for the prevention and control of infectious disease epidemics.
| S-EPMC2734164 | biostudies-literature
Project description:BackgroundDatabase search has been the main approach for proteoform identification by top-down tandem mass spectrometry. However, when the target proteoform that produced the spectrum contains post-translational modifications (PTMs) and/or mutations, it is quite time consuming to align a query spectrum against all protein sequences without any PTMs and mutations in a large database. Consequently, it is essential to develop efficient and sensitive filtering algorithms for speeding up database search.ResultsIn this paper, we propose a spectrum graph matching (SGM) based protein sequence filtering method for top-down mass spectral identification. It uses the subspectra of a query spectrum to generate spectrum graphs and searches them against a protein database to report the best candidates. As the sequence tag and gaped tag approaches need the preprocessing step to extract and select tags, the SGM filtering method circumvents this preprocessing step, thus simplifying data processing. We evaluated the filtration efficiency of the SGM filtering method with various parameter settings on an Escherichia coli top-down mass spectrometry data set and compared the performances of the SGM filtering method and two tag-based filtering methods on a data set of MCF-7 cells.ConclusionsExperimental results on the data sets show that the SGM filtering method achieves high sensitivity in protein sequence filtration. When coupled with a spectral alignment algorithm, the SGM filtering method significantly increases the number of identified proteoform spectrum-matches compared with the tag-based methods in top-down mass spectrometry data analysis.
| S-EPMC6157290 | biostudies-literature
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: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:The present study is to develop the novel robotic surgical technique and enhance the surgery quality for the treatment of distal rectal cancer.
| 67720 | ecrin-mdr-crc
Project description:Context-free grammars are fundamental for the description of linguistic syntax. However, most artificial grammar learning experiments have explored learning of simpler finite-state grammars, while studies exploring context-free grammars have not assessed awareness and implicitness. This paper explores the implicit learning of context-free grammars employing features of hierarchical organization, recursive embedding and long-distance dependencies. The grammars also featured the distinction between left- and right-branching structures, as well as between centre- and tail-embedding, both distinctions found in natural languages. People acquired unconscious knowledge of relations between grammatical classes even for dependencies over long distances, in ways that went beyond learning simpler relations (e.g. n-grams) between individual words. The structural distinctions drawn from linguistics also proved important as performance was greater for tail-embedding than centre-embedding structures. The results suggest the plausibility of implicit learning of complex context-free structures, which model some features of natural languages. They support the relevance of artificial grammar learning for probing mechanisms of language learning and challenge existing theories and computational models of implicit learning.
| S-EPMC3477156 | biostudies-literature
Project description:Recent progress in top-down proteomics has driven the demand for chromatographic methods compatible with mass spectrometry (MS) that can separate intact proteins. Hydrophilic interaction liquid chromatography (HILIC) has recently shown good potential for the characterization of glycoforms of intact proteins. In the present study, we demonstrate that HILIC can separate a wide range of proteins exhibiting orthogonal selectivity with respect to reversed-phase LC (RPLC). However, the application of HILIC to the analysis of low abundance proteins (e.g., in proteomics analysis) is hampered by low volume loadability, hindering down-scaling of the method to column diameters below 2.1 mm. Moreover, HILIC-MS sensitivity is decreased due to ion suppression from the trifluoroacetic acid (TFA) often used as the ion-pair agent to improve the selectivity and efficiency in the analysis of glycoproteins. Here, we introduce a capillary-based HILIC-MS method that overcomes these problems. Our method uses RPLC trap-columns to load and inject the sample, circumventing issues of protein solubility and volume loadability in capillary columns (200 μm ID). The low flow rates and use of a dopant gas in the electrospray interface improve protein-ionization efficiencies and reduce suppression by TFA. Overall, this allows the separation and detection of small protein quantities (down to 5 ng injected on column) as indicated by the analysis of a mixture of model proteins. The potential of the new capillary HILIC-MS is demonstrated by the analysis of a complex cell lysate.
| S-EPMC5990932 | biostudies-literature
Project description:Mesopredators abundance is often limited by top-order predators and also by key food resources. However, the contribution of these bidirectional forces to structure carnivore community is still unclear. Here, we studied how the presence and absence of an apex predator which is currently recovering its former distribution range, the Iberian lynx (Lynx pardinus), determined the absolute abundance and fine-scale spatiotemporal avoidance mechanisms of two sympatric mesocarnivores (stone marten Martes foina and common genet Genetta genetta) with different dietary plasticity. We hypothesized that the lynx causes a mesopredator suppression and subordinate predators develop segregation strategies in respect to their trophic niche breadth. We placed 120 camera-traps in Southern Spain for 8 months in two consecutive years to estimate mesocarnivore abundances by using SCR Bayesian models, prey availability and assess spatio-temporal patterns. We found that the lynx reduced mesocarnivore abundance up to 10 times. Stone marten, a mesopredator with a broad food resources spectrum, showed a total spatial exclusion with the apex predator. Meanwhile, fine-scale avoidance mechanisms allowed the genet to persist in low density inside lynx territories, probably taking advantage of high availability of its preferred prey. Thus, the strength of these top-down and bottom-up effects was rather species-specific. Given the recent recovery of large carnivore populations worldwide, variation in suppression levels on different mesopredator species could modify ecosystem functions provided by the carnivore community in contrasting ways.
| S-EPMC10011582 | biostudies-literature
Project description:Visual stimuli that deviate from the current context elicit augmented responses in the primary visual cortex (V1). These heightened responses, known as "deviance detection," require local inhibition in the V1 and top-down input from the anterior cingulate area (ACa). Here, we investigated the mechanisms by which the ACa and V1 interact to support deviance detection. Local field potential recordings in mice during an oddball paradigm showed that ACa-V1 synchrony peaks in the theta/alpha band (≈10 Hz). Two-photon imaging in the V1 revealed that mainly pyramidal neurons exhibited deviance detection, while contextually redundant stimuli increased vasoactive intestinal peptide (VIP)-positive interneuron (VIP) activity and decreased somatostatin-positive interneuron (SST) activity. Optogenetic drive of ACa-V1 inputs at 10 Hz activated V1-VIPs but inhibited V1-SSTs, mirroring the dynamics present during the oddball paradigm. Chemogenetic inhibition of V1-VIPs disrupted Aca-V1 synchrony and deviance detection in the V1. These results outline temporal and interneuron-specific mechanisms of top-down modulation that support visual context processing.
| S-EPMC10591868 | biostudies-literature
Project description:Top-down modulation of sensory processing is a critical neural mechanism subserving numerous important cognitive roles, one of which may be to inform lower-order sensory systems of the current 'task at hand' by conveying behavioral context to these systems. Accumulating evidence indicates that top-down cortical influences are carried by directed interareal synchronization of oscillatory neuronal populations, with recent results pointing to beta-frequency oscillations as particularly important for top-down processing. However, it remains to be determined if top-down beta-frequency oscillations indeed convey behavioral context. We measured spectral Granger Causality (sGC) using local field potentials recorded from microelectrodes chronically implanted in visual areas V1/V2, V4, and TEO of two rhesus macaque monkeys, and applied multivariate pattern analysis to the spatial patterns of top-down sGC. We decoded behavioral context by discriminating patterns of top-down (V4/TEO-to-V1/V2) beta-peak sGC for two different task rules governing correct responses to identical visual stimuli. The results indicate that top-down directed influences are carried to visual cortex by beta oscillations, and differentiate task demands even before visual stimulus processing. They suggest that top-down beta-frequency oscillatory processes coordinate processing of sensory information by conveying global knowledge states to early levels of the sensory cortical hierarchy independently of bottom-up stimulus-driven processing.
| S-EPMC5934398 | biostudies-literature