TY - CONF AB - Markov decision processes (MDPs) are standard models for probabilistic systems with non-deterministic behaviours. Long-run average rewards provide a mathematically elegant formalism for expressing long term performance. Value iteration (VI) is one of the simplest and most efficient algorithmic approaches to MDPs with other properties, such as reachability objectives. Unfortunately, a naive extension of VI does not work for MDPs with long-run average rewards, as there is no known stopping criterion. In this work our contributions are threefold. (1) We refute a conjecture related to stopping criteria for MDPs with long-run average rewards. (2) We present two practical algorithms for MDPs with long-run average rewards based on VI. First, we show that a combination of applying VI locally for each maximal end-component (MEC) and VI for reachability objectives can provide approximation guarantees. Second, extending the above approach with a simulation-guided on-demand variant of VI, we present an anytime algorithm that is able to deal with very large models. (3) Finally, we present experimental results showing that our methods significantly outperform the standard approaches on several benchmarks. AU - Ashok, Pranav AU - Chatterjee, Krishnendu AU - Daca, Przemyslaw AU - Kretinsky, Jan AU - Meggendorfer, Tobias ED - Majumdar, Rupak ED - Kunčak, Viktor ID - 645 SN - 978-331963386-2 TI - Value iteration for long run average reward in markov decision processes VL - 10426 ER - TY - JOUR AB - An instance of the valued constraint satisfaction problem (VCSP) is given by a finite set of variables, a finite domain of labels, and a sum of functions, each function depending on a subset of the variables. Each function can take finite values specifying costs of assignments of labels to its variables or the infinite value, which indicates an infeasible assignment. The goal is to find an assignment of labels to the variables that minimizes the sum. We study, assuming that P 6= NP, how the complexity of this very general problem depends on the set of functions allowed in the instances, the so-called constraint language. The case when all allowed functions take values in f0;1g corresponds to ordinary CSPs, where one deals only with the feasibility issue, and there is no optimization. This case is the subject of the algebraic CSP dichotomy conjecture predicting for which constraint languages CSPs are tractable (i.e., solvable in polynomial time) and for which they are NP-hard. The case when all allowed functions take only finite values corresponds to a finitevalued CSP, where the feasibility aspect is trivial and one deals only with the optimization issue. The complexity of finite-valued CSPs was fully classified by Thapper and Živný. An algebraic necessary condition for tractability of a general-valued CSP with a fixed constraint language was recently given by Kozik and Ochremiak. As our main result, we prove that if a constraint language satisfies this algebraic necessary condition, and the feasibility CSP (i.e., the problem of deciding whether a given instance has a feasible solution) corresponding to the VCSP with this language is tractable, then the VCSP is tractable. The algorithm is a simple combination of the assumed algorithm for the feasibility CSP and the standard LP relaxation. As a corollary, we obtain that a dichotomy for ordinary CSPs would imply a dichotomy for general-valued CSPs. AU - Kolmogorov, Vladimir AU - Krokhin, Andrei AU - Rolinek, Michal ID - 644 IS - 3 JF - SIAM Journal on Computing TI - The complexity of general-valued CSPs VL - 46 ER - TY - CONF AB - We present a novel convex relaxation and a corresponding inference algorithm for the non-binary discrete tomography problem, that is, reconstructing discrete-valued images from few linear measurements. In contrast to state of the art approaches that split the problem into a continuous reconstruction problem for the linear measurement constraints and a discrete labeling problem to enforce discrete-valued reconstructions, we propose a joint formulation that addresses both problems simultaneously, resulting in a tighter convex relaxation. For this purpose a constrained graphical model is set up and evaluated using a novel relaxation optimized by dual decomposition. We evaluate our approach experimentally and show superior solutions both mathematically (tighter relaxation) and experimentally in comparison to previously proposed relaxations. AU - Kuske, Jan AU - Swoboda, Paul AU - Petra, Stefanie ED - Lauze, François ED - Dong, Yiqiu ED - Bjorholm Dahl, Anders ID - 646 SN - 978-331958770-7 TI - A novel convex relaxation for non binary discrete tomography VL - 10302 ER - TY - CONF AB - Pseudoentropy has found a lot of important applications to cryptography and complexity theory. In this paper we focus on the foundational problem that has not been investigated so far, namely by how much pseudoentropy (the amount seen by computationally bounded attackers) differs from its information-theoretic counterpart (seen by unbounded observers), given certain limits on attacker’s computational power? We provide the following answer for HILL pseudoentropy, which exhibits a threshold behavior around the size exponential in the entropy amount:– If the attacker size (s) and advantage () satisfy s (formula presented) where k is the claimed amount of pseudoentropy, then the pseudoentropy boils down to the information-theoretic smooth entropy. – If s (formula presented) then pseudoentropy could be arbitrarily bigger than the information-theoretic smooth entropy. Besides answering the posted question, we show an elegant application of our result to the complexity theory, namely that it implies the clas-sical result on the existence of functions hard to approximate (due to Pippenger). In our approach we utilize non-constructive techniques: the duality of linear programming and the probabilistic method. AU - Skórski, Maciej ED - Jäger, Gerhard ED - Steila, Silvia ID - 648 SN - 978-331955910-0 TI - On the complexity of breaking pseudoentropy VL - 10185 ER - TY - CHAP AB - We give a short overview on a recently developed notion of Ricci curvature for discrete spaces. This notion relies on geodesic convexity properties of the relative entropy along geodesics in the space of probability densities, for a metric which is similar to (but different from) the 2-Wasserstein metric. The theory can be considered as a discrete counterpart to the theory of Ricci curvature for geodesic measure spaces developed by Lott–Sturm–Villani. AU - Maas, Jan ED - Najman, Laurent ED - Romon, Pascal ID - 649 SN - 978-3-319-58001-2 T2 - Modern Approaches to Discrete Curvature TI - Entropic Ricci curvature for discrete spaces VL - 2184 ER - TY - CONF AB - In this work we present a short and unified proof for the Strong and Weak Regularity Lemma, based on the cryptographic tech-nique called low-complexity approximations. In short, both problems reduce to a task of finding constructively an approximation for a certain target function under a class of distinguishers (test functions), where dis-tinguishers are combinations of simple rectangle-indicators. In our case these approximations can be learned by a simple iterative procedure, which yields a unified and simple proof, achieving for any graph with density d and any approximation parameter the partition size. The novelty in our proof is: (a) a simple approach which yields both strong and weaker variant, and (b) improvements when d = o(1). At an abstract level, our proof can be seen a refinement and simplification of the “analytic” proof given by Lovasz and Szegedy. AU - Skórski, Maciej ED - Jäger, Gerhard ED - Steila, Silvia ID - 650 SN - 03029743 TI - A cryptographic view of regularity lemmas: Simpler unified proofs and refined bounds VL - 10185 ER - TY - CONF AB - Graph games with omega-regular winning conditions provide a mathematical framework to analyze a wide range of problems in the analysis of reactive systems and programs (such as the synthesis of reactive systems, program repair, and the verification of branching time properties). Parity conditions are canonical forms to specify omega-regular winning conditions. Graph games with parity conditions are equivalent to mu-calculus model checking, and thus a very important algorithmic problem. Symbolic algorithms are of great significance because they provide scalable algorithms for the analysis of large finite-state systems, as well as algorithms for the analysis of infinite-state systems with finite quotient. A set-based symbolic algorithm uses the basic set operations and the one-step predecessor operators. We consider graph games with n vertices and parity conditions with c priorities (equivalently, a mu-calculus formula with c alternations of least and greatest fixed points). While many explicit algorithms exist for graph games with parity conditions, for set-based symbolic algorithms there are only two algorithms (notice that we use space to refer to the number of sets stored by a symbolic algorithm): (a) the basic algorithm that requires O(n^c) symbolic operations and linear space; and (b) an improved algorithm that requires O(n^{c/2+1}) symbolic operations but also O(n^{c/2+1}) space (i.e., exponential space). In this work we present two set-based symbolic algorithms for parity games: (a) our first algorithm requires O(n^{c/2+1}) symbolic operations and only requires linear space; and (b) developing on our first algorithm, we present an algorithm that requires O(n^{c/3+1}) symbolic operations and only linear space. We also present the first linear space set-based symbolic algorithm for parity games that requires at most a sub-exponential number of symbolic operations. AU - Chatterjee, Krishnendu AU - Dvorák, Wolfgang AU - Henzinger, Monika H AU - Loitzenbauer, Veronika ID - 6519 TI - Improved set-based symbolic algorithms for parity games VL - 82 ER - TY - CONF AB - A (possibly degenerate) drawing of a graph G in the plane is approximable by an embedding if it can be turned into an embedding by an arbitrarily small perturbation. We show that testing, whether a drawing of a planar graph G in the plane is approximable by an embedding, can be carried out in polynomial time, if a desired embedding of G belongs to a fixed isotopy class, i.e., the rotation system (or equivalently the faces) of the embedding of G and the choice of outer face are fixed. In other words, we show that c-planarity with embedded pipes is tractable for graphs with fixed embeddings. To the best of our knowledge an analogous result was previously known essentially only when G is a cycle. AU - Fulek, Radoslav ID - 6517 TI - Embedding graphs into embedded graphs VL - 92 ER - TY - CONF AB - We present an approach that enables robots to self-organize their sensorimotor behavior from scratch without providing specific information about neither the robot nor its environment. This is achieved by a simple neural control law that increases the consistency between external sensor dynamics and internal neural dynamics of the utterly simple controller. In this way, the embodiment and the agent-environment coupling are the only source of individual development. We show how an anthropomorphic tendon driven arm-shoulder system develops different behaviors depending on that coupling. For instance: Given a bottle half-filled with water, the arm starts to shake it, driven by the physical response of the water. When attaching a brush, the arm can be manipulated into wiping a table, and when connected to a revolvable wheel it finds out how to rotate it. Thus, the robot may be said to discover the affordances of the world. When allowing two (simulated) humanoid robots to interact physically, they engage into a joint behavior development leading to, for instance, spontaneous cooperation. More social effects are observed if the robots can visually perceive each other. Although, as an observer, it is tempting to attribute an apparent intentionality, there is nothing of the kind put in. As a conclusion, we argue that emergent behavior may be much less rooted in explicit intentions, internal motivations, or specific reward systems than is commonly believed. AU - Der, Ralf AU - Martius, Georg S ID - 652 SN - 978-150905069-7 TI - Dynamical self consistency leads to behavioral development and emergent social interactions in robots ER - TY - JOUR AB - Superhydrophobic surfaces reduce the frictional drag between water and solid materials, but this effect is often temporary. The realization of sustained drag reduction has applications for water vehicles and pipeline flows. AU - Hof, Björn ID - 651 IS - 7636 JF - Nature SN - 00280836 TI - Fluid dynamics: Water flows out of touch VL - 541 ER - TY - JOUR AB - The extent of heterogeneity among driver gene mutations present in naturally occurring metastases - that is, treatment-naive metastatic disease - is largely unknown. To address this issue, we carried out 60× whole-genome sequencing of 26 metastases from four patients with pancreatic cancer. We found that identical mutations in known driver genes were present in every metastatic lesion for each patient studied. Passenger gene mutations, which do not have known or predicted functional consequences, accounted for all intratumoral heterogeneity. Even with respect to these passenger mutations, our analysis suggests that the genetic similarity among the founding cells of metastases was higher than that expected for any two cells randomly taken from a normal tissue. The uniformity of known driver gene mutations among metastases in the same patient has critical and encouraging implications for the success of future targeted therapies in advanced-stage disease. AU - Makohon Moore, Alvin AU - Zhang, Ming AU - Reiter, Johannes AU - Božić, Ivana AU - Allen, Benjamin AU - Kundu, Deepanjan AU - Chatterjee, Krishnendu AU - Wong, Fay AU - Jiao, Yuchen AU - Kohutek, Zachary AU - Hong, Jungeui AU - Attiyeh, Marc AU - Javier, Breanna AU - Wood, Laura AU - Hruban, Ralph AU - Nowak, Martin AU - Papadopoulos, Nickolas AU - Kinzler, Kenneth AU - Vogelstein, Bert AU - Iacobuzio Donahue, Christine ID - 653 IS - 3 JF - Nature Genetics SN - 10614036 TI - Limited heterogeneity of known driver gene mutations among the metastases of individual patients with pancreatic cancer VL - 49 ER - TY - CONF AB - A memory-hard function (MHF) ƒn with parameter n can be computed in sequential time and space n. Simultaneously, a high amortized parallel area-time complexity (aAT) is incurred per evaluation. In practice, MHFs are used to limit the rate at which an adversary (using a custom computational device) can evaluate a security sensitive function that still occasionally needs to be evaluated by honest users (using an off-the-shelf general purpose device). The most prevalent examples of such sensitive functions are Key Derivation Functions (KDFs) and password hashing algorithms where rate limits help mitigate off-line dictionary attacks. As the honest users' inputs to these functions are often (low-entropy) passwords special attention is given to a class of side-channel resistant MHFs called iMHFs. Essentially all iMHFs can be viewed as some mode of operation (making n calls to some round function) given by a directed acyclic graph (DAG) with very low indegree. Recently, a combinatorial property of a DAG has been identified (called "depth-robustness") which results in good provable security for an iMHF based on that DAG. Depth-robust DAGs have also proven useful in other cryptographic applications. Unfortunately, up till now, all known very depth-robust DAGs are impractically complicated and little is known about their exact (i.e. non-asymptotic) depth-robustness both in theory and in practice. In this work we build and analyze (both formally and empirically) several exceedingly simple and efficient to navigate practical DAGs for use in iMHFs and other applications. For each DAG we: *Prove that their depth-robustness is asymptotically maximal. *Prove bounds of at least 3 orders of magnitude better on their exact depth-robustness compared to known bounds for other practical iMHF. *Implement and empirically evaluate their depth-robustness and aAT against a variety of state-of-the art (and several new) depth-reduction and low aAT attacks. We find that, against all attacks, the new DAGs perform significantly better in practice than Argon2i, the most widely deployed iMHF in practice. Along the way we also improve the best known empirical attacks on the aAT of Argon2i by implementing and testing several heuristic versions of a (hitherto purely theoretical) depth-reduction attack. Finally, we demonstrate practicality of our constructions by modifying the Argon2i code base to use one of the new high aAT DAGs. Experimental benchmarks on a standard off-the-shelf CPU show that the new modifications do not adversely affect the impressive throughput of Argon2i (despite seemingly enjoying significantly higher aAT). AU - Alwen, Joel F AU - Blocki, Jeremiah AU - Harsha, Ben ID - 6527 SN - 9781450349468 T2 - Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security TI - Practical graphs for optimal side-channel resistant memory-hard functions ER - TY - JOUR AB - In November 2016, developmental biologists, synthetic biologists and engineers gathered in Paris for a meeting called ‘Engineering the embryo’. The participants shared an interest in exploring how synthetic systems can reveal new principles of embryonic development, and how the in vitro manipulation and modeling of development using stem cells can be used to integrate ideas and expertise from physics, developmental biology and tissue engineering. As we review here, the conference pinpointed some of the challenges arising at the intersection of these fields, along with great enthusiasm for finding new approaches and collaborations. AU - Kicheva, Anna AU - Rivron, Nicolas ID - 654 IS - 5 JF - Development SN - 09501991 TI - Creating to understand – developmental biology meets engineering in Paris VL - 144 ER - TY - CONF AB - This paper studies the complexity of estimating Rényi divergences of discrete distributions: p observed from samples and the baseline distribution q known a priori. Extending the results of Acharya et al. (SODA'15) on estimating Rényi entropy, we present improved estimation techniques together with upper and lower bounds on the sample complexity. We show that, contrarily to estimating Rényi entropy where a sublinear (in the alphabet size) number of samples suffices, the sample complexity is heavily dependent on events occurring unlikely in q, and is unbounded in general (no matter what an estimation technique is used). For any divergence of integer order bigger than 1, we provide upper and lower bounds on the number of samples dependent on probabilities of p and q (the lower bounds hold for non-integer orders as well). We conclude that the worst-case sample complexity is polynomial in the alphabet size if and only if the probabilities of q are non-negligible. This gives theoretical insights into heuristics used in the applied literature to handle numerical instability, which occurs for small probabilities of q. Our result shows that they should be handled with care not only because of numerical issues, but also because of a blow up in the sample complexity. AU - Skórski, Maciej ID - 6526 SN - 9781509040964 T2 - 2017 IEEE International Symposium on Information Theory (ISIT) TI - On the complexity of estimating Rènyi divergences ER - TY - JOUR AB - The bacterial flagellum is a self-assembling nanomachine. The external flagellar filament, several times longer than a bacterial cell body, is made of a few tens of thousands subunits of a single protein: flagellin. A fundamental problem concerns the molecular mechanism of how the flagellum grows outside the cell, where no discernible energy source is available. Here, we monitored the dynamic assembly of individual flagella using in situ labelling and real-time immunostaining of elongating flagellar filaments. We report that the rate of flagellum growth, initially ~1,700 amino acids per second, decreases with length and that the previously proposed chain mechanism does not contribute to the filament elongation dynamics. Inhibition of the proton motive force-dependent export apparatus revealed a major contribution of substrate injection in driving filament elongation. The combination of experimental and mathematical evidence demonstrates that a simple, injection-diffusion mechanism controls bacterial flagella growth outside the cell. AU - Renault, Thibaud AU - Abraham, Anthony AU - Bergmiller, Tobias AU - Paradis, Guillaume AU - Rainville, Simon AU - Charpentier, Emmanuelle AU - Guet, Calin C AU - Tu, Yuhai AU - Namba, Keiichi AU - Keener, James AU - Minamino, Tohru AU - Erhardt, Marc ID - 655 JF - eLife SN - 2050084X TI - Bacterial flagella grow through an injection diffusion mechanism VL - 6 ER - TY - JOUR AB - Plant organs are typically organized into three main tissue layers. The middle ground tissue layer comprises the majority of the plant body and serves a wide range of functions, including photosynthesis, selective nutrient uptake and storage, and gravity sensing. Ground tissue patterning and maintenance in Arabidopsis are controlled by a well-established gene network revolving around the key regulator SHORT-ROOT (SHR). In contrast, it is completely unknown how ground tissue identity is first specified from totipotent precursor cells in the embryo. The plant signaling molecule auxin, acting through AUXIN RESPONSE FACTOR (ARF) transcription factors, is critical for embryo patterning. The auxin effector ARF5/MONOPTEROS (MP) acts both cell-autonomously and noncell-autonomously to control embryonic vascular tissue formation and root initiation, respectively. Here we show that auxin response and ARF activity cell-autonomously control the asymmetric division of the first ground tissue cells. By identifying embryonic target genes, we show that MP transcriptionally initiates the ground tissue lineage and acts upstream of the regulatory network that controls ground tissue patterning and maintenance. Strikingly, whereas the SHR network depends on MP, this MP function is, at least in part, SHR independent. Our study therefore identifies auxin response as a regulator of ground tissue specification in the embryonic root, and reveals that ground tissue initiation and maintenance use different regulators and mechanisms. Moreover, our data provide a framework for the simultaneous formation of multiple cell types by the same transcriptional regulator. AU - Möller, Barbara AU - Ten Hove, Colette AU - Xiang, Daoquan AU - Williams, Nerys AU - López, Lorena AU - Yoshida, Saiko AU - Smit, Margot AU - Datla, Raju AU - Weijers, Dolf ID - 657 IS - 12 JF - PNAS SN - 00278424 TI - Auxin response cell autonomously controls ground tissue initiation in the early arabidopsis embryo VL - 114 ER - TY - JOUR AB - Human neurons transplanted into a mouse model for Alzheimer’s disease show human-specific vulnerability to β-amyloid plaques and may help to identify new therapeutic targets. AU - Novarino, Gaia ID - 656 IS - 381 JF - Science Translational Medicine SN - 19466234 TI - Modeling Alzheimer's disease in mice with human neurons VL - 9 ER - TY - JOUR AB - With the accelerated development of robot technologies, control becomes one of the central themes of research. In traditional approaches, the controller, by its internal functionality, finds appropriate actions on the basis of specific objectives for the task at hand. While very successful in many applications, self-organized control schemes seem to be favored in large complex systems with unknown dynamics or which are difficult to model. Reasons are the expected scalability, robustness, and resilience of self-organizing systems. The paper presents a self-learning neurocontroller based on extrinsic differential plasticity introduced recently, applying it to an anthropomorphic musculoskeletal robot arm with attached objects of unknown physical dynamics. The central finding of the paper is the following effect: by the mere feedback through the internal dynamics of the object, the robot is learning to relate each of the objects with a very specific sensorimotor pattern. Specifically, an attached pendulum pilots the arm into a circular motion, a half-filled bottle produces axis oriented shaking behavior, a wheel is getting rotated, and wiping patterns emerge automatically in a table-plus-brush setting. By these object-specific dynamical patterns, the robot may be said to recognize the object's identity, or in other words, it discovers dynamical affordances of objects. Furthermore, when including hand coordinates obtained from a camera, a dedicated hand-eye coordination self-organizes spontaneously. These phenomena are discussed from a specific dynamical system perspective. Central is the dedicated working regime at the border to instability with its potentially infinite reservoir of (limit cycle) attractors "waiting" to be excited. Besides converging toward one of these attractors, variate behavior is also arising from a self-induced attractor morphing driven by the learning rule. We claim that experimental investigations with this anthropomorphic, self-learning robot not only generate interesting and potentially useful behaviors, but may also help to better understand what subjective human muscle feelings are, how they can be rooted in sensorimotor patterns, and how these concepts may feed back on robotics. AU - Der, Ralf AU - Martius, Georg S ID - 658 IS - MAR JF - Frontiers in Neurorobotics SN - 16625218 TI - Self organized behavior generation for musculoskeletal robots VL - 11 ER - TY - JOUR AB - Migration frequently involves Rac-mediated protrusion of lamellipodia, formed by Arp2/3 complex-dependent branching thought to be crucial for force generation and stability of these networks. The formins FMNL2 and FMNL3 are Cdc42 effectors targeting to the lamellipodium tip and shown here to nucleate and elongate actin filaments with complementary activities in vitro. In migrating B16-F1 melanoma cells, both formins contribute to the velocity of lamellipodium protrusion. Loss of FMNL2/3 function in melanoma cells and fibroblasts reduces lamellipodial width, actin filament density and -bundling, without changing patterns of Arp2/3 complex incorporation. Strikingly, in melanoma cells, FMNL2/3 gene inactivation almost completely abolishes protrusion forces exerted by lamellipodia and modifies their ultrastructural organization. Consistently, CRISPR/Cas-mediated depletion of FMNL2/3 in fibroblasts reduces both migration and capability of cells to move against viscous media. Together, we conclude that force generation in lamellipodia strongly depends on FMNL formin activity, operating in addition to Arp2/3 complex-dependent filament branching. AU - Kage, Frieda AU - Winterhoff, Moritz AU - Dimchev, Vanessa AU - Müller, Jan AU - Thalheim, Tobias AU - Freise, Anika AU - Brühmann, Stefan AU - Kollasser, Jana AU - Block, Jennifer AU - Dimchev, Georgi A AU - Geyer, Matthias AU - Schnittler, Hams AU - Brakebusch, Cord AU - Stradal, Theresia AU - Carlier, Marie AU - Sixt, Michael K AU - Käs, Josef AU - Faix, Jan AU - Rottner, Klemens ID - 659 JF - Nature Communications SN - 20411723 TI - FMNL formins boost lamellipodial force generation VL - 8 ER - TY - JOUR AB - Growing microtubules are protected from depolymerization by the presence of a GTP or GDP/Pi cap. End-binding proteins of the EB1 family bind to the stabilizing cap, allowing monitoring of its size in real time. The cap size has been shown to correlate with instantaneous microtubule stability. Here we have quantitatively characterized the properties of cap size fluctuations during steadystate growth and have developed a theory predicting their timescale and amplitude from the kinetics of microtubule growth and cap maturation. In contrast to growth speed fluctuations, cap size fluctuations show a characteristic timescale, which is defined by the lifetime of the cap sites. Growth fluctuations affect the amplitude of cap size fluctuations; however, cap size does not affect growth speed, indicating that microtubules are far from instability during most of their time of growth. Our theory provides the basis for a quantitative understanding of microtubule stability fluctuations during steady-state growth. AU - Rickman, Jamie AU - Düllberg, Christian F AU - Cade, Nicholas AU - Griffin, Lewis AU - Surrey, Thomas ID - 660 IS - 13 JF - PNAS SN - 00278424 TI - Steady state EB cap size fluctuations are determined by stochastic microtubule growth and maturation VL - 114 ER - TY - JOUR AB - We report a direct-numerical-simulation study of the Taylor-Couette flow in the quasi-Keplerian regime at shear Reynolds numbers up to (105). Quasi-Keplerian rotating flow has been investigated for decades as a simplified model system to study the origin of turbulence in accretion disks that is not fully understood. The flow in this study is axially periodic and thus the experimental end-wall effects on the stability of the flow are avoided. Using optimal linear perturbations as initial conditions, our simulations find no sustained turbulence: the strong initial perturbations distort the velocity profile and trigger turbulence that eventually decays. AU - Shi, Liang AU - Hof, Björn AU - Rampp, Markus AU - Avila, Marc ID - 662 IS - 4 JF - Physics of Fluids SN - 10706631 TI - Hydrodynamic turbulence in quasi Keplerian rotating flows VL - 29 ER - TY - CONF AB - In this paper, we propose an approach to automatically compute invariant clusters for nonlinear semialgebraic hybrid systems. An invariant cluster for an ordinary differential equation (ODE) is a multivariate polynomial invariant g(u→, x→) = 0, parametric in u→, which can yield an infinite number of concrete invariants by assigning different values to u→ so that every trajectory of the system can be overapproximated precisely by the intersection of a group of concrete invariants. For semialgebraic systems, which involve ODEs with multivariate polynomial right-hand sides, given a template multivariate polynomial g(u→, x→), an invariant cluster can be obtained by first computing the remainder of the Lie derivative of g(u→, x→) divided by g(u→, x→) and then solving the system of polynomial equations obtained from the coefficients of the remainder. Based on invariant clusters and sum-of-squares (SOS) programming, we present a new method for the safety verification of hybrid systems. Experiments on nonlinear benchmark systems from biology and control theory show that our approach is efficient. AU - Kong, Hui AU - Bogomolov, Sergiy AU - Schilling, Christian AU - Jiang, Yu AU - Henzinger, Thomas A ID - 663 SN - 978-145034590-3 T2 - Proceedings of the 20th International Conference on Hybrid Systems TI - Safety verification of nonlinear hybrid systems based on invariant clusters ER - TY - JOUR AB - Perinatal exposure to penicillin may result in longlasting gut and behavioral changes. AU - Novarino, Gaia ID - 667 IS - 387 JF - Science Translational Medicine SN - 19466234 TI - The antisocial side of antibiotics VL - 9 ER - TY - JOUR AB - Macrophage filopodia, finger-like membrane protrusions, were first implicated in phagocytosis more than 100 years ago, but little is still known about the involvement of these actin-dependent structures in particle clearance. Using spinning disk confocal microscopy to image filopodial dynamics in mouse resident Lifeact-EGFP macrophages, we show that filopodia, or filopodia-like structures, support pathogen clearance by multiple means. Filopodia supported the phagocytic uptake of bacterial (Escherichia coli) particles by (i) capturing along the filopodial shaft and surfing toward the cell body, the most common mode of capture; (ii) capturing via the tip followed by retraction; (iii) combinations of surfing and retraction; or (iv) sweeping actions. In addition, filopodia supported the uptake of zymosan (Saccharomyces cerevisiae) particles by (i) providing fixation, (ii) capturing at the tip and filopodia-guided actin anterograde flow with phagocytic cup formation, and (iii) the rapid growth of new protrusions. To explore the role of filopodia-inducing Cdc42, we generated myeloid-restricted Cdc42 knock-out mice. Cdc42-deficient macrophages exhibited rapid phagocytic cup kinetics, but reduced particle clearance, which could be explained by the marked rounded-up morphology of these cells. Macrophages lacking Myo10, thought to act downstream of Cdc42, had normal morphology, motility, and phagocytic cup formation, but displayed markedly reduced filopodia formation. In conclusion, live-cell imaging revealed multiple mechanisms involving macrophage filopodia in particle capture and engulfment. Cdc42 is not critical for filopodia or phagocytic cup formation, but plays a key role in driving macrophage lamellipodial spreading. AU - Horsthemke, Markus AU - Bachg, Anne AU - Groll, Katharina AU - Moyzio, Sven AU - Müther, Barbara AU - Hemkemeyer, Sandra AU - Wedlich Söldner, Roland AU - Sixt, Michael K AU - Tacke, Sebastian AU - Bähler, Martin AU - Hanley, Peter ID - 668 IS - 17 JF - Journal of Biological Chemistry SN - 00219258 TI - Multiple roles of filopodial dynamics in particle capture and phagocytosis and phenotypes of Cdc42 and Myo10 deletion VL - 292 ER - TY - JOUR AB - The exocyst, a eukaryotic tethering complex, coregulates targeted exocytosis as an effector of small GTPases in polarized cell growth. In land plants, several exocyst subunits are encoded by double or triple paralogs, culminating in tens of EXO70 paralogs. Out of 23 Arabidopsis thaliana EXO70 isoforms, we analyzed seven isoforms expressed in pollen. Genetic and microscopic analyses of single mutants in EXO70A2, EXO70C1, EXO70C2, EXO70F1, EXO70H3, EXO70H5, and EXO70H6 genes revealed that only a loss-of-function EXO70C2 allele resulted in a significant male-specific transmission defect (segregation 40%:51%:9%) due to aberrant pollen tube growth. Mutant pollen tubes grown in vitro exhibited an enhanced growth rate and a decreased thickness of the tip cell wall, causing tip bursts. However, exo70C2 pollen tubes could frequently recover and restart their speedy elongation, resulting in a repetitive stop-and-go growth dynamics. A pollenspecific depletion of the closest paralog, EXO70C1, using artificial microRNA in the exo70C2 mutant background, resulted in a complete pollen-specific transmission defect, suggesting redundant functions of EXO70C1 and EXO70C2. Both EXO70C1 and EXO70C2, GFP tagged and expressed under the control of their native promoters, localized in the cytoplasm of pollen grains, pollen tubes, and also root trichoblast cells. The expression of EXO70C2-GFP complemented the aberrant growth of exo70C2 pollen tubes. The absent EXO70C2 interactions with core exocyst subunits in the yeast two-hybrid assay, cytoplasmic localization, and genetic effect suggest an unconventional EXO70 function possibly as a regulator of exocytosis outside the exocyst complex. In conclusion, EXO70C2 is a novel factor contributing to the regulation of optimal tip growth of Arabidopsis pollen tubes. AU - Synek, Lukáš AU - Vukašinović, Nemanja AU - Kulich, Ivan AU - Hála, Michal AU - Aldorfová, Klára AU - Fendrych, Matyas AU - Žárský, Viktor ID - 669 IS - 1 JF - Plant Physiology SN - 00320889 TI - EXO70C2 is a key regulatory factor for optimal tip growth of pollen VL - 174 ER - TY - JOUR AB - Humans routinely use conditionally cooperative strategies when interacting in repeated social dilemmas. They are more likely to cooperate if others cooperated before, and are ready to retaliate if others defected. To capture the emergence of reciprocity, most previous models consider subjects who can only choose from a restricted set of representative strategies, or who react to the outcome of the very last round only. As players memorize more rounds, the dimension of the strategy space increases exponentially. This increasing computational complexity renders simulations for individuals with higher cognitive abilities infeasible, especially if multiplayer interactions are taken into account. Here, we take an axiomatic approach instead. We propose several properties that a robust cooperative strategy for a repeated multiplayer dilemma should have. These properties naturally lead to a unique class of cooperative strategies, which contains the classical Win-Stay Lose-Shift rule as a special case. A comprehensive numerical analysis for the prisoner's dilemma and for the public goods game suggests that strategies of this class readily evolve across various memory-n spaces. Our results reveal that successful strategies depend not only on how cooperative others were in the past but also on the respective context of cooperation. AU - Hilbe, Christian AU - Martinez, Vaquero AU - Chatterjee, Krishnendu AU - Nowak, Martin ID - 671 IS - 18 JF - PNAS SN - 00278424 TI - Memory-n strategies of direct reciprocity VL - 114 ER - TY - JOUR AB - We propose an efficient method to model paper tearing in the context of interactive modeling. The method uses geometrical information to automatically detect potential starting points of tears. We further introduce a new hybrid geometrical and physical-based method to compute the trajectory of tears while procedurally synthesizing high resolution details of the tearing path using a texture based approach. The results obtained are compared with real paper and with previous studies on the expected geometric paths of paper that tears. AU - Schreck, Camille AU - Rohmer, Damien AU - Hahmann, Stefanie ID - 670 IS - 2 JF - Computer Graphics Forum SN - 01677055 TI - Interactive paper tearing VL - 36 ER - TY - JOUR AB - Trafficking cells frequently transmigrate through epithelial and endothelial monolayers. How monolayers cooperate with the penetrating cells to support their transit is poorly understood. We studied dendritic cell (DC) entry into lymphatic capillaries as a model system for transendothelial migration. We find that the chemokine CCL21, which is the decisive guidance cue for intravasation, mainly localizes in the trans-Golgi network and intracellular vesicles of lymphatic endothelial cells. Upon DC transmigration, these Golgi deposits disperse and CCL21 becomes extracellularly enriched at the sites of endothelial cell-cell junctions. When we reconstitute the transmigration process in vitro, we find that secretion of CCL21-positive vesicles is triggered by a DC contact-induced calcium signal, and selective calcium chelation in lymphatic endothelium attenuates transmigration. Altogether, our data demonstrate a chemokine-mediated feedback between DCs and lymphatic endothelium, which facilitates transendothelial migration. AU - Vaahtomeri, Kari AU - Brown, Markus AU - Hauschild, Robert AU - De Vries, Ingrid AU - Leithner, Alexander F AU - Mehling, Matthias AU - Kaufmann, Walter AU - Sixt, Michael K ID - 672 IS - 5 JF - Cell Reports SN - 22111247 TI - Locally triggered release of the chemokine CCL21 promotes dendritic cell transmigration across lymphatic endothelia VL - 19 ER - TY - JOUR AB - Navigation of cells along gradients of guidance cues is a determining step in many developmental and immunological processes. Gradients can either be soluble or immobilized to tissues as demonstrated for the haptotactic migration of dendritic cells (DCs) toward higher concentrations of immobilized chemokine CCL21. To elucidate how gradient characteristics govern cellular response patterns, we here introduce an in vitro system allowing to track migratory responses of DCs to precisely controlled immobilized gradients of CCL21. We find that haptotactic sensing depends on the absolute CCL21 concentration and local steepness of the gradient, consistent with a scenario where DC directionality is governed by the signal-to-noise ratio of CCL21 binding to the receptor CCR7. We find that the conditions for optimal DC guidance are perfectly provided by the CCL21 gradients we measure in vivo. Furthermore, we find that CCR7 signal termination by the G-protein-coupled receptor kinase 6 (GRK6) is crucial for haptotactic but dispensable for chemotactic CCL21 gradient sensing in vitro and confirm those observations in vivo. These findings suggest that stable, tissue-bound CCL21 gradients as sustainable “roads” ensure optimal guidance in vivo. AU - Schwarz, Jan AU - Bierbaum, Veronika AU - Vaahtomeri, Kari AU - Hauschild, Robert AU - Brown, Markus AU - De Vries, Ingrid AU - Leithner, Alexander F AU - Reversat, Anne AU - Merrin, Jack AU - Tarrant, Teresa AU - Bollenbach, Tobias AU - Sixt, Michael K ID - 674 IS - 9 JF - Current Biology SN - 09609822 TI - Dendritic cells interpret haptotactic chemokine gradients in a manner governed by signal to noise ratio and dependent on GRK6 VL - 27 ER - TY - JOUR AB - The INO80 complex (INO80-C) is an evolutionarily conserved nucleosome remodeler that acts in transcription, replication, and genome stability. It is required for resistance against genotoxic agents and is involved in the repair of DNA double-strand breaks (DSBs) by homologous recombination (HR). However, the causes of the HR defect in INO80-C mutant cells are controversial. Here, we unite previous findings using a system to study HR with high spatial resolution in budding yeast. We find that INO80-C has at least two distinct functions during HR—DNA end resection and presynaptic filament formation. Importantly, the second function is linked to the histone variant H2A.Z. In the absence of H2A.Z, presynaptic filament formation and HR are restored in INO80-C-deficient mutants, suggesting that presynaptic filament formation is the crucial INO80-C function during HR. AU - Lademann, Claudio AU - Renkawitz, Jörg AU - Pfander, Boris AU - Jentsch, Stefan ID - 677 IS - 7 JF - Cell Reports SN - 22111247 TI - The INO80 complex removes H2A.Z to promote presynaptic filament formation during homologous recombination VL - 19 ER - TY - JOUR AB - The seminal observation that mechanical signals can elicit changes in biochemical signalling within cells, a process commonly termed mechanosensation and mechanotransduction, has revolutionized our understanding of the role of cell mechanics in various fundamental biological processes, such as cell motility, adhesion, proliferation and differentiation. In this Review, we will discuss how the interplay and feedback between mechanical and biochemical signals control tissue morphogenesis and cell fate specification in embryonic development. AU - Petridou, Nicoletta AU - Spiro, Zoltan P AU - Heisenberg, Carl-Philipp J ID - 678 IS - 6 JF - Nature Cell Biology SN - 14657392 TI - Multiscale force sensing in development VL - 19 ER - TY - JOUR AB - Two-player games on graphs provide the theoretical framework for many important problems such as reactive synthesis. While the traditional study of two-player zero-sum games has been extended to multi-player games with several notions of equilibria, they are decidable only for perfect-information games, whereas several applications require imperfect-information. In this paper we propose a new notion of equilibria, called doomsday equilibria, which is a strategy profile where all players satisfy their own objective, and if any coalition of players deviates and violates even one of the players' objective, then the objective of every player is violated. We present algorithms and complexity results for deciding the existence of doomsday equilibria for various classes of ω-regular objectives, both for imperfect-information games, and for perfect-information games. We provide optimal complexity bounds for imperfect-information games, and in most cases for perfect-information games. AU - Chatterjee, Krishnendu AU - Doyen, Laurent AU - Filiot, Emmanuel AU - Raskin, Jean ID - 681 JF - Information and Computation SN - 08905401 TI - Doomsday equilibria for omega-regular games VL - 254 ER - TY - CONF AB - In classical machine learning, regression is treated as a black box process of identifying a suitable function from a hypothesis set without attempting to gain insight into the mechanism connecting inputs and outputs. In the natural sciences, however, finding an interpretable function for a phenomenon is the prime goal as it allows to understand and generalize results. This paper proposes a novel type of function learning network, called equation learner (EQL), that can learn analytical expressions and is able to extrapolate to unseen domains. It is implemented as an end-to-end differentiable feed-forward network and allows for efficient gradient based training. Due to sparsity regularization concise interpretable expressions can be obtained. Often the true underlying source expression is identified. AU - Martius, Georg S AU - Lampert, Christoph ID - 6841 T2 - 5th International Conference on Learning Representations, ICLR 2017 - Workshop Track Proceedings TI - Extrapolation and learning equations ER - TY - JOUR AB - We generalize winning conditions in two-player games by adding a structural acceptance condition called obligations. Obligations are orthogonal to the linear winning conditions that define whether a play is winning. Obligations are a declaration that player 0 can achieve a certain value from a configuration. If the obligation is met, the value of that configuration for player 0 is 1. We define the value in such games and show that obligation games are determined. For Markov chains with Borel objectives and obligations, and finite turn-based stochastic parity games with obligations we give an alternative and simpler characterization of the value function. Based on this simpler definition we show that the decision problem of winning finite turn-based stochastic parity games with obligations is in NP∩co-NP. We also show that obligation games provide a game framework for reasoning about p-automata. © 2017 The Association for Symbolic Logic. AU - Chatterjee, Krishnendu AU - Piterman, Nir ID - 684 IS - 2 JF - Journal of Symbolic Logic SN - 0022-4812 TI - Obligation blackwell games and p-automata VL - 82 ER - TY - JOUR AB - By applying methods and principles from the physical sciences to biological problems, D'Arcy Thompson's On Growth and Form demonstrated how mathematical reasoning reveals elegant, simple explanations for seemingly complex processes. This has had a profound influence on subsequent generations of developmental biologists. We discuss how this influence can be traced through twentieth century morphologists, embryologists and theoreticians to current research that explores the molecular and cellular mechanisms of tissue growth and patterning, including our own studies of the vertebrate neural tube. AU - Briscoe, James AU - Kicheva, Anna ID - 685 JF - Mechanisms of Development SN - 09254773 TI - The physics of development 100 years after D'Arcy Thompson's “on growth and form” VL - 145 ER - TY - CONF AB - We show that the framework of topological data analysis can be extended from metrics to general Bregman divergences, widening the scope of possible applications. Examples are the Kullback - Leibler divergence, which is commonly used for comparing text and images, and the Itakura - Saito divergence, popular for speech and sound. In particular, we prove that appropriately generalized čech and Delaunay (alpha) complexes capture the correct homotopy type, namely that of the corresponding union of Bregman balls. Consequently, their filtrations give the correct persistence diagram, namely the one generated by the uniformly growing Bregman balls. Moreover, we show that unlike the metric setting, the filtration of Vietoris-Rips complexes may fail to approximate the persistence diagram. We propose algorithms to compute the thus generalized čech, Vietoris-Rips and Delaunay complexes and experimentally test their efficiency. Lastly, we explain their surprisingly good performance by making a connection with discrete Morse theory. AU - Edelsbrunner, Herbert AU - Wagner, Hubert ID - 688 SN - 18688969 TI - Topological data analysis with Bregman divergences VL - 77 ER - TY - JOUR AB - Pursuing the similarity between the Kontsevich-Soibelman construction of the cohomological Hall algebra (CoHA) of BPS states and Lusztig's construction of canonical bases for quantum enveloping algebras, and the similarity between the integrality conjecture for motivic Donaldson-Thomas invariants and the PBW theorem for quantum enveloping algebras, we build a coproduct on the CoHA associated to a quiver with potential. We also prove a cohomological dimensional reduction theorem, further linking a special class of CoHAs with Yangians, and explaining how to connect the study of character varieties with the study of CoHAs. AU - Davison, Ben ID - 687 IS - 2 JF - Quarterly Journal of Mathematics SN - 00335606 TI - The critical CoHA of a quiver with potential VL - 68 ER - TY - JOUR AB - Tissues are thought to behave like fluids with a given surface tension. Differences in tissue surface tension (TST) have been proposed to trigger cell sorting and tissue envelopment. D'Arcy Thompson in his seminal book ‘On Growth and Form’ has introduced this concept of differential TST as a key physical mechanism dictating tissue formation and organization within the developing organism. Over the past century, many studies have picked up the concept of differential TST and analyzed the role and cell biological basis of TST in development, underlining the importance and influence of this concept in developmental biology. AU - Heisenberg, Carl-Philipp J ID - 686 JF - Mechanisms of Development SN - 09254773 TI - D'Arcy Thompson's ‘on growth and form’: From soap bubbles to tissue self organization VL - 145 ER - TY - JOUR AB - Rett syndrome modeling in monkey mirrors the human disorder. AU - Novarino, Gaia ID - 689 IS - 393 JF - Science Translational Medicine SN - 19466234 TI - Rett syndrome modeling goes simian VL - 9 ER - TY - JOUR AB - Many central synapses contain a single presynaptic active zone and a single postsynaptic density. Vesicular release statistics at such “simple synapses” indicate that they contain a small complement of docking sites where vesicles repetitively dock and fuse. In this work, we investigate functional and morphological aspects of docking sites at simple synapses made between cerebellar parallel fibers and molecular layer interneurons. Using immunogold labeling of SDS-treated freeze-fracture replicas, we find that Cav2.1 channels form several clusters per active zone with about nine channels per cluster. The mean value and range of intersynaptic variation are similar for Cav2.1 cluster numbers and for functional estimates of docking-site numbers obtained from the maximum numbers of released vesicles per action potential. Both numbers grow in relation with synaptic size and decrease by a similar extent with age between 2 wk and 4 wk postnatal. Thus, the mean docking-site numbers were 3.15 at 2 wk (range: 1–10) and 2.03 at 4 wk (range: 1–4), whereas the mean numbers of Cav2.1 clusters were 2.84 at 2 wk (range: 1–8) and 2.37 at 4 wk (range: 1–5). These changes were accompanied by decreases of miniature current amplitude (from 93 pA to 56 pA), active-zone surface area (from 0.0427 μm2 to 0.0234 μm2), and initial success rate (from 0.609 to 0.353), indicating a tightening of synaptic transmission with development. Altogether, these results suggest a close correspondence between the number of functionally defined vesicular docking sites and that of clusters of voltage-gated calcium channels. AU - Miki, Takafumi AU - Kaufmann, Walter AU - Malagon, Gerardo AU - Gomez, Laura AU - Tabuchi, Katsuhiko AU - Watanabe, Masahiko AU - Shigemoto, Ryuichi AU - Marty, Alain ID - 693 IS - 26 JF - PNAS SN - 00278424 TI - Numbers of presynaptic Ca2+ channel clusters match those of functionally defined vesicular docking sites in single central synapses VL - 114 ER - TY - JOUR AB - A change regarding the extent of adhesion - hereafter referred to as adhesion plasticity - between adhesive and less-adhesive states of mammalian cells is important for their behavior. To investigate adhesion plasticity, we have selected a stable isogenic subpopulation of human MDA-MB-468 breast carcinoma cells growing in suspension. These suspension cells are unable to re-adhere to various matrices or to contract three-dimensional collagen lattices. By using transcriptome analysis, we identified the focal adhesion protein tensin3 (Tns3) as a determinant of adhesion plasticity. Tns3 is strongly reduced at mRNA and protein levels in suspension cells. Furthermore, by transiently challenging breast cancer cells to grow under non-adherent conditions markedly reduces Tns3 protein expression, which is regained upon re-adhesion. Stable knockdown of Tns3 in parental MDA-MB-468 cells results in defective adhesion, spreading and migration. Tns3-knockdown cells display impaired structure and dynamics of focal adhesion complexes as determined by immunostaining. Restoration of Tns3 protein expression in suspension cells partially rescues adhesion and focal contact composition. Our work identifies Tns3 as a crucial focal adhesion component regulated by, and functionally contributing to, the switch between adhesive and non-adhesive states in MDA-MB-468 cancer cells. AU - Veß, Astrid AU - Blache, Ulrich AU - Leitner, Laura AU - Kurz, Angela AU - Ehrenpfordt, Anja AU - Sixt, Michael K AU - Posern, Guido ID - 694 IS - 13 JF - Journal of Cell Science SN - 00219533 TI - A dual phenotype of MDA MB 468 cancer cells reveals mutual regulation of tensin3 and adhesion plasticity VL - 130 ER - TY - CONF AB - De, Trevisan and Tulsiani [CRYPTO 2010] show that every distribution over n-bit strings which has constant statistical distance to uniform (e.g., the output of a pseudorandom generator mapping n-1 to n bit strings), can be distinguished from the uniform distribution with advantage epsilon by a circuit of size O( 2^n epsilon^2). We generalize this result, showing that a distribution which has less than k bits of min-entropy, can be distinguished from any distribution with k bits of delta-smooth min-entropy with advantage epsilon by a circuit of size O(2^k epsilon^2/delta^2). As a special case, this implies that any distribution with support at most 2^k (e.g., the output of a pseudoentropy generator mapping k to n bit strings) can be distinguished from any given distribution with min-entropy k+1 with advantage epsilon by a circuit of size O(2^k epsilon^2). Our result thus shows that pseudoentropy distributions face basically the same non-uniform attacks as pseudorandom distributions. AU - Pietrzak, Krzysztof Z AU - Skórski, Maciej ID - 697 SN - 18688969 TI - Non uniform attacks against pseudoentropy VL - 80 ER - TY - JOUR AB - Extracellular matrix signals from the microenvironment regulate gene expression patterns and cell behavior. Using a combination of experiments and geometric models, we demonstrate correlations between cell geometry, three-dimensional (3D) organization of chromosome territories, and gene expression. Fluorescence in situ hybridization experiments showed that micropatterned fibroblasts cultured on anisotropic versus isotropic substrates resulted in repositioning of specific chromosomes, which contained genes that were differentially regulated by cell geometries. Experiments combined with ellipsoid packing models revealed that the mechanosensitivity of chromosomes was correlated with their orientation in the nucleus. Transcription inhibition experiments suggested that the intermingling degree was more sensitive to global changes in transcription than to chromosome radial positioning and its orientations. These results suggested that cell geometry modulated 3D chromosome arrangement, and their neighborhoods correlated with gene expression patterns in a predictable manner. This is central to understanding geometric control of genetic programs involved in cellular homeostasis and the associated diseases. AU - Wang, Yejun AU - Nagarajan, Mallika AU - Uhler, Caroline AU - Shivashankar, Gv ID - 698 IS - 14 JF - Molecular Biology of the Cell SN - 10591524 TI - Orientation and repositioning of chromosomes correlate with cell geometry dependent gene expression VL - 28 ER - TY - JOUR AB - In antagonistic symbioses, such as host–parasite interactions, one population’s success is the other’s loss. In mutualistic symbioses, such as division of labor, both parties can gain, but they might have different preferences over the possible mutualistic arrangements. The rates of evolution of the two populations in a symbiosis are important determinants of which population will be more successful: Faster evolution is thought to be favored in antagonistic symbioses (the “Red Queen effect”), but disfavored in certain mutualistic symbioses (the “Red King effect”). However, it remains unclear which biological parameters drive these effects. Here, we analyze the effects of the various determinants of evolutionary rate: generation time, mutation rate, population size, and the intensity of natural selection. Our main results hold for the case where mutation is infrequent. Slower evolution causes a long-term advantage in an important class of mutualistic interactions. Surprisingly, less intense selection is the strongest driver of this Red King effect, whereas relative mutation rates and generation times have little effect. In antagonistic interactions, faster evolution by any means is beneficial. Our results provide insight into the demographic evolution of symbionts. AU - Veller, Carl AU - Hayward, Laura AU - Nowak, Martin AU - Hilbe, Christian ID - 699 IS - 27 JF - PNAS SN - 00278424 TI - The red queen and king in finite populations VL - 114 ER - TY - JOUR AB - Microtubules provide the mechanical force required for chromosome separation during mitosis. However, little is known about the dynamic (high-frequency) mechanical properties of microtubules. Here, we theoretically propose to control the vibrations of a doubly clamped microtubule by tip electrodes and to detect its motion via the optomechanical coupling between the vibrational modes of the microtubule and an optical cavity. In the presence of a red-detuned strong pump laser, this coupling leads to optomechanical-induced transparency of an optical probe field, which can be detected with state-of-the art technology. The center frequency and line width of the transparency peak give the resonance frequency and damping rate of the microtubule, respectively, while the height of the peak reveals information about the microtubule-cavity field coupling. Our method opens the new possibilities to gain information about the physical properties of microtubules, which will enhance our capability to design physical cancer treatment protocols as alternatives to chemotherapeutic drugs. AU - Barzanjeh, Shabir AU - Salari, Vahid AU - Tuszynski, Jack AU - Cifra, Michal AU - Simon, Christoph ID - 700 IS - 1 JF - Physical Review E Statistical Nonlinear and Soft Matter Physics SN - 24700045 TI - Optomechanical proposal for monitoring microtubule mechanical vibrations VL - 96 ER - TY - JOUR AB - A d-dimensional simplex S is called a k-reptile (or a k-reptile simplex) if it can be tiled by k simplices with disjoint interiors that are all mutually congruent and similar to S. For d = 2, triangular k-reptiles exist for all k of the form a^2, 3a^2 or a^2+b^2 and they have been completely characterized by Snover, Waiveris, and Williams. On the other hand, the only k-reptile simplices that are known for d ≥ 3, have k = m^d, where m is a positive integer. We substantially simplify the proof by Matoušek and the second author that for d = 3, k-reptile tetrahedra can exist only for k = m^3. We then prove a weaker analogue of this result for d = 4 by showing that four-dimensional k-reptile simplices can exist only for k = m^2. AU - Kynčl, Jan AU - Patakova, Zuzana ID - 701 IS - 3 JF - The Electronic Journal of Combinatorics SN - 10778926 TI - On the nonexistence of k reptile simplices in ℝ^3 and ℝ^4 VL - 24 ER - TY - JOUR AB - Leading autism-associated mutation in mouse partially mimics human disorder. AU - Novarino, Gaia ID - 702 IS - 399 JF - Science Translational Medicine SN - 19466234 TI - The riddle of CHD8 haploinsufficiency in autism spectrum disorder VL - 9 ER - TY - JOUR AB - A hippocampal mossy fiber synapse has a complex structure and is implicated in learning and memory. In this synapse, the mossy fiber boutons attach to the dendritic shaft by puncta adherentia junctions and wrap around a multiply-branched spine, forming synaptic junctions. We have recently shown using transmission electron microscopy, immunoelectron microscopy and serial block face-scanning electron microscopy that atypical puncta adherentia junctions are formed in the afadin-deficient mossy fiber synapse and that the complexity of postsynaptic spines and mossy fiber boutons, the number of spine heads, the area of postsynaptic densities and the density of synaptic vesicles docked to active zones are decreased in the afadin-deficient synapse. We investigated here the roles of afadin in the functional differentiations of the mossy fiber synapse using the afadin-deficient mice. The electrophysiological studies showed that both the release probability of glutamate and the postsynaptic responsiveness to glutamate were markedly reduced, but not completely lost, in the afadin-deficient mossy fiber synapse, whereas neither long-term potentiation nor long-term depression was affected. These results indicate that afadin plays roles in the functional differentiations of the presynapse and the postsynapse of the hippocampal mossy fiber synapse. AU - Geng, Xiaoqi AU - Maruo, Tomohiko AU - Mandai, Kenji AU - Supriyanto, Irwan AU - Miyata, Muneaki AU - Sakakibara, Shotaro AU - Mizoguchi, Akira AU - Takai, Yoshimi AU - Mori, Masahiro ID - 706 IS - 8 JF - Genes to Cells SN - 13569597 TI - Roles of afadin in functional differentiations of hippocampal mossy fiber synapse VL - 22 ER - TY - JOUR AB - We answer a question of M. Gromov on the waist of the unit ball. AU - Akopyan, Arseniy AU - Karasev, Roman ID - 707 IS - 4 JF - Bulletin of the London Mathematical Society SN - 00246093 TI - A tight estimate for the waist of the ball VL - 49 ER - TY - JOUR AB - In the developing and adult brain, oligodendrocyte precursor cells (OPCs) are influenced by neuronal activity: they are involved in synaptic signaling with neurons, and their proliferation and differentiation into myelinating glia can be altered by transient changes in neuronal firing. An important question that has been unanswered is whether OPCs can discriminate different patterns of neuronal activity and respond to them in a distinct way. Here, we demonstrate in brain slices that the pattern of neuronal activity determines the functional changes triggered at synapses between axons and OPCs. Furthermore, we show that stimulation of the corpus callosum at different frequencies in vivo affects proliferation and differentiation of OPCs in a dissimilar way. Our findings suggest that neurons do not influence OPCs in “all-or-none” fashion but use their firing pattern to tune the response and behavior of these nonneuronal cells. AU - Nagy, Balint AU - Hovhannisyan, Anahit AU - Barzan, Ruxandra AU - Chen, Ting AU - Kukley, Maria ID - 708 IS - 8 JF - PLoS Biology SN - 15449173 TI - Different patterns of neuronal activity trigger distinct responses of oligodendrocyte precursor cells in the corpus callosum VL - 15 ER -