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 - In plants, vacuolar H+-ATPase (V-ATPase) activity acidifies both the trans-Golgi network/early endosome (TGN/EE) and the vacuole. This dual V-ATPase function has impeded our understanding of how the pH homeostasis within the plant TGN/EE controls exo- and endocytosis. Here, we show that the weak V-ATPase mutant deetiolated3 (det3) displayed a pH increase in the TGN/EE, but not in the vacuole, strongly impairing secretion and recycling of the brassinosteroid receptor and the cellulose synthase complexes to the plasma membrane, in contrast to mutants lacking tonoplast-localized V-ATPase activity only. The brassinosteroid insensitivity and the cellulose deficiency defects in det3 were tightly correlated with reduced Golgi and TGN/EE motility. Thus, our results provide strong evidence that acidification of the TGN/EE, but not of the vacuole, is indispensable for functional secretion and recycling in plants.
AU - Yu, Luo
AU - Scholl, Stefan
AU - Doering, Anett
AU - Yi, Zhang
AU - Irani, Niloufer
AU - Di Rubbo, Simone
AU - Neumetzler, Lutz
AU - Krishnamoorthy, Praveen
AU - Van Houtte, Isabelle
AU - Mylle, Evelien
AU - Bischoff, Volker
AU - Vernhettes, Samantha
AU - Winne, Johan
AU - Friml, Jirí
AU - Stierhof, York
AU - Schumacher, Karin
AU - Persson, Staffan
AU - Russinova, Eugenia
ID - 1383
IS - 7
JF - Nature Plants
TI - V-ATPase activity in the TGN/EE is required for exocytosis and recycling in Arabidopsis
VL - 1
ER -
TY - THES
AB - This thesis is concerned with the computation and approximation of intrinsic volumes. Given a smooth body M and a certain digital approximation of it, we develop algorithms to approximate various intrinsic volumes of M using only measurements taken from its digital approximations. The crucial idea behind our novel algorithms is to link the recent theory of persistent homology to the theory of intrinsic volumes via the Crofton formula from integral geometry and, in particular, via Euler characteristic computations. Our main contributions are a multigrid convergent digital algorithm to compute the first intrinsic volume of a solid body in R^n as well as an appropriate integration pipeline to approximate integral-geometric integrals defined over the Grassmannian manifold.
AU - Pausinger, Florian
ID - 1399
TI - On the approximation of intrinsic volumes
ER -
TY - THES
AB - Cancer results from an uncontrolled growth of abnormal cells. Sequentially accumulated genetic and epigenetic alterations decrease cell death and increase cell replication. We used mathematical models to quantify the effect of driver gene mutations. The recently developed targeted therapies can lead to dramatic regressions. However, in solid cancers, clinical responses are often short-lived because resistant cancer cells evolve. We estimated that approximately 50 different mutations can confer resistance to a typical targeted therapeutic agent. We find that resistant cells are likely to be present in expanded subclones before the start of the treatment. The dominant strategy to prevent the evolution of resistance is combination therapy. Our analytical results suggest that in most patients, dual therapy, but not monotherapy, can result in long-term disease control. However, long-term control can only occur if there are no possible mutations in the genome that can cause cross-resistance to both drugs. Furthermore, we showed that simultaneous therapy with two drugs is much more likely to result in long-term disease control than sequential therapy with the same drugs. To improve our understanding of the underlying subclonal evolution we reconstruct the evolutionary history of a patient's cancer from next-generation sequencing data of spatially-distinct DNA samples. Using a quantitative measure of genetic relatedness, we found that pancreatic cancers and their metastases demonstrated a higher level of relatedness than that expected for any two cells randomly taken from a normal tissue. This minimal amount of genetic divergence among advanced lesions indicates that genetic heterogeneity, when quantitatively defined, is not a fundamental feature of the natural history of untreated pancreatic cancers. Our newly developed, phylogenomic tool Treeomics finds evidence for seeding patterns of metastases and can directly be used to discover rules governing the evolution of solid malignancies to transform cancer into a more predictable disease.
AU - Reiter, Johannes
ID - 1400
TI - The subclonal evolution of cancer
ER -
TY - CONF
AB - We consider the problem of statistical computations with persistence diagrams, a summary representation of topological features in data. These diagrams encode persistent homology, a widely used invariant in topological data analysis. While several avenues towards a statistical treatment of the diagrams have been explored recently, we follow an alternative route that is motivated by the success of methods based on the embedding of probability measures into reproducing kernel Hilbert spaces. In fact, a positive definite kernel on persistence diagrams has recently been proposed, connecting persistent homology to popular kernel-based learning techniques such as support vector machines. However, important properties of that kernel enabling a principled use in the context of probability measure embeddings remain to be explored. Our contribution is to close this gap by proving universality of a variant of the original kernel, and to demonstrate its effective use in twosample hypothesis testing on synthetic as well as real-world data.
AU - Kwitt, Roland
AU - Huber, Stefan
AU - Niethammer, Marc
AU - Lin, Weili
AU - Bauer, Ulrich
ID - 1424
TI - Statistical topological data analysis-A kernel perspective
VL - 28
ER -
TY - CONF
AB - In this work we aim at extending the theoretical foundations of lifelong learning. Previous work analyzing this scenario is based on the assumption that learning tasks are sampled i.i.d. from a task environment or limited to strongly constrained data distributions. Instead, we study two scenarios when lifelong learning is possible, even though the observed tasks do not form an i.i.d. sample: first, when they are sampled from the same environment, but possibly with dependencies, and second, when the task environment is allowed to change over time in a consistent way. In the first case we prove a PAC-Bayesian theorem that can be seen as a direct generalization of the analogous previous result for the i.i.d. case. For the second scenario we propose to learn an inductive bias in form of a transfer procedure. We present a generalization bound and show on a toy example how it can be used to identify a beneficial transfer algorithm.
AU - Pentina, Anastasia
AU - Lampert, Christoph
ID - 1425
TI - Lifelong learning with non-i.i.d. tasks
VL - 2015
ER -
TY - CONF
AB - Evolutionary algorithms (EAs) form a popular optimisation paradigm inspired by natural evolution. In recent years the field of evolutionary computation has developed a rigorous analytical theory to analyse their runtime on many illustrative problems. Here we apply this theory to a simple model of natural evolution. In the Strong Selection Weak Mutation (SSWM) evolutionary regime the time between occurrence of new mutations is much longer than the time it takes for a new beneficial mutation to take over the population. In this situation, the population only contains copies of one genotype and evolution can be modelled as a (1+1)-type process where the probability of accepting a new genotype (improvements or worsenings) depends on the change in fitness. We present an initial runtime analysis of SSWM, quantifying its performance for various parameters and investigating differences to the (1+1) EA. We show that SSWM can have a moderate advantage over the (1+1) EA at crossing fitness valleys and study an example where SSWM outperforms the (1+1) EA by taking advantage of information on the fitness gradient.
AU - Paixao, Tiago
AU - Sudholt, Dirk
AU - Heredia, Jorge
AU - Trubenova, Barbora
ID - 1430
T2 - Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation
TI - First steps towards a runtime comparison of natural and artificial evolution
ER -
TY - CONF
AB - Cryptographic access control offers selective access to encrypted data via a combination of key management and functionality-rich cryptographic schemes, such as attribute-based encryption. Using this approach, publicly available meta-data may inadvertently leak information on the access policy that is enforced by cryptography, which renders cryptographic access control unusable in settings where this information is highly sensitive. We begin to address this problem by presenting rigorous definitions for policy privacy in cryptographic access control. For concreteness we set our results in the model of Role-Based Access Control (RBAC), where we identify and formalize several different flavors of privacy, however, our framework should serve as inspiration for other models of access control. Based on our insights we propose a new system which significantly improves on the privacy properties of state-of-the-art constructions. Our design is based on a novel type of privacy-preserving attribute-based encryption, which we introduce and show how to instantiate. We present our results in the context of a cryptographic RBAC system by Ferrara et al. (CSF'13), which uses cryptography to control read access to files, while write access is still delegated to trusted monitors. We give an extension of the construction that permits cryptographic control over write access. Our construction assumes that key management uses out-of-band channels between the policy enforcer and the users but eliminates completely the need for monitoring read/write access to the data.
AU - Ferrara, Anna
AU - Fuchsbauer, Georg
AU - Liu, Bin
AU - Warinschi, Bogdan
ID - 1474
TI - Policy privacy in cryptographic access control
ER -
TY - CONF
AB - Simple board games, like Tic-Tac-Toe and CONNECT-4, play an important role not only in the development of mathematical and logical skills, but also in the emotional and social development. In this paper, we address the problem of generating targeted starting positions for such games. This can facilitate new approaches for bringing novice players to mastery, and also leads to discovery of interesting game variants. We present an approach that generates starting states of varying hardness levels for player 1 in a two-player board game, given rules of the board game, the desired number of steps required for player 1 to win, and the expertise levels of the two players. Our approach leverages symbolic methods and iterative simulation to efficiently search the extremely large state space. We present experimental results that include discovery of states of varying hardness levels for several simple grid-based board games. The presence of such states for standard game variants like 4×4 Tic-Tac-Toe opens up new games to be played that have never been played as the default start state is heavily biased.
AU - Ahmed, Umair
AU - Chatterjee, Krishnendu
AU - Gulwani, Sumit
ID - 1481
T2 - Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence
TI - Automatic generation of alternative starting positions for simple traditional board games
VL - 2
ER -
TY - CONF
AB - Topological data analysis offers a rich source of valuable information to study vision problems. Yet, so far we lack a theoretically sound connection to popular kernel-based learning techniques, such as kernel SVMs or kernel PCA. In this work, we establish such a connection by designing a multi-scale kernel for persistence diagrams, a stable summary representation of topological features in data. We show that this kernel is positive definite and prove its stability with respect to the 1-Wasserstein distance. Experiments on two benchmark datasets for 3D shape classification/retrieval and texture recognition show considerable performance gains of the proposed method compared to an alternative approach that is based on the recently introduced persistence landscapes.
AU - Reininghaus, Jan
AU - Huber, Stefan
AU - Bauer, Ulrich
AU - Kwitt, Roland
ID - 1483
TI - A stable multi-scale kernel for topological machine learning
ER -
TY - CONF
AB - Motivated by biological questions, we study configurations of equal-sized disks in the Euclidean plane that neither pack nor cover. Measuring the quality by the probability that a random point lies in exactly one disk, we show that the regular hexagonal grid gives the maximum among lattice configurations.
AU - Edelsbrunner, Herbert
AU - Iglesias Ham, Mabel
AU - Kurlin, Vitaliy
ID - 1495
T2 - Proceedings of the 27th Canadian Conference on Computational Geometry
TI - Relaxed disk packing
VL - 2015-August
ER -
TY - JOUR
AB - Detecting allelic biases from high-throughput sequencing data requires an approach that maximises sensitivity while minimizing false positives. Here, we present Allelome.PRO, an automated user-friendly bioinformatics pipeline, which uses high-throughput sequencing data from reciprocal crosses of two genetically distinct mouse strains to detect allele-specific expression and chromatin modifications. Allelome.PRO extends approaches used in previous studies that exclusively analyzed imprinted expression to give a complete picture of the ‘allelome’ by automatically categorising the allelic expression of all genes in a given cell type into imprinted, strain-biased, biallelic or non-informative. Allelome.PRO offers increased sensitivity to analyze lowly expressed transcripts, together with a robust false discovery rate empirically calculated from variation in the sequencing data. We used RNA-seq data from mouse embryonic fibroblasts from F1 reciprocal crosses to determine a biologically relevant allelic ratio cutoff, and define for the first time an entire allelome. Furthermore, we show that Allelome.PRO detects differential enrichment of H3K4me3 over promoters from ChIP-seq data validating the RNA-seq results. This approach can be easily extended to analyze histone marks of active enhancers, or transcription factor binding sites and therefore provides a powerful tool to identify candidate cis regulatory elements genome wide.
AU - Andergassen, Daniel
AU - Dotter, Christoph
AU - Kulinski, Tomasz
AU - Guenzl, Philipp
AU - Bammer, Philipp
AU - Barlow, Denise
AU - Pauler, Florian
AU - Hudson, Quanah
ID - 1497
IS - 21
JF - Nucleic Acids Research
TI - Allelome.PRO, a pipeline to define allele-specific genomic features from high-throughput sequencing data
VL - 43
ER -
TY - CONF
AB - Fault-tolerant distributed algorithms play an important role in many critical/high-availability applications. These algorithms are notoriously difficult to implement correctly, due to asynchronous communication and the occurrence of faults, such as the network dropping messages or computers crashing. Nonetheless there is surprisingly little language and verification support to build distributed systems based on fault-tolerant algorithms. In this paper, we present some of the challenges that a designer has to overcome to implement a fault-tolerant distributed system. Then we review different models that have been proposed to reason about distributed algorithms and sketch how such a model can form the basis for a domain-specific programming language. Adopting a high-level programming model can simplify the programmer's life and make the code amenable to automated verification, while still compiling to efficiently executable code. We conclude by summarizing the current status of an ongoing language design and implementation project that is based on this idea.
AU - Dragoi, Cezara
AU - Henzinger, Thomas A
AU - Zufferey, Damien
ID - 1498
SN - 978-3-939897-80-4
TI - The need for language support for fault-tolerant distributed systems
VL - 32
ER -
TY - CONF
AB - We consider weighted automata with both positive and negative integer weights on edges and
study the problem of synchronization using adaptive strategies that may only observe whether
the current weight-level is negative or nonnegative. We show that the synchronization problem is decidable in polynomial time for deterministic weighted automata.
AU - Kretinsky, Jan
AU - Larsen, Kim
AU - Laursen, Simon
AU - Srba, Jiří
ID - 1499
TI - Polynomial time decidability of weighted synchronization under partial observability
VL - 42
ER -
TY - JOUR
AB - We consider Markov decision processes (MDPs) which are a standard model for probabilistic systems. We focus on qualitative properties for MDPs that can express that desired behaviors of the system arise almost-surely (with probability 1) or with positive probability. We introduce a new simulation relation to capture the refinement relation of MDPs with respect to qualitative properties, and present discrete graph algorithms with quadratic complexity to compute the simulation relation. We present an automated technique for assume-guarantee style reasoning for compositional analysis of two-player games by giving a counterexample guided abstraction-refinement approach to compute our new simulation relation. We show a tight link between two-player games and MDPs, and as a consequence the results for games are lifted to MDPs with qualitative properties. We have implemented our algorithms and show that the compositional analysis leads to significant improvements.
AU - Chatterjee, Krishnendu
AU - Chmelik, Martin
AU - Daca, Przemyslaw
ID - 1501
IS - 2
JF - Formal Methods in System Design
TI - CEGAR for compositional analysis of qualitative properties in Markov decision processes
VL - 47
ER -
TY - CONF
AB - We extend the theory of input-output conformance with operators for merge and quotient. The former is useful when testing against multiple requirements or views. The latter can be used to generate tests for patches of an already tested system. Both operators can combine systems with different action alphabets, which is usually the case when constructing complex systems and specifications from parts, for instance different views as well as newly defined functionality of a~previous version of the system.
AU - Beneš, Nikola
AU - Daca, Przemyslaw
AU - Henzinger, Thomas A
AU - Kretinsky, Jan
AU - Nickovic, Dejan
ID - 1502
SN - 978-1-4503-3471-6
TI - Complete composition operators for IOCO-testing theory
ER -
TY - JOUR
AB - This paper is aimed at deriving the universality of the largest eigenvalue of a class of high-dimensional real or complex sample covariance matrices of the form W N =Σ 1/2XX∗Σ 1/2 . Here, X = (xij )M,N is an M× N random matrix with independent entries xij , 1 ≤ i M,≤ 1 ≤ j ≤ N such that Exij = 0, E|xij |2 = 1/N . On dimensionality, we assume that M = M(N) and N/M → d ε (0, ∞) as N ∞→. For a class of general deterministic positive-definite M × M matrices Σ , under some additional assumptions on the distribution of xij 's, we show that the limiting behavior of the largest eigenvalue of W N is universal, via pursuing a Green function comparison strategy raised in [Probab. Theory Related Fields 154 (2012) 341-407, Adv. Math. 229 (2012) 1435-1515] by Erd″os, Yau and Yin for Wigner matrices and extended by Pillai and Yin [Ann. Appl. Probab. 24 (2014) 935-1001] to sample covariance matrices in the null case (&Epsi = I ). Consequently, in the standard complex case (Ex2 ij = 0), combing this universality property and the results known for Gaussian matrices obtained by El Karoui in [Ann. Probab. 35 (2007) 663-714] (nonsingular case) and Onatski in [Ann. Appl. Probab. 18 (2008) 470-490] (singular case), we show that after an appropriate normalization the largest eigenvalue of W N converges weakly to the type 2 Tracy-Widom distribution TW2 . Moreover, in the real case, we show that whenΣ is spiked with a fixed number of subcritical spikes, the type 1 Tracy-Widom limit TW1 holds for the normalized largest eigenvalue of W N , which extends a result of Féral and Péché in [J. Math. Phys. 50 (2009) 073302] to the scenario of nondiagonal Σ and more generally distributed X . In summary, we establish the Tracy-Widom type universality for the largest eigenvalue of generally distributed sample covariance matrices under quite light assumptions on &Sigma . Applications of these limiting results to statistical signal detection and structure recognition of separable covariance matrices are also discussed.
AU - Bao, Zhigang
AU - Pan, Guangming
AU - Zhou, Wang
ID - 1505
IS - 1
JF - Annals of Statistics
TI - Universality for the largest eigenvalue of sample covariance matrices with general population
VL - 43
ER -
TY - JOUR
AB - Consider the square random matrix An = (aij)n,n, where {aij:= a(n)ij , i, j = 1, . . . , n} is a collection of independent real random variables with means zero and variances one. Under the additional moment condition supn max1≤i,j ≤n Ea4ij <∞, we prove Girko's logarithmic law of det An in the sense that as n→∞ log | detAn| ? (1/2) log(n-1)! d/→√(1/2) log n N(0, 1).
AU - Bao, Zhigang
AU - Pan, Guangming
AU - Zhou, Wang
ID - 1506
IS - 3
JF - Bernoulli
TI - The logarithmic law of random determinant
VL - 21
ER -
TY - JOUR
AB - We consider generalized Wigner ensembles and general β-ensembles with analytic potentials for any β ≥ 1. The recent universality results in particular assert that the local averages of consecutive eigenvalue gaps in the bulk of the spectrum are universal in the sense that they coincide with those of the corresponding Gaussian β-ensembles. In this article, we show that local averaging is not necessary for this result, i.e. we prove that the single gap distributions in the bulk are universal. In fact, with an additional step, our result can be extended to any C4(ℝ) potential.
AU - Erdös, László
AU - Yau, Horng
ID - 1508
IS - 8
JF - Journal of the European Mathematical Society
TI - Gap universality of generalized Wigner and β ensembles
VL - 17
ER -
TY - JOUR
AB - The Auxin Binding Protein1 (ABP1) has been identified based on its ability to bind auxin with high affinity and studied for a long time as a prime candidate for the extracellular auxin receptor responsible for mediating in particular the fast non-transcriptional auxin responses. However, the contradiction between the embryo-lethal phenotypes of the originally described Arabidopsis T-DNA insertional knock-out alleles (abp1-1 and abp1-1s) and the wild type-like phenotypes of other recently described loss-of-function alleles (abp1-c1 and abp1-TD1) questions the biological importance of ABP1 and relevance of the previous genetic studies. Here we show that there is no hidden copy of the ABP1 gene in the Arabidopsis genome but the embryo-lethal phenotypes of abp1-1 and abp1-1s alleles are very similar to the knock-out phenotypes of the neighboring gene, BELAYA SMERT (BSM). Furthermore, the allelic complementation test between bsm and abp1 alleles shows that the embryo-lethality in the abp1-1 and abp1-1s alleles is caused by the off-target disruption of the BSM locus by the T-DNA insertions. This clarifies the controversy of different phenotypes among published abp1 knock-out alleles and asks for reflections on the developmental role of ABP1.
AU - Michalko, Jaroslav
AU - Dravecka, Marta
AU - Bollenbach, Tobias
AU - Friml, Jirí
ID - 1509
JF - F1000 Research
TI - Embryo-lethal phenotypes in early abp1 mutants are due to disruption of the neighboring BSM gene
VL - 4
ER -
TY - CONF
AB - The concept of well group in a special but important case captures homological properties of the zero set of a continuous map f from K to R^n on a compact space K that are invariant with respect to perturbations of f. The perturbations are arbitrary continuous maps within L_infty distance r from f for a given r > 0. The main drawback of the approach is that the computability of well groups was shown only when dim K = n or n = 1. Our contribution to the theory of well groups is twofold: on the one hand we improve on the computability issue, but on the other hand we present a range of examples where the well groups are incomplete invariants, that is, fail to capture certain important robust properties of the zero set. For the first part, we identify a computable subgroup of the well group that is obtained by cap product with the pullback of the orientation of R^n by f. In other words, well groups can be algorithmically approximated from below. When f is smooth and dim K < 2n-2, our approximation of the (dim K-n)th well group is exact. For the second part, we find examples of maps f, f' from K to R^n with all well groups isomorphic but whose perturbations have different zero sets. We discuss on a possible replacement of the well groups of vector valued maps by an invariant of a better descriptive power and computability status.
AU - Franek, Peter
AU - Krcál, Marek
ID - 1510
TI - On computability and triviality of well groups
VL - 34
ER -
TY - CONF
AB - The fact that the complete graph K_5 does not embed in the plane has been generalized in two independent directions. On the one hand, the solution of the classical Heawood problem for graphs on surfaces established that the complete graph K_n embeds in a closed surface M if and only if (n-3)(n-4) is at most 6b_1(M), where b_1(M) is the first Z_2-Betti number of M. On the other hand, Van Kampen and Flores proved that the k-skeleton of the n-dimensional simplex (the higher-dimensional analogue of K_{n+1}) embeds in R^{2k} if and only if n is less or equal to 2k+2. Two decades ago, Kuhnel conjectured that the k-skeleton of the n-simplex embeds in a compact, (k-1)-connected 2k-manifold with kth Z_2-Betti number b_k only if the following generalized Heawood inequality holds: binom{n-k-1}{k+1} is at most binom{2k+1}{k+1} b_k. This is a common generalization of the case of graphs on surfaces as well as the Van Kampen--Flores theorem. In the spirit of Kuhnel's conjecture, we prove that if the k-skeleton of the n-simplex embeds in a 2k-manifold with kth Z_2-Betti number b_k, then n is at most 2b_k binom{2k+2}{k} + 2k + 5. This bound is weaker than the generalized Heawood inequality, but does not require the assumption that M is (k-1)-connected. Our proof uses a result of Volovikov about maps that satisfy a certain homological triviality condition.
AU - Goaoc, Xavier
AU - Mabillard, Isaac
AU - Paták, Pavel
AU - Patakova, Zuzana
AU - Tancer, Martin
AU - Wagner, Uli
ID - 1511
TI - On generalized Heawood inequalities for manifolds: A Van Kampen–Flores-type nonembeddability result
VL - 34
ER -
TY - CONF
AB - We show that very weak topological assumptions are enough to ensure the existence of a Helly-type theorem. More precisely, we show that for any non-negative integers b and d there exists an integer h(b,d) such that the following holds. If F is a finite family of subsets of R^d such that the ith reduced Betti number (with Z_2 coefficients in singular homology) of the intersection of any proper subfamily G of F is at most b for every non-negative integer i less or equal to (d-1)/2, then F has Helly number at most h(b,d). These topological conditions are sharp: not controlling any of these first Betti numbers allow for families with unbounded Helly number. Our proofs combine homological non-embeddability results with a Ramsey-based approach to build, given an arbitrary simplicial complex K, some well-behaved chain map from C_*(K) to C_*(R^d). Both techniques are of independent interest.
AU - Goaoc, Xavier
AU - Paták, Pavel
AU - Patakova, Zuzana
AU - Tancer, Martin
AU - Wagner, Uli
ID - 1512
TI - Bounding Helly numbers via Betti numbers
VL - 34
ER -
TY - JOUR
AB - Insects of the order Hemiptera (true bugs) use a wide range of mechanisms of sex determination, including genetic sex determination, paternal genome elimination, and haplodiploidy. Genetic sex determination, the prevalent mode, is generally controlled by a pair of XY sex chromosomes or by an XX/X0 system, but different configurations that include additional sex chromosomes are also present. Although this diversity of sex determining systems has been extensively studied at the cytogenetic level, only the X chromosome of the model pea aphid Acyrthosiphon pisum has been analyzed at the genomic level, and little is known about X chromosome biology in the rest of the order.
In this study, we take advantage of published DNA- and RNA-seq data from three additional Hemiptera species to perform a comparative analysis of the gene content and expression of the X chromosome throughout this clade. We find that, despite showing evidence of dosage compensation, the X chromosomes of these species show female-biased expression, and a deficit of male-biased genes, in direct contrast to the pea aphid X. We further detect an excess of shared gene content between these very distant species, suggesting that despite the diversity of sex determining systems, the same chromosomal element is used as the X throughout a large portion of the order.
AU - Pal, Arka
AU - Vicoso, Beatriz
ID - 1513
IS - 12
JF - Genome Biology and Evolution
TI - The X chromosome of hemipteran insects: Conservation, dosage compensation and sex-biased expression
VL - 7
ER -
TY - JOUR
AB - We study the large deviation rate functional for the empirical distribution of independent Brownian particles with drift. In one dimension, it has been shown by Adams, Dirr, Peletier and Zimmer that this functional is asymptotically equivalent (in the sense of Γ-convergence) to the Jordan-Kinderlehrer-Otto functional arising in the Wasserstein gradient flow structure of the Fokker-Planck equation. In higher dimensions, part of this statement (the lower bound) has been recently proved by Duong, Laschos and Renger, but the upper bound remained open, since the proof of Duong et al relies on regularity properties of optimal transport maps that are restricted to one dimension. In this note we present a new proof of the upper bound, thereby generalising the result of Adams et al to arbitrary dimensions.
AU - Erbar, Matthias
AU - Maas, Jan
AU - Renger, Michiel
ID - 1517
JF - Electronic Communications in Probability
TI - From large deviations to Wasserstein gradient flows in multiple dimensions
VL - 20
ER -
TY - JOUR
AB - Evolutionary biologists have an array of powerful theoretical techniques that can accurately predict changes in the genetic composition of populations. Changes in gene frequencies and genetic associations between loci can be tracked as they respond to a wide variety of evolutionary forces. However, it is often less clear how to decompose these various forces into components that accurately reflect the underlying biology. Here, we present several issues that arise in the definition and interpretation of selection and selection coefficients, focusing on insights gained through the examination of selection coefficients in multilocus notation. Using this notation, we discuss how its flexibility-which allows different biological units to be identified as targets of selection-is reflected in the interpretation of the coefficients that the notation generates. In many situations, it can be difficult to agree on whether loci can be considered to be under "direct" versus "indirect" selection, or to quantify this selection. We present arguments for what the terms direct and indirect selection might best encompass, considering a range of issues, from viability and sexual selection to kin selection. We show how multilocus notation can discriminate between direct and indirect selection, and describe when it can do so.
AU - Barton, Nicholas H
AU - Servedio, Maria
ID - 1519
IS - 5
JF - Evolution
TI - The interpretation of selection coefficients
VL - 69
ER -
TY - CONF
AB - Creating mechanical automata that can walk in stable and pleasing manners is a challenging task that requires both skill and expertise. We propose to use computational design to offset the technical difficulties of this process. A simple drag-and-drop interface allows casual users to create personalized walking toys from a library of pre-defined template mechanisms. Provided with this input, our method leverages physical simulation and evolutionary optimization to refine the mechanical designs such that the resulting toys are able to walk. The optimization process is guided by an intuitive set of objectives that measure the quality of the walking motions. We demonstrate our approach on a set of simulated mechanical toys with different numbers of legs and various distinct gaits. Two fabricated prototypes showcase the feasibility of our designs.
AU - Bharaj, Gaurav
AU - Coros, Stelian
AU - Thomaszewski, Bernhard
AU - Tompkin, James
AU - Bickel, Bernd
AU - Pfister, Hanspeter
ID - 1520
SN - 978-1-4503-3496-9
TI - Computational design of walking automata
ER -
TY - JOUR
AB - Based on 16 recommendations, efforts should be made to achieve the following goal: By 2025, all scholarly publication activity in Austria should be Open Access. In other words, the final versions of all scholarly publications resulting from the support of public resources must be freely accessible on the Internet without delay (Gold Open Access). The resources required to meet this obligation shall be provided to the authors, or the cost of the publication venues shall be borne directly by the research organisations.
AU - Bauer, Bruno
AU - Blechl, Guido
AU - Bock, Christoph
AU - Danowski, Patrick
AU - Ferus, Andreas
AU - Graschopf, Anton
AU - König, Thomas
AU - Mayer, Katja
AU - Reckling, Falk
AU - Rieck, Katharina
AU - Seitz, Peter
AU - Stöger, Herwig
AU - Welzig, Elvira
ID - 1525
IS - 3
JF - VÖB Mitteilungen
TI - Arbeitsgruppe „Nationale Strategie“ des Open Access Network Austria OANA
VL - 68
ER -
TY - JOUR
AB - In growing cells, protein synthesis and cell growth are typically not synchronous, and, thus, protein concentrations vary over the cell division cycle. We have developed a theoretical description of genetic regulatory systems in bacteria that explicitly considers the cell division cycle to investigate its impact on gene expression. We calculate the cell-to-cell variations arising from cells being at different stages in the division cycle for unregulated genes and for basic regulatory mechanisms. These variations contribute to the extrinsic noise observed in single-cell experiments, and are most significant for proteins with short lifetimes. Negative autoregulation buffers against variation of protein concentration over the division cycle, but the effect is found to be relatively weak. Stronger buffering is achieved by an increased protein lifetime. Positive autoregulation can strongly amplify such variation if the parameters are set to values that lead to resonance-like behaviour. For cooperative positive autoregulation, the concentration variation over the division cycle diminishes the parameter region of bistability and modulates the switching times between the two stable states. The same effects are seen for a two-gene mutual-repression toggle switch. By contrast, an oscillatory circuit, the repressilator, is only weakly affected by the division cycle.
AU - Bierbaum, Veronika
AU - Klumpp, Stefan
ID - 1530
IS - 6
JF - Physical Biology
TI - Impact of the cell division cycle on gene circuits
VL - 12
ER -
TY - JOUR
AB - The Heat Kernel Signature (HKS) is a scalar quantity which is derived from the heat kernel of a given shape. Due to its robustness, isometry invariance, and multiscale nature, it has been successfully applied in many geometric applications. From a more general point of view, the HKS can be considered as a descriptor of the metric of a Riemannian manifold. Given a symmetric positive definite tensor field we may interpret it as the metric of some Riemannian manifold and thereby apply the HKS to visualize and analyze the given tensor data. In this paper, we propose a generalization of this approach that enables the treatment of indefinite tensor fields, like the stress tensor, by interpreting them as a generator of a positive definite tensor field. To investigate the usefulness of this approach we consider the stress tensor from the two-point-load model example and from a mechanical work piece.
AU - Zobel, Valentin
AU - Jan Reininghaus
AU - Hotz, Ingrid
ID - 1531
JF - Mathematics and Visualization
TI - Visualizing symmetric indefinite 2D tensor fields using The Heat Kernel Signature
VL - 40
ER -
TY - JOUR
AB - This paper addresses the problem of semantic segmentation, where the possible class labels are from a predefined set. We exploit top-down guidance, i.e., the coarse localization of the objects and their class labels provided by object detectors. For each detected bounding box, figure-ground segmentation is performed and the final result is achieved by merging the figure-ground segmentations. The main idea of the proposed approach, which is presented in our preliminary work, is to reformulate the figure-ground segmentation problem as sparse reconstruction pursuing the object mask in a nonparametric manner. The latent segmentation mask should be coherent subject to sparse error caused by intra-category diversity; thus, the object mask is inferred by making use of sparse representations over the training set. To handle local spatial deformations, local patch-level masks are also considered and inferred by sparse representations over the spatially nearby patches. The sparse reconstruction coefficients and the latent mask are alternately optimized by applying the Lasso algorithm and the accelerated proximal gradient method. The proposed formulation results in a convex optimization problem; thus, the global optimal solution is achieved. In this paper, we provide theoretical analysis of the convergence and optimality. We also give an extended numerical analysis of the proposed algorithm and a comprehensive comparison with the related semantic segmentation methods on the challenging PASCAL visual object class object segmentation datasets and the Weizmann horse dataset. The experimental results demonstrate that the proposed algorithm achieves a competitive performance when compared with the state of the arts.
AU - Xia, Wei
AU - Domokos, Csaba
AU - Xiong, Junjun
AU - Cheong, Loongfah
AU - Yan, Shuicheng
ID - 1533
IS - 8
JF - IEEE Transactions on Circuits and Systems for Video Technology
TI - Segmentation over detection via optimal sparse reconstructions
VL - 25
ER -
TY - JOUR
AB - PIN proteins are auxin export carriers that direct intercellular auxin flow and in turn regulate many aspects of plant growth and development including responses to environmental changes. The Arabidopsis R2R3-MYB transcription factor FOUR LIPS (FLP) and its paralogue MYB88 regulate terminal divisions during stomatal development, as well as female reproductive development and stress responses. Here we show that FLP and MYB88 act redundantly but differentially in regulating the transcription of PIN3 and PIN7 in gravity-sensing cells of primary and lateral roots. On the one hand, FLP is involved in responses to gravity stimulation in primary roots, whereas on the other, FLP and MYB88 function complementarily in establishing the gravitropic set-point angles of lateral roots. Our results support a model in which FLP and MYB88 expression specifically determines the temporal-spatial patterns of PIN3 and PIN7 transcription that are closely associated with their preferential functions during root responses to gravity.
AU - Wang, Hongzhe
AU - Yang, Kezhen
AU - Zou, Junjie
AU - Zhu, Lingling
AU - Xie, Zidian
AU - Morita, Miyoterao
AU - Tasaka, Masao
AU - Friml, Jirí
AU - Grotewold, Erich
AU - Beeckman, Tom
AU - Vanneste, Steffen
AU - Sack, Fred
AU - Le, Jie
ID - 1534
JF - Nature Communications
TI - Transcriptional regulation of PIN genes by FOUR LIPS and MYB88 during Arabidopsis root gravitropism
VL - 6
ER -
TY - JOUR
AB - Neuronal and neuroendocrine L-type calcium channels (Cav1.2, Cav1.3) open readily at relatively low membrane potentials and allow Ca2+ to enter the cells near resting potentials. In this way, Cav1.2 and Cav1.3 shape the action potential waveform, contribute to gene expression, synaptic plasticity, neuronal differentiation, hormone secretion and pacemaker activity. In the chromaffin cells (CCs) of the adrenal medulla, Cav1.3 is highly expressed and is shown to support most of the pacemaking current that sustains action potential (AP) firings and part of the catecholamine secretion. Cav1.3 forms Ca2+-nanodomains with the fast inactivating BK channels and drives the resting SK currents. These latter set the inter-spike interval duration between consecutive spikes during spontaneous firing and the rate of spike adaptation during sustained depolarizations. Cav1.3 plays also a primary role in the switch from “tonic” to “burst” firing that occurs in mouse CCs when either the availability of voltage-gated Na channels (Nav) is reduced or the β2 subunit featuring the fast inactivating BK channels is deleted. Here, we discuss the functional role of these “neuronlike” firing modes in CCs and how Cav1.3 contributes to them. The open issue is to understand how these novel firing patterns are adapted to regulate the quantity of circulating catecholamines during resting condition or in response to acute and chronic stress.
AU - Vandael, David H
AU - Marcantoni, Andrea
AU - Carbone, Emilio
ID - 1535
IS - 2
JF - Current Molecular Pharmacology
TI - Cav1.3 channels as key regulators of neuron-like firings and catecholamine release in chromaffin cells
VL - 8
ER -
TY - JOUR
AB - Strigolactones, first discovered as germination stimulants for parasitic weeds [1], are carotenoid-derived phytohormones that play major roles in inhibiting lateral bud outgrowth and promoting plant-mycorrhizal symbiosis [2-4]. Furthermore, strigolactones are involved in the regulation of lateral and adventitious root development, root cell division [5, 6], secondary growth [7], and leaf senescence [8]. Recently, we discovered the strigolactone transporter Petunia axillaris PLEIOTROPIC DRUG RESISTANCE 1 (PaPDR1), which is required for efficient mycorrhizal colonization and inhibition of lateral bud outgrowth [9]. However, how strigolactones are transported through the plant remained unknown. Here we show that PaPDR1 exhibits a cell-type-specific asymmetric localization in different root tissues. In root tips, PaPDR1 is co-expressed with the strigolactone biosynthetic gene DAD1 (CCD8), and it is localized at the apical membrane of root hypodermal cells, presumably mediating the shootward transport of strigolactone. Above the root tip, in the hypodermal passage cells that form gates for the entry of mycorrhizal fungi, PaPDR1 is present in the outer-lateral membrane, compatible with its postulated function as strigolactone exporter from root to soil. Transport studies are in line with our localization studies since (1) a papdr1 mutant displays impaired transport of strigolactones out of the root tip to the shoot as well as into the rhizosphere and (2) DAD1 expression and PIN1/PIN2 levels change in plants deregulated for PDR1 expression, suggestive of variations in endogenous strigolactone contents. In conclusion, our results indicate that the polar localizations of PaPDR1 mediate directional shootward strigolactone transport as well as localized exudation into the soil.
AU - Sasse, Joëlle
AU - Simon, Sibu
AU - Gübeli, Christian
AU - Liu, Guowei
AU - Cheng, Xi
AU - Friml, Jirí
AU - Bouwmeester, Harro
AU - Martinoia, Enrico
AU - Borghi, Lorenzo
ID - 1536
IS - 5
JF - Current Biology
TI - Asymmetric localizations of the ABC transporter PaPDR1 trace paths of directional strigolactone transport
VL - 25
ER -
TY - JOUR
AB - 3D amoeboid cell migration is central to many developmental and disease-related processes such as cancer metastasis. Here, we identify a unique prototypic amoeboid cell migration mode in early zebrafish embryos, termed stable-bleb migration. Stable-bleb cells display an invariant polarized balloon-like shape with exceptional migration speed and persistence. Progenitor cells can be reversibly transformed into stable-bleb cells irrespective of their primary fate and motile characteristics by increasing myosin II activity through biochemical or mechanical stimuli. Using a combination of theory and experiments, we show that, in stable-bleb cells, cortical contractility fluctuations trigger a stochastic switch into amoeboid motility, and a positive feedback between cortical flows and gradients in contractility maintains stable-bleb cell polarization. We further show that rearward cortical flows drive stable-bleb cell migration in various adhesive and non-adhesive environments, unraveling a highly versatile amoeboid migration phenotype.
AU - Ruprecht, Verena
AU - Wieser, Stefan
AU - Callan Jones, Andrew
AU - Smutny, Michael
AU - Morita, Hitoshi
AU - Sako, Keisuke
AU - Barone, Vanessa
AU - Ritsch Marte, Monika
AU - Sixt, Michael K
AU - Voituriez, Raphaël
AU - Heisenberg, Carl-Philipp J
ID - 1537
IS - 4
JF - Cell
TI - Cortical contractility triggers a stochastic switch to fast amoeboid cell motility
VL - 160
ER -
TY - JOUR
AB - Systems biology rests on the idea that biological complexity can be better unraveled through the interplay of modeling and experimentation. However, the success of this approach depends critically on the informativeness of the chosen experiments, which is usually unknown a priori. Here, we propose a systematic scheme based on iterations of optimal experiment design, flow cytometry experiments, and Bayesian parameter inference to guide the discovery process in the case of stochastic biochemical reaction networks. To illustrate the benefit of our methodology, we apply it to the characterization of an engineered light-inducible gene expression circuit in yeast and compare the performance of the resulting model with models identified from nonoptimal experiments. In particular, we compare the parameter posterior distributions and the precision to which the outcome of future experiments can be predicted. Moreover, we illustrate how the identified stochastic model can be used to determine light induction patterns that make either the average amount of protein or the variability in a population of cells follow a desired profile. Our results show that optimal experiment design allows one to derive models that are accurate enough to precisely predict and regulate the protein expression in heterogeneous cell populations over extended periods of time.
AU - Ruess, Jakob
AU - Parise, Francesca
AU - Milias Argeitis, Andreas
AU - Khammash, Mustafa
AU - Lygeros, John
ID - 1538
IS - 26
JF - PNAS
TI - Iterative experiment design guides the characterization of a light-inducible gene expression circuit
VL - 112
ER -
TY - JOUR
AB - Many stochastic models of biochemical reaction networks contain some chemical species for which the number of molecules that are present in the system can only be finite (for instance due to conservation laws), but also other species that can be present in arbitrarily large amounts. The prime example of such networks are models of gene expression, which typically contain a small and finite number of possible states for the promoter but an infinite number of possible states for the amount of mRNA and protein. One of the main approaches to analyze such models is through the use of equations for the time evolution of moments of the chemical species. Recently, a new approach based on conditional moments of the species with infinite state space given all the different possible states of the finite species has been proposed. It was argued that this approach allows one to capture more details about the full underlying probability distribution with a smaller number of equations. Here, I show that the result that less moments provide more information can only stem from an unnecessarily complicated description of the system in the classical formulation. The foundation of this argument will be the derivation of moment equations that describe the complete probability distribution over the finite state space but only low-order moments over the infinite state space. I will show that the number of equations that is needed is always less than what was previously claimed and always less than the number of conditional moment equations up to the same order. To support these arguments, a symbolic algorithm is provided that can be used to derive minimal systems of unconditional moment equations for models with partially finite state space.
AU - Ruess, Jakob
ID - 1539
IS - 24
JF - Journal of Chemical Physics
TI - Minimal moment equations for stochastic models of biochemical reaction networks with partially finite state space
VL - 143
ER -
TY - JOUR
AB - Plant sexual reproduction involves highly structured and specialized organs: stamens (male) and gynoecia (female, containing ovules). These organs synchronously develop within protective flower buds, until anthesis, via tightly coordinated mechanisms that are essential for effective fertilization and production of viable seeds. The phytohormone auxin is one of the key endogenous signalling molecules controlling initiation and development of these, and other, plant organs. In particular, its uneven distribution, resulting from tightly controlled production, metabolism and directional transport, is an important morphogenic factor. In this review we discuss how developmentally controlled and localized auxin biosynthesis and transport contribute to the coordinated development of plants' reproductive organs, and their fertilized derivatives (embryos) via the regulation of auxin levels and distribution within and around them. Current understanding of the links between de novo local auxin biosynthesis, auxin transport and/or signalling is presented to highlight the importance of the non-cell autonomous action of auxin production on development and morphogenesis of reproductive organs and embryos. An overview of transcription factor families, which spatiotemporally define local auxin production by controlling key auxin biosynthetic enzymes, is also presented.
AU - Robert, Hélène
AU - Crhák Khaitová, Lucie
AU - Mroue, Souad
AU - Benková, Eva
ID - 1540
IS - 16
JF - Journal of Experimental Botany
TI - The importance of localized auxin production for morphogenesis of reproductive organs and embryos in Arabidopsis
VL - 66
ER -
TY - CONF
AB - We present XSpeed a parallel state-space exploration algorithm for continuous systems with linear dynamics and nondeterministic inputs. The motivation of having parallel algorithms is to exploit the computational power of multi-core processors to speed-up performance. The parallelization is achieved on two fronts. First, we propose a parallel implementation of the support function algorithm by sampling functions in parallel. Second, we propose a parallel state-space exploration by slicing the time horizon and computing the reachable states in the time slices in parallel. The second method can be however applied only to a class of linear systems with invertible dynamics and fixed input. A GP-GPU implementation is also presented following a lazy evaluation strategy on support functions. The parallel algorithms are implemented in the tool XSpeed. We evaluated the performance on two benchmarks including an 28 dimension Helicopter model. Comparison with the sequential counterpart shows a maximum speed-up of almost 7× on a 6 core, 12 thread Intel Xeon CPU E5-2420 processor. Our GP-GPU implementation shows a maximum speed-up of 12× over the sequential implementation and 53× over SpaceEx (LGG scenario), the state of the art tool for reachability analysis of linear hybrid systems. Experiments illustrate that our parallel algorithm with time slicing not only speeds-up performance but also improves precision.
AU - Ray, Rajarshi
AU - Gurung, Amit
AU - Das, Binayak
AU - Bartocci, Ezio
AU - Bogomolov, Sergiy
AU - Grosu, Radu
ID - 1541
TI - XSpeed: Accelerating reachability analysis on multi-core processors
VL - 9434
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 - JOUR
AB - A plethora of diverse programmed cell death (PCD) processes has been described in living organisms. In animals and plants, different forms of PCD play crucial roles in development, immunity, and responses to the environment. While the molecular control of some animal PCD forms such as apoptosis is known in great detail, we still know comparatively little about the regulation of the diverse types of plant PCD. In part, this deficiency in molecular understanding is caused by the lack of reliable reporters to detect PCD processes. Here, we addressed this issue by using a combination of bioinformatics approaches to identify commonly regulated genes during diverse plant PCD processes in Arabidopsis (Arabidopsis thaliana). Our results indicate that the transcriptional signatures of developmentally controlled cell death are largely distinct from the ones associated with environmentally induced cell death. Moreover, different cases of developmental PCD share a set of cell death-associated genes. Most of these genes are evolutionary conserved within the green plant lineage, arguing for an evolutionary conserved core machinery of developmental PCD. Based on this information, we established an array of specific promoter-reporter lines for developmental PCD in Arabidopsis. These PCD indicators represent a powerful resource that can be used in addition to established morphological and biochemical methods to detect and analyze PCD processes in vivo and in planta.
AU - Olvera Carrillo, Yadira
AU - Van Bel, Michiel
AU - Van Hautegem, Tom
AU - Fendrych, Matyas
AU - Huysmans, Marlies
AU - Šimášková, Mária
AU - Van Durme, Matthias
AU - Buscaill, Pierre
AU - Rivas, Susana
AU - Coll, Núria
AU - Coppens, Frederik
AU - Maere, Steven
AU - Nowack, Moritz
ID - 1543
IS - 4
JF - Plant Physiology
TI - A conserved core of programmed cell death indicator genes discriminates developmentally and environmentally induced programmed cell death in plants
VL - 169
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 - Cell movement has essential functions in development, immunity, and cancer. Various cell migration patterns have been reported, but no general rule has emerged so far. Here, we show on the basis of experimental data in vitro and in vivo that cell persistence, which quantifies the straightness of trajectories, is robustly coupled to cell migration speed. We suggest that this universal coupling constitutes a generic law of cell migration, which originates in the advection of polarity cues by an actin cytoskeleton undergoing flows at the cellular scale. Our analysis relies on a theoretical model that we validate by measuring the persistence of cells upon modulation of actin flow speeds and upon optogenetic manipulation of the binding of an actin regulator to actin filaments. Beyond the quantitative prediction of the coupling, the model yields a generic phase diagram of cellular trajectories, which recapitulates the full range of observed migration patterns.
AU - Maiuri, Paolo
AU - Rupprecht, Jean
AU - Wieser, Stefan
AU - Ruprecht, Verena
AU - Bénichou, Olivier
AU - Carpi, Nicolas
AU - Coppey, Mathieu
AU - De Beco, Simon
AU - Gov, Nir
AU - Heisenberg, Carl-Philipp J
AU - Lage Crespo, Carolina
AU - Lautenschlaeger, Franziska
AU - Le Berre, Maël
AU - Lennon Duménil, Ana
AU - Raab, Matthew
AU - Thiam, Hawa
AU - Piel, Matthieu
AU - Sixt, Michael K
AU - Voituriez, Raphaël
ID - 1553
IS - 2
JF - Cell
TI - Actin flows mediate a universal coupling between cell speed and cell persistence
VL - 161
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 - γ-Aminobutyric acid (GABA)- and glycine-mediated hyperpolarizing inhibition is associated with a chloride influx that depends on the inwardly directed chloride electrochemical gradient. In neurons, the extrusion of chloride from the cytosol primarily depends on the expression of an isoform of potassium-chloride cotransporters (KCC2s). KCC2 is crucial in the regulation of the inhibitory tone of neural circuits, including pain processing neural assemblies. Thus we investigated the cellular distribution of KCC2 in neurons underlying pain processing in the superficial spinal dorsal horn of rats by using high-resolution immunocytochemical methods. We demonstrated that perikarya and dendrites widely expressed KCC2, but axon terminals proved to be negative for KCC2. In single ultrathin sections, silver deposits labeling KCC2 molecules showed different densities on the surface of dendritic profiles, some of which were negative for KCC2. In freeze fracture replicas and tissue sections double stained for the β3-subunit of GABAA receptors and KCC2, GABAA receptors were revealed on dendritic segments with high and also with low KCC2 densities. By measuring the distances between spots immunoreactive for gephyrin (a scaffolding protein of GABAA and glycine receptors) and KCC2 on the surface of neurokinin 1 (NK1) receptor-immunoreactive dendrites, we found that gephyrin-immunoreactive spots were located at various distances from KCC2 cotransporters; 5.7 % of them were recovered in the middle of 4-10-μm-long dendritic segments that were free of KCC2 immunostaining. The variable local densities of KCC2 may result in variable postsynaptic potentials evoked by the activation of GABAA and glycine receptors along the dendrites of spinal neurons.
AU - Javdani, Fariba
AU - Holló, Krisztina
AU - Hegedűs, Krisztina
AU - Kis, Gréta
AU - Hegyi, Zoltán
AU - Dócs, Klaudia
AU - Kasugai, Yu
AU - Fukazawa, Yugo
AU - Shigemoto, Ryuichi
AU - Antal, Miklós
ID - 1557
IS - 13
JF - Journal of Comparative Neurology
TI - Differential expression patterns of K+Cl- cotransporter 2 in neurons within the superficial spinal dorsal horn of rats
VL - 523
ER -
TY - JOUR
AB - CyclophilinAis a conserved peptidyl-prolyl cis-trans isomerase (PPIase) best known as the cellular receptor of the immunosuppressant cyclosporine A. Despite significant effort, evidence of developmental functions of cyclophilin A in non-plant systems has remained obscure. Mutations in a tomato (Solanum lycopersicum) cyclophilin A ortholog, DIAGEOTROPICA (DGT), have been shown to abolish the organogenesis of lateral roots; however, a mechanistic explanation of the phenotype is lacking. Here, we show that the dgt mutant lacks auxin maxima relevant to priming and specification of lateral root founder cells. DGT is expressed in shoot and root, and localizes to both the nucleus and cytoplasm during lateral root organogenesis. Mutation of ENTIRE/ IAA9, a member of the auxin-responsive Aux/IAA protein family of transcriptional repressors, partially restores the inability of dgt to initiate lateral root primordia but not the primordia outgrowth. By comparison, grafting of a wild-type scion restores the process of lateral root formation, consistent with participation of a mobile signal. Antibodies do not detect movement of the DGT protein into the dgt rootstock; however, experiments with radiolabeled auxin and an auxin-specific microelectrode demonstrate abnormal auxin fluxes. Functional studies of DGT in heterologous yeast and tobacco-leaf auxin-transport systems demonstrate that DGT negatively regulates PIN-FORMED (PIN) auxin efflux transporters by affecting their plasma membrane localization. Studies in tomato support complex effects of the dgt mutation on PIN expression level, expression domain and plasma membrane localization. Our data demonstrate that DGT regulates auxin transport in lateral root formation.
AU - Ivanchenko, Maria
AU - Zhu, Jinsheng
AU - Wang, Bangjun
AU - Medvecka, Eva
AU - Du, Yunlong
AU - Azzarello, Elisa
AU - Mancuso, Stefano
AU - Megraw, Molly
AU - Filichkin, Sergei
AU - Dubrovsky, Joseph
AU - Friml, Jirí
AU - Geisler, Markus
ID - 1558
IS - 4
JF - Development
TI - The cyclophilin a DIAGEOTROPICA gene affects auxin transport in both root and shoot to control lateral root formation
VL - 142
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
AB - Stromal cells in the subcapsular sinus of the lymph node 'decide' which cells and molecules are allowed access to the deeper parenchyma. The glycoprotein PLVAP is a crucial component of this selector function.
AU - Hons, Miroslav
AU - Sixt, Michael K
ID - 1560
IS - 4
JF - Nature Immunology
TI - The lymph node filter revealed
VL - 16
ER -
TY - JOUR
AB - Replication-deficient recombinant adenoviruses are potent vectors for the efficient transient expression of exogenous genes in resting immune cells. However, most leukocytes are refractory to efficient adenoviral transduction as they lack expression of the coxsackie/adenovirus receptor (CAR). To circumvent this obstacle, we generated the R26/CAG-CARΔ1StopF (where R26 is ROSA26 and CAG is CMV early enhancer/chicken β actin promoter) knock-in mouse line. This strain allows monitoring of in situ Cre recombinase activity through expression of CARΔ1. Simultaneously, CARΔ1 expression permits selective and highly efficient adenoviral transduction of immune cell populations, such as mast cells or T cells, directly ex vivo in bulk cultures without prior cell purification or activation. Furthermore, we show that CARΔ1 expression dramatically improves adenoviral infection of in vitro differentiated conventional and plasmacytoid dendritic cells (DCs), basophils, mast cells, as well as Hoxb8-immortalized hematopoietic progenitor cells. This novel dual function mouse strain will hence be a valuable tool to rapidly dissect the function of specific genes in leukocyte physiology.
AU - Heger, Klaus
AU - Kober, Maike
AU - Rieß, David
AU - Drees, Christoph
AU - De Vries, Ingrid
AU - Bertossi, Arianna
AU - Roers, Axel
AU - Sixt, Michael K
AU - Schmidt Supprian, Marc
ID - 1561
IS - 6
JF - European Journal of Immunology
TI - A novel Cre recombinase reporter mouse strain facilitates selective and efficient infection of primary immune cells with adenoviral vectors
VL - 45
ER -
TY - JOUR
AB - The plant hormone auxin is a key regulator of plant growth and development. Auxin levels are sensed and interpreted by distinct receptor systems that activate a broad range of cellular responses. The Auxin-Binding Protein1 (ABP1) that has been identified based on its ability to bind auxin with high affinity is a prime candidate for the extracellular receptor responsible for mediating a range of auxin effects, in particular, the fast non-transcriptional ones. Contradictory genetic studies suggested prominent or no importance of ABP1 in many developmental processes. However, how crucial the role of auxin binding to ABP1 is for its functions has not been addressed. Here, we show that the auxin-binding pocket of ABP1 is essential for its gain-of-function cellular and developmental roles. In total, 16 different abp1 mutants were prepared that possessed substitutions in the metal core or in the hydrophobic amino acids of the auxin-binding pocket as well as neutral mutations. Their analysis revealed that an intact auxin-binding pocket is a prerequisite for ABP1 to activate downstream components of the ABP1 signalling pathway, such as Rho of Plants (ROPs) and to mediate the clathrin association with membranes for endocytosis regulation. In planta analyses demonstrated the importance of the auxin binding pocket for all known ABP1-mediated postembryonic developmental processes, including morphology of leaf epidermal cells, root growth and root meristem activity, and vascular tissue differentiation. Taken together, these findings suggest that auxin binding to ABP1 is central to its function, supporting the role of ABP1 as auxin receptor.
AU - Grones, Peter
AU - Chen, Xu
AU - Simon, Sibu
AU - Kaufmann, Walter
AU - De Rycke, Riet
AU - Nodzyński, Tomasz
AU - Zažímalová, Eva
AU - Friml, Jirí
ID - 1562
IS - 16
JF - Journal of Experimental Botany
TI - Auxin-binding pocket of ABP1 is crucial for its gain-of-function cellular and developmental roles
VL - 66
ER -
TY - JOUR
AB - For a given self-map $f$ of $M$, a closed smooth connected and simply-connected manifold of dimension $m\geq 4$, we provide an algorithm for estimating the values of the topological invariant $D^m_r[f]$, which equals the minimal number of $r$-periodic points in the smooth homotopy class of $f$. Our results are based on the combinatorial scheme for computing $D^m_r[f]$ introduced by G. Graff and J. Jezierski [J. Fixed Point Theory Appl. 13 (2013), 63-84]. An open-source implementation of the algorithm programmed in C++ is publicly available at {\tt http://www.pawelpilarczyk.com/combtop/}.
AU - Graff, Grzegorz
AU - Pilarczyk, Pawel
ID - 1563
IS - 1
JF - Topological Methods in Nonlinear Analysis
TI - An algorithmic approach to estimating the minimal number of periodic points for smooth self-maps of simply-connected manifolds
VL - 45
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 - CONF
AB - My personal journey to the fascinating world of geometric forms started more than 30 years ago with the invention of alpha shapes in the plane. It took about 10 years before we generalized the concept to higher dimensions, we produced working software with a graphics interface for the three-dimensional case. At the same time, we added homology to the computations. Needless to say that this foreshadowed the inception of persistent homology, because it suggested the study of filtrations to capture the scale of a shape or data set. Importantly, this method has fast algorithms. The arguably most useful result on persistent homology is the stability of its diagrams under perturbations.
AU - Edelsbrunner, Herbert
ID - 1567
TI - Shape, homology, persistence, and stability
VL - 9411
ER -
TY - CONF
AB - Aiming at the automatic diagnosis of tumors from narrow band imaging (NBI) magnifying endoscopy (ME) images of the stomach, we combine methods from image processing, computational topology, and machine learning to classify patterns into normal, tubular, vessel. Training the algorithm on a small number of images of each type, we achieve a high rate of correct classifications. The analysis of the learning algorithm reveals that a handful of geometric and topological features are responsible for the overwhelming majority of decisions.
AU - Dunaeva, Olga
AU - Edelsbrunner, Herbert
AU - Lukyanov, Anton
AU - Machin, Michael
AU - Malkova, Daria
ID - 1568
T2 - Proceedings - 16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing
TI - The classification of endoscopy images with persistent homology
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 - Epistatic interactions can frustrate and shape evolutionary change. Indeed, phenotypes may fail to evolve when essential mutations are only accessible through positive selection if they are fixed simultaneously. How environmental variability affects such constraints is poorly understood. Here, we studied genetic constraints in fixed and fluctuating environments using the Escherichia coli lac operon as a model system for genotype-environment interactions. We found that, in different fixed environments, all trajectories that were reconstructed by applying point mutations within the transcription factor-operator interface became trapped at suboptima, where no additional improvements were possible. Paradoxically, repeated switching between these same environments allows unconstrained adaptation by continuous improvements. This evolutionary mode is explained by pervasive cross-environmental tradeoffs that reposition the peaks in such a way that trapped genotypes can repeatedly climb ascending slopes and hence, escape adaptive stasis. Using a Markov approach, we developed a mathematical framework to quantify the landscape-crossing rates and show that this ratchet-like adaptive mechanism is robust in a wide spectrum of fluctuating environments. Overall, this study shows that genetic constraints can be overcome by environmental change and that crossenvironmental tradeoffs do not necessarily impede but also, can facilitate adaptive evolution. Because tradeoffs and environmental variability are ubiquitous in nature, we speculate this evolutionary mode to be of general relevance.
AU - De Vos, Marjon
AU - Dawid, Alexandre
AU - Šunderlíková, Vanda
AU - Tans, Sander
ID - 1571
IS - 48
JF - PNAS
TI - Breaking evolutionary constraint with a tradeoff ratchet
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 prove that the dual of the digital Voronoi diagram constructed by flooding the plane from the data points gives a geometrically and topologically correct dual triangulation. This provides the proof of correctness for recently developed GPU algorithms that outperform traditional CPU algorithms for constructing two-dimensional Delaunay triangulations.
AU - Cao, Thanhtung
AU - Edelsbrunner, Herbert
AU - Tan, Tiowseng
ID - 1578
IS - 7
JF - Computational Geometry
TI - Triangulations from topologically correct digital Voronoi diagrams
VL - 48
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 - In animal embryos, morphogen gradients determine tissue patterning and morphogenesis. Shyer et al. provide evidence that, during vertebrate gut formation, tissue folding generates graded activity of signals required for subsequent steps of gut growth and differentiation, thereby revealing an intriguing link between tissue morphogenesis and morphogen gradient formation.
AU - Bollenbach, Mark Tobias
AU - Heisenberg, Carl-Philipp J
ID - 1581
IS - 3
JF - Cell
TI - Gradients are shaping up
VL - 161
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 - In this paper, we consider the fluctuation of mutual information statistics of a multiple input multiple output channel communication systems without assuming that the entries of the channel matrix have zero pseudovariance. To this end, we also establish a central limit theorem of the linear spectral statistics for sample covariance matrices under general moment conditions by removing the restrictions imposed on the second moment and fourth moment on the matrix entries in Bai and Silverstein (2004).
AU - Bao, Zhigang
AU - Pan, Guangming
AU - Zhou, Wang
ID - 1585
IS - 6
JF - IEEE Transactions on Information Theory
TI - Asymptotic mutual information statistics of MIMO channels and CLT of sample covariance matrices
VL - 61
ER -
TY - JOUR
AB - Through metabolic engineering cyanobacteria can be employed in biotechnology. Combining the capacity for oxygenic photosynthesis and carbon fixation with an engineered metabolic pathway allows carbon-based product formation from CO2, light, and water directly. Such cyanobacterial 'cell factories' are constructed to produce biofuels, bioplastics, and commodity chemicals. Efforts of metabolic engineers and synthetic biologists allow the modification of the intermediary metabolism at various branching points, expanding the product range. The new biosynthesis routes 'tap' the metabolism ever more efficiently, particularly through the engineering of driving forces and utilization of cofactors generated during the light reactions of photosynthesis, resulting in higher product titers. High rates of carbon rechanneling ultimately allow an almost-complete allocation of fixed carbon to product above biomass.
AU - Angermayr, Andreas
AU - Gorchs, Aleix
AU - Hellingwerf, Klaas
ID - 1586
IS - 6
JF - Trends in Biotechnology
TI - Metabolic engineering of cyanobacteria for the synthesis of commodity products
VL - 33
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 Taylor-Couette system where the radius ratio is close to unity. Systematically increasing the Reynolds number, we observe a number of previously known transitions, such as one from the classical Taylor vortex flow (TVF) to wavy vortex flow (WVF) and the transition to fully developed turbulence. Prior to the onset of turbulence, we observe intermittent bursting patterns of localized turbulent patches, confirming the experimentally observed pattern of very short wavelength bursts (VSWBs). A striking finding is that, for a Reynolds number larger than that for the onset of VSWBs, a new type of intermittently bursting behavior emerges: patterns of azimuthally closed rings of various orders. We call them ring-bursting patterns, which surround the cylinder completely but remain localized and separated in the axial direction through nonturbulent wavy structures. We employ a number of quantitative measures including the cross-flow energy to characterize the ring-bursting patterns and to distinguish them from the background flow. These patterns are interesting because they do not occur in the wide-gap Taylor-Couette flow systems. The narrow-gap regime is less studied but certainly deserves further attention to gain deeper insights into complex flow dynamics in fluids.
AU - Altmeyer, Sebastian
AU - Do, Younghae
AU - Lai, Ying
ID - 1588
IS - 5
JF - Physical Review E
TI - Ring-bursting behavior en route to turbulence in narrow-gap Taylor-Couette flows
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 - Quantitative extensions of temporal logics have recently attracted significant attention. In this work, we study frequency LTL (fLTL), an extension of LTL which allows to speak about frequencies of events along an execution. Such an extension is particularly useful for probabilistic systems that often cannot fulfil strict qualitative guarantees on the behaviour. It has been recently shown that controller synthesis for Markov decision processes and fLTL is decidable when all the bounds on frequencies are 1. As a step towards a complete quantitative solution, we show that the problem is decidable for the fragment fLTL\GU, where U does not occur in the scope of G (but still F can). Our solution is based on a novel translation of such quantitative formulae into equivalent deterministic automata.
AU - Forejt, Vojtěch
AU - Krčál, Jan
AU - Kretinsky, Jan
ID - 1594
TI - Controller synthesis for MDPs and frequency LTL\GU
VL - 9450
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 -
TY - JOUR
AB - We consider the quantitative analysis problem for interprocedural control-flow graphs (ICFGs). The input consists of an ICFG, a positive weight function that assigns every transition a positive integer-valued number, and a labelling of the transitions (events) as good, bad, and neutral events. The weight function assigns to each transition a numerical value that represents ameasure of how good or bad an event is. The quantitative analysis problem asks whether there is a run of the ICFG where the ratio of the sum of the numerical weights of good events versus the sum of weights of bad events in the long-run is at least a given threshold (or equivalently, to compute the maximal ratio among all valid paths in the ICFG). The quantitative analysis problem for ICFGs can be solved in polynomial time, and we present an efficient and practical algorithm for the problem. We show that several problems relevant for static program analysis, such as estimating the worst-case execution time of a program or the average energy consumption of a mobile application, can be modeled in our framework. We have implemented our algorithm as a tool in the Java Soot framework. We demonstrate the effectiveness of our approach with two case studies. First, we show that our framework provides a sound approach (no false positives) for the analysis of inefficiently-used containers. Second, we show that our approach can also be used for static profiling of programs which reasons about methods that are frequently invoked. Our experimental results show that our tool scales to relatively large benchmarks, and discovers relevant and useful information that can be used to optimize performance of the programs.
AU - Chatterjee, Krishnendu
AU - Pavlogiannis, Andreas
AU - Velner, Yaron
ID - 1604
IS - 1
JF - Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT
SN - 978-1-4503-3300-9
TI - Quantitative interprocedural analysis
VL - 50
ER -