TY - CONF
AB - We propose a general dual ascent framework for Lagrangean decomposition of combinatorial problems. Although methods of this type have shown their efficiency for a number of problems, so far there was no general algorithm applicable to multiple problem types. In this work, we propose such a general algorithm. It depends on several parameters, which can be used to optimize its performance in each particular setting. We demonstrate efficacy of our method on graph matching and multicut problems, where it outperforms state-of-the-art solvers including those based on subgradient optimization and off-the-shelf linear programming solvers.
AU - Swoboda, Paul
AU - Kuske, Jan
AU - Savchynskyy, Bogdan
ID - 917
SN - 978-153860457-1
TI - A dual ascent framework for Lagrangean decomposition of combinatorial problems
VL - 2017
ER -
TY - JOUR
AB - We introduce the Voronoi functional of a triangulation of a finite set of points in the Euclidean plane and prove that among all geometric triangulations of the point set, the Delaunay triangulation maximizes the functional. This result neither extends to topological triangulations in the plane nor to geometric triangulations in three and higher dimensions.
AU - Edelsbrunner, Herbert
AU - Glazyrin, Alexey
AU - Musin, Oleg
AU - Nikitenko, Anton
ID - 1173
IS - 5
JF - Combinatorica
SN - 02099683
TI - The Voronoi functional is maximized by the Delaunay triangulation in the plane
VL - 37
ER -
TY - CONF
AB - Security of cryptographic applications is typically defined by security games. The adversary, within certain resources, cannot win with probability much better than 0 (for unpredictability applications, like one-way functions) or much better than 1/2 (indistinguishability applications for instance encryption schemes). In so called squared-friendly applications the winning probability of the adversary, for different values of the application secret randomness, is not only close to 0 or 1/2 on average, but also concentrated in the sense that its second central moment is small. The class of squared-friendly applications, which contains all unpredictability applications and many indistinguishability applications, is particularly important for key derivation. Barak et al. observed that for square-friendly applications one can beat the "RT-bound", extracting secure keys with significantly smaller entropy loss. In turn Dodis and Yu showed that in squared-friendly applications one can directly use a "weak" key, which has only high entropy, as a secure key. In this paper we give sharp lower bounds on square security assuming security for "weak" keys. We show that any application which is either (a) secure with weak keys or (b) allows for entropy savings for keys derived by universal hashing, must be square-friendly. Quantitatively, our lower bounds match the positive results of Dodis and Yu and Barak et al. (TCC\'13, CRYPTO\'11) Hence, they can be understood as a general characterization of squared-friendly applications. While the positive results on squared-friendly applications where derived by one clever application of the Cauchy-Schwarz Inequality, for tight lower bounds we need more machinery. In our approach we use convex optimization techniques and some theory of circular matrices.
AU - Skórski, Maciej
ID - 1174
SN - 18688969
TI - Lower bounds on key derivation for square-friendly applications
VL - 66
ER -
TY - CONF
AB - We study space complexity and time-space trade-offs with a focus not on peak memory usage but on overall memory consumption throughout the computation. Such a cumulative space measure was introduced for the computational model of parallel black pebbling by [Alwen and Serbinenko ’15] as a tool for obtaining results in cryptography. We consider instead the non- deterministic black-white pebble game and prove optimal cumulative space lower bounds and trade-offs, where in order to minimize pebbling time the space has to remain large during a significant fraction of the pebbling. We also initiate the study of cumulative space in proof complexity, an area where other space complexity measures have been extensively studied during the last 10–15 years. Using and extending the connection between proof complexity and pebble games in [Ben-Sasson and Nordström ’08, ’11] we obtain several strong cumulative space results for (even parallel versions of) the resolution proof system, and outline some possible future directions of study of this, in our opinion, natural and interesting space measure.
AU - Alwen, Joel F
AU - De Rezende, Susanna
AU - Nordstrom, Jakob
AU - Vinyals, Marc
ED - Papadimitriou, Christos
ID - 1175
SN - 18688969
TI - Cumulative space in black-white pebbling and resolution
VL - 67
ER -
TY - CONF
AB - The algorithm Argon2i-B of Biryukov, Dinu and Khovratovich is currently being considered by the IRTF (Internet Research Task Force) as a new de-facto standard for password hashing. An older version (Argon2i-A) of the same algorithm was chosen as the winner of the recent Password Hashing Competition. An important competitor to Argon2i-B is the recently introduced Balloon Hashing (BH) algorithm of Corrigan-Gibs, Boneh and Schechter. A key security desiderata for any such algorithm is that evaluating it (even using a custom device) requires a large amount of memory amortized across multiple instances. Alwen and Blocki (CRYPTO 2016) introduced a class of theoretical attacks against Argon2i-A and BH. While these attacks yield large asymptotic reductions in the amount of memory, it was not, a priori, clear if (1) they can be extended to the newer Argon2i-B, (2) the attacks are effective on any algorithm for practical parameter ranges (e.g., 1GB of memory) and (3) if they can be effectively instantiated against any algorithm under realistic hardware constrains. In this work we answer all three of these questions in the affirmative for all three algorithms. This is also the first work to analyze the security of Argon2i-B. In more detail, we extend the theoretical attacks of Alwen and Blocki (CRYPTO 2016) to the recent Argon2i-B proposal demonstrating severe asymptotic deficiencies in its security. Next we introduce several novel heuristics for improving the attack's concrete memory efficiency even when on-chip memory bandwidth is bounded. We then simulate our attacks on randomly sampled Argon2i-A, Argon2i-B and BH instances and measure the resulting memory consumption for various practical parameter ranges and for a variety of upperbounds on the amount of parallelism available to the attacker. Finally we describe, implement, and test a new heuristic for applying the Alwen-Blocki attack to functions employing a technique developed by Corrigan-Gibs et al. for improving concrete security of memory-hard functions. We analyze the collected data and show the effects various parameters have on the memory consumption of the attack. In particular, we can draw several interesting conclusions about the level of security provided by these functions. · For the Alwen-Blocki attack to fail against practical memory parameters, Argon2i-B must be instantiated with more than 10 passes on memory - beyond the "paranoid" parameter setting in the current IRTF proposal. · The technique of Corrigan-Gibs for improving security can also be overcome by the Alwen-Blocki attack under realistic hardware constraints. · On a positive note, both the asymptotic and concrete security of Argon2i-B seem to improve on that of Argon2i-A.
AU - Alwen, Joel F
AU - Blocki, Jeremiah
ID - 1176
SN - 978-150905761-0
TI - Towards practical attacks on Argon2i and balloon hashing
ER -
TY - JOUR
AB - In this article we define an algebraic vertex of a generalized polyhedron and show that the set of algebraic vertices is the smallest set of points needed to define the polyhedron. We prove that the indicator function of a generalized polytope P is a linear combination of indicator functions of simplices whose vertices are algebraic vertices of P. We also show that the indicator function of any generalized polyhedron is a linear combination, with integer coefficients, of indicator functions of cones with apices at algebraic vertices and line-cones. The concept of an algebraic vertex is closely related to the Fourier–Laplace transform. We show that a point v is an algebraic vertex of a generalized polyhedron P if and only if the tangent cone of P, at v, has non-zero Fourier–Laplace transform.
AU - Akopyan, Arseniy
AU - Bárány, Imre
AU - Robins, Sinai
ID - 1180
JF - Advances in Mathematics
SN - 00018708
TI - Algebraic vertices of non-convex polyhedra
VL - 308
ER -
TY - JOUR
AB - We construct efficient authentication protocols and message authentication codes (MACs) whose security can be reduced to the learning parity with noise (LPN) problem. Despite a large body of work—starting with the (Formula presented.) protocol of Hopper and Blum in 2001—until now it was not even known how to construct an efficient authentication protocol from LPN which is secure against man-in-the-middle attacks. A MAC implies such a (two-round) protocol.
AU - Kiltz, Eike
AU - Pietrzak, Krzysztof Z
AU - Venturi, Daniele
AU - Cash, David
AU - Jain, Abhishek
ID - 1187
IS - 4
JF - Journal of Cryptology
TI - Efficient authentication from hard learning problems
VL - 30
ER -
TY - JOUR
AB - Variation in genotypes may be responsible for differences in dispersal rates, directional biases, and growth rates of individuals. These traits may favor certain genotypes and enhance their spatiotemporal spreading into areas occupied by the less advantageous genotypes. We study how these factors influence the speed of spreading in the case of two competing genotypes under the assumption that spatial variation of the total population is small compared to the spatial variation of the frequencies of the genotypes in the population. In that case, the dynamics of the frequency of one of the genotypes is approximately described by a generalized Fisher–Kolmogorov–Petrovskii–Piskunov (F–KPP) equation. This generalized F–KPP equation with (nonlinear) frequency-dependent diffusion and advection terms admits traveling wave solutions that characterize the invasion of the dominant genotype. Our existence results generalize the classical theory for traveling waves for the F–KPP with constant coefficients. Moreover, in the particular case of the quadratic (monostable) nonlinear growth–decay rate in the generalized F–KPP we study in detail the influence of the variance in diffusion and mean displacement rates of the two genotypes on the minimal wave propagation speed.
AU - Kollár, Richard
AU - Novak, Sebastian
ID - 1191
IS - 3
JF - Bulletin of Mathematical Biology
TI - Existence of traveling waves for the generalized F–KPP equation
VL - 79
ER -
TY - CONF
AB - The main result of this paper is a generalization of the classical blossom algorithm for finding perfect matchings. Our algorithm can efficiently solve Boolean CSPs where each variable appears in exactly two constraints (we call it edge CSP) and all constraints are even Δ-matroid relations (represented by lists of tuples). As a consequence of this, we settle the complexity classification of planar Boolean CSPs started by Dvorak and Kupec. Knowing that edge CSP is tractable for even Δ-matroid constraints allows us to extend the tractability result to a larger class of Δ-matroids that includes many classes that were known to be tractable before, namely co-independent, compact, local and binary.
AU - Kazda, Alexandr
AU - Kolmogorov, Vladimir
AU - Rolinek, Michal
ID - 1192
SN - 978-161197478-2
TI - Even delta-matroids and the complexity of planar Boolean CSPs
ER -
TY - CONF
AB - Termination is one of the basic liveness properties, and we study the termination problem for probabilistic programs with real-valued variables. Previous works focused on the qualitative problem that asks whether an input program terminates with probability~1 (almost-sure termination). A powerful approach for this qualitative problem is the notion of ranking supermartingales with respect to a given set of invariants. The quantitative problem (probabilistic termination) asks for bounds on the termination probability. A fundamental and conceptual drawback of the existing approaches to address probabilistic termination is that even though the supermartingales consider the probabilistic behavior of the programs, the invariants are obtained completely ignoring the probabilistic aspect. In this work we address the probabilistic termination problem for linear-arithmetic probabilistic programs with nondeterminism. We define the notion of {\em stochastic invariants}, which are constraints along with a probability bound that the constraints hold. We introduce a concept of {\em repulsing supermartingales}. First, we show that repulsing supermartingales can be used to obtain bounds on the probability of the stochastic invariants. Second, we show the effectiveness of repulsing supermartingales in the following three ways: (1)~With a combination of ranking and repulsing supermartingales we can compute lower bounds on the probability of termination; (2)~repulsing supermartingales provide witnesses for refutation of almost-sure termination; and (3)~with a combination of ranking and repulsing supermartingales we can establish persistence properties of probabilistic programs. We also present results on related computational problems and an experimental evaluation of our approach on academic examples.
AU - Chatterjee, Krishnendu
AU - Novotny, Petr
AU - Zikelic, Djordje
ID - 1194
IS - 1
SN - 07308566
TI - Stochastic invariants for probabilistic termination
VL - 52
ER -
TY - JOUR
AB - We define the . model-measuring problem: given a model . M and specification . ϕ, what is the maximal distance . ρ such that all models . M' within distance . ρ from . M satisfy (or violate) . ϕ. The model-measuring problem presupposes a distance function on models. We concentrate on . automatic distance functions, which are defined by weighted automata. The model-measuring problem subsumes several generalizations of the classical model-checking problem, in particular, quantitative model-checking problems that measure the degree of satisfaction of a specification; robustness problems that measure how much a model can be perturbed without violating the specification; and parameter synthesis for hybrid systems. We show that for automatic distance functions, and (a) . ω-regular linear-time, (b) . ω-regular branching-time, and (c) hybrid specifications, the model-measuring problem can be solved.We use automata-theoretic model-checking methods for model measuring, replacing the emptiness question for word, tree, and hybrid automata by the . optimal-value question for the weighted versions of these automata. For automata over words and trees, we consider weighted automata that accumulate weights by maximizing, summing, discounting, and limit averaging. For hybrid automata, we consider monotonic (parametric) hybrid automata, a hybrid counterpart of (discrete) weighted automata.We give several examples of using the model-measuring problem to compute various notions of robustness and quantitative satisfaction for temporal specifications. Further, we propose the modeling framework for model measuring to ease the specification and reduce the likelihood of errors in modeling.Finally, we present a variant of the model-measuring problem, called the . model-repair problem. The model-repair problem applies to models that do not satisfy the specification; it can be used to derive restrictions, under which the model satisfies the specification, i.e., to repair the model.
AU - Henzinger, Thomas A
AU - Otop, Jan
ID - 1196
JF - Nonlinear Analysis: Hybrid Systems
TI - Model measuring for discrete and hybrid systems
VL - 23
ER -
TY - JOUR
AB - We consider a model of fermions interacting via point interactions, defined via a certain weighted Dirichlet form. While for two particles the interaction corresponds to infinite scattering length, the presence of further particles effectively decreases the interaction strength. We show that the model becomes trivial in the thermodynamic limit, in the sense that the free energy density at any given particle density and temperature agrees with the corresponding expression for non-interacting particles.
AU - Moser, Thomas
AU - Seiringer, Robert
ID - 1198
IS - 3
JF - Letters in Mathematical Physics
SN - 03779017
TI - Triviality of a model of particles with point interactions in the thermodynamic limit
VL - 107
ER -
TY - JOUR
AB - Much of quantitative genetics is based on the ‘infinitesimal model’, under which selection has a negligible effect on the genetic variance. This is typically justified by assuming a very large number of loci with additive effects. However, it applies even when genes interact, provided that the number of loci is large enough that selection on each of them is weak relative to random drift. In the long term, directional selection will change allele frequencies, but even then, the effects of epistasis on the ultimate change in trait mean due to selection may be modest. Stabilising selection can maintain many traits close to their optima, even when the underlying alleles are weakly selected. However, the number of traits that can be optimised is apparently limited to ~4Ne by the ‘drift load’, and this is hard to reconcile with the apparent complexity of many organisms. Just as for the mutation load, this limit can be evaded by a particular form of negative epistasis. A more robust limit is set by the variance in reproductive success. This suggests that selection accumulates information most efficiently in the infinitesimal regime, when selection on individual alleles is weak, and comparable with random drift. A review of evidence on selection strength suggests that although most variance in fitness may be because of alleles with large Nes, substantial amounts of adaptation may be because of alleles in the infinitesimal regime, in which epistasis has modest effects.
AU - Barton, Nicholas H
ID - 1199
JF - Heredity
TI - How does epistasis influence the response to selection?
VL - 118
ER -
TY - JOUR
AB - The eigenvalue distribution of the sum of two large Hermitian matrices, when one of them is conjugated by a Haar distributed unitary matrix, is asymptotically given by the free convolution of their spectral distributions. We prove that this convergence also holds locally in the bulk of the spectrum, down to the optimal scales larger than the eigenvalue spacing. The corresponding eigenvectors are fully delocalized. Similar results hold for the sum of two real symmetric matrices, when one is conjugated by Haar orthogonal matrix.
AU - Bao, Zhigang
AU - Erdös, László
AU - Schnelli, Kevin
ID - 1207
IS - 3
JF - Communications in Mathematical Physics
SN - 00103616
TI - Local law of addition of random matrices on optimal scale
VL - 349
ER -
TY - JOUR
AB - We study parameter estimation in linear Gaussian covariance models, which are p-dimensional Gaussian models with linear constraints on the covariance matrix. Maximum likelihood estimation for this class of models leads to a non-convex optimization problem which typically has many local maxima. Using recent results on the asymptotic distribution of extreme eigenvalues of the Wishart distribution, we provide sufficient conditions for any hill climbing method to converge to the global maximum. Although we are primarily interested in the case in which n≫p, the proofs of our results utilize large sample asymptotic theory under the scheme n/p→γ>1. Remarkably, our numerical simulations indicate that our results remain valid for p as small as 2. An important consequence of this analysis is that, for sample sizes n≃14p, maximum likelihood estimation for linear Gaussian covariance models behaves as if it were a convex optimization problem. © 2016 The Royal Statistical Society and Blackwell Publishing Ltd.
AU - Zwiernik, Piotr
AU - Uhler, Caroline
AU - Richards, Donald
ID - 1208
IS - 4
JF - Journal of the Royal Statistical Society. Series B: Statistical Methodology
SN - 13697412
TI - Maximum likelihood estimation for linear Gaussian covariance models
VL - 79
ER -
TY - JOUR
AB - Systems such as fluid flows in channels and pipes or the complex Ginzburg–Landau system, defined over periodic domains, exhibit both continuous symmetries, translational and rotational, as well as discrete symmetries under spatial reflections or complex conjugation. The simplest, and very common symmetry of this type is the equivariance of the defining equations under the orthogonal group O(2). We formulate a novel symmetry reduction scheme for such systems by combining the method of slices with invariant polynomial methods, and show how it works by applying it to the Kuramoto–Sivashinsky system in one spatial dimension. As an example, we track a relative periodic orbit through a sequence of bifurcations to the onset of chaos. Within the symmetry-reduced state space we are able to compute and visualize the unstable manifolds of relative periodic orbits, their torus bifurcations, a transition to chaos via torus breakdown, and heteroclinic connections between various relative periodic orbits. It would be very hard to carry through such analysis in the full state space, without a symmetry reduction such as the one we present here.
AU - Budanur, Nazmi B
AU - Cvitanović, Predrag
ID - 1211
IS - 3-4
JF - Journal of Statistical Physics
TI - Unstable manifolds of relative periodic orbits in the symmetry reduced state space of the Kuramoto–Sivashinsky system
VL - 167
ER -
TY - CHAP
AB - Bacterial cytokinesis is commonly initiated by the Z-ring, a dynamic cytoskeletal structure that assembles at the site of division. Its primary component is FtsZ, a tubulin-like GTPase, that like its eukaryotic relative forms protein filaments in the presence of GTP. Since the discovery of the Z-ring 25 years ago, various models for the role of FtsZ have been suggested. However, important information about the architecture and dynamics of FtsZ filaments during cytokinesis is still missing. One reason for this lack of knowledge has been the small size of bacteria, which has made it difficult to resolve the orientation and dynamics of individual FtsZ filaments in the Z-ring. While superresolution microscopy experiments have helped to gain more information about the organization of the Z-ring in the dividing cell, they were not yet able to elucidate a mechanism of how FtsZ filaments reorganize during assembly and disassembly of the Z-ring. In this chapter, we explain how to use an in vitro reconstitution approach to investigate the self-organization of FtsZ filaments recruited to a biomimetic lipid bilayer by its membrane anchor FtsA. We show how to perform single-molecule experiments to study the behavior of individual FtsZ monomers during the constant reorganization of the FtsZ-FtsA filament network. We describe how to analyze the dynamics of single molecules and explain why this information can help to shed light onto possible mechanism of Z-ring constriction. We believe that similar experimental approaches will be useful to study the mechanism of membrane-based polymerization of other cytoskeletal systems, not only from prokaryotic but also eukaryotic origin.
AU - Baranova, Natalia
AU - Loose, Martin
ED - Echard, Arnaud
ID - 1213
SN - 0091679X
T2 - Cytokinesis
TI - Single-molecule measurements to study polymerization dynamics of FtsZ-FtsA copolymers
VL - 137
ER -
TY - JOUR
AB - We study controller synthesis problems for finite-state Markov decision processes, where the objective is to optimize the expected mean-payoff performance and stability (also known as variability in the literature). We argue that the basic notion of expressing the stability using the statistical variance of the mean payoff is sometimes insufficient, and propose an alternative definition. We show that a strategy ensuring both the expected mean payoff and the variance below given bounds requires randomization and memory, under both the above definitions. We then show that the problem of finding such a strategy can be expressed as a set of constraints.
AU - Brázdil, Tomáš
AU - Chatterjee, Krishnendu
AU - Forejt, Vojtěch
AU - Kučera, Antonín
ID - 1294
JF - Journal of Computer and System Sciences
TI - Trading performance for stability in Markov decision processes
VL - 84
ER -
TY - JOUR
AB - Evolutionary algorithms (EAs) form a popular optimisation paradigm inspired by natural evolution. In recent years the field of evolutionary computation has developed a rigorous analytical theory to analyse the runtimes of EAs on many illustrative problems. Here we apply this theory to a simple model of natural evolution. In the Strong Selection Weak Mutation (SSWM) evolutionary regime the time between occurrences of new mutations is much longer than the time it takes for a mutated genotype to take over the population. In this situation, the population only contains copies of one genotype and evolution can be modelled as a stochastic process evolving one genotype by means of mutation and selection between the resident and the mutated genotype. The probability of accepting the mutated genotype then depends on the change in fitness. We study this process, SSWM, from an algorithmic perspective, quantifying its expected optimisation time for various parameters and investigating differences to a similar evolutionary algorithm, the well-known (1+1) EA. We show that SSWM can have a moderate advantage over the (1+1) EA at crossing fitness valleys and study an example where SSWM outperforms the (1+1) EA by taking advantage of information on the fitness gradient.
AU - Paixao, Tiago
AU - Pérez Heredia, Jorge
AU - Sudholt, Dirk
AU - Trubenova, Barbora
ID - 1336
IS - 2
JF - Algorithmica
SN - 01784617
TI - Towards a runtime comparison of natural and artificial evolution
VL - 78
ER -
TY - JOUR
AB - We consider the local eigenvalue distribution of large self-adjoint N×N random matrices H=H∗ with centered independent entries. In contrast to previous works the matrix of variances sij=\mathbbmE|hij|2 is not assumed to be stochastic. Hence the density of states is not the Wigner semicircle law. Its possible shapes are described in the companion paper (Ajanki et al. in Quadratic Vector Equations on the Complex Upper Half Plane. arXiv:1506.05095). We show that as N grows, the resolvent, G(z)=(H−z)−1, converges to a diagonal matrix, diag(m(z)), where m(z)=(m1(z),…,mN(z)) solves the vector equation −1/mi(z)=z+∑jsijmj(z) that has been analyzed in Ajanki et al. (Quadratic Vector Equations on the Complex Upper Half Plane. arXiv:1506.05095). We prove a local law down to the smallest spectral resolution scale, and bulk universality for both real symmetric and complex hermitian symmetry classes.
AU - Ajanki, Oskari H
AU - Erdös, László
AU - Krüger, Torben H
ID - 1337
IS - 3-4
JF - Probability Theory and Related Fields
SN - 01788051
TI - Universality for general Wigner-type matrices
VL - 169
ER -
TY - JOUR
AB - We present a computer-aided programming approach to concurrency. The approach allows programmers to program assuming a friendly, non-preemptive scheduler, and our synthesis procedure inserts synchronization to ensure that the final program works even with a preemptive scheduler. The correctness specification is implicit, inferred from the non-preemptive behavior. Let us consider sequences of calls that the program makes to an external interface. The specification requires that any such sequence produced under a preemptive scheduler should be included in the set of sequences produced under a non-preemptive scheduler. We guarantee that our synthesis does not introduce deadlocks and that the synchronization inserted is optimal w.r.t. a given objective function. The solution is based on a finitary abstraction, an algorithm for bounded language inclusion modulo an independence relation, and generation of a set of global constraints over synchronization placements. Each model of the global constraints set corresponds to a correctness-ensuring synchronization placement. The placement that is optimal w.r.t. the given objective function is chosen as the synchronization solution. We apply the approach to device-driver programming, where the driver threads call the software interface of the device and the API provided by the operating system. Our experiments demonstrate that our synthesis method is precise and efficient. The implicit specification helped us find one concurrency bug previously missed when model-checking using an explicit, user-provided specification. We implemented objective functions for coarse-grained and fine-grained locking and observed that different synchronization placements are produced for our experiments, favoring a minimal number of synchronization operations or maximum concurrency, respectively.
AU - Cerny, Pavol
AU - Clarke, Edmund
AU - Henzinger, Thomas A
AU - Radhakrishna, Arjun
AU - Ryzhyk, Leonid
AU - Samanta, Roopsha
AU - Tarrach, Thorsten
ID - 1338
IS - 2-3
JF - Formal Methods in System Design
TI - From non-preemptive to preemptive scheduling using synchronization synthesis
VL - 50
ER -
TY - JOUR
AB - The behaviour of gene regulatory networks (GRNs) is typically analysed using simulation-based statistical testing-like methods. In this paper, we demonstrate that we can replace this approach by a formal verification-like method that gives higher assurance and scalability. We focus on Wagner’s weighted GRN model with varying weights, which is used in evolutionary biology. In the model, weight parameters represent the gene interaction strength that may change due to genetic mutations. For a property of interest, we synthesise the constraints over the parameter space that represent the set of GRNs satisfying the property. We experimentally show that our parameter synthesis procedure computes the mutational robustness of GRNs—an important problem of interest in evolutionary biology—more efficiently than the classical simulation method. We specify the property in linear temporal logic. We employ symbolic bounded model checking and SMT solving to compute the space of GRNs that satisfy the property, which amounts to synthesizing a set of linear constraints on the weights.
AU - Giacobbe, Mirco
AU - Guet, Calin C
AU - Gupta, Ashutosh
AU - Henzinger, Thomas A
AU - Paixao, Tiago
AU - Petrov, Tatjana
ID - 1351
IS - 8
JF - Acta Informatica
SN - 00015903
TI - Model checking the evolution of gene regulatory networks
VL - 54
ER -
TY - JOUR
AB - One of the major challenges in physically based modelling is making simulations efficient. Adaptive models provide an essential solution to these efficiency goals. These models are able to self-adapt in space and time, attempting to provide the best possible compromise between accuracy and speed. This survey reviews the adaptive solutions proposed so far in computer graphics. Models are classified according to the strategy they use for adaptation, from time-stepping and freezing techniques to geometric adaptivity in the form of structured grids, meshes and particles. Applications range from fluids, through deformable bodies, to articulated solids.
AU - Manteaux, Pierre
AU - Wojtan, Christopher J
AU - Narain, Rahul
AU - Redon, Stéphane
AU - Faure, François
AU - Cani, Marie
ID - 1367
IS - 6
JF - Computer Graphics Forum
SN - 01677055
TI - Adaptive physically based models in computer graphics
VL - 36
ER -
TY - JOUR
AB - We consider the problem of computing the set of initial states of a dynamical system such that there exists a control strategy to ensure that the trajectories satisfy a temporal logic specification with probability 1 (almost-surely). We focus on discrete-time, stochastic linear dynamics and specifications given as formulas of the Generalized Reactivity(1) fragment of Linear Temporal Logic over linear predicates in the states of the system. We propose a solution based on iterative abstraction-refinement, and turn-based 2-player probabilistic games. While the theoretical guarantee of our algorithm after any finite number of iterations is only a partial solution, we show that if our algorithm terminates, then the result is the set of all satisfying initial states. Moreover, for any (partial) solution our algorithm synthesizes witness control strategies to ensure almost-sure satisfaction of the temporal logic specification. While the proposed algorithm guarantees progress and soundness in every iteration, it is computationally demanding. We offer an alternative, more efficient solution for the reachability properties that decomposes the problem into a series of smaller problems of the same type. All algorithms are demonstrated on an illustrative case study.
AU - Svoreňová, Mária
AU - Kretinsky, Jan
AU - Chmelik, Martin
AU - Chatterjee, Krishnendu
AU - Cěrná, Ivana
AU - Belta, Cǎlin
ID - 1407
IS - 2
JF - Nonlinear Analysis: Hybrid Systems
TI - Temporal logic control for stochastic linear systems using abstraction refinement of probabilistic games
VL - 23
ER -
TY - CONF
AB - We study probabilistic models of natural images and extend the autoregressive family of PixelCNN models by incorporating latent variables. Subsequently, we describe two new generative image models that exploit different image transformations as latent variables: a quantized grayscale view of the image or a multi-resolution image pyramid. The proposed models tackle two known shortcomings of existing PixelCNN models: 1) their tendency to focus on low-level image details, while largely ignoring high-level image information, such as object shapes, and 2) their computationally costly procedure for image sampling. We experimentally demonstrate benefits of our LatentPixelCNN models, in particular showing that they produce much more realistically looking image samples than previous state-of-the-art probabilistic models.
AU - Kolesnikov, Alexander
AU - Lampert, Christoph
ID - 1000
SN - 978-151085514-4
T2 - 34th International Conference on Machine Learning
TI - PixelCNN models with auxiliary variables for natural image modeling
VL - 70
ER -
TY - CONF
AB - We present a computational approach for designing CurveUps, curvy shells that form from an initially flat state. They consist of small rigid tiles that are tightly held together by two pre-stretched elastic sheets attached to them. Our method allows the realization of smooth, doubly curved surfaces that can be fabricated as a flat piece. Once released, the restoring forces of the pre-stretched sheets support the object to take shape in 3D. CurveUps are structurally stable in their target configuration. The design process starts with a target surface. Our method generates a tile layout in 2D and optimizes the distribution, shape, and attachment areas of the tiles to obtain a configuration that is fabricable and in which the curved up state closely matches the target. Our approach is based on an efficient approximate model and a local optimization strategy for an otherwise intractable nonlinear optimization problem. We demonstrate the effectiveness of our approach for a wide range of shapes, all realized as physical prototypes.
AU - Guseinov, Ruslan
AU - Miguel, Eder
AU - Bickel, Bernd
ID - 1001
IS - 4
TI - CurveUps: Shaping objects from flat plates with tension-actuated curvature
VL - 36
ER -
TY - CONF
AB - We present an interactive design system to create functional mechanical objects. Our computational approach allows novice users to retarget an existing mechanical template to a user-specified input shape. Our proposed representation for a mechanical template encodes a parameterized mechanism, mechanical constraints that ensure a physically valid configuration, spatial relationships of mechanical parts to the user-provided shape, and functional constraints that specify an intended functionality. We provide an intuitive interface and optimization-in-the-loop approach for finding a valid configuration of the mechanism and the shape to ensure that higher-level functional goals are met. Our algorithm interactively optimizes the mechanism while the user manipulates the placement of mechanical components and the shape. Our system allows users to efficiently explore various design choices and to synthesize customized mechanical objects that can be fabricated with rapid prototyping technologies. We demonstrate the efficacy of our approach by retargeting various mechanical templates to different shapes and fabricating the resulting functional mechanical objects.
AU - Zhang, Ran
AU - Auzinger, Thomas
AU - Ceylan, Duygu
AU - Li, Wilmot
AU - Bickel, Bernd
ID - 1002
IS - 4
SN - 07300301
TI - Functionality-aware retargeting of mechanisms to 3D shapes
VL - 36
ER -
TY - CONF
AB - Network games (NGs) are played on directed graphs and are extensively used in network design and analysis. Search problems for NGs include finding special strategy profiles such as a Nash equilibrium and a globally optimal solution. The networks modeled by NGs may be huge. In formal verification, abstraction has proven to be an extremely effective technique for reasoning about systems with big and even infinite state spaces. We describe an abstraction-refinement methodology for reasoning about NGs. Our methodology is based on an abstraction function that maps the state space of an NG to a much smaller state space. We search for a global optimum and a Nash equilibrium by reasoning on an under- and an overapproximation defined on top of this smaller state space. When the approximations are too coarse to find such profiles, we refine the abstraction function. Our experimental results demonstrate the efficiency of the methodology.
AU - Avni, Guy
AU - Guha, Shibashis
AU - Kupferman, Orna
ID - 1003
SN - 10450823
TI - An abstraction-refinement methodology for reasoning about network games
ER -
TY - JOUR
AB - The fundamental tasks of the root system are, besides anchoring, mediating interactions between plant and soil and providing the plant with water and nutrients. The architecture of the root system is controlled by endogenous mechanisms that constantly integrate environmental signals, such as availability of nutrients and water. Extremely important for efficient soil exploitation and survival under less favorable conditions is the developmental flexibility of the root system that is largely determined by its postembryonic branching capacity. Modulation of initiation and outgrowth of lateral roots provides roots with an exceptional plasticity, allows optimal adjustment to underground heterogeneity, and enables effective soil exploitation and use of resources. Here we discuss recent advances in understanding the molecular mechanisms that shape the plant root system and integrate external cues to adapt to the changing environment.
AU - Ötvös, Krisztina
AU - Benková, Eva
ID - 1004
JF - Current Opinion in Genetics & Development
SN - 0959437X
TI - Spatiotemporal mechanisms of root branching
VL - 45
ER -
TY - JOUR
AB - Background: The phenomenon of immune priming, i.e. enhanced protection following a secondary exposure to a pathogen, has now been demonstrated in a wide range of invertebrate species. Despite accumulating phenotypic evidence, knowledge of its mechanistic underpinnings is currently very limited. Here we used the system of the red flour beetle, Tribolium castaneum and the insect pathogen Bacillus thuringiensis (Bt) to further our molecular understanding of the oral immune priming phenomenon. We addressed how ingestion of bacterial cues (derived from spore supernatants) of an orally pathogenic and non-pathogenic Bt strain affects gene expression upon later challenge exposure, using a whole-transcriptome sequencing approach. Results: Whereas gene expression of individuals primed with the orally non-pathogenic strain showed minor changes to controls, we found that priming with the pathogenic strain induced regulation of a large set of distinct genes, many of which are known immune candidates. Intriguingly, the immune repertoire activated upon priming and subsequent challenge qualitatively differed from the one mounted upon infection with Bt without previous priming. Moreover, a large subset of priming-specific genes showed an inverse regulation compared to their regulation upon challenge only. Conclusions: Our data demonstrate that gene expression upon infection is strongly affected by previous immune priming. We hypothesise that this shift in gene expression indicates activation of a more targeted and efficient response towards a previously encountered pathogen, in anticipation of potential secondary encounter.
AU - Greenwood, Jenny
AU - Milutinovic, Barbara
AU - Peuß, Robert
AU - Behrens, Sarah
AU - Essar, Daniela
AU - Rosenstiel, Philip
AU - Schulenburg, Hinrich
AU - Kurtz, Joachim
ID - 1006
IS - 1
JF - BMC Genomics
SN - 14712164
TI - Oral immune priming with Bacillus thuringiensis induces a shift in the gene expression of Tribolium castaneum larvae
VL - 18
ER -
TY - JOUR
AB - A nonlinear system possesses an invariance with respect to a set of transformations if its output dynamics remain invariant when transforming the input, and adjusting the initial condition accordingly. Most research has focused on invariances with respect to time-independent pointwise transformations like translational-invariance (u(t) -> u(t) + p, p in R) or scale-invariance (u(t) -> pu(t), p in R>0). In this article, we introduce the concept of s0-invariances with respect to continuous input transformations exponentially growing/decaying over time. We show that s0-invariant systems not only encompass linear time-invariant (LTI) systems with transfer functions having an irreducible zero at s0 in R, but also that the input/output relationship of nonlinear s0-invariant systems possesses properties well known from their linear counterparts. Furthermore, we extend the concept of s0-invariances to second- and higher-order s0-invariances, corresponding to invariances with respect to transformations of the time-derivatives of the input, and encompassing LTI systems with zeros of multiplicity two or higher. Finally, we show that nth-order 0-invariant systems realize – under mild conditions – nth-order nonlinear differential operators: when excited by an input of a characteristic functional form, the system’s output converges to a constant value only depending on the nth (nonlinear) derivative of the input.
AU - Lang, Moritz
AU - Sontag, Eduardo
ID - 1007
JF - Automatica
SN - 00051098
TI - Zeros of nonlinear systems with input invariances
VL - 81C
ER -
TY - CONF
AB - A standard objective in partially-observable Markov decision processes (POMDPs) is to find a policy that maximizes the expected discounted-sum payoff. However, such policies may still permit unlikely but highly undesirable outcomes, which is problematic especially in safety-critical applications. Recently, there has been a surge of interest in POMDPs where the goal is to maximize the probability to ensure that the payoff is at least a given threshold, but these approaches do not consider any optimization beyond satisfying this threshold constraint. In this work we go beyond both the “expectation” and “threshold” approaches and consider a “guaranteed payoff optimization (GPO)” problem for POMDPs, where we are given a threshold t and the objective is to find a policy σ such that a) each possible outcome of σ yields a discounted-sum payoff of at least t, and b) the expected discounted-sum payoff of σ is optimal (or near-optimal) among all policies satisfying a). We present a practical approach to tackle the GPO problem and evaluate it on standard POMDP benchmarks.
AU - Chatterjee, Krishnendu
AU - Novotny, Petr
AU - Pérez, Guillermo
AU - Raskin, Jean
AU - Zikelic, Djordje
ID - 1009
T2 - Proceedings of the 31st AAAI Conference on Artificial Intelligence
TI - Optimizing expectation with guarantees in POMDPs
VL - 5
ER -
TY - JOUR
AB - We prove a local law in the bulk of the spectrum for random Gram matrices XX∗, a generalization of sample covariance matrices, where X is a large matrix with independent, centered entries with arbitrary variances. The limiting eigenvalue density that generalizes the Marchenko-Pastur law is determined by solving a system of nonlinear equations. Our entrywise and averaged local laws are on the optimal scale with the optimal error bounds. They hold both in the square case (hard edge) and in the properly rectangular case (soft edge). In the latter case we also establish a macroscopic gap away from zero in the spectrum of XX∗.
AU - Alt, Johannes
AU - Erdös, László
AU - Krüger, Torben H
ID - 1010
JF - Electronic Journal of Probability
SN - 10836489
TI - Local law for random Gram matrices
VL - 22
ER -
TY - CONF
AB - Pushdown systems (PDSs) and recursive state machines (RSMs), which are linearly equivalent, are standard models for interprocedural analysis. Yet RSMs are more convenient as they (a) explicitly model function calls and returns, and (b) specify many natural parameters for algorithmic analysis, e.g., the number of entries and exits. We consider a general framework where RSM transitions are labeled from a semiring and path properties are algebraic with semiring operations, which can model, e.g., interprocedural reachability and dataflow analysis problems. Our main contributions are new algorithms for several fundamental problems. As compared to a direct translation of RSMs to PDSs and the best-known existing bounds of PDSs, our analysis algorithm improves the complexity for finite-height semirings (that subsumes reachability and standard dataflow properties). We further consider the problem of extracting distance values from the representation structures computed by our algorithm, and give efficient algorithms that distinguish the complexity of a one-time preprocessing from the complexity of each individual query. Another advantage of our algorithm is that our improvements carry over to the concurrent setting, where we improve the bestknown complexity for the context-bounded analysis of concurrent RSMs. Finally, we provide a prototype implementation that gives a significant speed-up on several benchmarks from the SLAM/SDV project.
AU - Chatterjee, Krishnendu
AU - Kragl, Bernhard
AU - Mishra, Samarth
AU - Pavlogiannis, Andreas
ED - Yang, Hongseok
ID - 1011
SN - 03029743
TI - Faster algorithms for weighted recursive state machines
VL - 10201
ER -
TY - JOUR
AB - Vortices are commonly observed in the context of classical hydrodynamics: from whirlpools after stirring the coffee in a cup to a violent atmospheric phenomenon such as a tornado, all classical vortices are characterized by an arbitrary circulation value of the local velocity field. On the other hand the appearance of vortices with quantized circulation represents one of the fundamental signatures of macroscopic quantum phenomena. In two-dimensional superfluids quantized vortices play a key role in determining finite-temperature properties, as the superfluid phase and the normal state are separated by a vortex unbinding transition, the Berezinskii-Kosterlitz-Thouless transition. Very recent experiments with two-dimensional superfluid fermions motivate the present work: we present theoretical results based on the renormalization group showing that the universal jump of the superfluid density and the critical temperature crucially depend on the interaction strength, providing a strong benchmark for forthcoming investigations.
AU - Bighin, Giacomo
AU - Salasnich, Luca
ID - 1015
JF - Scientific Reports
SN - 20452322
TI - Vortices and antivortices in two-dimensional ultracold Fermi gases
VL - 7
ER -
TY - JOUR
AB - The integrity and dynamic properties of the microtubule cytoskeleton are indispensable for the development of the mammalian brain. Consequently, mutations in the genes that encode the structural component (the α/β-tubulin heterodimer) can give rise to severe, sporadic neurodevelopmental disorders. These are commonly referred to as the tubulinopathies. Here we report the addition of recessive quadrupedalism, also known as Uner Tan syndrome (UTS), to the growing list of diseases caused by tubulin variants. Analysis of a consanguineous UTS family identified a biallelic TUBB2B mutation, resulting in a p.R390Q amino acid substitution. In addition to the identifying quadrupedal locomotion, all three patients showed severe cerebellar hypoplasia. None, however, displayed the basal ganglia malformations typically associated with TUBB2B mutations. Functional analysis of the R390Q substitution revealed that it did not affect the ability of β-tubulin to fold or become assembled into the α/β-heterodimer, nor did it influence the incorporation of mutant-containing heterodimers into microtubule polymers. The 390Q mutation in S. cerevisiae TUB2 did not affect growth under basal conditions, but did result in increased sensitivity to microtubule-depolymerizing drugs, indicative of a mild impact of this mutation on microtubule function. The TUBB2B mutation described here represents an unusual recessive mode of inheritance for missense-mediated tubulinopathies and reinforces the sensitivity of the developing cerebellum to microtubule defects.
AU - Breuss, Martin
AU - Nguyen, Thai
AU - Srivatsan, Anjana
AU - Leca, Ines
AU - Tian, Guoling
AU - Fritz, Tanja
AU - Hansen, Andi H
AU - Musaev, Damir
AU - Mcevoy Venneri, Jennifer
AU - Kiely, James
AU - Rosti, Rasim
AU - Scott, Eric
AU - Tan, Uner
AU - Kolodner, Richard
AU - Cowan, Nicholas
AU - Keays, David
AU - Gleeson, Joseph
ID - 1016
IS - 2
JF - Human Molecular Genetics
SN - 09646906
TI - Uner Tan syndrome caused by a homozygous TUBB2B mutation affecting microtubule stability
VL - 26
ER -
TY - JOUR
AB - The development of the vertebrate central nervous system is reliant on a complex cascade of biological processes that include mitotic division, relocation of migrating neurons, and the extension of dendritic and axonal processes. Each of these cellular events requires the diverse functional repertoire of the microtubule cytoskeleton for the generation of forces, assembly of macromolecular complexes and transport of molecules and organelles. The tubulins are a multi-gene family that encode for the constituents of microtubules, and have been implicated in a spectrum of neurological disorders. Evidence is building that different tubulins tune the functional properties of the microtubule cytoskeleton dependent on the cell type, developmental profile and subcellular localisation. Here we review of the origins of the functional specification of the tubulin gene family in the developing brain at a transcriptional, translational, and post-transcriptional level. We remind the reader that tubulins are not just loading controls for your average Western blot.
AU - Breuss, Martin
AU - Leca, Ines
AU - Gstrein, Thomas
AU - Hansen, Andi H
AU - Keays, David
ID - 1017
JF - Molecular and Cellular Neuroscience
SN - 10447431
TI - Tubulins and brain development: The origins of functional specification
VL - 84
ER -
TY - JOUR
AB - In plants, the multistep phosphorelay (MSP) pathway mediates a range of regulatory processes, including those activated by cytokinins. The crosstalk between cytokinin response and light is known for a long time. However, the molecular mechanism underlying the interactionbetween light and cytokinin signaling remains elusive. In the screen for upstream regulators we identified a LONG PALE HYPOCOTYL (LPH) gene whose activity is indispensable for spatiotemporally correct expression of CYTOKININ INDEPENDENT-1 (CKI1), encoding the constitutively active sensor histidine kinase that activates MSP signaling. lph is a new allele of HEME OXYGENASE 1 (HY1) which encodes the key protein in the biosynthesis of phytochromobilin, a cofactor of photoconvertiblephytochromes. Our analysis confirmed the light-dependent regulation oftheCKI1 expression pattern. We show that CKI1 expression is under the control of phytochrome A (phyA), functioning as a dual (both positive and negative) regulator of CKI1 expression, presumably via the phyA-regulated transcription factors PHYTOCHROME INTERACTING FACTOR 3 (PIF3) and CIRCADIAN CLOCK ASSOCIATED 1 (CCA1). Changes in CKI1 expression observed in lph/hy1-7 and phy mutants correlatewithmisregulation of MSP signaling, changedcytokinin sensitivity and developmental aberrations,previously shown to be associated with cytokinin and/or CKI1 action. Besides that, we demonstrate novel role of phyA-dependent CKI1 expression in the hypocotyl elongation and hook development during skotomorphogenesis. Based on these results, we propose that the light-dependent regulation of CKI1 provides a plausible mechanistic link underlying the well-known interaction between light- and cytokinin-controlled plant development.
AU - Dobisova, Tereza
AU - Hrdinova, Vendula
AU - Cuesta, Candela
AU - Michlickova, Sarka
AU - Urbankova, Ivana
AU - Hejatkova, Romana
AU - Zadnikova, Petra
AU - Pernisová, Markéta
AU - Benková, Eva
AU - Hejátko, Jan
ID - 1018
IS - 1
JF - Plant Physiology
TI - Light regulated expression of sensor histidine kinase CKI1 controls cytokinin related development
VL - 174
ER -
TY - JOUR
AB - As a consequence of its difference in copy number between males and females, the X chromosome is subject to unique evolutionary forces and gene regulatory mechanisms. Previous studies of Drosophila melanogaster have shown that the expression of X-linked, testis-specific reporter genes is suppressed in the male germline. However, it is not known whether this phenomenon is restricted to testis-expressed genes or if it is a more general property of genes with tissue-specific expression, which are also underrepresented on the X chromosome. To test this, we compared the expression of three tissue-specific reporter genes (ovary, accessory gland and Malpighian tubule) inserted at various autosomal and X-chromosomal locations. In contrast to testis-specific reporter genes, we found no reduction of X-linked expression in any of the other tissues. In accessory gland and Malpighian tubule, we detected higher expression of the X-linked reporter genes, which suggests that they are at least partially dosage compensated. We found no difference in the tissue-specificity of X-linked and autosomal reporter genes. These findings indicate that, in general, the X chromosome is not a detrimental environment for tissue-specific gene expression and that the suppression of X-linked expression is limited to the male germline.
AU - Argyridou, Eliza
AU - Huylmans, Ann K
AU - Königer, Annabella
AU - Parsch, John
ID - 1019
IS - 1
JF - Heredity
SN - 0018067X
TI - X-linkage is not a general inhibitor of tissue-specific gene expression in Drosophila melanogaster
VL - 119
ER -
TY - JOUR
AB - Cellulose is the most abundant biopolymer on Earth. Cellulose fibers, such as the one extracted form cotton or woodpulp, have been used by humankind for hundreds of years to make textiles and paper. Here we show how, by engineering light-matter interaction, we can optimize light scattering using exclusively cellulose nanocrystals. The produced material is sustainable, biocompatible, and when compared to ordinary microfiber-based paper, it shows enhanced scattering strength (×4), yielding a transport mean free path as low as 3.5 μm in the visible light range. The experimental results are in a good agreement with the theoretical predictions obtained with a diffusive model for light propagation.
AU - Caixeiro, Soraya
AU - Peruzzo, Matilda
AU - Onelli, Olimpia
AU - Vignolini, Silvia
AU - Sapienza, Riccardo
ID - 1020
IS - 9
JF - ACS Applied Materials and Interfaces
SN - 19448244
TI - Disordered cellulose based nanostructures for enhanced light scattering
VL - 9
ER -
TY - JOUR
AB - Most flows in nature and engineering are turbulent because of their large velocities and spatial scales. Laboratory experiments on rotating quasi-Keplerian flows, for which the angular velocity decreases radially but the angular momentum increases, are however laminar at Reynolds numbers exceeding one million. This is in apparent contradiction to direct numerical simulations showing that in these experiments turbulence transition is triggered by the axial boundaries. We here show numerically that as the Reynolds number increases, turbulence becomes progressively confined to the boundary layers and the flow in the bulk fully relaminarizes. Our findings support that turbulence is unlikely to occur in isothermal constant-density quasi-Keplerian flows.
AU - Lopez Alonso, Jose M
AU - Avila, Marc
ID - 1021
JF - Journal of Fluid Mechanics
SN - 00221120
TI - Boundary layer turbulence in experiments on quasi Keplerian flows
VL - 817
ER -
TY - JOUR
AB - We introduce a multiscale topological description of the Megaparsec web-like cosmic matter distribution. Betti numbers and topological persistence offer a powerful means of describing the rich connectivity structure of the cosmic web and of its multiscale arrangement of matter and galaxies. Emanating from algebraic topology and Morse theory, Betti numbers and persistence diagrams represent an extension and deepening of the cosmologically familiar topological genus measure and the related geometric Minkowski functionals. In addition to a description of the mathematical background, this study presents the computational procedure for computing Betti numbers and persistence diagrams for density field filtrations. The field may be computed starting from a discrete spatial distribution of galaxies or simulation particles. The main emphasis of this study concerns an extensive and systematic exploration of the imprint of different web-like morphologies and different levels of multiscale clustering in the corresponding computed Betti numbers and persistence diagrams. To this end, we use Voronoi clustering models as templates for a rich variety of web-like configurations and the fractal-like Soneira-Peebles models exemplify a range of multiscale configurations. We have identified the clear imprint of cluster nodes, filaments, walls, and voids in persistence diagrams, along with that of the nested hierarchy of structures in multiscale point distributions. We conclude by outlining the potential of persistent topology for understanding the connectivity structure of the cosmic web, in large simulations of cosmic structure formation and in the challenging context of the observed galaxy distribution in large galaxy surveys.
AU - Pranav, Pratyush
AU - Edelsbrunner, Herbert
AU - Van De Weygaert, Rien
AU - Vegter, Gert
AU - Kerber, Michael
AU - Jones, Bernard
AU - Wintraecken, Mathijs
ID - 1022
IS - 4
JF - Monthly Notices of the Royal Astronomical Society
SN - 00358711
TI - The topology of the cosmic web in terms of persistent Betti numbers
VL - 465
ER -
TY - JOUR
AB - We consider products of independent square non-Hermitian random matrices. More precisely, let X1,…, Xn be independent N × N random matrices with independent entries (real or complex with independent real and imaginary parts) with zero mean and variance 1/N. Soshnikov-O’Rourke [19] and Götze-Tikhomirov [15] showed that the empirical spectral distribution of the product of n random matrices with iid entries converges to (equation found). We prove that if the entries of the matrices X1,…, Xn are independent (but not necessarily identically distributed) and satisfy uniform subexponential decay condition, then in the bulk the convergence of the ESD of X1,…, Xn to (0.1) holds up to the scale N–1/2+ε.
AU - Nemish, Yuriy
ID - 1023
JF - Electronic Journal of Probability
SN - 10836489
TI - Local law for the product of independent non-Hermitian random matrices with independent entries
VL - 22
ER -
TY - JOUR
AB - Many organ surfaces are covered by a protective epithelial-cell layer. It emerges that such layers are maintained by cell stretching that triggers cell division mediated by the force-sensitive ion-channel protein Piezo1. See Letter p.118
AU - Heisenberg, Carl-Philipp J
ID - 1025
IS - 7643
JF - Nature
SN - 00280836
TI - Cell biology: Stretched divisions
VL - 543
ER -
TY - JOUR
AB - Auf der Suche nach einem Bibliothekssystem entschied sich die Forschungseinrichtung IST Austria im Jahr 2014 für das Open-Source-Produkt Koha. In einem ersten Schritt wurden zunächst Grundfunktionen aktiviert um im Anschluss diverse zusätzliche Tools zum Einsatz zu bringen. Die große Flexibilität des Systems erlaubt maßgeschneiderte Lösungen für unterschiedlichste Institutionen. Trotz Herausforderungen kann die Bibliothek auf eine erfolgreiche Implementierung zurückblicken.
AU - Villányi, Márton
ID - 1030
IS - 1
JF - Informationspraxis
SN - 2297-3249
TI - Ein freies Bibliothekssystem für wissenschaftliche Bibliotheken – Werkstattbericht der IST Austria Library
VL - 3
ER -
TY - JOUR
AB - A fundamental algorithmic problem at the heart of static analysis is Dyck reachability. The input is a graph where the edges are labeled with different types of opening and closing parentheses, and the reachability information is computed via paths whose parentheses are properly matched. We present new results for Dyck reachability problems with applications to alias analysis and data-dependence analysis. Our main contributions, that include improved upper bounds as well as lower bounds that establish optimality guarantees, are as follows: First, we consider Dyck reachability on bidirected graphs, which is the standard way of performing field-sensitive points-to analysis. Given a bidirected graph with n nodes and m edges, we present: (i) an algorithm with worst-case running time O(m + n · α(n)), where α(n) is the inverse Ackermann function, improving the previously known O(n2) time bound; (ii) a matching lower bound that shows that our algorithm is optimal wrt to worst-case complexity; and (iii) an optimal average-case upper bound of O(m) time, improving the previously known O(m · logn) bound. Second, we consider the problem of context-sensitive data-dependence analysis, where the task is to obtain analysis summaries of library code in the presence of callbacks. Our algorithm preprocesses libraries in almost linear time, after which the contribution of the library in the complexity of the client analysis is only linear, and only wrt the number of call sites. Third, we prove that combinatorial algorithms for Dyck reachability on general graphs with truly sub-cubic bounds cannot be obtained without obtaining sub-cubic combinatorial algorithms for Boolean Matrix Multiplication, which is a long-standing open problem. Thus we establish that the existing combinatorial algorithms for Dyck reachability are (conditionally) optimal for general graphs. We also show that the same hardness holds for graphs of constant treewidth. Finally, we provide a prototype implementation of our algorithms for both alias analysis and data-dependence analysis. Our experimental evaluation demonstrates that the new algorithms significantly outperform all existing methods on the two problems, over real-world benchmarks.
AU - Chatterjee, Krishnendu
AU - Choudhary, Bhavya
AU - Pavlogiannis, Andreas
ID - 10416
IS - POPL
JF - Proceedings of the ACM on Programming Languages
TI - Optimal Dyck reachability for data-dependence and Alias analysis
VL - 2
ER -
TY - JOUR
AB - We present a new dynamic partial-order reduction method for stateless model checking of concurrent programs. A common approach for exploring program behaviors relies on enumerating the traces of the program, without storing the visited states (aka stateless exploration). As the number of distinct traces grows exponentially, dynamic partial-order reduction (DPOR) techniques have been successfully used to partition the space of traces into equivalence classes (Mazurkiewicz partitioning), with the goal of exploring only few representative traces from each class.
We introduce a new equivalence on traces under sequential consistency semantics, which we call the observation equivalence. Two traces are observationally equivalent if every read event observes the same write event in both traces. While the traditional Mazurkiewicz equivalence is control-centric, our new definition is data-centric. We show that our observation equivalence is coarser than the Mazurkiewicz equivalence, and in many cases even exponentially coarser. We devise a DPOR exploration of the trace space, called data-centric DPOR, based on the observation equivalence.
AU - Chalupa, Marek
AU - Chatterjee, Krishnendu
AU - Pavlogiannis, Andreas
AU - Sinha, Nishant
AU - Vaidya, Kapil
ID - 10417
IS - POPL
JF - Proceedings of the ACM on Programming Languages
TI - Data-centric dynamic partial order reduction
VL - 2
ER -
TY - JOUR
AB - We present a new proof rule for proving almost-sure termination of probabilistic programs, including those that contain demonic non-determinism. An important question for a probabilistic program is whether the probability mass of all its diverging runs is zero, that is that it terminates "almost surely". Proving that can be hard, and this paper presents a new method for doing so. It applies directly to the program's source code, even if the program contains demonic choice. Like others, we use variant functions (a.k.a. "super-martingales") that are real-valued and decrease randomly on each loop iteration; but our key innovation is that the amount as well as the probability of the decrease are parametric. We prove the soundness of the new rule, indicate where its applicability goes beyond existing rules, and explain its connection to classical results on denumerable (non-demonic) Markov chains.
AU - Mciver, Annabelle
AU - Morgan, Carroll
AU - Kaminski, Benjamin Lucien
AU - Katoen, Joost P
ID - 10418
IS - POPL
JF - Proceedings of the ACM on Programming Languages
TI - A new proof rule for almost-sure termination
VL - 2
ER -
TY - JOUR
AB - The Ising model is one of the simplest and most famous models of interacting systems. It was originally proposed to model ferromagnetic interactions in statistical physics and is now widely used to model spatial processes in many areas such as ecology, sociology, and genetics, usually without testing its goodness-of-fit. Here, we propose an exact goodness-of-fit test for the finite-lattice Ising model. The theory of Markov bases has been developed in algebraic statistics for exact goodness-of-fit testing using a Monte Carlo approach. However, this beautiful theory has fallen short of its promise for applications, because finding a Markov basis is usually computationally intractable. We develop a Monte Carlo method for exact goodness-of-fit testing for the Ising model which avoids computing a Markov basis and also leads to a better connectivity of the Markov chain and hence to a faster convergence. We show how this method can be applied to analyze the spatial organization of receptors on the cell membrane.
AU - Martin Del Campo Sanchez, Abraham
AU - Cepeda Humerez, Sarah A
AU - Uhler, Caroline
ID - 2016
IS - 2
JF - Scandinavian Journal of Statistics
SN - 03036898
TI - Exact goodness-of-fit testing for the Ising model
VL - 44
ER -
TY - CONF
AB - We consider the problem of estimating the partition function Z(β)=∑xexp(−β(H(x)) of a Gibbs distribution with a Hamilton H(⋅), or more precisely the logarithm of the ratio q=lnZ(0)/Z(β). It has been recently shown how to approximate q with high probability assuming the existence of an oracle that produces samples from the Gibbs distribution for a given parameter value in [0,β]. The current best known approach due to Huber [9] uses O(qlnn⋅[lnq+lnlnn+ε−2]) oracle calls on average where ε is the desired accuracy of approximation and H(⋅) is assumed to lie in {0}∪[1,n]. We improve the complexity to O(qlnn⋅ε−2) oracle calls. We also show that the same complexity can be achieved if exact oracles are replaced with approximate sampling oracles that are within O(ε2qlnn) variation distance from exact oracles. Finally, we prove a lower bound of Ω(q⋅ε−2) oracle calls under a natural model of computation.
AU - Kolmogorov, Vladimir
ID - 274
T2 - Proceedings of the 31st Conference On Learning Theory
TI - A faster approximation algorithm for the Gibbs partition function
VL - 75
ER -
TY - THES
AB - The thesis encompasses several topics of plant cell biology which were studied in the model plant Arabidopsis thaliana. Chapter 1 concerns the plant hormone auxin and its polar transport through cells and tissues. The highly controlled, directional transport of auxin is facilitated by plasma membrane-localized transporters. Transporters from the PIN family direct auxin transport due to their polarized localizations at cell membranes. Substantial effort has been put into research on cellular trafficking of PIN proteins, which is thought to underlie their polar distribution. I participated in a forward genetic screen aimed at identifying novel regulators of PIN polarity. The screen yielded several genes which may be involved in PIN polarity regulation or participate in polar auxin transport by other means. Chapter 2 focuses on the endomembrane system, with particular attention to clathrin-mediated endocytosis. The project started with identification of several proteins that interact with clathrin light chains. Among them, I focused on two putative homologues of auxilin, which in non-plant systems is an endocytotic factor known for uncoating clathrin-coated vesicles in the final step of endocytosis. The body of my work consisted of an in-depth characterization of transgenic A. thaliana lines overexpressing these putative auxilins in an inducible manner. Overexpression of these proteins leads to an inhibition of endocytosis, as documented by imaging of cargoes and clathrin-related endocytic machinery. An extension of this work is an investigation into a concept of homeostatic regulation acting between distinct transport processes in the endomembrane system. With auxilin overexpressing lines, where endocytosis is blocked specifically, I made observations on the mutual relationship between two opposite trafficking processes of secretion and endocytosis. In Chapter 3, I analyze cortical microtubule arrays and their relationship to auxin signaling and polarized growth in elongating cells. In plants, microtubules are organized into arrays just below the plasma membrane, and it is thought that their function is to guide membrane-docked cellulose synthase complexes. These, in turn, influence cell wall structure and cell shape by directed deposition of cellulose fibres. In elongating cells, cortical microtubule arrays are able to reorient in relation to long cell axis, and these reorientations have been linked to cell growth and to signaling of growth-regulating factors such as auxin or light. In this chapter, I am addressing the causal relationship between microtubule array reorientation, growth, and auxin signaling. I arrive at a model where array reorientation is not guided by auxin directly, but instead is only controlled by growth, which, in turn, is regulated by auxin.
AU - Adamowski, Maciek
ID - 938
TI - Investigations into cell polarity and trafficking in the plant model Arabidopsis thaliana
ER -
TY - JOUR
AB - We reveal the existence of continuous families of guided single-mode solitons in planar waveguides with weakly nonlinear active core and absorbing boundaries. Stable propagation of TE and TM-polarized solitons is accompanied by attenuation of all other modes, i.e., the waveguide features properties of conservative and dissipative systems. If the linear spectrum of the waveguide possesses exceptional points, which occurs in the case of TM polarization, an originally focusing (defocusing) material nonlinearity may become effectively defocusing (focusing). This occurs due to the geometric phase of the carried eigenmode when the surface impedance encircles the exceptional point. In its turn, the change of the effective nonlinearity ensures the existence of dark (bright) solitons in spite of focusing (defocusing) Kerr nonlinearity of the core. The existence of an exceptional point can also result in anomalous enhancement of the effective nonlinearity. In terms of practical applications, the nonlinearity of the reported waveguide can be manipulated by controlling the properties of the absorbing cladding.
AU - Midya, Bikashkali
AU - Konotop, Vladimir
ID - 939
IS - 3
JF - Physical Review Letters
SN - 00319007
TI - Waveguides with absorbing boundaries: Nonlinearity controlled by an exceptional point and solitons
VL - 119
ER -
TY - CONF
AB - Recently there has been a proliferation of automated program repair (APR) techniques, targeting various programming languages. Such techniques can be generally classified into two families: syntactic- and semantics-based. Semantics-based APR, on which we focus, typically uses symbolic execution to infer semantic constraints and then program synthesis to construct repairs conforming to them. While syntactic-based APR techniques have been shown successful on bugs in real-world programs written in both C and Java, semantics-based APR techniques mostly target C programs. This leaves empirical comparisons of the APR families not fully explored, and developers without a Java-based semantics APR technique. We present JFix, a semantics-based APR framework that targets Java, and an associated Eclipse plugin. JFix is implemented atop Symbolic PathFinder, a well-known symbolic execution engine for Java programs. It extends one particular APR technique (Angelix), and is designed to be sufficiently generic to support a variety of such techniques. We demonstrate that semantics-based APR can indeed efficiently and effectively repair a variety of classes of bugs in large real-world Java programs. This supports our claim that the framework can both support developers seeking semantics-based repair of bugs in Java programs, as well as enable larger scale empirical studies comparing syntactic- and semantics-based APR targeting Java. The demonstration of our tool is available via the project website at: https://xuanbachle.github.io/semanticsrepair/
AU - Le, Xuan
AU - Chu, Duc Hiep
AU - Lo, David
AU - Le Goues, Claire
AU - Visser, Willem
ID - 941
T2 - Proceedings of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis
TI - JFIX: Semantics-based repair of Java programs via symbolic PathFinder
ER -
TY - CONF
AB - A notable class of techniques for automatic program repair is known as semantics-based. Such techniques, e.g., Angelix, infer semantic specifications via symbolic execution, and then use program synthesis to construct new code that satisfies those inferred specifications. However, the obtained specifications are naturally incomplete, leaving the synthesis engine with a difficult task of synthesizing a general solution from a sparse space of many possible solutions that are consistent with the provided specifications but that do not necessarily generalize. We present S3, a new repair synthesis engine that leverages programming-by-examples methodology to synthesize high-quality bug repairs. The novelty in S3 that allows it to tackle the sparse search space to create more general repairs is three-fold: (1) A systematic way to customize and constrain the syntactic search space via a domain-specific language, (2) An efficient enumeration-based search strategy over the constrained search space, and (3) A number of ranking features based on measures of the syntactic and semantic distances between candidate solutions and the original buggy program. We compare S3’s repair effectiveness with state-of-the-art synthesis engines Angelix, Enumerative, and CVC4. S3 can successfully and correctly fix at least three times more bugs than the best baseline on datasets of 52 bugs in small programs, and 100 bugs in real-world large programs.
AU - Le, Xuan
AU - Chu, Duc Hiep
AU - Lo, David
AU - Le Goues, Claire
AU - Visser, Willem
ID - 942
SN - 978-145035105-8
TI - S3: Syntax- and semantic-guided repair synthesis via programming by examples
VL - F130154
ER -
TY - JOUR
AB - Like many developing tissues, the vertebrate neural tube is patterned by antiparallel morphogen gradients. To understand how these inputs are interpreted, we measured morphogen signaling and target gene expression in mouse embryos and chick ex vivo assays. From these data, we derived and validated a characteristic decoding map that relates morphogen input to the positional identity of neural progenitors. Analysis of the observed responses indicates that the underlying interpretation strategy minimizes patterning errors in response to the joint input of noisy opposing gradients. We reverse-engineered a transcriptional network that provides a mechanistic basis for the observed cell fate decisions and accounts for the precision and dynamics of pattern formation. Together, our data link opposing gradient dynamics in a growing tissue to precise pattern formation.
AU - Zagórski, Marcin P
AU - Tabata, Yoji
AU - Brandenberg, Nathalie
AU - Lutolf, Matthias
AU - Tkacik, Gasper
AU - Bollenbach, Tobias
AU - Briscoe, James
AU - Kicheva, Anna
ID - 943
IS - 6345
JF - Science
SN - 00368075
TI - Decoding of position in the developing neural tube from antiparallel morphogen gradients
VL - 356
ER -
TY - JOUR
AB - The concerted production of neurons and glia by neural stem cells (NSCs) is essential for neural circuit assembly. In the developing cerebral cortex, radial glia progenitors (RGPs) generate nearly all neocortical neurons and certain glia lineages. RGP proliferation behavior shows a high degree of non-stochasticity, thus a deterministic characteristic of neuron and glia production. However, the cellular and molecular mechanisms controlling RGP behavior and proliferation dynamics in neurogenesis and glia generation remain unknown. By using mosaic analysis with double markers (MADM)-based genetic paradigms enabling the sparse and global knockout with unprecedented single-cell resolution, we identified Lgl1 as a critical regulatory component. We uncover Lgl1-dependent tissue-wide community effects required for embryonic cortical neurogenesis and novel cell-autonomous Lgl1 functions controlling RGP-mediated glia genesis and postnatal NSC behavior. These results suggest that NSC-mediated neuron and glia production is tightly regulated through the concerted interplay of sequential Lgl1-dependent global and cell intrinsic mechanisms.
AU - Beattie, Robert J
AU - Postiglione, Maria P
AU - Burnett, Laura
AU - Laukoter, Susanne
AU - Streicher, Carmen
AU - Pauler, Florian
AU - Xiao, Guanxi
AU - Klezovitch, Olga
AU - Vasioukhin, Valeri
AU - Ghashghaei, Troy
AU - Hippenmeyer, Simon
ID - 944
IS - 3
JF - Neuron
SN - 08966273
TI - Mosaic analysis with double markers reveals distinct sequential functions of Lgl1 in neural stem cells
VL - 94
ER -
TY - JOUR
AB - Cytosine methylation regulates essential genome functions across eukaryotes, but the fundamental question of whether nucleosomal or naked DNA is the preferred substrate of plant and animal methyltransferases remains unresolved. Here, we show that genetic inactivation of a single DDM1/Lsh family nucleosome remodeler biases methylation toward inter-nucleosomal linker DNA in Arabidopsis thaliana and mouse. We find that DDM1 enables methylation of DNA bound to the nucleosome, suggesting that nucleosome-free DNA is the preferred substrate of eukaryotic methyltransferases in vivo. Furthermore, we show that simultaneous mutation of DDM1 and linker histone H1 in Arabidopsis reproduces the strong linker-specific methylation patterns of species that diverged from flowering plants and animals over a billion years ago. Our results indicate that in the absence of remodeling, nucleosomes are strong barriers to DNA methyltransferases. Linker-specific methylation can evolve simply by breaking the connection between nucleosome remodeling and DNA methylation.
AU - Lyons, David B
AU - Zilberman, Daniel
ID - 9445
JF - eLife
TI - DDM1 and Lsh remodelers allow methylation of DNA wrapped in nucleosomes
VL - 6
ER -
TY - JOUR
AB - While chromosome-wide dosage compensation of the X chromosome has been found in many species, studies in ZW clades have indicated that compensation of the Z is more localized and/or incomplete. In the ZW Lepidoptera, some species show complete compensation of the Z chromosome, while others lack full equalization, but what drives these inconsistencies is unclear. Here, we compare patterns of male and female gene expression on the Z chromosome of two closely related butterfly species, Papilio xuthus and Papilio machaon, and in multiple tissues of two moths species, Plodia interpunctella and Bombyx mori, which were previously found to differ in the extent to which they equalize Z-linked gene expression between the sexes. We find that, while some species and tissues seem to have incomplete dosage compensation, this is in fact due to the accumulation of male-biased genes and the depletion of female-biased genes on the Z chromosome. Once this is accounted for, the Z chromosome is fully compensated in all four species, through the up-regulation of Z expression in females and in some cases additional down-regulation in males. We further find that both sex-biased genes and Z-linked genes have increased rates of expression divergence in this clade, and that this can lead to fast shifts in patterns of gene expression even between closely related species. Taken together, these results show that the uneven distribution of sex-biased genes on sex chromosomes can confound conclusions about dosage compensation and that Z chromosome-wide dosage compensation is not only possible but ubiquitous among Lepidoptera.
AU - Huylmans, Ann K
AU - Macon, Ariana
AU - Vicoso, Beatriz
ID - 945
IS - 10
JF - Molecular Biology and Evolution
SN - 07374038
TI - Global dosage compensation is ubiquitous in Lepidoptera, but counteracted by the masculinization of the Z chromosome
VL - 34
ER -
TY - JOUR
AB - Roots navigate through soil integrating environmental signals to orient their growth. The Arabidopsis root is a widely used model for developmental, physiological and cell biological studies. Live imaging greatly aids these efforts, but the horizontal sample position and continuous root tip displacement present significant difficulties. Here, we develop a confocal microscope setup for vertical sample mounting and integrated directional illumination. We present TipTracker – a custom software for automatic tracking of diverse moving objects usable on various microscope setups. Combined, this enables observation of root tips growing along the natural gravity vector over prolonged periods of time, as well as the ability to induce rapid gravity or light stimulation. We also track migrating cells in the developing zebrafish embryo, demonstrating the utility of this system in the acquisition of high-resolution data sets of dynamic samples. We provide detailed descriptions of the tools enabling the easy implementation on other microscopes.
AU - Von Wangenheim, Daniel
AU - Hauschild, Robert
AU - Fendrych, Matyas
AU - Barone, Vanessa
AU - Benková, Eva
AU - Friml, Jirí
ID - 946
JF - eLife
TI - Live tracking of moving samples in confocal microscopy for vertically grown roots
VL - 6
ER -
TY - JOUR
AB - Viewing the ways a living cell can organize its metabolism as the phase space of a physical system, regulation can be seen as the ability to reduce the entropy of that space by selecting specific cellular configurations that are, in some sense, optimal. Here we quantify the amount of regulation required to control a cell's growth rate by a maximum-entropy approach to the space of underlying metabolic phenotypes, where a configuration corresponds to a metabolic flux pattern as described by genome-scale models. We link the mean growth rate achieved by a population of cells to the minimal amount of metabolic regulation needed to achieve it through a phase diagram that highlights how growth suppression can be as costly (in regulatory terms) as growth enhancement. Moreover, we provide an interpretation of the inverse temperature β controlling maximum-entropy distributions based on the underlying growth dynamics. Specifically, we show that the asymptotic value of β for a cell population can be expected to depend on (i) the carrying capacity of the environment, (ii) the initial size of the colony, and (iii) the probability distribution from which the inoculum was sampled. Results obtained for E. coli and human cells are found to be remarkably consistent with empirical evidence.
AU - De Martino, Daniele
AU - Capuani, Fabrizio
AU - De Martino, Andrea
ID - 947
IS - 1
JF - Physical Review E Statistical Nonlinear and Soft Matter Physics
SN - 24700045
TI - Quantifying the entropic cost of cellular growth control
VL - 96
ER -
TY - CONF
AB - Two-player games on graphs are widely studied in formal methods as they model the interaction between a system and its environment. The game is played by moving a token throughout a graph to produce an infinite path. There are several common modes to determine how the players move the token through the graph; e.g., in turn-based games the players alternate turns in moving the token. We study the bidding mode of moving the token, which, to the best of our knowledge, has never been studied in infinite-duration games. Both players have separate budgets, which sum up to $1$. In each turn, a bidding takes place. Both players submit bids simultaneously, and a bid is legal if it does not exceed the available budget. The winner of the bidding pays his bid to the other player and moves the token. For reachability objectives, repeated bidding games have been studied and are called Richman games. There, a central question is the existence and computation of threshold budgets; namely, a value t\in [0,1] such that if\PO's budget exceeds $t$, he can win the game, and if\PT's budget exceeds 1-t, he can win the game. We focus on parity games and mean-payoff games. We show the existence of threshold budgets in these games, and reduce the problem of finding them to Richman games. We also determine the strategy-complexity of an optimal strategy. Our most interesting result shows that memoryless strategies suffice for mean-payoff bidding games.
AU - Avni, Guy
AU - Henzinger, Thomas A
AU - Chonev, Ventsislav K
ID - 950
SN - 1868-8969
TI - Infinite-duration bidding games
VL - 85
ER -
TY - JOUR
AB - Methylation in the bodies of active genes is common in animals and vascular plants. Evolutionary patterns indicate homeostatic functions for this type of methylation.
AU - Zilberman, Daniel
ID - 9506
IS - 1
JF - Genome Biology
SN - 1474-760X
TI - An evolutionary case for functional gene body methylation in plants and animals
VL - 18
ER -
TY - JOUR
AB - Dengue-suppressing Wolbachia strains are promising tools for arbovirus control, particularly as they have the potential to self-spread following local introductions. To test this, we followed the frequency of the transinfected Wolbachia strain wMel through Ae. aegypti in Cairns, Australia, following releases at 3 nonisolated locations within the city in early 2013. Spatial spread was analysed graphically using interpolation and by fitting a statistical model describing the position and width of the wave. For the larger 2 of the 3 releases (covering 0.97 km2 and 0.52 km2), we observed slow but steady spatial spread, at about 100–200 m per year, roughly consistent with theoretical predictions. In contrast, the smallest release (0.11 km2) produced erratic temporal and spatial dynamics, with little evidence of spread after 2 years. This is consistent with the prediction concerning fitness-decreasing Wolbachia transinfections that a minimum release area is needed to achieve stable local establishment and spread in continuous habitats. Our graphical and likelihood analyses produced broadly consistent estimates of wave speed and wave width. Spread at all sites was spatially heterogeneous, suggesting that environmental heterogeneity will affect large-scale Wolbachia transformations of urban mosquito populations. The persistence and spread of Wolbachia in release areas meeting minimum area requirements indicates the promise of successful large-scale population transfo
AU - Schmidt, Tom
AU - Barton, Nicholas H
AU - Rasic, Gordana
AU - Turley, Andrew
AU - Montgomery, Brian
AU - Iturbe Ormaetxe, Inaki
AU - Cook, Peter
AU - Ryan, Peter
AU - Ritchie, Scott
AU - Hoffmann, Ary
AU - O’Neill, Scott
AU - Turelli, Michael
ID - 951
IS - 5
JF - PLoS Biology
SN - 15449173
TI - Local introduction and heterogeneous spatial spread of dengue-suppressing Wolbachia through an urban population of Aedes Aegypti
VL - 15
ER -
TY - JOUR
AB - A novel strategy for controlling the spread of arboviral diseases such as dengue, Zika and chikungunya is to transform mosquito populations with virus-suppressing Wolbachia. In general, Wolbachia transinfected into mosquitoes induce fitness costs through lower viability or fecundity. These maternally inherited bacteria also produce a frequency-dependent advantage for infected females by inducing cytoplasmic incompatibility (CI), which kills the embryos produced by uninfected females mated to infected males. These competing effects, a frequency-dependent advantage and frequency-independent costs, produce bistable Wolbachia frequency dynamics. Above a threshold frequency, denoted pˆ, CI drives fitness-decreasing Wolbachia transinfections through local populations; but below pˆ, infection frequencies tend to decline to zero. If pˆ is not too high, CI also drives spatial spread once infections become established over sufficiently large areas. We illustrate how simple models provide testable predictions concerning the spatial and temporal dynamics of Wolbachia introductions, focusing on rate of spatial spread, the shape of spreading waves, and the conditions for initiating spread from local introductions. First, we consider the robustness of diffusion-based predictions to incorporating two important features of wMel-Aedes aegypti biology that may be inconsistent with the diffusion approximations, namely fast local dynamics induced by complete CI (i.e., all embryos produced from incompatible crosses die) and long-tailed, non-Gaussian dispersal. With complete CI, our numerical analyses show that long-tailed dispersal changes wave-width predictions only slightly; but it can significantly reduce wave speed relative to the diffusion prediction; it also allows smaller local introductions to initiate spatial spread. Second, we use approximations for pˆ and dispersal distances to predict the outcome of 2013 releases of wMel-infected Aedes aegypti in Cairns, Australia, Third, we describe new data from Ae. aegypti populations near Cairns, Australia that demonstrate long-distance dispersal and provide an approximate lower bound on pˆ for wMel in northeastern Australia. Finally, we apply our analyses to produce operational guidelines for efficient transformation of vector populations over large areas. We demonstrate that even very slow spatial spread, on the order of 10-20 m/month (as predicted), can produce area-wide population transformation within a few years following initial releases covering about 20-30% of the target area.
AU - Turelli, Michael
AU - Barton, Nicholas H
ID - 952
JF - Theoretical Population Biology
SN - 00405809
TI - Deploying dengue-suppressing Wolbachia: Robust models predict slow but effective spatial spread in Aedes aegypti
VL - 115
ER -
TY - JOUR
AB - The role of natural selection in the evolution of adaptive phenotypes has undergone constant probing by evolutionary biologists, employing both theoretical and empirical approaches. As Darwin noted, natural selection can act together with other processes, including random changes in the frequencies of phenotypic differences that are not under strong selection, and changes in the environment, which may reflect evolutionary changes in the organisms themselves. As understanding of genetics developed after 1900, the new genetic discoveries were incorporated into evolutionary biology. The resulting general principles were summarized by Julian Huxley in his 1942 book Evolution: the modern synthesis. Here, we examine how recent advances in genetics, developmental biology and molecular biology, including epigenetics, relate to today's understanding of the evolution of adaptations. We illustrate how careful genetic studies have repeatedly shown that apparently puzzling results in a wide diversity of organisms involve processes that are consistent with neo-Darwinism. They do not support important roles in adaptation for processes such as directed mutation or the inheritance of acquired characters, and therefore no radical revision of our understanding of the mechanism of adaptive evolution is needed.
AU - Charlesworth, Deborah
AU - Barton, Nicholas H
AU - Charlesworth, Brian
ID - 953
IS - 1855
JF - Proceedings of the Royal Society of London Series B Biological Sciences
TI - The sources of adaptive evolution
VL - 284
ER -
TY - JOUR
AB - Understanding the relation between genotype and phenotype remains a major challenge. The difficulty of predicting individual mutation effects, and particularly the interactions between them, has prevented the development of a comprehensive theory that links genotypic changes to their phenotypic effects. We show that a general thermodynamic framework for gene regulation, based on a biophysical understanding of protein-DNA binding, accurately predicts the sign of epistasis in a canonical cis-regulatory element consisting of overlapping RNA polymerase and repressor binding sites. Sign and magnitude of individual mutation effects are sufficient to predict the sign of epistasis and its environmental dependence. Thus, the thermodynamic model offers the correct null prediction for epistasis between mutations across DNA-binding sites. Our results indicate that a predictive theory for the effects of cis-regulatory mutations is possible from first principles, as long as the essential molecular mechanisms and the constraints these impose on a biological system are accounted for.
AU - Lagator, Mato
AU - Paixao, Tiago
AU - Barton, Nicholas H
AU - Bollback, Jonathan P
AU - Guet, Calin C
ID - 954
JF - eLife
SN - 2050084X
TI - On the mechanistic nature of epistasis in a canonical cis-regulatory element
VL - 6
ER -
TY - JOUR
AB - Gene expression is controlled by networks of regulatory proteins that interact specifically with external signals and DNA regulatory sequences. These interactions force the network components to co-evolve so as to continually maintain function. Yet, existing models of evolution mostly focus on isolated genetic elements. In contrast, we study the essential process by which regulatory networks grow: the duplication and subsequent specialization of network components. We synthesize a biophysical model of molecular interactions with the evolutionary framework to find the conditions and pathways by which new regulatory functions emerge. We show that specialization of new network components is usually slow, but can be drastically accelerated in the presence of regulatory crosstalk and mutations that promote promiscuous interactions between network components.
AU - Friedlander, Tamar
AU - Prizak, Roshan
AU - Barton, Nicholas H
AU - Tkacik, Gasper
ID - 955
IS - 1
JF - Nature Communications
SN - 20411723
TI - Evolution of new regulatory functions on biophysically realistic fitness landscapes
VL - 8
ER -
TY - JOUR
AB - We study a class of ergodic quantum Markov semigroups on finite-dimensional unital C⁎-algebras. These semigroups have a unique stationary state σ, and we are concerned with those that satisfy a quantum detailed balance condition with respect to σ. We show that the evolution on the set of states that is given by such a quantum Markov semigroup is gradient flow for the relative entropy with respect to σ in a particular Riemannian metric on the set of states. This metric is a non-commutative analog of the 2-Wasserstein metric, and in several interesting cases we are able to show, in analogy with work of Otto on gradient flows with respect to the classical 2-Wasserstein metric, that the relative entropy is strictly and uniformly convex with respect to the Riemannian metric introduced here. As a consequence, we obtain a number of new inequalities for the decay of relative entropy for ergodic quantum Markov semigroups with detailed balance.
AU - Carlen, Eric
AU - Maas, Jan
ID - 956
IS - 5
JF - Journal of Functional Analysis
SN - 00221236
TI - Gradient flow and entropy inequalities for quantum Markov semigroups with detailed balance
VL - 273
ER -
TY - CHAP
AB - Small molecule biosensors based on Forster resonance energy transfer (FRET) enable small molecule signaling to be monitored with high spatial and temporal resolution in complex cellular environments. FRET sensors can be constructed by fusing a pair of fluorescent proteins to a suitable recognition domain, such as a member of the solute-binding protein (SBP) superfamily. However, naturally occurring SBPs may be unsuitable for incorporation into FRET sensors due to their low thermostability, which may preclude imaging under physiological conditions, or because the positions of their N- and C-termini may be suboptimal for fusion of fluorescent proteins, which may limit the dynamic range of the resulting sensors. Here, we show how these problems can be overcome using ancestral protein reconstruction and circular permutation. Ancestral protein reconstruction, used as a protein engineering strategy, leverages phylogenetic information to improve the thermostability of proteins, while circular permutation enables the termini of an SBP to be repositioned to maximize the dynamic range of the resulting FRET sensor. We also provide a protocol for cloning the engineered SBPs into FRET sensor constructs using Golden Gate assembly and discuss considerations for in situ characterization of the FRET sensors.
AU - Clifton, Ben
AU - Whitfield, Jason
AU - Sanchez Romero, Inmaculada
AU - Herde, Michel
AU - Henneberger, Christian
AU - Janovjak, Harald L
AU - Jackson, Colin
ED - Stein, Viktor
ID - 957
SN - 10643745
T2 - Synthetic Protein Switches
TI - Ancestral protein reconstruction and circular permutation for improving the stability and dynamic range of FRET sensors
VL - 1596
ER -
TY - CHAP
AB - Biosensors that exploit Forster resonance energy transfer (FRET) can be used to visualize biological and physiological processes and are capable of providing detailed information in both spatial and temporal dimensions. In a FRET-based biosensor, substrate binding is associated with a change in the relative positions of two fluorophores, leading to a change in FRET efficiency that may be observed in the fluorescence spectrum. As a result, their design requires a ligand-binding protein that exhibits a conformational change upon binding. However, not all ligand-binding proteins produce responsive sensors upon conjugation to fluorescent proteins or dyes, and identifying the optimum locations for the fluorophores often involves labor-intensive iterative design or high-throughput screening. Combining the genetic fusion of a fluorescent protein to the ligand-binding protein with site-specific covalent attachment of a fluorescent dye can allow fine control over the positions of the two fluorophores, allowing the construction of very sensitive sensors. This relies upon the accurate prediction of the locations of the two fluorophores in bound and unbound states. In this chapter, we describe a method for computational identification of dye-attachment sites that allows the use of cysteine modification to attach synthetic dyes that can be paired with a fluorescent protein for the purposes of creating FRET sensors.
AU - Mitchell, Joshua
AU - Zhang, William
AU - Herde, Michel
AU - Henneberger, Christian
AU - Janovjak, Harald L
AU - O'Mara, Megan
AU - Jackson, Colin
ED - Stein, Viktor
ID - 958
SN - 10643745
T2 - Synthetic Protein Switches
TI - Method for developing optical sensors using a synthetic dye fluorescent protein FRET pair and computational modeling and assessment
VL - 1596
ER -
TY - JOUR
AB - In this work it is shown that scale-free tails in metabolic flux distributions inferred in stationary models are an artifact due to reactions involved in thermodynamically unfeasible cycles, unbounded by physical constraints and in principle able to perform work without expenditure of free energy. After implementing thermodynamic constraints by removing such loops, metabolic flux distributions scale meaningfully with the physical limiting factors, acquiring in turn a richer multimodal structure potentially leading to symmetry breaking while optimizing for objective functions.
AU - De Martino, Daniele
ID - 959
IS - 6
JF - Physical Review E Statistical Nonlinear and Soft Matter Physics
SN - 24700045
TI - Scales and multimodal flux distributions in stationary metabolic network models via thermodynamics
VL - 95
ER -
TY - JOUR
AB - The human cerebral cortex is the seat of our cognitive abilities and composed of an extraordinary number of neurons, organized in six distinct layers. The establishment of specific morphological and physiological features in individual neurons needs to be regulated with high precision. Impairments in the sequential developmental programs instructing corticogenesis lead to alterations in the cortical cytoarchitecture which is thought to represent the major underlying cause for several neurological disorders including neurodevelopmental and psychiatric diseases. In this review we discuss the role of cell polarity at sequential stages during cortex development. We first provide an overview of morphological cell polarity features in cortical neural stem cells and newly-born postmitotic neurons. We then synthesize a conceptual molecular and biochemical framework how cell polarity is established at the cellular level through a break in symmetry in nascent cortical projection neurons. Lastly we provide a perspective how the molecular mechanisms applying to single cells could be probed and integrated in an in vivo and tissue-wide context.
AU - Hansen, Andi H
AU - Düllberg, Christian F
AU - Mieck, Christine
AU - Loose, Martin
AU - Hippenmeyer, Simon
ID - 960
JF - Frontiers in Cellular Neuroscience
SN - 16625102
TI - Cell polarity in cerebral cortex development - cellular architecture shaped by biochemical networks
VL - 11
ER -
TY - CONF
AB - We present a new algorithm for model counting of a class of string constraints. In addition to the classic operation of concatenation, our class includes some recursively defined operations such as Kleene closure, and replacement of substrings. Additionally, our class also includes length constraints on the string expressions, which means, by requiring reasoning about numbers, that we face a multi-sorted logic. In the end, our string constraints are motivated by their use in programming for web applications. Our algorithm comprises two novel features: the ability to use a technique of (1) partial derivatives for constraints that are already in a solved form, i.e. a form where its (string) satisfiability is clearly displayed, and (2) non-progression, where cyclic reasoning in the reduction process may be terminated (thus allowing for the algorithm to look elsewhere). Finally, we experimentally compare our model counter with two recent works on model counting of similar constraints, SMC [18] and ABC [5], to demonstrate its superior performance.
AU - Trinh, Minh
AU - Chu, Duc Hiep
AU - Jaffar, Joxan
ED - Majumdar, Rupak
ED - Kunčak, Viktor
ID - 962
SN - 03029743
TI - Model counting for recursively-defined strings
VL - 10427
ER -
TY - CONF
AB - Network games are widely used as a model for selfish resource-allocation problems. In the classical model, each player selects a path connecting her source and target vertex. The cost of traversing an edge depends on the number of players that traverse it. Thus, it abstracts the fact that different users may use a resource at different times and for different durations, which plays an important role in defining the costs of the users in reality. For example, when transmitting packets in a communication network, routing traffic in a road network, or processing a task in a production system, the traversal of the network involves an inherent delay, and so sharing and congestion of resources crucially depends on time. We study timed network games , which add a time component to network games. Each vertex v in the network is associated with a cost function, mapping the load on v to the price that a player pays for staying in v for one time unit with this load. In addition, each edge has a guard, describing time intervals in which the edge can be traversed, forcing the players to spend time on vertices. Unlike earlier work that add a time component to network games, the time in our model is continuous and cannot be discretized. In particular, players have uncountably many strategies, and a game may have uncountably many pure Nash equilibria. We study properties of timed network games with cost-sharing or congestion cost functions: their stability, equilibrium inefficiency, and complexity. In particular, we show that the answer to the question whether we can restrict attention to boundary strategies, namely ones in which edges are traversed only at the boundaries of guards, is mixed.
AU - Avni, Guy
AU - Guha, Shibashis
AU - Kupferman, Orna
ID - 963
SN - 18688969
TI - Timed network games with clocks
VL - 83
ER -
TY - GEN
AB - Branching morphogenesis of the epithelial ureteric bud forms the renal collecting duct system and is critical for normal nephron number, while low nephron number is implicated in hypertension and renal disease. Ureteric bud growth and branching requires GDNF signaling from the surrounding mesenchyme to cells at the ureteric bud tips, via the Ret receptor tyrosine kinase and coreceptor Gfrα1; Ret signaling up-regulates transcription factors Etv4 and Etv5, which are also critical for branching. Despite extensive knowledge of the genetic control of these events, it is not understood, at the cellular level, how renal branching morphogenesis is achieved or how Ret signaling influences epithelial cell behaviors to promote this process. Analysis of chimeric embryos previously suggested a role for Ret signaling in promoting cell rearrangements in the nephric duct, but this method was unsuited to study individual cell behaviors during ureteric bud branching. Here, we use Mosaic Analysis with Double Markers (MADM), combined with organ culture and time-lapse imaging, to trace the movements and divisions of individual ureteric bud tip cells. We first examine wild-type clones and then Ret or Etv4 mutant/wild-type clones in which the mutant and wild-type sister cells are differentially and heritably marked by green and red fluorescent proteins. We find that, in normal kidneys, most individual tip cells behave as self-renewing progenitors, some of whose progeny remain at the tips while others populate the growing UB trunks. In Ret or Etv4 MADM clones, the wild-type cells generated at a UB tip are much more likely to remain at, or move to, the new tips during branching and elongation, while their Ret−/− or Etv4−/− sister cells tend to lag behind and contribute only to the trunks. By tracking successive mitoses in a cell lineage, we find that Ret signaling has little effect on proliferation, in contrast to its effects on cell movement. Our results show that Ret/Etv4 signaling promotes directed cell movements in the ureteric bud tips, and suggest a model in which these cell movements mediate branching morphogenesis.
AU - Riccio, Paul
AU - Cebrián, Christina
AU - Zong, Hui
AU - Hippenmeyer, Simon
AU - Costantini, Frank
ID - 9707
TI - Data from: Ret and Etv4 promote directed movements of progenitor cells during renal branching morphogenesis
ER -
TY - GEN
AB - Across the nervous system, certain population spiking patterns are observed far more frequently than others. A hypothesis about this structure is that these collective activity patterns function as population codewords–collective modes–carrying information distinct from that of any single cell. We investigate this phenomenon in recordings of ∼150 retinal ganglion cells, the retina’s output. We develop a novel statistical model that decomposes the population response into modes; it predicts the distribution of spiking activity in the ganglion cell population with high accuracy. We found that the modes represent localized features of the visual stimulus that are distinct from the features represented by single neurons. Modes form clusters of activity states that are readily discriminated from one another. When we repeated the same visual stimulus, we found that the same mode was robustly elicited. These results suggest that retinal ganglion cells’ collective signaling is endowed with a form of error-correcting code–a principle that may hold in brain areas beyond retina.
AU - Prentice, Jason
AU - Marre, Olivier
AU - Ioffe, Mark
AU - Loback, Adrianna
AU - Tkačik, Gašper
AU - Berry, Michael
ID - 9709
TI - Data from: Error-robust modes of the retinal population code
ER -
TY - GEN
AB - Mathematica notebooks used to generate figures.
AU - Etheridge, Alison
AU - Barton, Nicholas H
ID - 9842
TI - Data for: Establishment in a new habitat by polygenic adaptation
ER -
TY - GEN
AU - Nikolic, Nela
AU - Schreiber, Frank
AU - Dal Co, Alma
AU - Kiviet, Daniel
AU - Bergmiller, Tobias
AU - Littmann, Sten
AU - Kuypers, Marcel
AU - Ackermann, Martin
ID - 9844
TI - Source data for figures and tables
ER -
TY - GEN
AB - Estimates of 13 C-arabinose and 2 H-glucose uptake from the fractions of heavy isotopes measured in single cells
AU - Nikolic, Nela
AU - Schreiber, Frank
AU - Dal Co, Alma
AU - Kiviet, Daniel
AU - Bergmiller, Tobias
AU - Littmann, Sten
AU - Kuypers, Marcel
AU - Ackermann, Martin
ID - 9845
TI - Mathematical model
ER -
TY - GEN
AU - Nikolic, Nela
AU - Schreiber, Frank
AU - Dal Co, Alma
AU - Kiviet, Daniel
AU - Bergmiller, Tobias
AU - Littmann, Sten
AU - Kuypers, Marcel
AU - Ackermann, Martin
ID - 9846
TI - Supplementary methods
ER -
TY - GEN
AB - This text provides additional information about the model, a derivation of the analytic results in Eq (4), and details about simulations of an additional parameter set.
AU - Lukacisinova, Marta
AU - Novak, Sebastian
AU - Paixao, Tiago
ID - 9849
TI - Modelling and simulation details
ER -
TY - GEN
AB - In this text, we discuss how a cost of resistance and the possibility of lethal mutations impact our model.
AU - Lukacisinova, Marta
AU - Novak, Sebastian
AU - Paixao, Tiago
ID - 9850
TI - Extensions of the model
ER -
TY - GEN
AB - Based on the intuitive derivation of the dynamics of SIM allele frequency pM in the main text, we present a heuristic prediction for the long-term SIM allele frequencies with χ > 1 stresses and compare it to numerical simulations.
AU - Lukacisinova, Marta
AU - Novak, Sebastian
AU - Paixao, Tiago
ID - 9851
TI - Heuristic prediction for multiple stresses
ER -
TY - GEN
AB - We show how different combination strategies affect the fraction of individuals that are multi-resistant.
AU - Lukacisinova, Marta
AU - Novak, Sebastian
AU - Paixao, Tiago
ID - 9852
TI - Resistance frequencies for different combination strategies
ER -
TY - GEN
AB - Egg laying rates and infection loads of C. obscurior queens
AU - Giehr, Julia
AU - Grasse, Anna V
AU - Cremer, Sylvia
AU - Heinze, Jürgen
AU - Schrempf, Alexandra
ID - 9853
TI - Raw data from ant queens increase their reproductive efforts after pathogen infection
ER -
TY - GEN
AB - Includes derivation of optimal estimation algorithm, generalisation to non-poisson noise statistics, correlated input noise, and implementation of in a multi-layer neural network.
AU - Chalk, Matthew J
AU - Masset, Paul
AU - Gutkin, Boris
AU - Denève, Sophie
ID - 9855
TI - Supplementary appendix
ER -
TY - GEN
AU - Schmidt, Tom
AU - Barton, Nicholas H
AU - Rasic, Gordana
AU - Turley, Andrew
AU - Montgomery, Brian
AU - Iturbe Ormaetxe, Inaki
AU - Cook, Peter
AU - Ryan, Peter
AU - Ritchie, Scott
AU - Hoffmann, Ary
AU - O’Neill, Scott
AU - Turelli, Michael
ID - 9856
TI - Supporting Information concerning additional likelihood analyses and results
ER -
TY - GEN
AU - Schmidt, Tom
AU - Barton, Nicholas H
AU - Rasic, Gordana
AU - Turley, Andrew
AU - Montgomery, Brian
AU - Iturbe Ormaetxe, Inaki
AU - Cook, Peter
AU - Ryan, Peter
AU - Ritchie, Scott
AU - Hoffmann, Ary
AU - O’Neill, Scott
AU - Turelli, Michael
ID - 9857
TI - Supporting information concerning observed wMel frequencies and analyses of habitat variables
ER -
TY - GEN
AU - Schmidt, Tom
AU - Barton, Nicholas H
AU - Rasic, Gordana
AU - Turley, Andrew
AU - Montgomery, Brian
AU - Iturbe Ormaetxe, Inaki
AU - Cook, Peter
AU - Ryan, Peter
AU - Ritchie, Scott
AU - Hoffmann, Ary
AU - O’Neill, Scott
AU - Turelli, Michael
ID - 9858
TI - Excel file with data on mosquito densities, Wolbachia infection status and housing characteristics
ER -
TY - GEN
AB - Lists of all differentially expressed genes in the different priming-challenge treatments (compared to the fully naïve control; xlsx file). Relevant columns include the following: sample_1 and sample_2 – treatment groups being compared; Normalised FPKM sample_1 and sample_2 – FPKM of samples being compared; log2(fold_change) – log2(FPKM sample 2/FPKM sample 1), i.e. negative means sample 1 upregulated compared with sample 2, positive means sample 2 upregulated compared with sample 1; cuffdiff test_statistic – test statistic of differential expression test; p_value – p-value of differential expression test; q_value (FDR correction) – adjusted P-value of differential expression test. (XLSX 598 kb)
AU - Greenwood, Jenny
AU - Milutinovic, Barbara
AU - Peuß, Robert
AU - Behrens, Sarah
AU - Essar, Daniela
AU - Rosenstiel, Philip
AU - Schulenburg, Hinrich
AU - Kurtz, Joachim
ID - 9859
TI - Additional file 1: Table S1. of Oral immune priming with Bacillus thuringiensis induces a shift in the gene expression of Tribolium castaneum larvae
ER -
TY - GEN
AU - Greenwood, Jenny
AU - Milutinovic, Barbara
AU - Peuß, Robert
AU - Behrens, Sarah
AU - Essar, Daniela
AU - Rosenstiel, Philip
AU - Schulenburg, Hinrich
AU - Kurtz, Joachim
ID - 9860
TI - Additional file 5: Table S3. of Oral immune priming with Bacillus thuringiensis induces a shift in the gene expression of Tribolium castaneum larvae
ER -
TY - GEN
AB - As a consequence of its difference in copy number between males and females, the X chromosome is subject to unique evolutionary forces and gene regulatory mechanisms. Previous studies of Drosophila melanogaster have shown that the expression of X-linked, testis-specific reporter genes is suppressed in the male germline. However, it is not known whether this phenomenon is restricted to testis-expressed genes or if it is a more general property of genes with tissue-specific expression, which are also underrepresented on the X chromosome. To test this, we compared the expression of three tissue-specific reporter genes (ovary, accessory gland and Malpighian tubule) inserted at various autosomal and X-chromosomal locations. In contrast to testis-specific reporter genes, we found no reduction of X-linked expression in any of the other tissues. In accessory gland and Malpighian tubule, we detected higher expression of the X-linked reporter genes, which suggests that they are at least partially dosage compensated. We found no difference in the tissue-specificity of X-linked and autosomal reporter genes. These findings indicate that, in general, the X chromosome is not a detrimental environment for tissue-specific gene expression and that the suppression of X-linked expression is limited to the male germline.
AU - Argyridou, Eliza
AU - Huylmans, Ann K
AU - Königer, Annabella
AU - Parsch, John
ID - 9861
TI - Data from: X-linkage is not a general inhibitor of tissue-specific gene expression in Drosophila melanogaster
ER -
TY - JOUR
AB - The current-phase relation (CPR) of a Josephson junction (JJ) determines how the supercurrent evolves with the superconducting phase difference across the junction. Knowledge of the CPR is essential in order to understand the response of a JJ to various external parameters. Despite the rising interest in ultraclean encapsulated graphene JJs, the CPR of such junctions remains unknown. Here, we use a fully gate-tunable graphene superconducting quantum intereference device (SQUID) to determine the CPR of ballistic graphene JJs. Each of the two JJs in the SQUID is made with graphene encapsulated in hexagonal boron nitride. By independently controlling the critical current of the JJs, we can operate the SQUID either in a symmetric or asymmetric configuration. The highly asymmetric SQUID allows us to phase-bias one of the JJs and thereby directly obtain its CPR. The CPR is found to be skewed, deviating significantly from a sinusoidal form. The skewness can be tuned with the gate voltage and oscillates in antiphase with Fabry-Pérot resistance oscillations of the ballistic graphene cavity. We compare our experiments with tight-binding calculations that include realistic graphene-superconductor interfaces and find a good qualitative agreement.
AU - Nanda, Gaurav
AU - Aguilera Servin, Juan L
AU - Rakyta, Péter
AU - Kormányos, Andor
AU - Kleiner, Reinhold
AU - Koelle, Dieter
AU - Watanabe, Kazuo
AU - Taniguchi, Takashi
AU - Vandersypen, Lieven
AU - Goswami, Srijit
ID - 988
IS - 6
JF - Nano Letters
SN - 15306984
TI - Current-phase relation of ballistic graphene Josephson junctions
VL - 17
ER -
TY - CONF
AB - We present a generalized optimal transport model in which the mass-preserving constraint for the L2-Wasserstein distance is relaxed by introducing a source term in the continuity equation. The source term is also incorporated in the path energy by means of its squared L2-norm in time of a functional with linear growth in space. This extension of the original transport model enables local density modulations, which is a desirable feature in applications such as image warping and blending. A key advantage of the use of a functional with linear growth in space is that it allows for singular sources and sinks, which can be supported on points or lines. On a technical level, the L2-norm in time ensures a disintegration of the source in time, which we use to obtain the well-posedness of the model and the existence of geodesic paths. The numerical discretization is based on the proximal splitting approach [18] and selected numerical test cases show the potential of the proposed approach. Furthermore, the approach is applied to the warping and blending of textures.
AU - Maas, Jan
AU - Rumpf, Martin
AU - Simon, Stefan
ED - Lauze, François
ED - Dong, Yiqiu
ED - Bjorholm Dahl, Anders
ID - 989
SN - 03029743
TI - Transport based image morphing with intensity modulation
VL - 10302
ER -
TY - JOUR
AB - Assortative mating is an important driver of speciation in populations with gene flow and is predicted to evolve under certain conditions in few-locus models. However, the evolution of assortment is less understood for mating based on quantitative traits, which are often characterized by high genetic variability and extensive linkage disequilibrium between trait loci. We explore this scenario for a two-deme model with migration, by considering a single polygenic trait subject to divergent viability selection across demes, as well as assortative mating and sexual selection within demes, and investigate how trait divergence is shaped by various evolutionary forces. Our analysis reveals the existence of sharp thresholds of assortment strength, at which divergence increases dramatically. We also study the evolution of assortment via invasion of modifiers of mate discrimination and show that the ES assortment strength has an intermediate value under a range of migration-selection parameters, even in diverged populations, due to subtle effects which depend sensitively on the extent of phenotypic variation within these populations. The evolutionary dynamics of the polygenic trait is studied using the hypergeometric and infinitesimal models. We further investigate the sensitivity of our results to the assumptions of the hypergeometric model, using individual-based simulations.
AU - Sachdeva, Himani
AU - Barton, Nicholas H
ID - 990
IS - 6
JF - Evolution; International Journal of Organic Evolution
SN - 00143820
TI - Divergence and evolution of assortative mating in a polygenic trait model of speciation with gene flow
VL - 71
ER -
TY - JOUR
AB - Synaptotagmin 7 (Syt7) was originally identified as a slow Ca2+ sensor for lysosome fusion, but its function at fast synapses is controversial. The paper by Luo and Südhof (2017) in this issue of Neuron shows that at the calyx of Held in the auditory brainstem Syt7 triggers asynchronous release during stimulus trains, resulting in reliable and temporally precise high-frequency transmission. Thus, a slow Ca2+ sensor contributes to the fast signaling properties of the calyx synapse.
AU - Chen, Chong
AU - Jonas, Peter M
ID - 991
IS - 4
JF - Neuron
SN - 08966273
TI - Synaptotagmins: That’s why so many
VL - 94
ER -
TY - THES
AB - An instance of the Constraint Satisfaction Problem (CSP) is given by a finite set of
variables, a finite domain of labels, and a set of constraints, each constraint acting on
a subset of the variables. The goal is to find an assignment of labels to its variables
that satisfies all constraints (or decide whether one exists). If we allow more general
“soft” constraints, which come with (possibly infinite) costs of particular assignments,
we obtain instances from a richer class called Valued Constraint Satisfaction Problem
(VCSP). There the goal is to find an assignment with minimum total cost.
In this thesis, we focus (assuming that P
6
=
NP) on classifying computational com-
plexity of CSPs and VCSPs under certain restricting conditions. Two results are the core
content of the work. In one of them, we consider VCSPs parametrized by a constraint
language, that is the set of “soft” constraints allowed to form the instances, and finish
the complexity classification modulo (missing pieces of) complexity classification for
analogously parametrized CSP. The other result is a generalization of Edmonds’ perfect
matching algorithm. This generalization contributes to complexity classfications in two
ways. First, it gives a new (largest known) polynomial-time solvable class of Boolean
CSPs in which every variable may appear in at most two constraints and second, it
settles full classification of Boolean CSPs with planar drawing (again parametrized by a
constraint language).
AU - Rolinek, Michal
ID - 992
TI - Complexity of constraint satisfaction
ER -
TY - JOUR
AB - In real-world applications, observations are often constrained to a small fraction of a system. Such spatial subsampling can be caused by the inaccessibility or the sheer size of the system, and cannot be overcome by longer sampling. Spatial subsampling can strongly bias inferences about a system’s aggregated properties. To overcome the bias, we derive analytically a subsampling scaling framework that is applicable to different observables, including distributions of neuronal avalanches, of number of people infected during an epidemic outbreak, and of node degrees. We demonstrate how to infer the correct distributions of the underlying full system, how to apply it to distinguish critical from subcritical systems, and how to disentangle subsampling and finite size effects. Lastly, we apply subsampling scaling to neuronal avalanche models and to recordings from developing neural networks. We show that only mature, but not young networks follow power-law scaling, indicating self-organization to criticality during development.
AU - Levina (Martius), Anna
AU - Priesemann, Viola
ID - 993
JF - Nature Communications
SN - 20411723
TI - Subsampling scaling
VL - 8
ER -
TY - JOUR
AB - The formation of vortices is usually considered to be the main mechanism of angular momentum disposal in superfluids. Recently, it was predicted that a superfluid can acquire angular momentum via an alternative, microscopic route -- namely, through interaction with rotating impurities, forming so-called `angulon quasiparticles' [Phys. Rev. Lett. 114, 203001 (2015)]. The angulon instabilities correspond to transfer of a small number of angular momentum quanta from the impurity to the superfluid, as opposed to vortex instabilities, where angular momentum is quantized in units of ℏ per atom. Furthermore, since conventional impurities (such as molecules) represent three-dimensional (3D) rotors, the angular momentum transferred is intrinsically 3D as well, as opposed to a merely planar rotation which is inherent to vortices. Herein we show that the angulon theory can explain the anomalous broadening of the spectroscopic lines observed for CH 3 and NH 3 molecules in superfluid helium nanodroplets, thereby providing a fingerprint of the emerging angulon instabilities in experiment.
AU - Cherepanov, Igor
AU - Lemeshko, Mikhail
ID - 994
IS - 3
JF - Physical Review Materials
TI - Fingerprints of angulon instabilities in the spectra of matrix-isolated molecules
VL - 1
ER -
TY - JOUR
AB - Recently it was shown that an impurity exchanging orbital angular momentum with a surrounding bath can be described in terms of the angulon quasiparticle [Phys. Rev. Lett. 118, 095301 (2017)]. The angulon consists of a quantum rotor dressed by a many-particle field of boson excitations, and can be formed out of, for example, a molecule or a nonspherical atom in superfluid helium, or out of an electron coupled to lattice phonons or a Bose condensate. Here we develop an approach to the angulon based on the path-integral formalism, which sets the ground for a systematic, perturbative treatment of the angulon problem. The resulting perturbation series can be interpreted in terms of Feynman diagrams, from which, in turn, one can derive a set of diagrammatic rules. These rules extend the machinery of the graphical theory of angular momentum - well known from theoretical atomic spectroscopy - to the case where an environment with an infinite number of degrees of freedom is present. In particular, we show that each diagram can be interpreted as a 'skeleton', which enforces angular momentum conservation, dressed by an additional many-body contribution. This connection between the angulon theory and the graphical theory of angular momentum is particularly important as it allows to systematically and substantially simplify the analytical representation of each diagram. In order to exemplify the technique, we calculate the 1- and 2-loop contributions to the angulon self-energy, the spectral function, and the quasiparticle weight. The diagrammatic theory we develop paves the way to investigate next-to-leading order quantities in a more compact way compared to the variational approaches.
AU - Bighin, Giacomo
AU - Lemeshko, Mikhail
ID - 995
IS - 8
JF - Physical Review B - Condensed Matter and Materials Physics
SN - 24699950
TI - Diagrammatic approach to orbital quantum impurities interacting with a many-particle environment
VL - 96
ER -