TY - GEN
AB - Recently there has been a significant effort to handle quantitative properties in formal verification and synthesis. While weighted automata over finite and infinite words provide a natural and flexible framework to express quantitative properties, perhaps surprisingly, some basic system properties such as average response time cannot be expressed using weighted automata, nor in any other know decidable formalism. In this work, we introduce nested weighted automata as a natural extension of weighted automata which makes it possible to express important quantitative properties such as average response time.
In nested weighted automata, a master automaton spins off and collects results from weighted slave automata, each of which computes a quantity along a finite portion of an infinite word. Nested weighted automata can be viewed as the quantitative analogue of monitor automata, which are used in run-time verification. We establish an almost complete decidability picture for the basic decision problems about nested weighted automata, and illustrate their applicability in several domains. In particular, nested weighted automata can be used to decide average response time properties.
AU - Chatterjee, Krishnendu
AU - Henzinger, Thomas A
AU - Otop, Jan
ID - 5436
SN - 2664-1690
TI - Nested weighted automata
ER -
TY - GEN
AB - We consider the core algorithmic problems related to verification of systems with respect to three classical quantitative properties, namely, the mean-payoff property, the ratio property, and the minimum initial credit for energy property.
The algorithmic problem given a graph and a quantitative property asks to compute the optimal value (the infimum value over all traces) from every node of the graph. We consider graphs with constant treewidth, and it is well-known that the control-flow graphs of most programs have constant treewidth. Let $n$ denote the number of nodes of a graph, $m$ the number of edges (for constant treewidth graphs $m=O(n)$) and $W$ the largest absolute value of the weights.
Our main theoretical results are as follows.
First, for constant treewidth graphs we present an algorithm that approximates the mean-payoff value within a multiplicative factor of $\epsilon$ in time $O(n \cdot \log (n/\epsilon))$ and linear space, as compared to the classical algorithms that require quadratic time. Second, for the ratio property we present an algorithm that for constant treewidth graphs works in time $O(n \cdot \log (|a\cdot b|))=O(n\cdot\log (n\cdot W))$, when the output is $\frac{a}{b}$, as compared to the previously best known algorithm with running time $O(n^2 \cdot \log (n\cdot W))$. Third, for the minimum initial credit problem we show that (i)~for general graphs the problem can be solved in $O(n^2\cdot m)$ time and the associated decision problem can be solved in $O(n\cdot m)$ time, improving the previous known $O(n^3\cdot m\cdot \log (n\cdot W))$ and $O(n^2 \cdot m)$ bounds, respectively; and (ii)~for constant treewidth graphs we present an algorithm that requires $O(n\cdot \log n)$ time, improving the previous known $O(n^4 \cdot \log (n \cdot W))$ bound.
We have implemented some of our algorithms and show that they present a significant speedup on standard benchmarks.
AU - Chatterjee, Krishnendu
AU - Ibsen-Jensen, Rasmus
AU - Pavlogiannis, Andreas
ID - 5437
SN - 2664-1690
TI - Faster algorithms for quantitative verification in constant treewidth graphs
ER -
TY - GEN
AB - The edit distance between two words w1, w2 is the minimal number of word operations (letter insertions, deletions, and substitutions) necessary to transform w1 to w2. The edit distance generalizes to languages L1, L2, where the edit distance is the minimal number k such that for every word from L1 there exists a word in L2 with edit distance at most k. We study the edit distance computation problem between pushdown automata and their subclasses.
The problem of computing edit distance to a pushdown automaton is undecidable, and in practice, the interesting question is to compute the edit distance from a pushdown automaton (the implementation, a standard model for programs with recursion) to a regular language (the specification). In this work, we present a complete picture of decidability and complexity for deciding whether, for a given threshold k, the edit distance from a pushdown automaton to a finite automaton is at most k.
AU - Chatterjee, Krishnendu
AU - Henzinger, Thomas A
AU - Ibsen-Jensen, Rasmus
AU - Otop, Jan
ID - 5438
SN - 2664-1690
TI - Edit distance for pushdown automata
ER -
TY - GEN
AB - The target discounted-sum problem is the following: Given a rational discount factor 0 < λ < 1 and three rational values a, b, and t, does there exist a finite or an infinite sequence w ε(a, b)∗ or w ε(a, b)w, such that Σ|w| i=0 w(i)λi equals t? The problem turns out to relate to many fields of mathematics and computer science, and its decidability question is surprisingly hard to solve. We solve the finite version of the problem, and show the hardness of the infinite version, linking it to various areas and open problems in mathematics and computer science: β-expansions, discounted-sum automata, piecewise affine maps, and generalizations of the Cantor set. We provide some partial results to the infinite version, among which are solutions to its restriction to eventually-periodic sequences and to the cases that λ λ 1/2 or λ = 1/n, for every n ε N. We use our results for solving some open problems on discounted-sum automata, among which are the exact-value problem for nondeterministic automata over finite words and the universality and inclusion problems for functional automata.
AU - Boker, Udi
AU - Henzinger, Thomas A
AU - Otop, Jan
ID - 5439
SN - 2664-1690
TI - The target discounted-sum problem
ER -
TY - GEN
AB - Evolution occurs in populations of reproducing individuals. The structure of the population affects the outcome of the evolutionary process. Evolutionary graph theory is a powerful approach to study this phenomenon. There are two graphs. The interaction graph specifies who interacts with whom for payoff in the context of evolution. The replacement graph specifies who competes with whom for reproduction. The vertices of the two graphs are the same, and each vertex corresponds to an individual of the population. The fitness (or the reproductive rate) is a non-negative number, and depends on the payoff. A key quantity is the fixation probability of a new mutant. It is defined as the probability that a newly introduced mutant (on a single vertex) generates a lineage of offspring which eventually takes over the entire population of resident individuals. The basic computational questions are as follows: (i) the qualitative question asks whether the fixation probability is positive; and (ii) the quantitative approximation question asks for an approximation of the fixation probability. Our main results are as follows: First, we consider a special case of the general problem, where the residents do not reproduce. We show that the qualitative question is NP-complete, and the quantitative approximation question is #P-complete, and the hardness results hold even in the special case where the interaction and the replacement graphs coincide. Second, we show that in general both the qualitative and the quantitative approximation questions are PSPACE-complete. The PSPACE-hardness result for quantitative approximation holds even when the fitness is always positive.
AU - Chatterjee, Krishnendu
AU - Ibsen-Jensen, Rasmus
AU - Nowak, Martin
ID - 5440
SN - 2664-1690
TI - The complexity of evolutionary games on graphs
ER -
TY - GEN
AB - We study algorithmic questions for concurrent systems where the transitions are labeled from a complete, closed semiring, and path properties are algebraic with semiring operations. The algebraic path properties can model dataflow analysis problems, the shortest path problem, and many other natural problems that arise in program analysis. We consider that each component of the concurrent system is a graph with constant treewidth, a property satisfied by the controlflow graphs of most programs. We allow for multiple possible queries, which arise naturally in demand driven dataflow analysis. The study of multiple queries allows us to consider the tradeoff between the resource usage of the one-time preprocessing and for each individual query. The traditional approach constructs the product graph of all components and applies the best-known graph algorithm on the product. In this approach, even the answer to a single query requires the transitive closure (i.e., the results of all possible queries), which provides no room for tradeoff between preprocessing and query time. Our main contributions are algorithms that significantly improve the worst-case running time of the traditional approach, and provide various tradeoffs depending on the number of queries. For example, in a concurrent system of two components, the traditional approach requires hexic time in the worst case for answering one query as well as computing the transitive closure, whereas we show that with one-time preprocessing in almost cubic time, each subsequent query can be answered in at most linear time, and even the transitive closure can be computed in almost quartic time. Furthermore, we establish conditional optimality results showing that the worst-case running time of our algorithms cannot be improved without achieving major breakthroughs in graph algorithms (i.e., improving the worst-case bound for the shortest path problem in general graphs). Preliminary experimental results show that our algorithms perform favorably on several benchmarks.
AU - Chatterjee, Krishnendu
AU - Ibsen-Jensen, Rasmus
AU - Goharshady, Amir
AU - Pavlogiannis, Andreas
ID - 5441
SN - 2664-1690
TI - Algorithms for algebraic path properties in concurrent systems of constant treewidth components
ER -
TY - GEN
AB - We study algorithmic questions for concurrent systems where the transitions are labeled from a complete, closed semiring, and path properties are algebraic with semiring operations. The algebraic path properties can model dataflow analysis problems, the shortest path problem, and many other natural properties that arise in program analysis.
We consider that each component of the concurrent system is a graph with constant treewidth, and it is known that the controlflow graphs of most programs have constant treewidth. We allow for multiple possible queries, which arise naturally in demand driven dataflow analysis problems (e.g., alias analysis). The study of multiple queries allows us to consider the tradeoff between the resource usage of the \emph{one-time} preprocessing and for \emph{each individual} query. The traditional approaches construct the product graph of all components and apply the best-known graph algorithm on the product. In the traditional approach, even the answer to a single query requires the transitive closure computation (i.e., the results of all possible queries), which provides no room for tradeoff between preprocessing and query time.
Our main contributions are algorithms that significantly improve the worst-case running time of the traditional approach, and provide various tradeoffs depending on the number of queries. For example, in a concurrent system of two components, the traditional approach requires hexic time in the worst case for answering one query as well as computing the transitive closure, whereas we show that with one-time preprocessing in almost cubic time,
each subsequent query can be answered in at most linear time, and even the transitive closure can be computed in almost quartic time. Furthermore, we establish conditional optimality results that show that the worst-case running times of our algorithms cannot be improved without achieving major breakthroughs in graph algorithms (such as improving
the worst-case bounds for the shortest path problem in general graphs whose current best-known bound has not been improved in five decades). Finally, we provide a prototype implementation of our algorithms which significantly outperforms the existing algorithmic methods on several benchmarks.
AU - Anonymous, 1
AU - Anonymous, 2
AU - Anonymous, 3
AU - Anonymous, 4
ID - 5442
SN - 2664-1690
TI - Algorithms for algebraic path properties in concurrent systems of constant treewidth components
ER -
TY - GEN
AB - POMDPs are standard models for probabilistic planning problems, where an agent interacts with an uncertain environment. We study the problem of almost-sure reachability, where given a set of target states, the question is to decide whether there is a policy to ensure that the target set is reached with probability 1 (almost-surely). While in general the problem is EXPTIME-complete, in many practical cases policies with a small amount of memory suffice. Moreover, the existing solution to the problem is explicit, which first requires to construct explicitly an exponential reduction to a belief-support MDP. In this work, we first study the existence of observation-stationary strategies, which is NP-complete, and then small-memory strategies. We present a symbolic algorithm by an efficient encoding to SAT and using a SAT solver for the problem. We report experimental results demonstrating the scalability of our symbolic (SAT-based) approach.
AU - Chatterjee, Krishnendu
AU - Chmelik, Martin
AU - Davies, Jessica
ID - 5443
SN - 2664-1690
TI - A symbolic SAT-based algorithm for almost-sure reachability with small strategies in POMDPs
ER -
TY - GEN
AB - A comprehensive understanding of the clonal evolution of cancer is critical for understanding neoplasia. Genome-wide sequencing data enables evolutionary studies at unprecedented depth. However, classical phylogenetic methods often struggle with noisy sequencing data of impure DNA samples and fail to detect subclones that have different evolutionary trajectories. We have developed a tool, called Treeomics, that allows us to reconstruct the phylogeny of a cancer with commonly available sequencing technologies. Using Bayesian inference and Integer Linear Programming, robust phylogenies consistent with the biological processes underlying cancer evolution were obtained for pancreatic, ovarian, and prostate cancers. Furthermore, Treeomics correctly identified sequencing artifacts such as those resulting from low statistical power; nearly 7% of variants were misclassified by conventional statistical methods. These artifacts can skew phylogenies by creating illusory tumor heterogeneity among distinct samples. Importantly, we show that the evolutionary trees generated with Treeomics are mathematically optimal.
AU - Reiter, Johannes
AU - Makohon-Moore, Alvin
AU - Gerold, Jeffrey
AU - Bozic, Ivana
AU - Chatterjee, Krishnendu
AU - Iacobuzio-Donahue, Christine
AU - Vogelstein, Bert
AU - Nowak, Martin
ID - 5444
SN - 2664-1690
TI - Reconstructing robust phylogenies of metastatic cancers
ER -
TY - DATA
AB - This repository contains the experimental part of the CAV 2015 publication Counterexample Explanation by Learning Small Strategies in Markov Decision Processes.
We extended the probabilistic model checker PRISM to represent strategies of Markov Decision Processes as Decision Trees.
The archive contains a java executable version of the extended tool (prism_dectree.jar) together with a few examples of the PRISM benchmark library.
To execute the program, please have a look at the README.txt, which provides instructions and further information on the archive.
The archive contains scripts that (if run often enough) reproduces the data presented in the publication.
AU - Fellner, Andreas
ID - 5549
KW - Markov Decision Process
KW - Decision Tree
KW - Probabilistic Verification
KW - Counterexample Explanation
TI - Experimental part of CAV 2015 publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes
ER -
TY - JOUR
AB - Parasitism creates selection for resistance mechanisms in host populations and is hypothesized to promote increased host evolvability. However, the influence of these traits on host evolution when parasites are no longer present is unclear. We used experimental evolution and whole-genome sequencing of Escherichia coli to determine the effects of past and present exposure to parasitic viruses (phages) on the spread of mutator alleles, resistance, and bacterial competitive fitness. We found that mutator alleles spread rapidly during adaptation to any of four different phage species, and this pattern was even more pronounced with multiple phages present simultaneously. However, hypermutability did not detectably accelerate adaptation in the absence of phages and recovery of fitness costs associated with resistance. Several lineages evolved phage resistance through elevated mucoidy, and during subsequent evolution in phage-free conditions they rapidly reverted to nonmucoid, phage-susceptible phenotypes. Genome sequencing revealed that this phenotypic reversion was achieved by additional genetic changes rather than by genotypic reversion of the initial resistance mutations. Insertion sequence (IS) elements played a key role in both the acquisition of resistance and adaptation in the absence of parasites; unlike single nucleotide polymorphisms, IS insertions were not more frequent in mutator lineages. Our results provide a genetic explanation for rapid reversion of mucoidy, a phenotype observed in other bacterial species including human pathogens. Moreover, this demonstrates that the types of genetic change underlying adaptation to fitness costs, and consequently the impact of evolvability mechanisms such as increased point-mutation rates, depend critically on the mechanism of resistance.
AU - Wielgoss, Sébastien
AU - Bergmiller, Tobias
AU - Bischofberger, Anna M.
AU - Hall, Alex R.
ID - 5749
IS - 3
JF - Molecular Biology and Evolution
SN - 0737-4038
TI - Adaptation to Parasites and Costs of Parasite Resistance in Mutator and Nonmutator Bacteria
VL - 33
ER -
TY - JOUR
AB - The theory of population genetics and evolutionary computation have been evolving separately for nearly 30 years. Many results have been independently obtained in both fields and many others are unique to its respective field. We aim to bridge this gap by developing a unifying framework for evolutionary processes that allows both evolutionary algorithms and population genetics models to be cast in the same formal framework. The framework we present here decomposes the evolutionary process into its several components in order to facilitate the identification of similarities between different models. In particular, we propose a classification of evolutionary operators based on the defining properties of the different components. We cast several commonly used operators from both fields into this common framework. Using this, we map different evolutionary and genetic algorithms to different evolutionary regimes and identify candidates with the most potential for the translation of results between the fields. This provides a unified description of evolutionary processes and represents a stepping stone towards new tools and results to both fields.
AU - Paixao, Tiago
AU - Badkobeh, Golnaz
AU - Barton, Nicholas H
AU - Çörüş, Doğan
AU - Dang, Duccuong
AU - Friedrich, Tobias
AU - Lehre, Per
AU - Sudholt, Dirk
AU - Sutton, Andrew
AU - Trubenova, Barbora
ID - 1542
JF - Journal of Theoretical Biology
TI - Toward a unifying framework for evolutionary processes
VL - 383
ER -
TY - CHAP
AB - Cell division in prokaryotes and eukaryotes is commonly initiated by the well-controlled binding of proteins to the cytoplasmic side of the cell membrane. However, a precise characterization of the spatiotemporal dynamics of membrane-bound proteins is often difficult to achieve in vivo. Here, we present protocols for the use of supported lipid bilayers to rebuild the cytokinetic machineries of cells with greatly different dimensions: the bacterium Escherichia coli and eggs of the vertebrate Xenopus laevis. Combined with total internal reflection fluorescence microscopy, these experimental setups allow for precise quantitative analyses of membrane-bound proteins. The protocols described to obtain glass-supported membranes from bacterial and vertebrate lipids can be used as starting points for other reconstitution experiments. We believe that similar biochemical assays will be instrumental to study the biochemistry and biophysics underlying a variety of complex cellular tasks, such as signaling, vesicle trafficking, and cell motility.
AU - Nguyen, Phuong
AU - Field, Christine
AU - Groen, Aaron
AU - Mitchison, Timothy
AU - Loose, Martin
ID - 1544
T2 - Building a Cell from its Components Parts
TI - Using supported bilayers to study the spatiotemporal organization of membrane-bound proteins
VL - 128
ER -
TY - JOUR
AB - Synaptic efficacy and precision are influenced by the coupling of voltage-gated Ca2+ channels (VGCCs) to vesicles. But because the topography of VGCCs and their proximity to vesicles is unknown, a quantitative understanding of the determinants of vesicular release at nanometer scale is lacking. To investigate this, we combined freeze-fracture replica immunogold labeling of Cav2.1 channels, local [Ca2+] imaging, and patch pipette perfusion of EGTA at the calyx of Held. Between postnatal day 7 and 21, VGCCs formed variable sized clusters and vesicular release became less sensitive to EGTA, whereas fixed Ca2+ buffer properties remained constant. Experimentally constrained reaction-diffusion simulations suggest that Ca2+ sensors for vesicular release are located at the perimeter of VGCC clusters (<30nm) and predict that VGCC number per cluster determines vesicular release probability without altering release time course. This "perimeter release model" provides a unifying framework accounting for developmental changes in both synaptic efficacy and time course.
AU - Nakamura, Yukihiro
AU - Harada, Harumi
AU - Kamasawa, Naomi
AU - Matsui, Ko
AU - Rothman, Jason
AU - Shigemoto, Ryuichi
AU - Silver, R Angus
AU - Digregorio, David
AU - Takahashi, Tomoyuki
ID - 1546
IS - 1
JF - Neuron
TI - Nanoscale distribution of presynaptic Ca2+ channels and its impact on vesicular release during development
VL - 85
ER -
TY - JOUR
AB - Let G be a graph on the vertex set V(G) = {x1,…,xn} with the edge set E(G), and let R = K[x1,…, xn] be the polynomial ring over a field K. Two monomial ideals are associated to G, the edge ideal I(G) generated by all monomials xixj with {xi,xj} ∈ E(G), and the vertex cover ideal IG generated by monomials ∏xi∈Cxi for all minimal vertex covers C of G. A minimal vertex cover of G is a subset C ⊂ V(G) such that each edge has at least one vertex in C and no proper subset of C has the same property. Indeed, the vertex cover ideal of G is the Alexander dual of the edge ideal of G. In this paper, for an unmixed bipartite graph G we consider the lattice of vertex covers LG and we explicitly describe the minimal free resolution of the ideal associated to LG which is exactly the vertex cover ideal of G. Then we compute depth, projective dimension, regularity and extremal Betti numbers of R/I(G) in terms of the associated lattice.
AU - Mohammadi, Fatemeh
AU - Moradi, Somayeh
ID - 1547
IS - 3
JF - Bulletin of the Korean Mathematical Society
TI - Resolution of unmixed bipartite graphs
VL - 52
ER -
TY - JOUR
AB - Reproduction within a host and transmission to the next host are crucial for the virulence and fitness of pathogens. Nevertheless, basic knowledge about such parameters is often missing from the literature, even for well-studied bacteria, such as Bacillus thuringiensis, an endospore-forming insect pathogen, which infects its hosts via the oral route. To characterize bacterial replication success, we made use of an experimental oral infection system for the red flour beetle Tribolium castaneum and developed a flow cytometric assay for the quantification of both spore ingestion by the individual beetle larvae and the resulting spore load after bacterial replication and resporulation within cadavers. On average, spore numbers increased 460-fold, showing that Bacillus thuringiensis grows and replicates successfully in insect cadavers. By inoculating cadaver-derived spores and spores from bacterial stock cultures into nutrient medium, we next investigated outgrowth characteristics of vegetative cells and found that cadaver- derived bacteria showed reduced growth compared to bacteria from the stock cultures. Interestingly, this reduced growth was a consequence of inhibited spore germination, probably originating from the host and resulting in reduced host mortality in subsequent infections by cadaver-derived spores. Nevertheless, we further showed that Bacillus thuringiensis transmission was possible via larval cannibalism when no other food was offered. These results contribute to our understanding of the ecology of Bacillus thuringiensis as an insect pathogen.
AU - Milutinovic, Barbara
AU - Höfling, Christina
AU - Futo, Momir
AU - Scharsack, Jörn
AU - Kurtz, Joachim
ID - 1548
IS - 23
JF - Applied and Environmental Microbiology
TI - Infection of Tribolium castaneum with Bacillus thuringiensis: Quantification of bacterial replication within cadavers, transmission via cannibalism, and inhibition of spore germination
VL - 81
ER -
TY - CHAP
AB - Nature has incorporated small photochromic molecules, colloquially termed 'photoswitches', in photoreceptor proteins to sense optical cues in photo-taxis and vision. While Nature's ability to employ light-responsive functionalities has long been recognized, it was not until recently that scientists designed, synthesized and applied synthetic photochromes to manipulate many of which open rapidly and locally in their native cell types, biological processes with the temporal and spatial resolution of light. Ion channels in particular have come to the forefront of proteins that can be put under the designer control of synthetic photochromes. Photochromic ion channel controllers are comprised of three classes, photochromic soluble ligands (PCLs), photochromic tethered ligands (PTLs) and photochromic crosslinkers (PXs), and in each class ion channel functionality is controlled through reversible changes in photochrome structure. By acting as light-dependent ion channel agonists, antagonist or modulators, photochromic controllers effectively converted a wide range of ion channels, including voltage-gated ion channels, 'leak channels', tri-, tetra- and pentameric ligand-gated ion channels, and temperaturesensitive ion channels, into man-made photoreceptors. Control by photochromes can be reversible, unlike in the case of 'caged' compounds, and non-invasive with high spatial precision, unlike pharmacology and electrical manipulation. Here, we introduce design principles of emerging photochromic molecules that act on ion channels and discuss the impact that these molecules are beginning to have on ion channel biophysics and neuronal physiology.
AU - Mckenzie, Catherine
AU - Sanchez Romero, Inmaculada
AU - Janovjak, Harald L
ID - 1549
SN - 978-1-4939-2844-6
T2 - Novel chemical tools to study ion channel biology
TI - Flipping the photoswitch: Ion channels under light control
VL - 869
ER -
TY - JOUR
AB - The medial ganglionic eminence (MGE) gives rise to the majority of mouse forebrain interneurons. Here, we examine the lineage relationship among MGE-derived interneurons using a replication-defective retroviral library containing a highly diverse set of DNA barcodes. Recovering the barcodes from the mature progeny of infected progenitor cells enabled us to unambiguously determine their respective lineal relationship. We found that clonal dispersion occurs across large areas of the brain and is not restricted by anatomical divisions. As such, sibling interneurons can populate the cortex, hippocampus striatum, and globus pallidus. The majority of interneurons appeared to be generated from asymmetric divisions of MGE progenitor cells, followed by symmetric divisions within the subventricular zone. Altogether, our findings uncover that lineage relationships do not appear to determine interneuron allocation to particular regions. As such, it is likely that clonally related interneurons have considerable flexibility as to the particular forebrain circuits to which they can contribute.
AU - Mayer, Christian
AU - Jaglin, Xavier
AU - Cobbs, Lucy
AU - Bandler, Rachel
AU - Streicher, Carmen
AU - Cepko, Constance
AU - Hippenmeyer, Simon
AU - Fishell, Gord
ID - 1550
IS - 5
JF - Neuron
TI - Clonally related forebrain interneurons disperse broadly across both functional areas and structural boundaries
VL - 87
ER -
TY - JOUR
AB - Reciprocal coevolution between host and pathogen is widely seen as a major driver of evolution and biological innovation. Yet, to date, the underlying genetic mechanisms and associated trait functions that are unique to rapid coevolutionary change are generally unknown. We here combined experimental evolution of the bacterial biocontrol agent Bacillus thuringiensis and its nematode host Caenorhabditis elegans with large-scale phenotyping, whole genome analysis, and functional genetics to demonstrate the selective benefit of pathogen virulence and the underlying toxin genes during the adaptation process. We show that: (i) high virulence was specifically favoured during pathogen–host coevolution rather than pathogen one-sided adaptation to a nonchanging host or to an environment without host; (ii) the pathogen genotype BT-679 with known nematocidal toxin genes and high virulence specifically swept to fixation in all of the independent replicate populations under coevolution but only some under one-sided adaptation; (iii) high virulence in the BT-679-dominated populations correlated with elevated copy numbers of the plasmid containing the nematocidal toxin genes; (iv) loss of virulence in a toxin-plasmid lacking BT-679 isolate was reconstituted by genetic reintroduction or external addition of the toxins.We conclude that sustained coevolution is distinct from unidirectional selection in shaping the pathogen's genome and life history characteristics. To our knowledge, this study is the first to characterize the pathogen genes involved in coevolutionary adaptation in an animal host–pathogen interaction system.
AU - El Masri, Leila
AU - Branca, Antoine
AU - Sheppard, Anna
AU - Papkou, Andrei
AU - Laehnemann, David
AU - Guenther, Patrick
AU - Prahl, Swantje
AU - Saebelfeld, Manja
AU - Hollensteiner, Jacqueline
AU - Liesegang, Heiko
AU - Brzuszkiewicz, Elzbieta
AU - Daniel, Rolf
AU - Michiels, Nico
AU - Schulte, Rebecca
AU - Kurtz, Joachim
AU - Rosenstiel, Philip
AU - Telschow, Arndt
AU - Bornberg Bauer, Erich
AU - Schulenburg, Hinrich
ID - 1551
IS - 6
JF - PLoS Biology
TI - Host–pathogen coevolution: The selective advantage of Bacillus thuringiensis virulence and its cry toxin genes
VL - 13
ER -
TY - JOUR
AB - The visualization of hormonal signaling input and output is key to understanding how multicellular development is regulated. The plant signaling molecule auxin triggers many growth and developmental responses, but current tools lack the sensitivity or precision to visualize these. We developed a set of fluorescent reporters that allow sensitive and semiquantitative readout of auxin responses at cellular resolution in Arabidopsis thaliana. These generic tools are suitable for any transformable plant species.
AU - Liao, Cheyang
AU - Smet, Wouter
AU - Brunoud, Géraldine
AU - Yoshida, Saiko
AU - Vernoux, Teva
AU - Weijers, Dolf
ID - 1554
IS - 3
JF - Nature Methods
TI - Reporters for sensitive and quantitative measurement of auxin response
VL - 12
ER -
TY - JOUR
AB - We show that incorporating spatial dispersal of individuals into a simple vaccination epidemic model may give rise to a model that exhibits rich dynamical behavior. Using an SIVS (susceptible-infected-vaccinated-susceptible) model as a basis, we describe the spread of an infectious disease in a population split into two regions. In each subpopulation, both forward and backward bifurcations can occur. This implies that for disconnected regions the two-patch system may admit several steady states. We consider traveling between the regions and investigate the impact of spatial dispersal of individuals on the model dynamics. We establish conditions for the existence of multiple nontrivial steady states in the system, and we study the structure of the equilibria. The mathematical analysis reveals an unusually rich dynamical behavior, not normally found in the simple epidemic models. In addition to the disease-free equilibrium, eight endemic equilibria emerge from backward transcritical and saddle-node bifurcation points, forming an interesting bifurcation diagram. Stability of steady states, their bifurcations, and the global dynamics are investigated with analytical tools, numerical simulations, and rigorous set-oriented numerical computations.
AU - Knipl, Diána
AU - Pilarczyk, Pawel
AU - Röst, Gergely
ID - 1555
IS - 2
JF - SIAM Journal on Applied Dynamical Systems
TI - Rich bifurcation structure in a two patch vaccination model
VL - 14
ER -
TY - JOUR
AB - The elongator complex subunit 2 (ELP2) protein, one subunit of an evolutionarily conserved histone acetyltransferase complex, has been shown to participate in leaf patterning, plant immune and abiotic stress responses in Arabidopsis thaliana. Here, its role in root development was explored. Compared to the wild type, the elp2 mutant exhibited an accelerated differentiation of its root stem cells and cell division was more active in its quiescent centre (QC). The key transcription factors responsible for maintaining root stem cell and QC identity, such as AP2 transcription factors PLT1 (PLETHORA1) and PLT2 (PLETHORA2), GRAS transcription factors such as SCR (SCARECROW) and SHR (SHORT ROOT) and WUSCHEL-RELATED HOMEOBOX5 transcription factor WOX5, were all strongly down-regulated in the mutant. On the other hand, expression of the G2/M transition activator CYCB1 was substantially induced in elp2. The auxin efflux transporters PIN1 and PIN2 showed decreased protein levels and PIN1 also displayed mild polarity alterations in elp2, which resulted in a reduced auxin content in the root tip. Either the acetylation or methylation level of each of these genes differed between the mutant and the wild type, suggesting that the ELP2 regulation of root development involves the epigenetic modification of a range of transcription factors and other developmental regulators.
AU - Jia, Yuebin
AU - Tian, Huiyu
AU - Li, Hongjiang
AU - Yu, Qianqian
AU - Wang, Lei
AU - Friml, Jirí
AU - Ding, Zhaojun
ID - 1556
IS - 15
JF - Journal of Experimental Botany
TI - The Arabidopsis thaliana elongator complex subunit 2 epigenetically affects root development
VL - 66
ER -
TY - JOUR
AB - There are deep, yet largely unexplored, connections between computer science and biology. Both disciplines examine how information proliferates in time and space. Central results in computer science describe the complexity of algorithms that solve certain classes of problems. An algorithm is deemed efficient if it can solve a problem in polynomial time, which means the running time of the algorithm is a polynomial function of the length of the input. There are classes of harder problems for which the fastest possible algorithm requires exponential time. Another criterion is the space requirement of the algorithm. There is a crucial distinction between algorithms that can find a solution, verify a solution, or list several distinct solutions in given time and space. The complexity hierarchy that is generated in this way is the foundation of theoretical computer science. Precise complexity results can be notoriously difficult. The famous question whether polynomial time equals nondeterministic polynomial time (i.e., P = NP) is one of the hardest open problems in computer science and all of mathematics. Here, we consider simple processes of ecological and evolutionary spatial dynamics. The basic question is: What is the probability that a new invader (or a new mutant)will take over a resident population?We derive precise complexity results for a variety of scenarios. We therefore show that some fundamental questions in this area cannot be answered by simple equations (assuming that P is not equal to NP).
AU - Ibsen-Jensen, Rasmus
AU - Chatterjee, Krishnendu
AU - Nowak, Martin
ID - 1559
IS - 51
JF - PNAS
TI - Computational complexity of ecological and evolutionary spatial dynamics
VL - 112
ER -
TY - JOUR
AU - Gilson, Matthieu
AU - Savin, Cristina
AU - Zenke, Friedemann
ID - 1564
IS - 11
JF - Frontiers in Computational Neuroscience
TI - Editorial: Emergent neural computation from the interaction of different forms of plasticity
VL - 9
ER -
TY - JOUR
AB - Leptin is an adipokine produced by the adipose tissue regulating body weight through its appetite-suppressing effect. Besides being expressed in the hypothalamus and hippocampus, leptin receptors (ObRs) are also present in chromaffin cells of the adrenal medulla. In the present study, we report the effect of leptin on mouse chromaffin cell (MCC) functionality, focusing on cell excitability and catecholamine secretion. Acute application of leptin (1 nm) on spontaneously firing MCCs caused a slowly developing membrane hyperpolarization followed by complete blockade of action potential (AP) firing. This inhibitory effect at rest was abolished by the BK channel blocker paxilline (1 μm), suggesting the involvement of BK potassium channels. Single-channel recordings in 'perforated microvesicles' confirmed that leptin increased BK channel open probability without altering its unitary conductance. BK channel up-regulation was associated with the phosphoinositide 3-kinase (PI3K) signalling cascade because the PI3K specific inhibitor wortmannin (100 nm) fully prevented BK current increase. We also tested the effect of leptin on evoked AP firing and Ca2+-driven exocytosis. Although leptin preserves well-adapted AP trains of lower frequency, APs are broader and depolarization-evoked exocytosis is increased as a result of the larger size of the ready-releasable pool and higher frequency of vesicle release. The kinetics and quantal size of single secretory events remained unaltered. Leptin had no effect on firing and secretion in db-/db- mice lacking the ObR gene, confirming its specificity. In conclusion, leptin exhibits a dual action on MCC activity. It dampens AP firing at rest but preserves AP firing and increases catecholamine secretion during sustained stimulation, highlighting the importance of the adipo-adrenal axis in the leptin-mediated increase of sympathetic tone and catecholamine release.
AU - Gavello, Daniela
AU - Vandael, David H
AU - Gosso, Sara
AU - Carbone, Emilio
AU - Carabelli, Valentina
ID - 1565
IS - 22
JF - Journal of Physiology
TI - Dual action of leptin on rest-firing and stimulated catecholamine release via phosphoinositide 3-kinase-riven BK channel up-regulation in mouse chromaffin cells
VL - 593
ER -
TY - JOUR
AB - Deposits of misfolded proteins in the human brain are associated with the development of many neurodegenerative diseases. Recent studies show that these proteins have common traits even at the monomer level. Among them, a polyglutamine region that is present in huntingtin is known to exhibit a correlation between the length of the chain and the severity as well as the earliness of the onset of Huntington disease. Here, we apply bias exchange molecular dynamics to generate structures of polyglutamine expansions of several lengths and characterize the resulting independent conformations. We compare the properties of these conformations to those of the standard proteins, as well as to other homopolymeric tracts. We find that, similar to the previously studied polyvaline chains, the set of possible transient folds is much broader than the set of known-to-date folds, although the conformations have different structures. We show that the mechanical stability is not related to any simple geometrical characteristics of the structures. We demonstrate that long polyglutamine expansions result in higher mechanical stability than the shorter ones. They also have a longer life span and are substantially more prone to form knotted structures. The knotted region has an average length of 35 residues, similar to the typical threshold for most polyglutamine-related diseases. Similarly, changes in shape and mechanical stability appear once the total length of the peptide exceeds this threshold of 35 glutamine residues. We suggest that knotted conformers may also harm the cellular machinery and thus lead to disease.
AU - Gómez Sicilia, Àngel
AU - Sikora, Mateusz K
AU - Cieplak, Marek
AU - Carrión Vázquez, Mariano
ID - 1566
IS - 10
JF - PLoS Computational Biology
TI - An exploration of the universe of polyglutamine structures
VL - 11
ER -
TY - JOUR
AB - Spatial regulation of the plant hormone indole-3-acetic acid (IAA, or auxin) is essential for plant development. Auxin gradient establishment is mediated by polarly localized auxin transporters, including PIN-FORMED (PIN) proteins. Their localization and abundance at the plasma membrane are tightly regulated by endomembrane machinery, especially the endocytic and recycling pathways mediated by the ADP ribosylation factor guanine nucleotide exchange factor (ARF-GEF) GNOM. We assessed the role of the early secretory pathway in establishing PIN1 polarity in Arabidopsis thaliana by pharmacological and genetic approaches. We identified the compound endosidin 8 (ES8), which selectively interferes with PIN1 basal polarity without altering the polarity of apical proteins. ES8 alters the auxin distribution pattern in the root and induces a strong developmental phenotype, including reduced root length. The ARF-GEF- defective mutants gnom-like 1 ( gnl1-1) and gnom ( van7) are significantly resistant to ES8. The compound does not affect recycling or vacuolar trafficking of PIN1 but leads to its intracellular accumulation, resulting in loss of PIN1 basal polarity at the plasma membrane. Our data confirm a role for GNOM in endoplasmic reticulum (ER) - Golgi trafficking and reveal that a GNL1/GNOM-mediated early secretory pathway selectively regulates PIN1 basal polarity establishment in a manner essential for normal plant development.
AU - Doyle, Siamsa
AU - Haegera, Ash
AU - Vain, Thomas
AU - Rigala, Adeline
AU - Viotti, Corrado
AU - Łangowskaa, Małgorzata
AU - Maa, Qian
AU - Friml, Jirí
AU - Raikhel, Natasha
AU - Hickse, Glenn
AU - Robert, Stéphanie
ID - 1569
IS - 7
JF - PNAS
TI - An early secretory pathway mediated by gnom-like 1 and gnom is essential for basal polarity establishment in Arabidopsis thaliana
VL - 112
ER -
TY - JOUR
AB - Grounding autonomous behavior in the nervous system is a fundamental challenge for neuroscience. In particular, self-organized behavioral development provides more questions than answers. Are there special functional units for curiosity, motivation, and creativity? This paper argues that these features can be grounded in synaptic plasticity itself, without requiring any higher-level constructs. We propose differential extrinsic plasticity (DEP) as a new synaptic rule for self-learning systems and apply it to a number of complex robotic systems as a test case. Without specifying any purpose or goal, seemingly purposeful and adaptive rhythmic behavior is developed, displaying a certain level of sensorimotor intelligence. These surprising results require no systemspecific modifications of the DEP rule. They rather arise from the underlying mechanism of spontaneous symmetry breaking,which is due to the tight brain body environment coupling. The new synaptic rule is biologically plausible and would be an interesting target for neurobiological investigation. We also argue that this neuronal mechanism may have been a catalyst in natural evolution.
AU - Der, Ralf
AU - Martius, Georg S
ID - 1570
IS - 45
JF - PNAS
TI - Novel plasticity rule can explain the development of sensorimotor intelligence
VL - 112
ER -
TY - JOUR
AB - We consider the quantum ferromagnetic Heisenberg model in three dimensions, for all spins S ≥ 1/2. We rigorously prove the validity of the spin-wave approximation for the excitation spectrum, at the level of the first non-trivial contribution to the free energy at low temperatures. Our proof comes with explicit, constructive upper and lower bounds on the error term. It uses in an essential way the bosonic formulation of the model in terms of the Holstein-Primakoff representation. In this language, the model describes interacting bosons with a hard-core on-site repulsion and a nearest-neighbor attraction. This attractive interaction makes the lower bound on the free energy particularly tricky: the key idea there is to prove a differential inequality for the two-particle density, which is thereby shown to be smaller than the probability density of a suitably weighted two-particle random process on the lattice.
AU - Correggi, Michele
AU - Giuliani, Alessandro
AU - Seiringer, Robert
ID - 1572
IS - 1
JF - Communications in Mathematical Physics
TI - Validity of the spin-wave approximation for the free energy of the Heisenberg ferromagnet
VL - 339
ER -
TY - JOUR
AB - We present a new, simpler proof of the unconditional uniqueness of solutions to the cubic Gross-Pitaevskii hierarchy in ℝ3. One of the main tools in our analysis is the quantum de Finetti theorem. Our uniqueness result is equivalent to the one established in the celebrated works of Erdos, Schlein, and Yau.
AU - Chen, Thomas
AU - Hainzl, Christian
AU - Pavlović, Nataša
AU - Seiringer, Robert
ID - 1573
IS - 10
JF - Communications on Pure and Applied Mathematics
TI - Unconditional uniqueness for the cubic gross pitaevskii hierarchy via quantum de finetti
VL - 68
ER -
TY - JOUR
AB - Multiple plant developmental processes, such as lateral root development, depend on auxin distribution patterns that are in part generated by the PIN-formed family of auxin-efflux transporters. Here we propose that AUXIN RESPONSE FACTOR7 (ARF7) and the ARF7-regulated FOUR LIPS/MYB124 (FLP) transcription factors jointly form a coherent feed-forward motif that mediates the auxin-responsive PIN3 transcription in planta to steer the early steps of lateral root formation. This regulatory mechanism might endow the PIN3 circuitry with a temporal 'memory' of auxin stimuli, potentially maintaining and enhancing the robustness of the auxin flux directionality during lateral root development. The cooperative action between canonical auxin signalling and other transcription factors might constitute a general mechanism by which transcriptional auxin-sensitivity can be regulated at a tissue-specific level.
AU - Chen, Qian
AU - Liu, Yang
AU - Maere, Steven
AU - Lee, Eunkyoung
AU - Van Isterdael, Gert
AU - Xie, Zidian
AU - Xuan, Wei
AU - Lucas, Jessica
AU - Vassileva, Valya
AU - Kitakura, Saeko
AU - Marhavy, Peter
AU - Wabnik, Krzysztof T
AU - Geldner, Niko
AU - Benková, Eva
AU - Le, Jie
AU - Fukaki, Hidehiro
AU - Grotewold, Erich
AU - Li, Chuanyou
AU - Friml, Jirí
AU - Sack, Fred
AU - Beeckman, Tom
AU - Vanneste, Steffen
ID - 1574
JF - Nature Communications
TI - A coherent transcriptional feed-forward motif model for mediating auxin-sensitive PIN3 expression during lateral root development
VL - 6
ER -
TY - JOUR
AB - The immune response relies on the migration of leukocytes and on their ability to stop in precise anatomical locations to fulfil their task. How leukocyte migration and function are coordinated is unknown. Here we show that in immature dendritic cells, which patrol their environment by engulfing extracellular material, cell migration and antigen capture are antagonistic. This antagonism results from transient enrichment of myosin IIA at the cell front, which disrupts the back-to-front gradient of the motor protein, slowing down locomotion but promoting antigen capture. We further highlight that myosin IIA enrichment at the cell front requires the MHC class II-associated invariant chain (Ii). Thus, by controlling myosin IIA localization, Ii imposes on dendritic cells an intermittent antigen capture behaviour that might facilitate environment patrolling. We propose that the requirement for myosin II in both cell migration and specific cell functions may provide a general mechanism for their coordination in time and space.
AU - Chabaud, Mélanie
AU - Heuzé, Mélina
AU - Bretou, Marine
AU - Vargas, Pablo
AU - Maiuri, Paolo
AU - Solanes, Paola
AU - Maurin, Mathieu
AU - Terriac, Emmanuel
AU - Le Berre, Maël
AU - Lankar, Danielle
AU - Piolot, Tristan
AU - Adelstein, Robert
AU - Zhang, Yingfan
AU - Sixt, Michael K
AU - Jacobelli, Jordan
AU - Bénichou, Olivier
AU - Voituriez, Raphaël
AU - Piel, Matthieu
AU - Lennon Duménil, Ana
ID - 1575
JF - Nature Communications
TI - Cell migration and antigen capture are antagonistic processes coupled by myosin II in dendritic cells
VL - 6
ER -
TY - JOUR
AB - Gene expression is controlled primarily by interactions between transcription factor proteins (TFs) and the regulatory DNA sequence, a process that can be captured well by thermodynamic models of regulation. These models, however, neglect regulatory crosstalk: the possibility that noncognate TFs could initiate transcription, with potentially disastrous effects for the cell. Here, we estimate the importance of crosstalk, suggest that its avoidance strongly constrains equilibrium models of TF binding, and propose an alternative nonequilibrium scheme that implements kinetic proofreading to suppress erroneous initiation. This proposal is consistent with the observed covalent modifications of the transcriptional apparatus and predicts increased noise in gene expression as a trade-off for improved specificity. Using information theory, we quantify this trade-off to find when optimal proofreading architectures are favored over their equilibrium counterparts. Such architectures exhibit significant super-Poisson noise at low expression in steady state.
AU - Cepeda Humerez, Sarah A
AU - Rieckh, Georg
AU - Tkacik, Gasper
ID - 1576
IS - 24
JF - Physical Review Letters
TI - Stochastic proofreading mechanism alleviates crosstalk in transcriptional regulation
VL - 115
ER -
TY - JOUR
AB - Contrary to the pattern seen in mammalian sex chromosomes, where most Y-linked genes have X-linked homologs, the Drosophila X and Y chromosomes appear to be unrelated. Most of the Y-linked genes have autosomal paralogs, so autosome-to-Y transposition must be the main source of Drosophila Y-linked genes. Here we show how these genes were acquired. We found a previously unidentified gene (flagrante delicto Y, FDY) that originated from a recent duplication of the autosomal gene vig2 to the Y chromosome of Drosophila melanogaster. Four contiguous genes were duplicated along with vig2, but they became pseudogenes through the accumulation of deletions and transposable element insertions, whereas FDY remained functional, acquired testis-specific expression, and now accounts for ∼20% of the vig2-like mRNA in testis. FDY is absent in the closest relatives of D. melanogaster, and DNA sequence divergence indicates that the duplication to the Y chromosome occurred ∼2 million years ago. Thus, FDY provides a snapshot of the early stages of the establishment of a Y-linked gene and demonstrates how the Drosophila Y has been accumulating autosomal genes.
AU - Carvalho, Antonio
AU - Vicoso, Beatriz
AU - Russo, Claudia
AU - Swenor, Bonnielin
AU - Clark, Andrew
ID - 1577
IS - 40
JF - PNAS
TI - Birth of a new gene on the Y chromosome of Drosophila melanogaster
VL - 112
ER -
TY - JOUR
AB - We show that the Galois group of any Schubert problem involving lines in projective space contains the alternating group. This constitutes the largest family of enumerative problems whose Galois groups have been largely determined. Using a criterion of Vakil and a special position argument due to Schubert, our result follows from a particular inequality among Kostka numbers of two-rowed tableaux. In most cases, a combinatorial injection proves the inequality. For the remaining cases, we use the Weyl integral formulas to obtain an integral formula for these Kostka numbers. This rewrites the inequality as an integral, which we estimate to establish the inequality.
AU - Brooks, Christopher
AU - Martin Del Campo Sanchez, Abraham
AU - Sottile, Frank
ID - 1579
IS - 6
JF - Transactions of the American Mathematical Society
TI - Galois groups of Schubert problems of lines are at least alternating
VL - 367
ER -
TY - JOUR
AB - Synapsins (Syns) are an evolutionarily conserved family of presynaptic proteins crucial for the fine-tuning of synaptic function. A large amount of experimental evidences has shown that Syns are involved in the development of epileptic phenotypes and several mutations in Syn genes have been associated with epilepsy in humans and animal models. Syn mutations induce alterations in circuitry and neurotransmitter release, differentially affecting excitatory and inhibitory synapses, thus causing an excitation/inhibition imbalance in network excitability toward hyperexcitability that may be a determinant with regard to the development of epilepsy. Another approach to investigate epileptogenic mechanisms is to understand how silencing Syn affects the cellular behavior of single neurons and is associated with the hyperexcitable phenotypes observed in epilepsy. Here, we examined the functional effects of antisense-RNA inhibition of Syn expression on individually identified and isolated serotonergic cells of the Helix land snail. We found that Helix synapsin silencing increases cell excitability characterized by a slightly depolarized resting membrane potential, decreases the rheobase, reduces the threshold for action potential (AP) firing and increases the mean and instantaneous firing rates, with respect to control cells. The observed increase of Ca2+ and BK currents in Syn-silenced cells seems to be related to changes in the shape of the AP waveform. These currents sustain the faster spiking in Syn-deficient cells by increasing the after hyperpolarization and limiting the Na+ and Ca2+ channel inactivation during repetitive firing. This in turn speeds up the depolarization phase by reaching the AP threshold faster. Our results provide evidence that Syn silencing increases intrinsic cell excitability associated with increased Ca2+ and Ca2+-dependent BK currents in the absence of excitatory or inhibitory inputs.
AU - Brenes, Oscar
AU - Vandael, David H
AU - Carbone, Emilio
AU - Montarolo, Pier
AU - Ghirardi, Mirella
ID - 1580
JF - Neuroscience
TI - Knock-down of synapsin alters cell excitability and action potential waveform by potentiating BK and voltage gated Ca2 currents in Helix serotonergic neurons
VL - 311
ER -
TY - JOUR
AB - We investigate weighted straight skeletons from a geometric, graph-theoretical, and combinatorial point of view. We start with a thorough definition and shed light on some ambiguity issues in the procedural definition. We investigate the geometry, combinatorics, and topology of faces and the roof model, and we discuss in which cases a weighted straight skeleton is connected. Finally, we show that the weighted straight skeleton of even a simple polygon may be non-planar and may contain cycles, and we discuss under which restrictions on the weights and/or the input polygon the weighted straight skeleton still behaves similar to its unweighted counterpart. In particular, we obtain a non-procedural description and a linear-time construction algorithm for the straight skeleton of strictly convex polygons with arbitrary weights.
AU - Biedl, Therese
AU - Held, Martin
AU - Huber, Stefan
AU - Kaaser, Dominik
AU - Palfrader, Peter
ID - 1582
IS - 2
JF - Computational Geometry: Theory and Applications
TI - Weighted straight skeletons in the plane
VL - 48
ER -
TY - JOUR
AB - We study the characteristics of straight skeletons of monotone polygonal chains and use them to devise an algorithm for computing positively weighted straight skeletons of monotone polygons. Our algorithm runs in O(nlogn) time and O(n) space, where n denotes the number of vertices of the polygon.
AU - Biedl, Therese
AU - Held, Martin
AU - Huber, Stefan
AU - Kaaser, Dominik
AU - Palfrader, Peter
ID - 1583
IS - 2
JF - Information Processing Letters
TI - A simple algorithm for computing positively weighted straight skeletons of monotone polygons
VL - 115
ER -
TY - JOUR
AB - We investigate weighted straight skeletons from a geometric, graph-theoretical, and combinatorial point of view. We start with a thorough definition and shed light on some ambiguity issues in the procedural definition. We investigate the geometry, combinatorics, and topology of faces and the roof model, and we discuss in which cases a weighted straight skeleton is connected. Finally, we show that the weighted straight skeleton of even a simple polygon may be non-planar and may contain cycles, and we discuss under which restrictions on the weights and/or the input polygon the weighted straight skeleton still behaves similar to its unweighted counterpart. In particular, we obtain a non-procedural description and a linear-time construction algorithm for the straight skeleton of strictly convex polygons with arbitrary weights.
AU - Biedl, Therese
AU - Held, Martin
AU - Huber, Stefan
AU - Kaaser, Dominik
AU - Palfrader, Peter
ID - 1584
IS - 5
JF - Computational Geometry: Theory and Applications
TI - Reprint of: Weighted straight skeletons in the plane
VL - 48
ER -
TY - JOUR
AB - We investigate the quantum interference shifts between energetically close states, where the state structure is observed by laser spectroscopy. We report a compact and analytical expression that models the quantum interference induced shift for any admixture of circular polarization of the incident laser and angle of observation. An experimental scenario free of quantum interference can thus be predicted with this formula. Although this study is exemplified here for muonic deuterium, it can be applied to any other laser spectroscopy measurement of ns-n′p frequencies of a nonrelativistic atomic system, via an ns→n′p→n′′s scheme.
AU - Amaro, Pedro
AU - Fratini, Filippo
AU - Safari, Laleh
AU - Antognini, Aldo
AU - Indelicato, Paul
AU - Pohl, Randolf
AU - Santos, José
ID - 1587
IS - 6
JF - Physical Review A - Atomic, Molecular, and Optical Physics
TI - Quantum interference shifts in laser spectroscopy with elliptical polarization
VL - 92
ER -
TY - JOUR
AB - We investigate the dynamics of ferrofluidic wavy vortex flows in the counter-rotating Taylor-Couette system, with a focus on wavy flows with a mixture of the dominant azimuthal modes. Without external magnetic field flows are stable and pro-grade with respect to the rotation of the inner cylinder. More complex behaviors can arise when an axial or a transverse magnetic field is applied. Depending on the direction and strength of the field, multi-stable wavy states and bifurcations can occur. We uncover the phenomenon of flow pattern reversal as the strength of the magnetic field is increased through a critical value. In between the regimes of pro-grade and retrograde flow rotations, standing waves with zero angular velocities can emerge. A striking finding is that, under a transverse magnetic field, a second reversal in the flow pattern direction can occur, where the flow pattern evolves into pro-grade rotation again from a retrograde state. Flow reversal is relevant to intriguing phenomena in nature such as geomagnetic reversal. Our results suggest that, in ferrofluids, flow pattern reversal can be induced by varying a magnetic field in a controlled manner, which can be realized in laboratory experiments with potential applications in the development of modern fluid devices.
AU - Altmeyer, Sebastian
AU - Do, Younghae
AU - Lai, Ying
ID - 1589
JF - Scientific Reports
TI - Magnetic field induced flow pattern reversal in a ferrofluidic Taylor-Couette system
VL - 5
ER -
TY - CHAP
AB - The straight skeleton of a polygon is the geometric graph obtained by tracing the vertices during a mitered offsetting process. It is known that the straight skeleton of a simple polygon is a tree, and one can naturally derive directions on the edges of the tree from the propagation of the shrinking process. In this paper, we ask the reverse question: Given a tree with directed edges, can it be the straight skeleton of a polygon? And if so, can we find a suitable simple polygon? We answer these questions for all directed trees where the order of edges around each node is fixed.
AU - Aichholzer, Oswin
AU - Biedl, Therese
AU - Hackl, Thomas
AU - Held, Martin
AU - Huber, Stefan
AU - Palfrader, Peter
AU - Vogtenhuber, Birgit
ID - 1590
T2 - Graph Drawing and Network Visualization
TI - Representing directed trees as straight skeletons
VL - 9411
ER -
TY - JOUR
AB - Auxin participates in a multitude of developmental processes, as well as responses to environmental cues. Compared with other plant hormones, auxin exhibits a unique property, as it undergoes directional, cell-to-cell transport facilitated by plasma membrane-localized transport proteins. Among them, a prominent role has been ascribed to the PIN family of auxin efflux facilitators. PIN proteins direct polar auxin transport on account of their asymmetric subcellular localizations. In this review, we provide an overview of the multiple developmental roles of PIN proteins, including the atypical endoplasmic reticulum-localized members of the family, and look at the family from an evolutionary perspective. Next, we cover the cell biological and molecular aspects of PIN function, in particular the establishment of their polar subcellular localization. Hormonal and environmental inputs into the regulation of PIN action are summarized as well.
AU - Adamowski, Maciek
AU - Friml, Jirí
ID - 1591
IS - 1
JF - Plant Cell
TI - PIN-dependent auxin transport: Action, regulation, and evolution
VL - 27
ER -
TY - JOUR
AB - Plants are sessile organisms that are permanently restricted to their site of germination. To compensate for their lack of mobility, plants evolved unique mechanisms enabling them to rapidly react to ever changing environmental conditions and flexibly adapt their postembryonic developmental program. A prominent demonstration of this developmental plasticity is their ability to bend organs in order to reach the position most optimal for growth and utilization of light, nutrients, and other resources. Shortly after germination, dicotyledonous seedlings form a bended structure, the so-called apical hook, to protect the delicate shoot meristem and cotyledons from damage when penetrating through the soil. Upon perception of a light stimulus, the apical hook rapidly opens and the photomorphogenic developmental program is activated. After germination, plant organs are able to align their growth with the light source and adopt the most favorable orientation through bending, in a process named phototropism. On the other hand, when roots and shoots are diverted from their upright orientation, they immediately detect a change in the gravity vector and bend to maintain a vertical growth direction. Noteworthy, despite the diversity of external stimuli perceived by different plant organs, all plant tropic movements share a common mechanistic basis: differential cell growth. In our review, we will discuss the molecular principles underlying various tropic responses with the focus on mechanisms mediating the perception of external signals, transduction cascades and downstream responses that regulate differential cell growth and consequently, organ bending. In particular, we highlight common and specific features of regulatory pathways in control of the bending of organs and a role for the plant hormone auxin as a key regulatory component.
AU - Žádníková, Petra
AU - Smet, Dajo
AU - Zhu, Qiang
AU - Van Der Straeten, Dominique
AU - Benková, Eva
ID - 1593
IS - 4
JF - Frontiers in Plant Science
TI - Strategies of seedlings to overcome their sessile nature: Auxin in mobility control
VL - 6
ER -
TY - CONF
AB - A drawing of a graph G is radial if the vertices of G are placed on concentric circles C1, . . . , Ck with common center c, and edges are drawn radially: every edge intersects every circle centered at c at most once. G is radial planar if it has a radial embedding, that is, a crossing- free radial drawing. If the vertices of G are ordered or partitioned into ordered levels (as they are for leveled graphs), we require that the assignment of vertices to circles corresponds to the given ordering or leveling. We show that a graph G is radial planar if G has a radial drawing in which every two edges cross an even number of times; the radial embedding has the same leveling as the radial drawing. In other words, we establish the weak variant of the Hanani-Tutte theorem for radial planarity. This generalizes a result by Pach and Tóth.
AU - Fulek, Radoslav
AU - Pelsmajer, Michael
AU - Schaefer, Marcus
ID - 1595
TI - Hanani-Tutte for radial planarity
VL - 9411
ER -
TY - CONF
AB - Let C={C1,...,Cn} denote a collection of translates of a regular convex k-gon in the plane with the stacking order. The collection C forms a visibility clique if for everyi < j the intersection Ci and (Ci ∩ Cj)\⋃i<l<jCl =∅.elements that are stacked between them, i.e., We show that if C forms a visibility clique its size is bounded from above by O(k4) thereby improving the upper bound of 22k from the aforementioned paper. We also obtain an upper bound of 22(k/2)+2 on the size of a visibility clique for homothetes of a convex (not necessarily regular) k-gon.
AU - Fulek, Radoslav
AU - Radoičić, Radoš
ID - 1596
TI - Vertical visibility among parallel polygons in three dimensions
VL - 9411
ER -
TY - JOUR
AB - We consider Markov decision processes (MDPs) with specifications given as Büchi (liveness) objectives, and examine the problem of computing the set of almost-sure winning vertices such that the objective can be ensured with probability 1 from these vertices. We study for the first time the average-case complexity of the classical algorithm for computing the set of almost-sure winning vertices for MDPs with Büchi objectives. Our contributions are as follows: First, we show that for MDPs with constant out-degree the expected number of iterations is at most logarithmic and the average-case running time is linear (as compared to the worst-case linear number of iterations and quadratic time complexity). Second, for the average-case analysis over all MDPs we show that the expected number of iterations is constant and the average-case running time is linear (again as compared to the worst-case linear number of iterations and quadratic time complexity). Finally we also show that when all MDPs are equally likely, the probability that the classical algorithm requires more than a constant number of iterations is exponentially small.
AU - Chatterjee, Krishnendu
AU - Joglekar, Manas
AU - Shah, Nisarg
ID - 1598
IS - 3
JF - Theoretical Computer Science
TI - Average case analysis of the classical algorithm for Markov decision processes with Büchi objectives
VL - 573
ER -
TY - CONF
AB - We propose a flexible exchange format for ω-automata, as typically used in formal verification, and implement support for it in a range of established tools. Our aim is to simplify the interaction of tools, helping the research community to build upon other people’s work. A key feature of the format is the use of very generic acceptance conditions, specified by Boolean combinations of acceptance primitives, rather than being limited to common cases such as Büchi, Streett, or Rabin. Such flexibility in the choice of acceptance conditions can be exploited in applications, for example in probabilistic model checking, and furthermore encourages the development of acceptance-agnostic tools for automata manipulations. The format allows acceptance conditions that are either state-based or transition-based, and also supports alternating automata.
AU - Babiak, Tomáš
AU - Blahoudek, František
AU - Duret Lutz, Alexandre
AU - Klein, Joachim
AU - Kretinsky, Jan
AU - Mueller, Daniel
AU - Parker, David
AU - Strejček, Jan
ID - 1601
TI - The Hanoi omega-automata format
VL - 9206
ER -
TY - JOUR
AB - Interprocedural analysis is at the heart of numerous applications in programming languages, such as alias analysis, constant propagation, etc. Recursive state machines (RSMs) are standard models for interprocedural analysis. We consider a general framework with RSMs where the transitions are labeled from a semiring, and path properties are algebraic with semiring operations. RSMs with algebraic path properties can model interprocedural dataflow analysis problems, the shortest path problem, the most probable path problem, etc. The traditional algorithms for interprocedural analysis focus on path properties where the starting point is fixed as the entry point of a specific method. In this work, we consider possible multiple queries as required in many applications such as in alias analysis. The study of multiple queries allows us to bring in a very important algorithmic distinction between the resource usage of the one-time preprocessing vs for each individual query. The second aspect that we consider is that the control flow graphs for most programs have constant treewidth. Our main contributions are simple and implementable algorithms that supportmultiple queries for algebraic path properties for RSMs that have constant treewidth. Our theoretical results show that our algorithms have small additional one-time preprocessing, but can answer subsequent queries significantly faster as compared to the current best-known solutions for several important problems, such as interprocedural reachability and shortest path. We provide a prototype implementation for interprocedural reachability and intraprocedural shortest path that gives a significant speed-up on several benchmarks.
AU - Chatterjee, Krishnendu
AU - Ibsen-Jensen, Rasmus
AU - Pavlogiannis, Andreas
AU - Goyal, Prateesh
ID - 1602
IS - 1
JF - ACM SIGPLAN Notices
TI - Faster algorithms for algebraic path properties in recursive state machines with constant treewidth
VL - 50
ER -
TY - CONF
AB - For deterministic systems, a counterexample to a property can simply be an error trace, whereas counterexamples in probabilistic systems are necessarily more complex. For instance, a set of erroneous traces with a sufficient cumulative probability mass can be used. Since these are too large objects to understand and manipulate, compact representations such as subchains have been considered. In the case of probabilistic systems with non-determinism, the situation is even more complex. While a subchain for a given strategy (or scheduler, resolving non-determinism) is a straightforward choice, we take a different approach. Instead, we focus on the strategy itself, and extract the most important decisions it makes, and present its succinct representation.
The key tools we employ to achieve this are (1) introducing a concept of importance of a state w.r.t. the strategy, and (2) learning using decision trees. There are three main consequent advantages of our approach. Firstly, it exploits the quantitative information on states, stressing the more important decisions. Secondly, it leads to a greater variability and degree of freedom in representing the strategies. Thirdly, the representation uses a self-explanatory data structure. In summary, our approach produces more succinct and more explainable strategies, as opposed to e.g. binary decision diagrams. Finally, our experimental results show that we can extract several rules describing the strategy even for very large systems that do not fit in memory, and based on the rules explain the erroneous behaviour.
AU - Brázdil, Tomáš
AU - Chatterjee, Krishnendu
AU - Chmelik, Martin
AU - Fellner, Andreas
AU - Kretinsky, Jan
ID - 1603
TI - Counterexample explanation by learning small strategies in Markov decision processes
VL - 9206
ER -