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 -