TY - GEN
AB - POMDPs are standard models for probabilistic planning problems, where an agent interacts with an uncertain environment. We study the problem of almost-sure reachability, where given a set of target states, the question is to decide whether there is a policy to ensure that the target set is reached with probability 1 (almost-surely). While in general the problem is EXPTIME-complete, in many practical cases policies with a small amount of memory suffice. Moreover, the existing solution to the problem is explicit, which first requires to construct explicitly an exponential reduction to a belief-support MDP. In this work, we first study the existence of observation-stationary strategies, which is NP-complete, and then small-memory strategies. We present a symbolic algorithm by an efficient encoding to SAT and using a SAT solver for the problem. We report experimental results demonstrating the scalability of our symbolic (SAT-based) approach.
AU - Chatterjee, Krishnendu
AU - Chmelik, Martin
AU - Davies, Jessica
ID - 5443
SN - 2664-1690
TI - A symbolic SAT-based algorithm for almost-sure reachability with small strategies in POMDPs
ER -
TY - GEN
AB - A comprehensive understanding of the clonal evolution of cancer is critical for understanding neoplasia. Genome-wide sequencing data enables evolutionary studies at unprecedented depth. However, classical phylogenetic methods often struggle with noisy sequencing data of impure DNA samples and fail to detect subclones that have different evolutionary trajectories. We have developed a tool, called Treeomics, that allows us to reconstruct the phylogeny of a cancer with commonly available sequencing technologies. Using Bayesian inference and Integer Linear Programming, robust phylogenies consistent with the biological processes underlying cancer evolution were obtained for pancreatic, ovarian, and prostate cancers. Furthermore, Treeomics correctly identified sequencing artifacts such as those resulting from low statistical power; nearly 7% of variants were misclassified by conventional statistical methods. These artifacts can skew phylogenies by creating illusory tumor heterogeneity among distinct samples. Importantly, we show that the evolutionary trees generated with Treeomics are mathematically optimal.
AU - Reiter, Johannes
AU - Makohon-Moore, Alvin
AU - Gerold, Jeffrey
AU - Bozic, Ivana
AU - Chatterjee, Krishnendu
AU - Iacobuzio-Donahue, Christine
AU - Vogelstein, Bert
AU - Nowak, Martin
ID - 5444
SN - 2664-1690
TI - Reconstructing robust phylogenies of metastatic cancers
ER -
TY - DATA
AB - This repository contains the experimental part of the CAV 2015 publication Counterexample Explanation by Learning Small Strategies in Markov Decision Processes.
We extended the probabilistic model checker PRISM to represent strategies of Markov Decision Processes as Decision Trees.
The archive contains a java executable version of the extended tool (prism_dectree.jar) together with a few examples of the PRISM benchmark library.
To execute the program, please have a look at the README.txt, which provides instructions and further information on the archive.
The archive contains scripts that (if run often enough) reproduces the data presented in the publication.
AU - Fellner, Andreas
ID - 5549
KW - Markov Decision Process
KW - Decision Tree
KW - Probabilistic Verification
KW - Counterexample Explanation
TI - Experimental part of CAV 2015 publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes
ER -
TY - JOUR
AB - Parasitism creates selection for resistance mechanisms in host populations and is hypothesized to promote increased host evolvability. However, the influence of these traits on host evolution when parasites are no longer present is unclear. We used experimental evolution and whole-genome sequencing of Escherichia coli to determine the effects of past and present exposure to parasitic viruses (phages) on the spread of mutator alleles, resistance, and bacterial competitive fitness. We found that mutator alleles spread rapidly during adaptation to any of four different phage species, and this pattern was even more pronounced with multiple phages present simultaneously. However, hypermutability did not detectably accelerate adaptation in the absence of phages and recovery of fitness costs associated with resistance. Several lineages evolved phage resistance through elevated mucoidy, and during subsequent evolution in phage-free conditions they rapidly reverted to nonmucoid, phage-susceptible phenotypes. Genome sequencing revealed that this phenotypic reversion was achieved by additional genetic changes rather than by genotypic reversion of the initial resistance mutations. Insertion sequence (IS) elements played a key role in both the acquisition of resistance and adaptation in the absence of parasites; unlike single nucleotide polymorphisms, IS insertions were not more frequent in mutator lineages. Our results provide a genetic explanation for rapid reversion of mucoidy, a phenotype observed in other bacterial species including human pathogens. Moreover, this demonstrates that the types of genetic change underlying adaptation to fitness costs, and consequently the impact of evolvability mechanisms such as increased point-mutation rates, depend critically on the mechanism of resistance.
AU - Wielgoss, Sébastien
AU - Bergmiller, Tobias
AU - Bischofberger, Anna M.
AU - Hall, Alex R.
ID - 5749
IS - 3
JF - Molecular Biology and Evolution
SN - 0737-4038
TI - Adaptation to Parasites and Costs of Parasite Resistance in Mutator and Nonmutator Bacteria
VL - 33
ER -
TY - JOUR
AB - We present here the first integer-based algorithm for constructing a well-defined lattice sphere specified by integer radius and integer center. The algorithm evolves from a unique correspondence between the lattice points comprising the sphere and the distribution of sum of three square numbers in integer intervals. We characterize these intervals to derive a useful set of recurrences, which, in turn, aids in efficient computation. Each point of the lattice sphere is determined by resorting to only a few primitive operations in the integer domain. The symmetry of its quadraginta octants provides an added advantage by confining the computation to its prima quadraginta octant. Detailed theoretical analysis and experimental results have been furnished to demonstrate its simplicity and elegance.
AU - Biswas, Ranita
AU - Bhowmick, Partha
ID - 5804
IS - 4
JF - Theoretical Computer Science
SN - 0304-3975
TI - From prima quadraginta octant to lattice sphere through primitive integer operations
VL - 624
ER -
TY - JOUR
AU - Biswas, Ranita
AU - Bhowmick, Partha
ID - 5807
IS - 11
JF - Theoretical Computer Science
SN - 0304-3975
TI - On different topological classes of spherical geodesic paths and circles inZ3
VL - 605
ER -
TY - JOUR
AU - Biswas, Ranita
AU - Bhowmick, Partha
ID - 5808
IS - 6-8
JF - The Visual Computer
SN - 0178-2789
TI - Layer the sphere
VL - 31
ER -
TY - JOUR
AB - Transcription of eukaryotic protein-coding genes commences with the assembly of a conserved initiation complex, which consists of RNA polymerase II (Pol II) and the general transcription factors, at promoter DNA. After two decades of research, the structural basis of transcription initiation is emerging. Crystal structures of many components of the initiation complex have been resolved, and structural information on Pol II complexes with general transcription factors has recently been obtained. Although mechanistic details await elucidation, available data outline how Pol II cooperates with the general transcription factors to bind to and open promoter DNA, and how Pol II directs RNA synthesis and escapes from the promoter.
AU - Sainsbury, Sarah
AU - Bernecky, Carrie A
AU - Cramer, Patrick
ID - 594
IS - 3
JF - Nature Reviews Molecular Cell Biology
TI - Structural basis of transcription initiation by RNA polymerase II
VL - 16
ER -
TY - JOUR
AB - Carbon dioxide (CO2) gradients are ubiquitous and provide animals with information about their environment, such as the potential presence of prey or predators. The nematode Caenorhabditis elegans avoids elevated CO2, and previous work identified three neuron pairs called “BAG,” “AFD,” and “ASE” that respond to CO2 stimuli. Using in vivo Ca2+ imaging and behavioral analysis, we show that C. elegans can detect CO2 independently of these sensory pathways. Many of the C. elegans sensory neurons we examined, including the AWC olfactory neurons, the ASJ and ASK gustatory neurons, and the ASH and ADL nociceptors, respond to a rise in CO2 with a rise in Ca2+. In contrast, glial sheath cells harboring the sensory endings of C. elegans’ major chemosensory neurons exhibit strong and sustained decreases in Ca2+ in response to high CO2. Some of these CO2 responses appear to be cell intrinsic. Worms therefore may couple detection of CO2 to that of other cues at the earliest stages of sensory processing. We show that C. elegans persistently suppresses oviposition at high CO2. Hermaphrodite-specific neurons (HSNs), the executive neurons driving egg-laying, are tonically inhibited when CO2 is elevated. CO2 modulates the egg-laying system partly through the AWC olfactory neurons: High CO2 tonically activates AWC by a cGMP-dependent mechanism, and AWC output inhibits the HSNs. Our work shows that CO2 is a more complex sensory cue for C. elegans than previously thought, both in terms of behavior and neural circuitry.
AU - Fenk, Lorenz A.
AU - de Bono, Mario
ID - 6118
IS - 27
JF - Proceedings of the National Academy of Sciences
SN - 0027-8424
TI - Environmental CO2 inhibits Caenorhabditis elegans egg-laying by modulating olfactory neurons and evokes widespread changes in neural activity
VL - 112
ER -
TY - JOUR
AB - Brains organize behavior and physiology to optimize the response to threats or opportunities. We dissect how 21% O2, an indicator of surface exposure, reprograms C. elegans' global state, inducing sustained locomotory arousal and altering expression of neuropeptides, metabolic enzymes, and other non-neural genes. The URX O2-sensing neurons drive arousal at 21% O2 by tonically activating the RMG interneurons. Stimulating RMG is sufficient to switch behavioral state. Ablating the ASH, ADL, or ASK sensory neurons connected to RMG by gap junctions does not disrupt arousal. However, disrupting cation currents in these neurons curtails RMG neurosecretion and arousal. RMG signals high O2 by peptidergic secretion. Neuropeptide reporters reveal neural circuit state, as neurosecretion stimulates neuropeptide expression. Neural imaging in unrestrained animals shows that URX and RMG encode O2 concentration rather than behavior, while the activity of downstream interneurons such as AVB and AIY reflect both O2 levels and the behavior being executed.
AU - Laurent, Patrick
AU - Soltesz, Zoltan
AU - Nelson, Geoffrey M
AU - Chen, Changchun
AU - Arellano-Carbajal, Fausto
AU - Levy, Emmanuel
AU - de Bono, Mario
ID - 6120
JF - eLife
SN - 2050-084X
TI - Decoding a neural circuit controlling global animal state in C. elegans
VL - 4
ER -
TY - JOUR
AB - The osteoclast-associated receptor (OSCAR) is a collagen-binding immune receptor with important roles in dendritic cell maturation and activation of inflammatory monocytes as well as in osteoclastogenesis. The crystal structure of the OSCAR ectodomain is presented, both free and in complex with a consensus triple-helical peptide (THP). The structures revealed a collagen-binding site in each immunoglobulin-like domain (D1 and D2). The THP binds near a predicted collagen-binding groove in D1, but a more extensive interaction with D2 is facilitated by the unusually wide D1-D2 interdomain angle in OSCAR. Direct binding assays, combined with site-directed mutagenesis, confirm that the primary collagen-binding site in OSCAR resides in D2, in marked contrast to the related collagen receptors, glycoprotein VI (GPVI) and leukocyte-associated immunoglobulin-like receptor-1 (LAIR-1). Monomeric OSCAR D1D2 binds to the consensus THP with a KD of 28 µM measured in solution, but shows a higher affinity (KD 1.5 μM) when binding to a solid-phase THP, most likely due to an avidity effect. These data suggest a 2-stage model for the interaction of OSCAR with a collagen fibril, with transient, low-affinity interactions initiated by the membrane-distal D1, followed by firm adhesion to the primary binding site in D2.
AU - Zhou, Long
AU - Hinerman, J. M.
AU - Blaszczyk, M.
AU - Miller, J. L. C.
AU - Conrady, D. G.
AU - Barrow, A. D.
AU - Chirgadze, D. Y.
AU - Bihan, D.
AU - Farndale, R. W.
AU - Herr, A. B.
ID - 6507
IS - 5
JF - Blood
SN - 0006-4971
TI - Structural basis for collagen recognition by the immune receptor OSCAR
VL - 127
ER -
TY - JOUR
AB - Motivated by the significant performance gains which polar codes experience under successive cancellation list decoding, their scaling exponent is studied as a function of the list size. In particular, the error probability is fixed, and the tradeoff between the block length and back-off from capacity is analyzed. A lower bound is provided on the error probability under MAP decoding with list size L for any binary-input memoryless output-symmetric channel and for any class of linear codes such that their minimum distance is unbounded as the block length grows large. Then, it is shown that under MAP decoding, although the introduction of a list can significantly improve the involved constants, the scaling exponent itself, i.e., the speed at which capacity is approached, stays unaffected for any finite list size. In particular, this result applies to polar codes, since their minimum distance tends to infinity as the block length increases. A similar result is proved for genie-aided successive cancellation decoding when transmission takes place over the binary erasure channel, namely, the scaling exponent remains constant for any fixed number of helps from the genie. Note that since genie-aided successive cancellation decoding might be strictly worse than successive cancellation list decoding, the problem of establishing the scaling exponent of the latter remains open.
AU - Mondelli, Marco
AU - Hassani, Hamed
AU - Urbanke, Rudiger
ID - 6736
IS - 9
JF - IEEE Transactions on Information Theory
TI - Scaling exponent of list decoders with applications to polar codes
VL - 61
ER -
TY - JOUR
AB - This paper presents polar coding schemes for the two-user discrete memoryless broadcast channel (DM-BC) which achieve Marton's region with both common and private messages. This is the best achievable rate region known to date, and it is tight for all classes of two-user DM-BCs whose capacity regions are known. To accomplish this task, we first construct polar codes for both the superposition as well as binning strategy. By combining these two schemes, we obtain Marton's region with private messages only. Finally, we show how to handle the case of common information. The proposed coding schemes possess the usual advantages of polar codes, i.e., they have low encoding and decoding complexity and a superpolynomial decay rate of the error probability. We follow the lead of Goela, Abbe, and Gastpar, who recently introduced polar codes emulating the superposition and binning schemes. To align the polar indices, for both schemes, their solution involves some degradedness constraints that are assumed to hold between the auxiliary random variables and channel outputs. To remove these constraints, we consider the transmission of k blocks and employ a chaining construction that guarantees the proper alignment of the polarized indices. The techniques described in this paper are quite general, and they can be adopted to many other multiterminal scenarios whenever there polar indices need to be aligned.
AU - Mondelli, Marco
AU - Hassani, Hamed
AU - Sason, Igal
AU - Urbanke, Rudiger
ID - 6737
IS - 2
JF - IEEE Transactions on Information Theory
TI - Achieving Marton’s region for broadcast channels using polar codes
VL - 61
ER -
TY - JOUR
AB - Torque magnetization measurements on YBa2Cu3Oy (YBCO) at doping y=6.67 (p=0.12), in dc fields (B) up to 33 T and temperatures down to 4.5 K, show that weak diamagnetism persists above the extrapolated irreversibility field Hirr(T=0)≈24 T. The differential susceptibility dM/dB, however, is more rapidly suppressed for B≳16 T than expected from the properties of the low field superconducting state, and saturates at a low value for fields B≳24 T. In addition, torque measurements on a p=0.11 YBCO crystal in pulsed field up to 65 T and temperatures down to 8 K show similar behavior, with no additional features at higher fields. We offer two candidate scenarios to explain these observations: (a) superconductivity survives but is heavily suppressed at high field by competition with charge-density-wave (CDW) order; (b) static superconductivity disappears near 24 T and is followed by a region of fluctuating superconductivity, which causes dM/dB to saturate at high field. The diamagnetic signal observed above 50 T for the p=0.11 crystal at 40 K and below may be caused by changes in the normal state susceptibility rather than bulk or fluctuating superconductivity. There will be orbital (Landau) diamagnetism from electron pockets and possibly a reduction in spin susceptibility caused by the stronger three-dimensional ordered CDW.
AU - Yu, Jing Fei
AU - Ramshaw, B. J.
AU - Kokanović, I.
AU - Modic, Kimberly A
AU - Harrison, N.
AU - Day, James
AU - Liang, Ruixing
AU - Hardy, W. N.
AU - Bonn, D. A.
AU - McCollam, A.
AU - Julian, S. R.
AU - Cooper, J. R.
ID - 7070
IS - 18
JF - Physical Review B
SN - 1098-0121
TI - Magnetization of underdoped YBa2Cu3Oy above the irreversibility field
VL - 92
ER -
TY - JOUR
AB - In this paper, we develop an energy method to study finite speed of propagation and waiting time phenomena for the stochastic porous media equation with linear multiplicative noise in up to three spatial dimensions. Based on a novel iteration technique and on stochastic counterparts of weighted integral estimates used in the deterministic setting, we formulate a sufficient criterion on the growth of initial data which locally guarantees a waiting time phenomenon to occur almost surely. Up to a logarithmic factor, this criterion coincides with the optimal criterion known from the deterministic setting. Our technique can be modified to prove finite speed of propagation as well.
AU - Julian Fischer
AU - Grün, Günther
ID - 1311
IS - 1
JF - SIAM Journal on Mathematical Analysis
TI - Finite speed of propagation and waiting times for the stochastic porous medium equation: A unifying approach
VL - 47
ER -
TY - JOUR
AB - We present an algorithm for the derivation of lower bounds on support propagation for a certain class of nonlinear parabolic equations. We proceed by combining the ideas in some recent papers by the author with the algorithmic construction of entropies due to Jüngel and Matthes, reducing the problem to a quantifier elimination problem. Due to its complexity, the quantifier elimination problem cannot be solved by present exact algorithms. However, by tackling the quantifier elimination problem numerically, in the case of the thin-film equation we are able to improve recent results by the author in the regime of strong slippage n ∈ (1, 2). For certain second-order doubly nonlinear parabolic equations, we are able to extend the known lower bounds on free boundary propagation to the case of irregular oscillatory initial data. Finally, we apply our method to a sixth-order quantum drift-diffusion equation, resulting in an upper bound on the time which it takes for the support to reach every point in the domain.
AU - Julian Fischer
ID - 1313
IS - 1
JF - Interfaces and Free Boundaries
TI - Estimates on front propagation for nonlinear higher-order parabolic equations: An algorithmic approach
VL - 17
ER -
TY - JOUR
AB - We derive a posteriori estimates for the modeling error caused by the assumption of perfect incompressibility in the incompressible Navier-Stokes equation: Real fluids are never perfectly incompressible but always feature at least some low amount of compressibility. Thus, their behavior is described by the compressible Navier-Stokes equation, the pressure being a steep function of the density. We rigorously estimate the difference between an approximate solution to the incompressible Navier-Stokes equation and any weak solution to the compressible Navier-Stokes equation in the sense of Lions (without assuming any additional regularity of solutions). Heuristics and numerical results suggest that our error estimates are of optimal order in the case of "well-behaved" flows and divergence-free approximations of the velocity field. Thus, we expect our estimates to justify the idealization of fluids as perfectly incompressible also in practical situations.
AU - Fischer, Julian L
ID - 1314
IS - 5
JF - SIAM Journal on Numerical Analysis
TI - A posteriori modeling error estimates for the assumption of perfect incompressibility in the Navier-Stokes equation
VL - 53
ER -
TY - JOUR
AB - In the present work we introduce the notion of a renormalized solution for reaction–diffusion systems with entropy-dissipating reactions. We establish the global existence of renormalized solutions. In the case of integrable reaction terms our notion of a renormalized solution reduces to the usual notion of a weak solution. Our existence result in particular covers all reaction–diffusion systems involving a single reversible reaction with mass-action kinetics and (possibly species-dependent) Fick-law diffusion; more generally, it covers the case of systems of reversible reactions with mass-action kinetics which satisfy the detailed balance condition. For such equations the existence of any kind of solution in general was an open problem, thereby motivating the study of renormalized solutions.
AU - Julian Fischer
ID - 1316
IS - 1
JF - Archive for Rational Mechanics and Analysis
TI - Global existence of renormalized solutions to entropy-dissipating reaction–diffusion systems
VL - 218
ER -
TY - JOUR
AB - In plants, vacuolar H+-ATPase (V-ATPase) activity acidifies both the trans-Golgi network/early endosome (TGN/EE) and the vacuole. This dual V-ATPase function has impeded our understanding of how the pH homeostasis within the plant TGN/EE controls exo- and endocytosis. Here, we show that the weak V-ATPase mutant deetiolated3 (det3) displayed a pH increase in the TGN/EE, but not in the vacuole, strongly impairing secretion and recycling of the brassinosteroid receptor and the cellulose synthase complexes to the plasma membrane, in contrast to mutants lacking tonoplast-localized V-ATPase activity only. The brassinosteroid insensitivity and the cellulose deficiency defects in det3 were tightly correlated with reduced Golgi and TGN/EE motility. Thus, our results provide strong evidence that acidification of the TGN/EE, but not of the vacuole, is indispensable for functional secretion and recycling in plants.
AU - Yu, Luo
AU - Scholl, Stefan
AU - Doering, Anett
AU - Yi, Zhang
AU - Irani, Niloufer
AU - Di Rubbo, Simone
AU - Neumetzler, Lutz
AU - Krishnamoorthy, Praveen
AU - Van Houtte, Isabelle
AU - Mylle, Evelien
AU - Bischoff, Volker
AU - Vernhettes, Samantha
AU - Winne, Johan
AU - Friml, Jirí
AU - Stierhof, York
AU - Schumacher, Karin
AU - Persson, Staffan
AU - Russinova, Eugenia
ID - 1383
IS - 7
JF - Nature Plants
TI - V-ATPase activity in the TGN/EE is required for exocytosis and recycling in Arabidopsis
VL - 1
ER -
TY - THES
AB - This thesis is concerned with the computation and approximation of intrinsic volumes. Given a smooth body M and a certain digital approximation of it, we develop algorithms to approximate various intrinsic volumes of M using only measurements taken from its digital approximations. The crucial idea behind our novel algorithms is to link the recent theory of persistent homology to the theory of intrinsic volumes via the Crofton formula from integral geometry and, in particular, via Euler characteristic computations. Our main contributions are a multigrid convergent digital algorithm to compute the first intrinsic volume of a solid body in R^n as well as an appropriate integration pipeline to approximate integral-geometric integrals defined over the Grassmannian manifold.
AU - Pausinger, Florian
ID - 1399
TI - On the approximation of intrinsic volumes
ER -