A Lower Bound on DNNF Encodings of Pseudo-Boolean Constraints
Ontology highlight
ABSTRACT:
SUBMITTER: Pulina L
PROVIDER: S-EPMC7326562 | biostudies-literature | 2020 Jun
REPOSITORIES: biostudies-literature
Similar Datasets
Project description:Our understanding of real-world connected systems has benefited from studying their evolution, from random wirings and rewirings to growth-dependent topologies. Long overlooked in this search has been the role of the innate: networks that connect based on identity-dependent compatibility rules. Inspired by the genetic principles that guide brain connectivity, we derive a network encoding process that can utilize wiring rules to reproducibly generate specific topologies. To illustrate the representational power of this approach, we propose stochastic and deterministic processes for generating a wide range of network topologies. Specifically, we detail network heuristics that generate structured graphs, such as feed-forward and hierarchical networks. In addition, we characterize a Random Genetic (RG) family of networks, which, like Erdős-Rényi graphs, display critical phase transitions, however their modular underpinnings lead to markedly different behaviors under targeted attacks. The proposed framework provides a relevant null-model for social and biological systems, where diverse metrics of identity underpin a node's preferred connectivity.
| S-EPMC8225892 | biostudies-literature
Project description:Difference constraints have been used for termination analysis in the literature, where they denote relational inequalities of the form x'?y+c , and describe that the value of x in the current state is at most the value of y in the previous state plus some constant c?Z . We believe that difference constraints are also a good choice for complexity and resource bound analysis because the complexity of imperative programs typically arises from counter increments and resets, which can be modeled naturally by difference constraints. In this article we propose a bound analysis based on difference constraints. We make the following contributions: (1) our analysis handles bound analysis problems of high practical relevance which current approaches cannot handle: we extend the range of bound analysis to a class of challenging but natural loop iteration patterns which typically appear in parsing and string-matching routines. (2) We advocate the idea of using bound analysis to infer invariants: our soundness proven algorithm obtains invariants through bound analysis, the inferred invariants are in turn used for obtaining bounds. Our bound analysis therefore does not rely on external techniques for invariant generation. (3) We demonstrate that difference constraints are a suitable abstract program model for automatic complexity and resource bound analysis: we provide efficient abstraction techniques for obtaining difference constraint programs from imperative code. (4) We report on a thorough experimental comparison of state-of-the-art bound analysis tools: we set up a tool comparison on (a) a large benchmark of real-world C code, (b) a benchmark built of examples taken from the bound analysis literature and (c) a benchmark of challenging iteration patterns which we found in real source code. (5) Our analysis is more scalable than existing approaches: we discuss how we achieve scalability.
| S-EPMC6044401 | biostudies-literature
Project description:TRPV4 (transient receptor potential vanilloid 4) channels are Ca2+-permeable channels that play a key role in regulating vascular tone. In arterial myocytes, opening of TRPV4 channels creates local increases in Ca2+ influx, detectable optically as "TRPV4 sparklets." TRPV4 sparklet activity can be enhanced by the action of the vasoconstrictor angiotensin II (AngII). This modulation depends on the activation of subcellular signaling domains that comprise protein kinase C α (PKCα) bound to the anchoring protein AKAP150. Here, we used super-resolution nanoscopy, patch-clamp electrophysiology, Ca2+ imaging, and mathematical modeling approaches to test the hypothesis that AKAP150-dependent modulation of TRPV4 channels is critically dependent on the distance between these two proteins in the sarcolemma of arterial myocytes. Our data show that the distance between AKAP150 and TRPV4 channel clusters varies with sex and arterial bed. Consistent with our hypothesis, we further find that basal and AngII-induced TRPV4 channel activity decays exponentially as the distance between TRPV4 and AKAP150 increases. Our data suggest a maximum radius of action of ∼200 nm for local modulation of TRPV4 channels by AKAP150-associated PKCα.
| S-EPMC5460949 | biostudies-literature
Project description:We propose a model for cohesin-mediated loop extrusion, where the loop extrusion is driven entropically by the energy difference between supercoiled and torsionally relaxed chromatin fibers. Different levels of negative supercoiling are controlled by varying imposed friction between the cohesin ring and the chromatin fiber. The speed of generation of negative supercoiling by RNA polymerase associated with TOP1 is kept constant and corresponds to 10 rotations per second. The model was tested by coarse-grained molecular simulations for a wide range of frictions between 2 to 200 folds of that of generic fiber and the surrounding medium. The higher friction allowed for the accumulation of higher levels of supercoiling, while the resulting extrusion rate also increased. The obtained extrusion rates for the given range of investigated frictions were between 1 and 10 kbps, but also a saturation of the rate at high frictions was observed. The calculated contact maps indicate a qualitative improvement obtained at lower levels of supercoiling. The fits of mathematical equations qualitatively reproduce the loop sizes and levels of supercoiling obtained from simulations and support the proposed mechanism of entropically driven extrusion. The cohesin ring is bound on the fibers pseudo-topologically, and the model suggests that the topological binding is not necessary.
| S-EPMC7915857 | biostudies-literature
Project description:Decision trees play an important role both in Machine Learning and Knowledge Representation. They are attractive due to their immediate interpretability. In the spirit of Occam’s razor, and interpretability, it is desirable to calculate the smallest tree. This, however, has proven to be a challenging task and greedy approaches are typically used to learn trees in practice. Nevertheless, recent work showed that by the use of SAT solvers one may calculate the optimal size tree for real-world benchmarks. This paper proposes a novel SAT-based encoding that explicitly models paths in the tree, which enables us to control the tree’s depth as well as size. At the level of individual SAT calls, we investigate splitting the search space into tree topologies. Our tool outperforms the existing implementation. But also, the experimental results show that minimizing the depth first and then minimizing the number of nodes enables solving a larger set of instances.
| S-EPMC7326558 | biostudies-literature
Project description:How early does the brain decode object categories? Addressing this question is critical to constrain the type of neuronal architecture supporting object categorization. In this context, much effort has been devoted to estimating face processing speed. With onsets estimated from 50 to 150 ms, the timing of the first face-sensitive responses in humans remains controversial. This controversy is due partially to the susceptibility of dynamic brain measurements to filtering distortions and analysis issues. Here, using distributions of single-trial event-related potentials (ERPs), causal filtering, statistical analyses at all electrodes and time points, and effective correction for multiple comparisons, we present evidence that the earliest categorical differences start around 90 ms following stimulus presentation. These results were obtained from a representative group of 120 participants, aged 18-81, who categorized images of faces and noise textures. The results were reliable across testing days, as determined by test-retest assessment in 74 of the participants. Furthermore, a control experiment showed similar ERP onsets for contrasts involving images of houses or white noise. Face onsets did not change with age, suggesting that face sensitivity occurs within 100 ms across the adult lifespan. Finally, the simplicity of the face-texture contrast, and the dominant midline distribution of the effects, suggest the face responses were evoked by relatively simple image properties and are not face specific. Our results provide a new lower benchmark for the earliest neuronal responses to complex objects in the human visual system.
| S-EPMC4982026 | biostudies-literature
Project description:We use simple models of the costs and benefits of microbial gene expression to show that changing a protein's expression away from its optimum by 2-fold should reduce fitness by at least [Formula: see text], where P is the fraction the cell's protein that the gene accounts for. As microbial genes are usually expressed at above 5 parts per million, and effective population sizes are likely to be above 10(6), this implies that 2-fold changes to gene expression levels are under strong selection, as [Formula: see text], where Ne is the effective population size and s is the selection coefficient. Thus, most gene duplications should be selected against. On the other hand, we predict that for most genes, small changes in the expression will be effectively neutral.
| S-EPMC4943197 | biostudies-literature
Project description:The central enzyme in N-linked glycosylation is the oligosaccharyl transferase (OTase), which catalyzes glycan transfer from a polyprenyldiphosphate-linked carrier to select asparagines within acceptor proteins. PglB from Campylobacter jejuni is a single-subunit OTase with homology to the Stt3 subunit of the complex multimeric yeast OTase. Sequence identity between PglB and Stt3 is low (17.9%); however, both have a similar predicted architecture and contain the conserved WWDxG motif. To investigate the relationship between PglB and other Stt3 proteins, sequence analysis was performed using 28 homologues from evolutionarily distant organisms. Since detection of small conserved motifs within large membrane-associated proteins is complicated by divergent sequences surrounding the motifs, we developed a program to parse sequences according to predicted topology and then analyze topologically related regions. This approach identified three conserved motifs that served as the basis for subsequent mutagenesis and functional studies. This work reveals that several inter-transmembrane loop regions of PglB/Stt3 contain strictly conserved motifs that are essential for PglB function. The recent publication of a 3.4 Å resolution structure of full-length C. lari OTase provides clear structural evidence that these loops play a fundamental role in catalysis [ Lizak , C. ; ( 2011 ) Nature 474 , 350 - 355 ]. The current study provides biochemical support for the role of the inter-transmembrane domain loops in OTase catalysis and demonstrates the utility of combining topology prediction and sequence analysis for exposing buried pockets of homology in large membrane proteins. The described approach allowed detection of the catalytic motifs prior to availability of structural data and reveals additional catalytically relevant residues that are not predicted by structural data alone.
| S-EPMC3164389 | biostudies-literature
Project description:The natural ligands for family B G protein-coupled receptors are moderate-length linear peptides having diffuse pharmacophores. The amino-terminal regions of these ligands are critical for biological activity, with their amino-terminal truncation leading to production of orthosteric antagonists. The carboxyl-terminal regions of these peptides are thought to occupy a ligand-binding cleft within the disulfide-bonded amino-terminal domains of these receptors, with the peptides in amphipathic helical conformations. In this work, we have characterized the binding and activity of a series of 11 truncated and lactam-constrained secretin(5-27) analogues at the prototypic member of this family, the secretin receptor. One peptide in this series with lactam connecting residues 16 and 20 [c[E(16),K(20)][Y(10)]sec(5-27)] improved the binding affinity of its unconstrained parental peptide 22-fold while retaining the absence of endogenous biological activity and competitive antagonist characteristics. Homology modeling with molecular mechanics and molecular dynamics simulations established that this constrained peptide occupies the ligand-binding cleft in an orientation similar to that of natural full-length secretin and provided insights into why this peptide was more effective than other truncated conformationally constrained peptides in the series. This lactam bridge is believed to stabilize an extended α-helical conformation of this peptide while in solution and not to interfere with critical residue-residue approximations while docked to the receptor.
| S-EPMC3177990 | biostudies-literature
Project description:A lower bound on the sinc function is given. Application for the sequence {b(n)}(n=1)(∞) which related to Carleman inequality is given as well.
| S-EPMC4121092 | biostudies-other