TY - JOUR
AB - The human pathogen Streptococcus pneumoniae is decorated with a special class of surface-proteins known as choline-binding proteins (CBPs) attached to phosphorylcholine (PCho) moieties from cell-wall teichoic acids. By a combination of X-ray crystallography, NMR, molecular dynamics techniques and in vivo virulence and phagocytosis studies, we provide structural information of choline-binding protein L (CbpL) and demonstrate its impact on pneumococcal pathogenesis and immune evasion. CbpL is a very elongated three-module protein composed of (i) an Excalibur Ca 2+ -binding domain -reported in this work for the very first time-, (ii) an unprecedented anchorage module showing alternate disposition of canonical and non-canonical choline-binding sites that allows vine-like binding of fully-PCho-substituted teichoic acids (with two choline moieties per unit), and (iii) a Ltp-Lipoprotein domain. Our structural and infection assays indicate an important role of the whole multimodular protein allowing both to locate CbpL at specific places on the cell wall and to interact with host components in order to facilitate pneumococcal lung infection and transmigration from nasopharynx to the lungs and blood. CbpL implication in both resistance against killing by phagocytes and pneumococcal pathogenesis further postulate this surface-protein as relevant among the pathogenic arsenal of the pneumococcus.
AU - Gutierrez-Fernandez, Javier
AU - Saleh, Malek
AU - Alcorlo, Martín
AU - Gómez Mejóa, Alejandro
AU - Pantoja Uceda, David
AU - Treviño, Miguel
AU - Vob, Franziska
AU - Abdullah, Mohammed
AU - Galán Bartual, Sergio
AU - Seinen, Jolien
AU - Sánchez Murcia, Pedro
AU - Gago, Federico
AU - Bruix, Marta
AU - Hammerschmidt, Sven
AU - Hermoso, Juan
ID - 1186
JF - Scientific Reports
TI - Modular architecture and unique teichoic acid recognition features of choline-binding protein L CbpL contributing to pneumococcal pathogenesis
VL - 6
ER -
TY - JOUR
AB - We consider a population dynamics model coupling cell growth to a diffusion in the space of metabolic phenotypes as it can be obtained from realistic constraints-based modelling.
In the asymptotic regime of slow
diffusion, that coincides with the relevant experimental range, the resulting
non-linear Fokker–Planck equation is solved for the steady state in the WKB
approximation that maps it into the ground state of a quantum particle in an
Airy potential plus a centrifugal term. We retrieve scaling laws for growth rate
fluctuations and time response with respect to the distance from the maximum
growth rate suggesting that suboptimal populations can have a faster response
to perturbations.
AU - De Martino, Daniele
AU - Masoero, Davide
ID - 1188
IS - 12
JF - Journal of Statistical Mechanics: Theory and Experiment
TI - Asymptotic analysis of noisy fitness maximization, applied to metabolism & growth
VL - 2016
ER -
TY - CONF
AB - We consider the recent formulation of the Algorithmic Lovász Local Lemma [1], [2] for finding objects that avoid "bad features", or "flaws". It extends the Moser-Tardos resampling algorithm [3] to more general discrete spaces. At each step the method picks a flaw present in the current state and "resamples" it using a "resampling oracle" provided by the user. However, it is less flexible than the Moser-Tardos method since [1], [2] require a specific flaw selection rule, whereas [3] allows an arbitrary rule (and thus can potentially be implemented more efficiently). We formulate a new "commutativity" condition, and prove that it is sufficient for an arbitrary rule to work. It also enables an efficient parallelization under an additional assumption. We then show that existing resampling oracles for perfect matchings and permutations do satisfy this condition. Finally, we generalize the precondition in [2] (in the case of symmetric potential causality graphs). This unifies special cases that previously were treated separately.
AU - Kolmogorov, Vladimir
ID - 1193
T2 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science
TI - Commutativity in the algorithmic Lovasz local lemma
VL - 2016-December
ER -
TY - JOUR
AB - The genetic analysis of experimentally evolving populations typically relies on short reads from pooled individuals (Pool-Seq). While this method provides reliable allele frequency estimates, the underlying haplotype structure remains poorly characterized. With small population sizes and adaptive variants that start from low frequencies, the interpretation of selection signatures in most Evolve and Resequencing studies remains challenging. To facilitate the characterization of selection targets, we propose a new approach that reconstructs selected haplotypes from replicated time series, using Pool-Seq data. We identify selected haplotypes through the correlated frequencies of alleles carried by them. Computer simulations indicate that selected haplotype-blocks of several Mb can be reconstructed with high confidence and low error rates, even when allele frequencies change only by 20% across three replicates. Applying this method to real data from D. melanogaster populations adapting to a hot environment, we identify a selected haplotype-block of 6.93 Mb. We confirm the presence of this haplotype-block in evolved populations by experimental haplotyping, demonstrating the power and accuracy of our haplotype reconstruction from Pool-Seq data. We propose that the combination of allele frequency estimates with haplotype information will provide the key to understanding the dynamics of adaptive alleles.
AU - Franssen, Susan
AU - Barton, Nicholas H
AU - Schlötterer, Christian
ID - 1195
IS - 1
JF - Molecular Biology and Evolution
TI - Reconstruction of haplotype-blocks selected during experimental evolution.
VL - 34
ER -
TY - JOUR
AU - Hilbe, Christian
AU - Traulsen, Arne
ID - 1200
JF - Physics of Life Reviews
TI - Only the combination of mathematics and agent based simulations can leverage the full potential of evolutionary modeling: Comment on “Evolutionary game theory using agent-based methods” by C. Adami, J. Schossau and A. Hintze
VL - 19
ER -
TY - JOUR
AU - Milutinovic, Barbara
AU - Peuß, Robert
AU - Ferro, Kevin
AU - Kurtz, Joachim
ID - 1202
IS - 4
JF - Zoology
TI - Immune priming in arthropods: an update focusing on the red flour beetle
VL - 119
ER -
TY - JOUR
AB - Haemophilus haemolyticus has been recently discovered to have the potential to cause invasive disease. It is closely related to nontypeable Haemophilus influenzae (NT H. influenzae). NT H. influenzae and H. haemolyticus are often misidentified because none of the existing tests targeting the known phenotypes of H. haemolyticus are able to specifically identify H. haemolyticus. Through comparative genomic analysis of H. haemolyticus and NT H. influenzae, we identified genes unique to H. haemolyticus that can be used as targets for the identification of H. haemolyticus. A real-time PCR targeting purT (encoding phosphoribosylglycinamide formyltransferase 2 in the purine synthesis pathway) was developed and evaluated. The lower limit of detection was 40 genomes/PCR; the sensitivity and specificity in detecting H. haemolyticus were 98.9% and 97%, respectively. To improve the discrimination of H. haemolyticus and NT H. influenzae, a testing scheme combining two targets (H. haemolyticus purT and H. influenzae hpd, encoding protein D lipoprotein) was also evaluated and showed 96.7% sensitivity and 98.2% specificity for the identification of H. haemolyticus and 92.8% sensitivity and 100% specificity for the identification of H. influenzae, respectively. The dual-target testing scheme can be used for the diagnosis and surveillance of infection and disease caused by H. haemolyticus and NT H. influenzae.
AU - Hu, Fang
AU - Rishishwar, Lavanya
AU - Sivadas, Ambily
AU - Mitchell, Gabriel
AU - King, Jordan
AU - Murphy, Timothy
AU - Gilsdorf, Janet
AU - Mayer, Leonard
AU - Wang, Xin
ID - 1203
IS - 12
JF - Journal of Clinical Microbiology
TI - Comparative genomic analysis of Haemophilus haemolyticus and nontypeable Haemophilus influenzae and a new testing scheme for their discrimination
VL - 54
ER -
TY - JOUR
AB - In science, as in life, "surprises" can be adequately appreciated only in the presence of a null model, what we expect a priori. In physics, theories sometimes express the values of dimensionless physical constants as combinations of mathematical constants like π or e. The inverse problem also arises, whereby the measured value of a physical constant admits a "surprisingly" simple approximation in terms of well-known mathematical constants. Can we estimate the probability for this to be a mere coincidence, rather than an inkling of some theory? We answer the question in the most naive form.
AU - Amir, Ariel
AU - Lemeshko, Mikhail
AU - Tokieda, Tadashi
ID - 1204
IS - 6
JF - American Mathematical Monthly
TI - Surprises in numerical expressions of physical constants
VL - 123
ER -
TY - CONF
AB - In this paper, we present a formal model-driven engineering approach to establishing a safety-assured implementation of Multifunction vehicle bus controller (MVBC) based on the generic reference models and requirements described in the International Electrotechnical Commission (IEC) standard IEC-61375. First, the generic models described in IEC-61375 are translated into a network of timed automata, and some safety requirements tested in IEC-61375 are formalized as timed computation tree logic (TCTL) formulas. With the help of Uppaal, we check and debug whether the timed automata satisfy the formulas or not. Within this step, several logic inconsistencies in the original standard are detected and corrected. Then, we apply the tool Times to generate C code from the verified model, which was later synthesized into a real MVBC chip. Finally, the runtime verification tool RMOR is applied to verify some safety requirements at the implementation level. We set up a real platform with worldwide mostly used MVBC D113, and verify the correctness and the scalability of the synthesized MVBC chip more comprehensively. The errors in the standard has been confirmed and the resulted MVBC has been deployed in real train communication network.
AU - Jiang, Yu
AU - Liu, Han
AU - Song, Houbing
AU - Kong, Hui
AU - Gu, Ming
AU - Sun, Jiaguang
AU - Sha, Lui
ID - 1205
TI - Safety assured formal model driven design of the multifunction vehicle bus controller
VL - 9995
ER -
TY - JOUR
AB - We study a polar molecule immersed in a superfluid environment, such as a helium nanodroplet or a Bose–Einstein condensate, in the presence of a strong electrostatic field. We show that coupling of the molecular pendular motion, induced by the field, to the fluctuating bath leads to formation of pendulons—spherical harmonic librators dressed by a field of many-particle excitations. We study the behavior of the pendulon in a broad range of molecule–bath and molecule–field interaction strengths, and reveal that its spectrum features a series of instabilities which are absent in the field-free case of the angulon quasiparticle. Furthermore, we show that an external field allows to fine-tune the positions of these instabilities in the molecular rotational spectrum. This opens the door to detailed experimental studies of redistribution of orbital angular momentum in many-particle systems. © 2016 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim
AU - Redchenko, Elena
AU - Lemeshko, Mikhail
ID - 1206
IS - 22
JF - ChemPhysChem
TI - Libration of strongly oriented polar molecules inside a superfluid
VL - 17
ER -
TY - JOUR
AB - NADH-ubiquinone oxidoreductase (complex I) is the largest (∼1 MDa) and the least characterized complex of the mitochondrial electron transport chain. Because of the ease of sample availability, previous work has focused almost exclusively on bovine complex I. However, only medium resolution structural analyses of this complex have been reported. Working with other mammalian complex I homologues is a potential approach for overcoming these limitations. Due to the inherent difficulty of expressing large membrane protein complexes, screening of complex I homologues is limited to large mammals reared for human consumption. The high sequence identity among these available sources may preclude the benefits of screening. Here, we report the characterization of complex I purified from Ovis aries (ovine) heart mitochondria. All 44 unique subunits of the intact complex were identified by mass spectrometry. We identified differences in the subunit composition of subcomplexes of ovine complex I as compared with bovine, suggesting differential stability of inter-subunit interactions within the complex. Furthermore, the 42-kDa subunit, which is easily lost from the bovine enzyme, remains tightly bound to ovine complex I. Additionally, we developed a novel purification protocol for highly active and stable mitochondrial complex I using the branched-chain detergent lauryl maltose neopentyl glycol. Our data demonstrate that, although closely related, significant differences exist between the biochemical properties of complex I prepared from ovine and bovine mitochondria and that ovine complex I represents a suitable alternative target for further structural studies.
AU - Letts, James A
AU - Degliesposti, Gianluca
AU - Fiedorczuk, Karol
AU - Skehel, Mark
AU - Sazanov, Leonid A
ID - 1209
IS - 47
JF - Journal of Biological Chemistry
TI - Purification of ovine respiratory complex i results in a highly active and stable preparation
VL - 291
ER -
TY - JOUR
AB - Plants adjust their growth according to gravity. Gravitropism involves gravity perception, signal transduction, and asymmetric growth response, with organ bending as a consequence [1]. Asymmetric growth results from the asymmetric distribution of the plant-specific signaling molecule auxin [2] that is generated by lateral transport, mediated in the hypocotyl predominantly by the auxin transporter PIN-FORMED3 (PIN3) [3–5]. Gravity stimulation polarizes PIN3 to the bottom sides of endodermal cells, correlating with increased auxin accumulation in adjacent tissues at the lower side of the stimulated organ, where auxin induces cell elongation and, hence, organ bending. A curvature response allows the hypocotyl to resume straight growth at a defined angle [6], implying that at some point auxin symmetry is restored to prevent overbending. Here, we present initial insights into cellular and molecular mechanisms that lead to the termination of the tropic response. We identified an auxin feedback on PIN3 polarization as underlying mechanism that restores symmetry of the PIN3-dependent auxin flow. Thus, two mechanistically distinct PIN3 polarization events redirect auxin fluxes at different time points of the gravity response: first, gravity-mediated redirection of PIN3-mediated auxin flow toward the lower hypocotyl side, where auxin gradually accumulates and promotes growth, and later PIN3 polarization to the opposite cell side, depleting this auxin maximum to end the bending. Accordingly, genetic or pharmacological interference with the late PIN3 polarization prevents termination of the response and leads to hypocotyl overbending. This observation reveals a role of auxin feedback on PIN polarity in the termination of the tropic response. © 2016 Elsevier Ltd
AU - Rakusová, Hana
AU - Abbas, Mohamad
AU - Han, Huibin
AU - Song, Siyuan
AU - Robert, Hélène
AU - Friml, Jirí
ID - 1212
IS - 22
JF - Current Biology
TI - Termination of shoot gravitropic responses by auxin feedback on PIN3 polarity
VL - 26
ER -
TY - JOUR
AB - A framework fo r extracting features in 2D transient flows, based on the acceleration field to ensure Galilean invariance is proposed in this paper. The minima of the acceleration magnitude (a superset of acceleration zeros) are extracted and discriminated into vortices and saddle points, based on the spectral properties of the velocity Jacobian. The extraction of topological features is performed with purely combinatorial algorithms from discrete computational topology. The feature points are prioritized with persistence, as a physically meaningful importance measure. These feature points are tracked in time with a robust algorithm for tracking features. Thus, a space-time hierarchy of the minima is built and vortex merging events are detected. We apply the acceleration feature extraction strategy to three two-dimensional shear flows: (1) an incompressible periodic cylinder wake, (2) an incompressible planar mixing layer and (3) a weakly compressible planar jet. The vortex-like acceleration feature points are shown to be well aligned with acceleration zeros, maxima of the vorticity magnitude, minima of the pressure field and minima of λ2.
AU - Kasten, Jens
AU - Reininghaus, Jan
AU - Hotz, Ingrid
AU - Hege, Hans
AU - Noack, Bernd
AU - Daviller, Guillaume
AU - Morzyński, Marek
ID - 1216
IS - 1
JF - Archives of Mechanics
TI - Acceleration feature points of unsteady shear flows
VL - 68
ER -
TY - JOUR
AB - Investigating the physiology of cyanobacteria cultured under a diel light regime is relevant for a better understanding of the resulting growth characteristics and for specific biotechnological applications that are foreseen for these photosynthetic organisms. Here, we present the results of a multiomics study of the model cyanobacterium Synechocystis sp. strain PCC 6803, cultured in a lab-scale photobioreactor in physiological conditions relevant for large-scale culturing. The culture was sparged withN2 andCO2, leading to an anoxic environment during the dark period. Growth followed the availability of light. Metabolite analysis performed with 1Hnuclear magnetic resonance analysis showed that amino acids involved in nitrogen and sulfur assimilation showed elevated levels in the light. Most protein levels, analyzed through mass spectrometry, remained rather stable. However, several high-light-response proteins and stress-response proteins showed distinct changes at the onset of the light period. Microarray-based transcript analysis found common patterns of~56% of the transcriptome following the diel regime. These oscillating transcripts could be grouped coarsely into genes that were upregulated and downregulated in the dark period. The accumulated glycogen was degraded in the anaerobic environment in the dark. A small part was degraded gradually, reflecting basic maintenance requirements of the cells in darkness. Surprisingly, the largest part was degraded rapidly in a short time span at the end of the dark period. This degradation could allow rapid formation of metabolic intermediates at the end of the dark period, preparing the cells for the resumption of growth at the start of the light period.
AU - Angermayr, Andreas
AU - Van Alphen, Pascal
AU - Hasdemir, Dicle
AU - Kramer, Gertjan
AU - Iqbal, Muzamal
AU - Van Grondelle, Wilmar
AU - Hoefsloot, Huub
AU - Choi, Younghae
AU - Hellingwerf, Klaas
ID - 1218
IS - 14
JF - Applied and Environmental Microbiology
TI - Culturing synechocystis sp. Strain pcc 6803 with N2 and CO2 in a diel regime reveals multiphase glycogen dynamics with low maintenance costs
VL - 82
ER -
TY - JOUR
AB - We consider N×N random matrices of the form H = W + V where W is a real symmetric or complex Hermitian Wigner matrix and V is a random or deterministic, real, diagonal matrix whose entries are independent of W. We assume subexponential decay for the matrix entries of W, and we choose V so that the eigenvalues ofW and V are typically of the same order. For a large class of diagonal matrices V , we show that the local statistics in the bulk of the spectrum are universal in the limit of large N.
AU - Lee, Jioon
AU - Schnelli, Kevin
AU - Stetler, Ben
AU - Yau, Horngtzer
ID - 1219
IS - 3
JF - Annals of Probability
TI - Bulk universality for deformed wigner matrices
VL - 44
ER -
TY - CONF
AB - Theoretical and numerical aspects of aerodynamic efficiency of propulsion systems coupled to the boundary layer of a fuselage are studied. We discuss the effects of local flow fields, which are affected both by conservative flow acceleration as well as total pressure losses, on the efficiency of boundary layer immersed propulsion devices. We introduce the concept of a boundary layer retardation turbine that helps reduce skin friction over the fuselage. We numerically investigate efficiency gains offered by boundary layer and wake interacting devices. We discuss the results in terms of a total energy consumption framework and show that efficiency gains of any device depend on all the other elements of the propulsion system.
AU - Mikić, Gregor
AU - Stoll, Alex
AU - Bevirt, Joe
AU - Grah, Rok
AU - Moore, Mark
ID - 1220
TI - Fuselage boundary layer ingestion propulsion applied to a thin haul commuter aircraft for optimal efficiency
ER -
TY - JOUR
AB - The Auxin Binding Protein 1 (ABP1) is one of the most studied proteins in plants. Since decades ago, it has been the prime receptor candidate for the plant hormone auxin with a plethora of described functions in auxin signaling and development. The developmental importance of ABP1 has recently been questioned by identification of Arabidopsis thaliana abp1 knock-out alleles that show no obvious phenotypes under normal growth conditions. In this study, we examined the contradiction between the normal growth and development of the abp1 knock-outs and the strong morphological defects observed in three different ethanol-inducible abp1 knock-down mutants ( abp1-AS, SS12K, SS12S). By analyzing segregating populations of abp1 knock-out vs. abp1 knock-down crosses we show that the strong morphological defects that were believed to be the result of conditional down-regulation of ABP1 can be reproduced also in the absence of the functional ABP1 protein. This data suggests that the phenotypes in abp1 knock-down lines are due to the off-target effects and asks for further reflections on the biological function of ABP1 or alternative explanations for the missing phenotypic defects in the abp1 loss-of-function alleles.
AU - Michalko, Jaroslav
AU - Glanc, Matous
AU - Perrot Rechenmann, Catherine
AU - Friml, Jirí
ID - 1221
JF - F1000 Research
TI - Strong morphological defects in conditional Arabidopsis abp1 knock-down mutants generated in absence of functional ABP1 protein
VL - 5
ER -
TY - JOUR
AB - We consider packings of congruent circles on a square flat torus, i.e., periodic (w.r.t. a square lattice) planar circle packings, with the maximal circle radius. This problem is interesting due to a practical reason—the problem of “super resolution of images.” We have found optimal arrangements for N=6, 7 and 8 circles. Surprisingly, for the case N=7 there are three different optimal arrangements. Our proof is based on a computer enumeration of toroidal irreducible contact graphs.
AU - Musin, Oleg
AU - Nikitenko, Anton
ID - 1222
IS - 1
JF - Discrete & Computational Geometry
TI - Optimal packings of congruent circles on a square flat torus
VL - 55
ER -
TY - JOUR
AB - We consider a random Schrödinger operator on the binary tree with a random potential which is the sum of a random radially symmetric potential, Qr, and a random transversally periodic potential, κQt, with coupling constant κ. Using a new one-dimensional dynamical systems approach combined with Jensen's inequality in hyperbolic space (our key estimate) we obtain a fractional moment estimate proving localization for small and large κ. Together with a previous result we therefore obtain a model with two Anderson transitions, from localization to delocalization and back to localization, when increasing κ. As a by-product we also have a partially new proof of one-dimensional Anderson localization at any disorder.
AU - Froese, Richard
AU - Lee, Darrick
AU - Sadel, Christian
AU - Spitzer, Wolfgang
AU - Stolz, Günter
ID - 1223
IS - 3
JF - Journal of Spectral Theory
TI - Localization for transversally periodic random potentials on binary trees
VL - 6
ER -
TY - CONF
AB - At Crypto 2015 Fuchsbauer, Hanser and Slamanig (FHS) presented the first standard-model construction of efficient roundoptimal blind signatures that does not require complexity leveraging. It is conceptually simple and builds on the primitive of structure-preserving signatures on equivalence classes (SPS-EQ). FHS prove the unforgeability of their scheme assuming EUF-CMA security of the SPS-EQ scheme and hardness of a version of the DH inversion problem. Blindness under adversarially chosen keys is proven under an interactive variant of the DDH assumption. We propose a variant of their scheme whose blindness can be proven under a non-interactive assumption, namely a variant of the bilinear DDH assumption. We moreover prove its unforgeability assuming only unforgeability of the underlying SPS-EQ but no additional assumptions as needed for the FHS scheme.
AU - Fuchsbauer, Georg
AU - Hanser, Christian
AU - Kamath Hosdurg, Chethan
AU - Slamanig, Daniel
ID - 1225
TI - Practical round-optimal blind signatures in the standard model from weaker assumptions
VL - 9841
ER -
TY - JOUR
AB - Mitochondrial complex I (also known as NADH:ubiquinone oxidoreductase) contributes to cellular energy production by transferring electrons from NADH to ubiquinone coupled to proton translocation across the membrane. It is the largest protein assembly of the respiratory chain with a total mass of 970 kilodaltons. Here we present a nearly complete atomic structure of ovine (Ovis aries) mitochondrial complex I at 3.9 Å resolution, solved by cryo-electron microscopy with cross-linking and mass-spectrometry mapping experiments. All 14 conserved core subunits and 31 mitochondria-specific supernumerary subunits are resolved within the L-shaped molecule. The hydrophilic matrix arm comprises flavin mononucleotide and 8 iron-sulfur clusters involved in electron transfer, and the membrane arm contains 78 transmembrane helices, mostly contributed by antiporter-like subunits involved in proton translocation. Supernumerary subunits form an interlinked, stabilizing shell around the conserved core. Tightly bound lipids (including cardiolipins) further stabilize interactions between the hydrophobic subunits. Subunits with possible regulatory roles contain additional cofactors, NADPH and two phosphopantetheine molecules, which are shown to be involved in inter-subunit interactions. We observe two different conformations of the complex, which may be related to the conformationally driven coupling mechanism and to the active-deactive transition of the enzyme. Our structure provides insight into the mechanism, assembly, maturation and dysfunction of mitochondrial complex I, and allows detailed molecular analysis of disease-causing mutations.
AU - Fiedorczuk, Karol
AU - Letts, James A
AU - Degliesposti, Gianluca
AU - Kaszuba, Karol
AU - Skehel, Mark
AU - Sazanov, Leonid A
ID - 1226
IS - 7625
JF - Nature
TI - Atomic structure of the entire mammalian mitochondrial complex i
VL - 538
ER -
TY - CONF
AB - Many biological systems can be modeled as multiaffine hybrid systems. Due to the nonlinearity of multiaffine systems, it is difficult to verify their properties of interest directly. A common strategy to tackle this problem is to construct and analyze a discrete overapproximation of the original system. However, the conservativeness of a discrete abstraction significantly determines the level of confidence we can have in the properties of the original system. In this paper, in order to reduce the conservativeness of a discrete abstraction, we propose a new method based on a sufficient and necessary decision condition for computing discrete transitions between states in the abstract system. We assume the state space partition of a multiaffine system to be based on a set of multivariate polynomials. Hence, a rectangular partition defined in terms of polynomials of the form (xi − c) is just a simple case of multivariate polynomial partition, and the new decision condition applies naturally. We analyze and demonstrate the improvement of our method over the existing methods using some examples.
AU - Kong, Hui
AU - Bartocci, Ezio
AU - Bogomolov, Sergiy
AU - Grosu, Radu
AU - Henzinger, Thomas A
AU - Jiang, Yu
AU - Schilling, Christian
ID - 1227
TI - Discrete abstraction of multiaffine systems
VL - 9957
ER -
TY - CONF
AB - Witness encryption (WE) was introduced by Garg et al. [GGSW13]. A WE scheme is defined for some NP language L and lets a sender encrypt messages relative to instances x. A ciphertext for x can be decrypted using w witnessing x ∈ L, but hides the message if x ∈ L. Garg et al. construct WE from multilinear maps and give another construction [GGH+13b] using indistinguishability obfuscation (iO) for circuits. Due to the reliance on such heavy tools, WE can cur- rently hardly be implemented on powerful hardware and will unlikely be realizable on constrained devices like smart cards any time soon. We construct a WE scheme where encryption is done by simply computing a Naor-Yung ciphertext (two CPA encryptions and a NIZK proof). To achieve this, our scheme has a setup phase, which outputs public parameters containing an obfuscated circuit (only required for decryption), two encryption keys and a common reference string (used for encryption). This setup need only be run once, and the parame- ters can be used for arbitrary many encryptions. Our scheme can also be turned into a functional WE scheme, where a message is encrypted w.r.t. a statement and a function f, and decryption with a witness w yields f (m, w). Our construction is inspired by the functional encryption scheme by Garg et al. and we prove (selective) security assuming iO and statistically simulation-sound NIZK. We give a construction of the latter in bilinear groups and combining it with ElGamal encryption, our ciphertexts are of size 1.3 kB at a 128-bit security level and can be computed on a smart card.
AU - Abusalah, Hamza M
AU - Fuchsbauer, Georg
AU - Pietrzak, Krzysztof Z
ID - 1229
TI - Offline witness encryption
VL - 9696
ER -
TY - CONF
AB - Concolic testing is a promising method for generating test suites for large programs. However, it suffers from the path-explosion problem and often fails to find tests that cover difficult-to-reach parts of programs. In contrast, model checkers based on counterexample-guided abstraction refinement explore programs exhaustively, while failing to scale on large programs with precision. In this paper, we present a novel method that iteratively combines concolic testing and model checking to find a test suite for a given coverage criterion. If concolic testing fails to cover some test goals, then the model checker refines its program abstraction to prove more paths infeasible, which reduces the search space for concolic testing. We have implemented our method on top of the concolictesting tool Crest and the model checker CpaChecker. We evaluated our tool on a collection of programs and a category of SvComp benchmarks. In our experiments, we observed an improvement in branch coverage compared to Crest from 48% to 63% in the best case, and from 66% to 71% on average.
AU - Daca, Przemyslaw
AU - Gupta, Ashutosh
AU - Henzinger, Thomas A
ID - 1230
TI - Abstraction-driven concolic testing
VL - 9583
ER -
TY - CONF
AB - We study the time-and memory-complexities of the problem of computing labels of (multiple) randomly selected challenge-nodes in a directed acyclic graph. The w-bit label of a node is the hash of the labels of its parents, and the hash function is modeled as a random oracle. Specific instances of this problem underlie both proofs of space [Dziembowski et al. CRYPTO’15] as well as popular memory-hard functions like scrypt. As our main tool, we introduce the new notion of a probabilistic parallel entangled pebbling game, a new type of combinatorial pebbling game on a graph, which is closely related to the labeling game on the same graph. As a first application of our framework, we prove that for scrypt, when the underlying hash function is invoked n times, the cumulative memory complexity (CMC) (a notion recently introduced by Alwen and Serbinenko (STOC’15) to capture amortized memory-hardness for parallel adversaries) is at least Ω(w · (n/ log(n))2). This bound holds for adversaries that can store many natural functions of the labels (e.g., linear combinations), but still not arbitrary functions thereof. We then introduce and study a combinatorial quantity, and show how a sufficiently small upper bound on it (which we conjecture) extends our CMC bound for scrypt to hold against arbitrary adversaries. We also show that such an upper bound solves the main open problem for proofs-of-space protocols: namely, establishing that the time complexity of computing the label of a random node in a graph on n nodes (given an initial kw-bit state) reduces tightly to the time complexity for black pebbling on the same graph (given an initial k-node pebbling).
AU - Alwen, Joel F
AU - Chen, Binyi
AU - Kamath Hosdurg, Chethan
AU - Kolmogorov, Vladimir
AU - Pietrzak, Krzysztof Z
AU - Tessaro, Stefano
ID - 1231
TI - On the complexity of scrypt and proofs of space in the parallel random oracle model
VL - 9666
ER -
TY - CONF
AB - About three decades ago it was realized that implementing private channels between parties which can be adaptively corrupted requires an encryption scheme that is secure against selective opening attacks. Whether standard (IND-CPA) security implies security against selective opening attacks has been a major open question since. The only known reduction from selective opening to IND-CPA security loses an exponential factor. A polynomial reduction is only known for the very special case where the distribution considered in the selective opening security experiment is a product distribution, i.e., the messages are sampled independently from each other. In this paper we give a reduction whose loss is quantified via the dependence graph (where message dependencies correspond to edges) of the underlying message distribution. In particular, for some concrete distributions including Markov distributions, our reduction is polynomial.
AU - Fuchsbauer, Georg
AU - Heuer, Felix
AU - Kiltz, Eike
AU - Pietrzak, Krzysztof Z
ID - 1233
TI - Standard security does imply security against selective opening for markov distributions
VL - 9562
ER -
TY - CONF
AB - We present a new algorithm for the statistical model checking of Markov chains with respect to unbounded temporal properties, including full linear temporal logic. The main idea is that we monitor each simulation run on the fly, in order to detect quickly if a bottom strongly connected component is entered with high probability, in which case the simulation run can be terminated early. As a result, our simulation runs are often much shorter than required by termination bounds that are computed a priori for a desired level of confidence on a large state space. In comparison to previous algorithms for statistical model checking our method is not only faster in many cases but also requires less information about the system, namely, only the minimum transition probability that occurs in the Markov chain. In addition, our method can be generalised to unbounded quantitative properties such as mean-payoff bounds.
AU - Daca, Przemyslaw
AU - Henzinger, Thomas A
AU - Kretinsky, Jan
AU - Petrov, Tatjana
ID - 1234
TI - Faster statistical model checking for unbounded temporal properties
VL - 9636
ER -
TY - CONF
AB - A constrained pseudorandom function (CPRF) F: K×X → Y for a family T of subsets of χ is a function where for any key k ∈ K and set S ∈ T one can efficiently compute a short constrained key kS, which allows to evaluate F(k, ·) on all inputs x ∈ S, while the outputs on all inputs x /∈ S look random even given kS. Abusalah et al. recently constructed the first constrained PRF for inputs of arbitrary length whose sets S are decided by Turing machines. They use their CPRF to build broadcast encryption and the first ID-based non-interactive key exchange for an unbounded number of users. Their constrained keys are obfuscated circuits and are therefore large. In this work we drastically reduce the key size and define a constrained key for a Turing machine M as a short signature on M. For this, we introduce a new signature primitive with constrained signing keys that let one only sign certain messages, while forging a signature on others is hard even when knowing the coins for key generation.
AU - Abusalah, Hamza M
AU - Fuchsbauer, Georg
ID - 1235
TI - Constrained PRFs for unbounded inputs with short keys
VL - 9696
ER -
TY - CONF
AB - A constrained pseudorandom function F: K × X → Y for a family T ⊆ 2X of subsets of X is a function where for any key k ∈ K and set S ∈ T one can efficiently compute a constrained key kS which allows to evaluate F (k, ·) on all inputs x ∈ S, while even given this key, the outputs on all inputs x ∉ S look random. At Asiacrypt’13 Boneh and Waters gave a construction which supports the most general set family so far. Its keys kc are defined for sets decided by boolean circuits C and enable evaluation of the PRF on any x ∈ X where C(x) = 1. In their construction the PRF input length and the size of the circuits C for which constrained keys can be computed must be fixed beforehand during key generation. We construct a constrained PRF that has an unbounded input length and whose constrained keys can be defined for any set recognized by a Turing machine. The only a priori bound we make is on the description size of the machines. We prove our construction secure assuming publiccoin differing-input obfuscation. As applications of our constrained PRF we build a broadcast encryption scheme where the number of potential receivers need not be fixed at setup (in particular, the length of the keys is independent of the number of parties) and the first identity-based non-interactive key exchange protocol with no bound on the number of parties that can agree on a shared key.
AU - Abusalah, Hamza M
AU - Fuchsbauer, Georg
AU - Pietrzak, Krzysztof Z
ID - 1236
TI - Constrained PRFs for unbounded inputs
VL - 9610
ER -
TY - JOUR
AB - The dynamic localization of endosomal compartments labeled with targeted fluorescent protein tags is routinely followed by time lapse fluorescence microscopy approaches and single particle tracking algorithms. In this way trajectories of individual endosomes can be mapped and linked to physiological processes as cell growth. However, other aspects of dynamic behavior including endosomal interactions are difficult to follow in this manner. Therefore, we characterized the localization and dynamic properties of early and late endosomes throughout the entire course of root hair formation by means of spinning disc time lapse imaging and post-acquisition automated multitracking and quantitative analysis. Our results show differential motile behavior of early and late endosomes and interactions of late endosomes that may be specified to particular root hair domains. Detailed data analysis revealed a particular transient interaction between late endosomes—termed herein as dancing-endosomes—which is not concluding to vesicular fusion. Endosomes preferentially located in the root hair tip interacted as dancing-endosomes and traveled short distances during this interaction. Finally, sizes of early and late endosomes were addressed by means of super-resolution structured illumination microscopy (SIM) to corroborate measurements on the spinning disc. This is a first study providing quantitative microscopic data on dynamic spatio-temporal interactions of endosomes during root hair tip growth.
AU - Von Wangenheim, Daniel
AU - Rosero, Amparo
AU - Komis, George
AU - Šamajová, Olga
AU - Ovečka, Miroslav
AU - Voigt, Boris
AU - Šamaj, Jozef
ID - 1238
IS - JAN2016
JF - Frontiers in Plant Science
TI - Endosomal interactions during root hair growth
VL - 6
ER -
TY - JOUR
AB - Background: Long non-coding RNAs (lncRNAs) are increasingly implicated as gene regulators and may ultimately be more numerous than protein-coding genes in the human genome. Despite large numbers of reported lncRNAs, reference annotations are likely incomplete due to their lower and tighter tissue-specific expression compared to mRNAs. An unexplored factor potentially confounding lncRNA identification is inter-individual expression variability. Here, we characterize lncRNA natural expression variability in human primary granulocytes. Results: We annotate granulocyte lncRNAs and mRNAs in RNA-seq data from 10 healthy individuals, identifying multiple lncRNAs absent from reference annotations, and use this to investigate three known features (higher tissue-specificity, lower expression, and reduced splicing efficiency) of lncRNAs relative to mRNAs. Expression variability was examined in seven individuals sampled three times at 1- or more than 1-month intervals. We show that lncRNAs display significantly more inter-individual expression variability compared to mRNAs. We confirm this finding in two independent human datasets by analyzing multiple tissues from the GTEx project and lymphoblastoid cell lines from the GEUVADIS project. Using the latter dataset we also show that including more human donors into the transcriptome annotation pipeline allows identification of an increasing number of lncRNAs, but minimally affects mRNA gene number. Conclusions: A comprehensive annotation of lncRNAs is known to require an approach that is sensitive to low and tight tissue-specific expression. Here we show that increased inter-individual expression variability is an additional general lncRNA feature to consider when creating a comprehensive annotation of human lncRNAs or proposing their use as prognostic or disease markers.
AU - Kornienko, Aleksandra
AU - Dotter, Christoph
AU - Guenzl, Philipp
AU - Gisslinger, Heinz
AU - Gisslinger, Bettina
AU - Cleary, Ciara
AU - Kralovics, Robert
AU - Pauler, Florian
AU - Barlow, Denise
ID - 1240
IS - 1
JF - Genome Biology
TI - Long non-coding RNAs display higher natural expression variation than protein-coding genes in healthy humans
VL - 17
ER -
TY - JOUR
AB - How likely is it that a population escapes extinction through adaptive evolution? The answer to this question is of great relevance in conservation biology, where we aim at species’ rescue and the maintenance of biodiversity, and in agriculture and medicine, where we seek to hamper the emergence of pesticide or drug resistance. By reshuffling the genome, recombination has two antagonistic effects on the probability of evolutionary rescue: It generates and it breaks up favorable gene combinations. Which of the two effects prevails depends on the fitness effects of mutations and on the impact of stochasticity on the allele frequencies. In this article, we analyze a mathematical model for rescue after a sudden environmental change when adaptation is contingent on mutations at two loci. The analysis reveals a complex nonlinear dependence of population survival on recombination. We moreover find that, counterintuitively, a fast eradication of the wild type can promote rescue in the presence of recombination. The model also shows that two-step rescue is not unlikely to happen and can even be more likely than single-step rescue (where adaptation relies on a single mutation), depending on the circumstances.
AU - Uecker, Hildegard
AU - Hermisson, Joachim
ID - 1241
IS - 2
JF - Genetics
TI - The role of recombination in evolutionary rescue
VL - 202
ER -
TY - JOUR
AB - A crucial step in the regulation of gene expression is binding of transcription factor (TF) proteins to regulatory sites along the DNA. But transcription factors act at nanomolar concentrations, and noise due to random arrival of these molecules at their binding sites can severely limit the precision of regulation. Recent work on the optimization of information flow through regulatory networks indicates that the lower end of the dynamic range of concentrations is simply inaccessible, overwhelmed by the impact of this noise. Motivated by the behavior of homeodomain proteins, such as the maternal morphogen Bicoid in the fruit fly embryo, we suggest a scheme in which transcription factors also act as indirect translational regulators, binding to the mRNA of other regulatory proteins. Intuitively, each mRNA molecule acts as an independent sensor of the input concentration, and averaging over these multiple sensors reduces the noise. We analyze information flow through this scheme and identify conditions under which it outperforms direct transcriptional regulation. Our results suggest that the dual role of homeodomain proteins is not just a historical accident, but a solution to a crucial physics problem in the regulation of gene expression.
AU - Sokolowski, Thomas R
AU - Walczak, Aleksandra
AU - Bialek, William
AU - Tkacik, Gasper
ID - 1242
IS - 2
JF - Physical Review E Statistical Nonlinear and Soft Matter Physics
TI - Extending the dynamic range of transcription factor action by translational regulation
VL - 93
ER -
TY - JOUR
AB - Cell polarity refers to a functional spatial organization of proteins that is crucial for the control of essential cellular processes such as growth and division. To establish polarity, cells rely on elaborate regulation networks that control the distribution of proteins at the cell membrane. In fission yeast cells, a microtubule-dependent network has been identified that polarizes the distribution of signaling proteins that restricts growth to cell ends and targets the cytokinetic machinery to the middle of the cell. Although many molecular components have been shown to play a role in this network, it remains unknown which molecular functionalities are minimally required to establish a polarized protein distribution in this system. Here we show that a membrane-binding protein fragment, which distributes homogeneously in wild-type fission yeast cells, can be made to concentrate at cell ends by attaching it to a cytoplasmic microtubule end-binding protein. This concentration results in a polarized pattern of chimera proteins with a spatial extension that is very reminiscent of natural polarity patterns in fission yeast. However, chimera levels fluctuate in response to microtubule dynamics, and disruption of microtubules leads to disappearance of the pattern. Numerical simulations confirm that the combined functionality of membrane anchoring and microtubule tip affinity is in principle sufficient to create polarized patterns. Our chimera protein may thus represent a simple molecular functionality that is able to polarize the membrane, onto which additional layers of molecular complexity may be built to provide the temporal robustness that is typical of natural polarity patterns.
AU - Recouvreux, Pierre
AU - Sokolowski, Thomas R
AU - Grammoustianou, Aristea
AU - Tenwolde, Pieter
AU - Dogterom, Marileen
ID - 1244
IS - 7
JF - PNAS
TI - Chimera proteins with affinity for membranes and microtubule tips polarize in the membrane of fission yeast cells
VL - 113
ER -
TY - JOUR
AB - Near-field imaging is a powerful tool to investigate the complex structure of light at the nanoscale. Recent advances in near-field imaging have indicated the possibility for the complete reconstruction of both electric and magnetic components of the evanescent field. Here we study the electro-magnetic field structure of surface plasmon polariton waves propagating along subwavelength gold nanowires by performing phase- and polarization-resolved near-field microscopy in collection mode. By applying the optical reciprocity theorem, we describe the signal collected by the probe as an overlap integral of the nanowire's evanescent field and the probe's response function. As a result, we find that the probe's sensitivity to the magnetic field is approximately equal to its sensitivity to the electric field. Through rigorous modeling of the nanowire mode as well as the aperture probe response function, we obtain a good agreement between experimentally measured signals and a numerical model. Our findings provide a better understanding of aperture-based near-field imaging of the nanoscopic plasmonic and photonic structures and are helpful for the interpretation of future near-field experiments.
AU - Kabakova, Irina
AU - De Hoogh, Anouk
AU - Van Der Wel, Ruben
AU - Wulf, Matthias
AU - Le Feber, Boris
AU - Kuipers, Laurens
ID - 1246
JF - Scientific Reports
TI - Imaging of electric and magnetic fields near plasmonic nanowires
VL - 6
ER -
TY - JOUR
AB - The shaping of organs in plants depends on the intercellular flow of the phytohormone auxin, of which the directional signaling is determined by the polar subcellular localization of PIN-FORMED (PIN) auxin transport proteins. Phosphorylation dynamics of PIN proteins are affected by the protein phosphatase 2A (PP2A) and the PINOID kinase, which act antagonistically to mediate their apical-basal polar delivery. Here, we identified the ROTUNDA3 (RON3) protein as a regulator of the PP2A phosphatase activity in Arabidopsis thaliana. The RON3 gene was map-based cloned starting from the ron3-1 leaf mutant and found to be a unique, plant-specific gene coding for a protein with high and dispersed proline content. The ron3-1 and ron3-2 mutant phenotypes [i.e., reduced apical dominance, primary root length, lateral root emergence, and growth; increased ectopic stages II, IV, and V lateral root primordia; decreased auxin maxima in indole-3-acetic acid (IAA)-treated root apical meristems; hypergravitropic root growth and response; increased IAA levels in shoot apices; and reduced auxin accumulation in root meristems] support a role for RON3 in auxin biology. The affinity-purified PP2A complex with RON3 as bait suggested that RON3 might act in PIN transporter trafficking. Indeed, pharmacological interference with vesicle trafficking processes revealed that single ron3-2 and double ron3-2 rcn1 mutants have altered PIN polarity and endocytosis in specific cells. Our data indicate that RON3 contributes to auxin-mediated development by playing a role in PIN recycling and polarity establishment through regulation of the PP2A complex activity.
AU - Karampelias, Michael
AU - Neyt, Pia
AU - De Groeve, Steven
AU - Aesaert, Stijn
AU - Coussens, Griet
AU - Rolčík, Jakub
AU - Bruno, Leonardo
AU - De Winne, Nancy
AU - Van Minnebruggen, Annemie
AU - Van Montagu, Marc
AU - Ponce, Maria
AU - Micol, José
AU - Friml, Jirí
AU - De Jaeger, Geert
AU - Van Lijsebettens, Mieke
ID - 1247
IS - 10
JF - PNAS
TI - ROTUNDA3 function in plant development by phosphatase 2A-mediated regulation of auxin transporter recycling
VL - 113
ER -
TY - JOUR
AB - Life depends as much on the flow of information as on the flow of energy. Here we review the many efforts to make this intuition precise. Starting with the building blocks of information theory, we explore examples where it has been possible to measure, directly, the flow of information in biological networks, or more generally where information-theoretic ideas have been used to guide the analysis of experiments. Systems of interest range from single molecules (the sequence diversity in families of proteins) to groups of organisms (the distribution of velocities in flocks of birds), and all scales in between. Many of these analyses are motivated by the idea that biological systems may have evolved to optimize the gathering and representation of information, and we review the experimental evidence for this optimization, again across a wide range of scales.
AU - Tkacik, Gasper
AU - Bialek, William
ID - 1248
JF - Annual Review of Condensed Matter Physics
TI - Information processing in living systems
VL - 7
ER -
TY - JOUR
AB - Actin and myosin assemble into a thin layer of a highly dynamic network underneath the membrane of eukaryotic cells. This network generates the forces that drive cell- and tissue-scale morphogenetic processes. The effective material properties of this active network determine large-scale deformations and other morphogenetic events. For example, the characteristic time of stress relaxation (the Maxwell time τM) in the actomyosin sets the timescale of large-scale deformation of the cortex. Similarly, the characteristic length of stress propagation (the hydrodynamic length λ) sets the length scale of slow deformations, and a large hydrodynamic length is a prerequisite for long-ranged cortical flows. Here we introduce a method to determine physical parameters of the actomyosin cortical layer in vivo directly from laser ablation experiments. For this we investigate the cortical response to laser ablation in the one-cell-stage Caenorhabditis elegans embryo and in the gastrulating zebrafish embryo. These responses can be interpreted using a coarse-grained physical description of the cortex in terms of a two-dimensional thin film of an active viscoelastic gel. To determine the Maxwell time τM, the hydrodynamic length λ, the ratio of active stress ζΔμ, and per-area friction γ, we evaluated the response to laser ablation in two different ways: by quantifying flow and density fields as a function of space and time, and by determining the time evolution of the shape of the ablated region. Importantly, both methods provide best-fit physical parameters that are in close agreement with each other and that are similar to previous estimates in the two systems. Our method provides an accurate and robust means for measuring physical parameters of the actomyosin cortical layer. It can be useful for investigations of actomyosin mechanics at the cellular-scale, but also for providing insights into the active mechanics processes that govern tissue-scale morphogenesis.
AU - Saha, Arnab
AU - Nishikawa, Masatoshi
AU - Behrndt, Martin
AU - Heisenberg, Carl-Philipp J
AU - Julicher, Frank
AU - Grill, Stephan
ID - 1249
IS - 6
JF - Biophysical Journal
TI - Determining physical properties of the cell cortex
VL - 110
ER -
TY - JOUR
AB - In bacteria, replicative aging manifests as a difference in growth or survival between the two cells emerging from division. One cell can be regarded as an aging mother with a decreased potential for future survival and division, the other as a rejuvenated daughter. Here, we aimed at investigating some of the processes involved in aging in the bacterium Escherichia coli, where the two types of cells can be distinguished by the age of their cell poles. We found that certain changes in the regulation of the carbohydrate metabolism can affect aging. A mutation in the carbon storage regulator gene, csrA, leads to a dramatically shorter replicative lifespan; csrA mutants stop dividing once their pole exceeds an age of about five divisions. These old-pole cells accumulate glycogen at their old cell poles; after their last division, they do not contain a chromosome, presumably because of spatial exclusion by the glycogen aggregates. The new-pole daughters produced by these aging mothers are born young; they only express the deleterious phenotype once their pole is old. These results demonstrate how manipulations of nutrient allocation can lead to the exclusion of the chromosome and limit replicative lifespan in E. coli, and illustrate how mutations can have phenotypic effects that are specific for cells with old poles. This raises the question how bacteria can avoid the accumulation of such mutations in their genomes over evolutionary times, and how they can achieve the long replicative lifespans that have recently been reported.
AU - Boehm, Alex
AU - Arnoldini, Markus
AU - Bergmiller, Tobias
AU - Röösli, Thomas
AU - Bigosch, Colette
AU - Ackermann, Martin
ID - 1250
IS - 4
JF - PLoS Genetics
TI - Genetic manipulation of glycogen allocation affects replicative lifespan in E coli
VL - 12
ER -
TY - JOUR
AB - Plant growth and architecture is regulated by the polar distribution of the hormone auxin. Polarity and flexibility of this process is provided by constant cycling of auxin transporter vesicles along actin filaments, coordinated by a positive auxinactin feedback loop. Both polar auxin transport and vesicle cycling are inhibited by synthetic auxin transport inhibitors, such as 1-Nnaphthylphthalamic acid (NPA), counteracting the effect of auxin; however, underlying targets and mechanisms are unclear. Using NMR, we map the NPA binding surface on the Arabidopsis thaliana ABCB chaperone TWISTED DWARF1 (TWD1).We identify ACTIN7 as a relevant, although likely indirect, TWD1 interactor, and show TWD1-dependent regulation of actin filament organization and dynamics and that TWD1 is required for NPA-mediated actin cytoskeleton remodeling. The TWD1-ACTIN7 axis controls plasma membrane presence of efflux transporters, and as a consequence act7 and twd1 share developmental and physiological phenotypes indicative of defects in auxin transport. These can be phenocopied by NPA treatment or by chemical actin (de)stabilization. We provide evidence that TWD1 determines downstreamlocations of auxin efflux transporters by adjusting actin filament debundling and dynamizing processes and mediating NPA action on the latter. This function appears to be evolutionary conserved since TWD1 expression in budding yeast alters actin polarization and cell polarity and provides NPA sensitivity.
AU - Zhu, Jinsheng
AU - Bailly, Aurélien
AU - Zwiewka, Marta
AU - Sovero, Valpuri
AU - Di Donato, Martin
AU - Ge, Pei
AU - Oehri, Jacqueline
AU - Aryal, Bibek
AU - Hao, Pengchao
AU - Linnert, Miriam
AU - Burgardt, Noelia
AU - Lücke, Christian
AU - Weiwad, Matthias
AU - Michel, Max
AU - Weiergräber, Oliver
AU - Pollmann, Stephan
AU - Azzarello, Elisa
AU - Mancuso, Stefano
AU - Ferro, Noel
AU - Fukao, Yoichiro
AU - Hoffmann, Céline
AU - Wedlich Söldner, Roland
AU - Friml, Jirí
AU - Thomas, Clément
AU - Geisler, Markus
ID - 1251
IS - 4
JF - Plant Cell
TI - TWISTED DWARF1 mediates the action of auxin transport inhibitors on actin cytoskeleton dynamics
VL - 28
ER -
TY - JOUR
AB - We study the homomorphism induced in homology by a closed correspondence between topological spaces, using projections from the graph of the correspondence to its domain and codomain. We provide assumptions under which the homomorphism induced by an outer approximation of a continuous map coincides with the homomorphism induced in homology by the map. In contrast to more classical results we do not require that the projection to the domain have acyclic preimages. Moreover, we show that it is possible to retrieve correct homological information from a correspondence even if some data is missing or perturbed. Finally, we describe an application to combinatorial maps that are either outer approximations of continuous maps or reconstructions of such maps from a finite set of data points.
AU - Harker, Shaun
AU - Kokubu, Hiroshi
AU - Mischaikow, Konstantin
AU - Pilarczyk, Pawel
ID - 1252
IS - 4
JF - Proceedings of the American Mathematical Society
TI - Inducing a map on homology from a correspondence
VL - 144
ER -
TY - JOUR
AB - This article provides an introduction to the role of microRNAs in the nervous system and outlines their potential involvement in the pathophysiology of schizophrenia, which is hypothesized to arise owing to environmental factors and genetic predisposition.
AU - Tsai, Lihuei
AU - Siegert, Sandra
ID - 1253
IS - 4
JF - JAMA Psychiatry
TI - How MicroRNAs Are involved in splitting the mind
VL - 73
ER -
TY - JOUR
AB - We use rigorous numerical techniques to compute a lower bound for the exponent of expansivity outside a neighborhood of the critical point for thousands of intervals of parameter values in the quadratic family. We first compute a radius of the critical neighborhood outside which the map is uniformly expanding. This radius is taken as small as possible, yet large enough for our numerical procedure to succeed in proving that the expansivity exponent outside this neighborhood is positive. Then, for each of the intervals, we compute a lower bound for this expansivity exponent, valid for all the parameters in that interval. We illustrate and study the distribution of the radii and the expansivity exponents. The results of our computations are mathematically rigorous. The source code of the software and the results of the computations are made publicly available at http://www.pawelpilarczyk.com/quadratic/.
AU - Golmakani, Ali
AU - Luzzatto, Stefano
AU - Pilarczyk, Pawel
ID - 1254
IS - 2
JF - Experimental Mathematics
TI - Uniform expansivity outside a critical neighborhood in the quadratic family
VL - 25
ER -
TY - JOUR
AB - Down syndrome cell adhesion molecule 1 (Dscam1) has widereaching and vital neuronal functions although the role it plays in insect and crustacean immunity is less well understood. In this study, we combine different approaches to understand the roles that Dscam1 plays in fitness-related contexts in two model insect species. Contrary to our expectations, we found no short-term modulation of Dscam1 gene expression after haemocoelic or oral bacterial exposure in Tribolium castaneum, or after haemocoelic bacterial exposure in Drosophila melanogaster. Furthermore, RNAi-mediated Dscam1 knockdown and subsequent bacterial exposure did not reduce T. castaneum survival. However, Dscam1 knockdown in larvae resulted in adult locomotion defects, as well as dramatically reduced fecundity in males and females. We suggest that Dscam1 does not always play a straightforward role in immunity, but strongly influences behaviour and fecundity. This study takes a step towards understanding more about the role of this intriguing gene from different phenotypic perspectives.
AU - Peuß, Robert
AU - Wensing, Kristina
AU - Woestmann, Luisa
AU - Eggert, Hendrik
AU - Milutinovic, Barbara
AU - Sroka, Marlene
AU - Scharsack, Jörn
AU - Kurtz, Joachim
AU - Armitage, Sophie
ID - 1255
IS - 4
JF - Royal Society Open Science
TI - Down syndrome cell adhesion molecule 1: Testing for a role in insect immunity, behaviour and reproduction
VL - 3
ER -
TY - CONF
AB - Simulink is widely used for model driven development (MDD) of industrial software systems. Typically, the Simulink based development is initiated from Stateflow modeling, followed by simulation, validation and code generation mapped to physical execution platforms. However, recent industrial trends have raised the demands of rigorous verification on safety-critical applications, which is unfortunately challenging for Simulink. In this paper, we present an approach to bridge the Stateflow based model driven development and a well- defined rigorous verification. First, we develop a self- contained toolkit to translate Stateflow model into timed automata, where major advanced modeling features in Stateflow are supported. Taking advantage of the strong verification capability of Uppaal, we can not only find bugs in Stateflow models which are missed by Simulink Design Verifier, but also check more important temporal properties. Next, we customize a runtime verifier for the generated nonintrusive VHDL and C code of Stateflow model for monitoring. The major strength of the customization is the flexibility to collect and analyze runtime properties with a pure software monitor, which opens more opportunities for engineers to achieve high reliability of the target system compared with the traditional act that only relies on Simulink Polyspace. We incorporate these two parts into original Stateflow based MDD seamlessly. In this way, safety-critical properties are both verified at the model level, and at the consistent system implementation level with physical execution environment in consideration. We apply our approach on a train controller design, and the verified implementation is tested and deployed on a real hardware platform.
AU - Jiang, Yu
AU - Yang, Yixiao
AU - Liu, Han
AU - Kong, Hui
AU - Gu, Ming
AU - Sun, Jiaguang
AU - Sha, Lui
ID - 1256
TI - From stateflow simulation to verified implementation: A verification approach and a real-time train controller design
ER -
TY - JOUR
AB - We consider products of random matrices that are small, independent identically distributed perturbations of a fixed matrix (Formula presented.). Focusing on the eigenvalues of (Formula presented.) of a particular size we obtain a limit to a SDE in a critical scaling. Previous results required (Formula presented.) to be a (conjugated) unitary matrix so it could not have eigenvalues of different modulus. From the result we can also obtain a limit SDE for the Markov process given by the action of the random products on the flag manifold. Applying the result to random Schrödinger operators we can improve some results by Valko and Virag showing GOE statistics for the rescaled eigenvalue process of a sequence of Anderson models on long boxes. In particular, we solve a problem posed in their work.
AU - Sadel, Christian
AU - Virág, Bálint
ID - 1257
IS - 3
JF - Communications in Mathematical Physics
TI - A central limit theorem for products of random matrices and GOE statistics for the Anderson model on long boxes
VL - 343
ER -
TY - JOUR
AB - We consider the Bogolubov–Hartree–Fock functional for a fermionic many-body system with two-body interactions. For suitable interaction potentials that have a strong enough attractive tail in order to allow for two-body bound states, but are otherwise sufficiently repulsive to guarantee stability of the system, we show that in the low-density limit the ground state of this model consists of a Bose–Einstein condensate of fermion pairs. The latter can be described by means of the Gross–Pitaevskii energy functional.
AU - Bräunlich, Gerhard
AU - Hainzl, Christian
AU - Seiringer, Robert
ID - 1259
IS - 2
JF - Mathematical Physics, Analysis and Geometry
TI - Bogolubov–Hartree–Fock theory for strongly interacting fermions in the low density limit
VL - 19
ER -
TY - JOUR
AB - In this work, the Gardner problem of inferring interactions and fields for an Ising neural network from given patterns under a local stability hypothesis is addressed under a dual perspective. By means of duality arguments, an integer linear system is defined whose solution space is the dual of the Gardner space and whose solutions represent mutually unstable patterns. We propose and discuss Monte Carlo methods in order to find and remove unstable patterns and uniformly sample the space of interactions thereafter. We illustrate the problem on a set of real data and perform ensemble calculation that shows how the emergence of phase dominated by unstable patterns can be triggered in a nonlinear discontinuous way.
AU - De Martino, Daniele
ID - 1260
IS - 6
JF - International Journal of Modern Physics C
TI - The dual of the space of interactions in neural network models
VL - 27
ER -
TY - JOUR
AB - We consider a non-standard finite-volume discretization of a strongly non-linear fourth order diffusion equation on the d-dimensional cube, for arbitrary . The scheme preserves two important structural properties of the equation: the first is the interpretation as a gradient flow in a mass transportation metric, and the second is an intimate relation to a linear Fokker-Planck equation. Thanks to these structural properties, the scheme possesses two discrete Lyapunov functionals. These functionals approximate the entropy and the Fisher information, respectively, and their dissipation rates converge to the optimal ones in the discrete-to-continuous limit. Using the dissipation, we derive estimates on the long-time asymptotics of the discrete solutions. Finally, we present results from numerical experiments which indicate that our discretization is able to capture significant features of the complex original dynamics, even with a rather coarse spatial resolution.
AU - Maas, Jan
AU - Matthes, Daniel
ID - 1261
IS - 7
JF - Nonlinearity
TI - Long-time behavior of a finite volume discretization for a fourth order diffusion equation
VL - 29
ER -
TY - JOUR
AB - Linking classical microwave electrical circuits to the optical telecommunication band is at the core of modern communication. Future quantum information networks will require coherent microwave-to-optical conversion to link electronic quantum processors and memories via low-loss optical telecommunication networks. Efficient conversion can be achieved with electro-optical modulators operating at the single microwave photon level. In the standard electro-optic modulation scheme, this is impossible because both up- and down-converted sidebands are necessarily present. Here, we demonstrate true single-sideband up- or down-conversion in a triply resonant whispering gallery mode resonator by explicitly addressing modes with asymmetric free spectral range. Compared to previous experiments, we show a 3 orders of magnitude improvement of the electro-optical conversion efficiency, reaching 0.1% photon number conversion for a 10 GHz microwave tone at 0.42 mW of optical pump power. The presented scheme is fully compatible with existing superconducting 3D circuit quantum electrodynamics technology and can be used for nonclassical state conversion and communication. Our conversion bandwidth is larger than 1 MHz and is not fundamentally limited.
AU - Rueda, Alfredo
AU - Sedlmeir, Florian
AU - Collodo, Michele
AU - Vogl, Ulrich
AU - Stiller, Birgit
AU - Schunk, Gerhard
AU - Strekalov, Dmitry
AU - Marquardt, Christoph
AU - Fink, Johannes M
AU - Painter, Oskar
AU - Leuchs, Gerd
AU - Schwefel, Harald
ID - 1263
IS - 6
JF - Optica
TI - Efficient microwave to optical photon conversion: An electro-optical realization
VL - 3
ER -
TY - JOUR
AB - n contrast with the wealth of recent reports about the function of μ-adaptins and clathrin adaptor protein (AP) complexes, there is very little information about the motifs that determine the sorting of membrane proteins within clathrin-coated vesicles in plants. Here, we investigated putative sorting signals in the large cytosolic loop of the Arabidopsis (Arabidopsis thaliana) PIN-FORMED1 (PIN1) auxin transporter, which are involved in binding μ-adaptins and thus in PIN1 trafficking and localization. We found that Phe-165 and Tyr-280, Tyr-328, and Tyr-394 are involved in the binding of different μ-adaptins in vitro. However, only Phe-165, which binds μA(μ2)- and μD(μ3)-adaptin, was found to be essential for PIN1 trafficking and localization in vivo. The PIN1:GFP-F165A mutant showed reduced endocytosis but also localized to intracellular structures containing several layers of membranes and endoplasmic reticulum (ER) markers, suggesting that they correspond to ER or ER-derived membranes. While PIN1:GFP localized normally in a μA (μ2)-adaptin mutant, it accumulated in big intracellular structures containing LysoTracker in a μD (μ3)-adaptin mutant, consistent with previous results obtained with mutants of other subunits of the AP-3 complex. Our data suggest that Phe-165, through the binding of μA (μ2)- and μD (μ3)-adaptin, is important for PIN1 endocytosis and for PIN1 trafficking along the secretory pathway, respectively.
AU - Sancho Andrés, Gloria
AU - Soriano Ortega, Esther
AU - Gao, Caiji
AU - Bernabé Orts, Joan
AU - Narasimhan, Madhumitha
AU - Müller, Anna
AU - Tejos, Ricardo
AU - Jiang, Liwen
AU - Friml, Jirí
AU - Aniento, Fernando
AU - Marcote, Maria
ID - 1264
IS - 3
JF - Plant Physiology
TI - Sorting motifs involved in the trafficking and localization of the PIN1 auxin efflux carrier
VL - 171
ER -
TY - JOUR
AB - Cortical networks exhibit ‘global oscillations’, in which neural spike times are entrained to an underlying oscillatory rhythm, but where individual neurons fire irregularly, on only a fraction of cycles. While the network dynamics underlying global oscillations have been well characterised, their function is debated. Here, we show that such global oscillations are a direct consequence of optimal efficient coding in spiking networks with synaptic delays and noise. To avoid firing unnecessary spikes, neurons need to share information about the network state. Ideally, membrane potentials should be strongly correlated and reflect a ‘prediction error’ while the spikes themselves are uncorrelated and occur rarely. We show that the most efficient representation is when: (i) spike times are entrained to a global Gamma rhythm (implying a consistent representation of the error); but (ii) few neurons fire on each cycle (implying high efficiency), while (iii) excitation and inhibition are tightly balanced. This suggests that cortical networks exhibiting such dynamics are tuned to achieve a maximally efficient population code.
AU - Chalk, Matthew J
AU - Gutkin, Boris
AU - Denève, Sophie
ID - 1266
IS - 2016JULY
JF - eLife
TI - Neural oscillations as a signature of efficient coding in the presence of synaptic delays
VL - 5
ER -
TY - JOUR
AB - We give a simplified proof of the nonexistence of large nuclei in the liquid drop model and provide an explicit bound. Our bound is within a factor of 2.3 of the conjectured value and seems to be the first quantitative result.
AU - Frank, Rupert
AU - Killip, Rowan
AU - Nam, Phan
ID - 1267
IS - 8
JF - Letters in Mathematical Physics
TI - Nonexistence of large nuclei in the liquid drop model
VL - 106
ER -
TY - JOUR
AB - Plants are continuously exposed to a myriad of external signals such as fluctuating nutrients availability, drought, heat, cold, high salinity, or pathogen/pest attacks that can severely affect their development, growth, and fertility. As sessile organisms, plants must therefore be able to sense and rapidly react to these external inputs, activate efficient responses, and adjust development to changing conditions. In recent years, significant progress has been made towards understanding the molecular mechanisms underlying the intricate and complex communication between plants and the environment. It is now becoming increasingly evident that hormones have an important regulatory role in plant adaptation and defense mechanisms.
AU - Benková, Eva
ID - 1269
IS - 6
JF - Plant Molecular Biology
TI - Plant hormones in interactions with the environment
VL - 91
ER -
TY - THES
AB - In this thesis we present a computer-aided programming approach to concurrency. Our approach
helps the programmer by automatically fixing concurrency-related bugs, i.e. bugs that occur
when the program is executed using an aggressive preemptive scheduler, but not when using a
non-preemptive (cooperative) scheduler. Bugs are program behaviours that are incorrect w.r.t.
a specification. We consider both user-provided explicit specifications in the form of assertion
statements in the code as well as an implicit specification. The implicit specification is inferred
from the non-preemptive behaviour. Let us consider sequences of calls that the program makes
to an external interface. The implicit specification requires that any such sequence produced
under a preemptive scheduler should be included in the set of sequences produced under a
non-preemptive scheduler.
We consider several semantics-preserving fixes that go beyond atomic sections typically
explored in the synchronisation synthesis literature. Our synthesis is able to place locks, barriers
and wait-signal statements and last, but not least reorder independent statements. The latter
may be useful if a thread is released to early, e.g., before some initialisation is completed. We
guarantee that our synthesis does not introduce deadlocks and that the synchronisation inserted
is optimal w.r.t. a given objective function.
We dub our solution trace-based synchronisation synthesis and it is loosely based on
counterexample-guided inductive synthesis (CEGIS). The synthesis works by discovering a
trace that is incorrect w.r.t. the specification and identifying ordering constraints crucial to trigger
the specification violation. Synchronisation may be placed immediately (greedy approach) or
delayed until all incorrect traces are found (non-greedy approach). For the non-greedy approach
we construct a set of global constraints over synchronisation placements. Each model of the
global constraints set corresponds to a correctness-ensuring synchronisation placement. The
placement that is optimal w.r.t. the given objective function is chosen as the synchronisation
solution.
We evaluate our approach on a number of realistic (albeit simplified) Linux device-driver
benchmarks. The benchmarks are versions of the drivers with known concurrency-related bugs.
For the experiments with an explicit specification we added assertions that would detect the bugs
in the experiments. Device drivers lend themselves to implicit specification, where the device and
the operating system are the external interfaces. Our experiments demonstrate that our synthesis
method is precise and efficient. We implemented objective functions for coarse-grained and
fine-grained locking and observed that different synchronisation placements are produced for
our experiments, favouring e.g. a minimal number of synchronisation operations or maximum
concurrency.
AU - Tarrach, Thorsten
ID - 1130
TI - Automatic synthesis of synchronisation primitives for concurrent programs
ER -
TY - JOUR
AB - CA3–CA3 recurrent excitatory synapses are thought to play a key role in memory storage and pattern completion. Whether the plasticity properties of these synapses are consistent with their proposed network functions remains unclear. Here, we examine the properties of spike timing-dependent plasticity (STDP) at CA3–CA3 synapses. Low-frequency pairing of excitatory postsynaptic potentials (EPSPs) and action potentials (APs) induces long-term potentiation (LTP), independent of temporal order. The STDP curve is symmetric and broad (half-width ~150 ms). Consistent with these STDP induction properties, AP–EPSP sequences lead to supralinear summation of spine [Ca2+] transients. Furthermore, afterdepolarizations (ADPs) following APs efficiently propagate into dendrites of CA3 pyramidal neurons, and EPSPs summate with dendritic ADPs. In autoassociative network models, storage and recall are more robust with symmetric than with asymmetric STDP rules. Thus, a specialized STDP induction rule allows reliable storage and recall of information in the hippocampal CA3 network.
AU - Mishra, Rajiv Kumar
AU - Kim, Sooyun
AU - Guzmán, José
AU - Jonas, Peter M
ID - 1432
JF - Nature Communications
TI - Symmetric spike timing-dependent plasticity at CA3–CA3 synapses optimizes storage and recall in autoassociative networks
VL - 7
ER -
TY - THES
AB - CA3 pyramidal neurons are thought to pay a key role in memory storage and pattern completion by activity-dependent synaptic plasticity between CA3-CA3 recurrent excitatory synapses. To examine the induction rules of synaptic plasticity at CA3-CA3 synapses, we performed whole-cell patch-clamp recordings in acute hippocampal slices from rats (postnatal 21-24 days) at room temperature. Compound excitatory postsynaptic potentials (ESPSs) were recorded by tract stimulation in stratum oriens in the presence of 10 µM gabazine. High-frequency stimulation (HFS) induced N-methyl-D-aspartate (NMDA) receptor-dependent long-term potentiation (LTP). Although LTP by HFS did not requier postsynaptic spikes, it was blocked by Na+-channel blockers suggesting that local active processes (e.g.) dendritic spikes) may contribute to LTP induction without requirement of a somatic action potential (AP). We next examined the properties of spike timing-dependent plasticity (STDP) at CA3-CA3 synapses. Unexpectedly, low-frequency pairing of EPSPs and backpropagated action potentialy (bAPs) induced LTP, independent of temporal order. The STDP curve was symmetric and broad, with a half-width of ~150 ms. Consistent with these specific STDP induction properties, post-presynaptic sequences led to a supralinear summation of spine [Ca2+] transients. Furthermore, in autoassociative network models, storage and recall was substantially more robust with symmetric than with asymmetric STDP rules. In conclusion, we found associative forms of LTP at CA3-CA3 recurrent collateral synapses with distinct induction rules. LTP induced by HFS may be associated with dendritic spikes. In contrast, low frequency pairing of pre- and postsynaptic activity induced LTP only if EPSP-AP were temporally very close. Together, these induction mechanisms of synaptiic plasticity may contribute to memory storage in the CA3-CA3 microcircuit at different ranges of activity.
AU - Mishra, Rajiv Kumar
ID - 1396
TI - Synaptic plasticity rules at CA3-CA3 recurrent synapses in hippocampus
ER -
TY - THES
AB - Directed cell migration is a hallmark feature, present in almost all multi-cellular
organisms. Despite its importance, basic questions regarding force transduction
or directional sensing are still heavily investigated. Directed migration of cells
guided by immobilized guidance cues - haptotaxis - occurs in key-processes,
such as embryonic development and immunity (Middleton et al., 1997; Nguyen
et al., 2000; Thiery, 1984; Weber et al., 2013). Immobilized guidance cues
comprise adhesive ligands, such as collagen and fibronectin (Barczyk et al.,
2009), or chemokines - the main guidance cues for migratory leukocytes
(Middleton et al., 1997; Weber et al., 2013). While adhesive ligands serve as
attachment sites guiding cell migration (Carter, 1965), chemokines instruct
haptotactic migration by inducing adhesion to adhesive ligands and directional
guidance (Rot and Andrian, 2004; Schumann et al., 2010). Quantitative analysis
of the cellular response to immobilized guidance cues requires in vitro assays
that foster cell migration, offer accurate control of the immobilized cues on a
subcellular scale and in the ideal case closely reproduce in vivo conditions. The
exploration of haptotactic cell migration through design and employment of such
assays represents the main focus of this work.
Dendritic cells (DCs) are leukocytes, which after encountering danger
signals such as pathogens in peripheral organs instruct naïve T-cells and
consequently the adaptive immune response in the lymph node (Mellman and
Steinman, 2001). To reach the lymph node from the periphery, DCs follow
haptotactic gradients of the chemokine CCL21 towards lymphatic vessels
(Weber et al., 2013). Questions about how DCs interpret haptotactic CCL21
gradients have not yet been addressed. The main reason for this is the lack of
an assay that offers diverse haptotactic environments, hence allowing the study
of DC migration as a response to different signals of immobilized guidance cue.
In this work, we developed an in vitro assay that enables us to
quantitatively assess DC haptotaxis, by combining precisely controllable
chemokine photo-patterning with physically confining migration conditions. With this tool at hand, we studied the influence of CCL21 gradient properties and
concentration on DC haptotaxis. We found that haptotactic gradient sensing
depends on the absolute CCL21 concentration in combination with the local
steepness of the gradient. Our analysis suggests that the directionality of
migrating DCs is governed by the signal-to-noise ratio of CCL21 binding to its
receptor CCR7. Moreover, the haptotactic CCL21 gradient formed in vivo
provides an optimal shape for DCs to recognize haptotactic guidance cue.
By reconstitution of the CCL21 gradient in vitro we were also able to
study the influence of CCR7 signal termination on DC haptotaxis. To this end,
we used DCs lacking the G-protein coupled receptor kinase GRK6, which is
responsible for CCL21 induced CCR7 receptor phosphorylation and
desensitization (Zidar et al., 2009). We found that CCR7 desensitization by
GRK6 is crucial for maintenance of haptotactic CCL21 gradient sensing in vitro
and confirm those observations in vivo.
In the context of the organism, immobilized haptotactic guidance cues
often coincide and compete with soluble chemotactic guidance cues. During
wound healing, fibroblasts are exposed and influenced by adhesive cues and
soluble factors at the same time (Wu et al., 2012; Wynn, 2008). Similarly,
migrating DCs are exposed to both, soluble chemokines (CCL19 and truncated
CCL21) inducing chemotactic behavior as well as the immobilized CCL21. To
quantitatively assess these complex coinciding immobilized and soluble
guidance cues, we implemented our chemokine photo-patterning technique in a
microfluidic system allowing for chemotactic gradient generation. To validate
the assay, we observed DC migration in competing CCL19/CCL21
environments.
Adhesiveness guided haptotaxis has been studied intensively over the
last century. However, quantitative studies leading to conceptual models are
largely missing, again due to the lack of a precisely controllable in vitro assay. A
requirement for such an in vitro assay is that it must prevent any uncontrolled
cell adhesion. This can be accomplished by stable passivation of the surface. In
addition, controlled adhesion must be sustainable, quantifiable and dose
dependent in order to create homogenous gradients. Therefore, we developed a novel covalent photo-patterning technique satisfying all these needs. In
combination with a sustainable poly-vinyl alcohol (PVA) surface coating we
were able to generate gradients of adhesive cue to direct cell migration. This
approach allowed us to characterize the haptotactic migratory behavior of
zebrafish keratocytes in vitro. Furthermore, defined patterns of adhesive cue
allowed us to control for cell shape and growth on a subcellular scale.
AU - Schwarz, Jan
ID - 1129
TI - Quantitative analysis of haptotactic cell migration
ER -
TY - THES
AB - Motivated by topological Tverberg-type problems in topological combinatorics and by classical
results about embeddings (maps without double points), we study the question whether a finite
simplicial complex K can be mapped into Rd without triple, quadruple, or, more generally, r-fold points (image points with at least r distinct preimages), for a given multiplicity r ≤ 2. In particular, we are interested in maps f : K → Rd that have no global r -fold intersection points, i.e., no r -fold points with preimages in r pairwise disjoint simplices of K , and we seek necessary and sufficient conditions for the existence of such maps.
We present higher-multiplicity analogues of several classical results for embeddings, in particular of the completeness of the Van Kampen obstruction for embeddability of k -dimensional
complexes into R2k , k ≥ 3. Speciffically, we show that under suitable restrictions on the dimensions(viz., if dimK = (r ≥ 1)k and d = rk \ for some k ≥ 3), a well-known deleted product criterion (DPC ) is not only necessary but also sufficient for the existence of maps without global r -fold points. Our main technical tool is a higher-multiplicity version of the classical Whitney trick , by which pairs of isolated r -fold points of opposite sign can be eliminated by local modiffications of the map, assuming codimension d – dimK ≥ 3.
An important guiding idea for our work was that suffciency of the DPC, together with an old
result of Özaydin's on the existence of equivariant maps, might yield an approach to disproving the remaining open cases of the the long-standing topological Tverberg conjecture , i.e., to construct maps from the N -simplex σN to Rd without r-Tverberg points when r not a prime power and
N = (d + 1)(r – 1). Unfortunately, our proof of the sufficiency of the DPC requires codimension d – dimK ≥ 3, which is not satisfied for K = σN .
In 2015, Frick [16] found a very elegant way to overcome this \codimension 3 obstacle" and
to construct the first counterexamples to the topological Tverberg conjecture for all parameters(d; r ) with d ≥ 3r + 1 and r not a prime power, by a reduction1 to a suitable lower-dimensional skeleton, for which the codimension 3 restriction is satisfied and maps without r -Tverberg points exist by Özaydin's result and sufficiency of the DPC.
In this thesis, we present a different construction (which does not use the constraint method) that yields counterexamples for d ≥ 3r , r not a prime power.
AU - Mabillard, Isaac
ID - 1123
TI - Eliminating higher-multiplicity intersections: an r-fold Whitney trick for the topological Tverberg conjecture
ER -
TY - THES
AB - Horizontal gene transfer (HGT), the lateral acquisition of genes across existing species
boundaries, is a major evolutionary force shaping microbial genomes that facilitates
adaptation to new environments as well as resistance to antimicrobial drugs. As such,
understanding the mechanisms and constraints that determine the outcomes of HGT
events is crucial to understand the dynamics of HGT and to design better strategies to
overcome the challenges that originate from it.
Following the insertion and expression of a newly transferred gene, the success of an
HGT event will depend on the fitness effect it has on the recipient (host) cell. Therefore,
predicting the impact of HGT on the genetic composition of a population critically
depends on the distribution of fitness effects (DFE) of horizontally transferred genes.
However, to date, we have little knowledge of the DFE of newly transferred genes, and
hence little is known about the shape and scale of this distribution.
It is particularly important to better understand the selective barriers that determine
the fitness effects of newly transferred genes. In spite of substantial bioinformatics
efforts to identify horizontally transferred genes and selective barriers, a systematic
experimental approach to elucidate the roles of different selective barriers in defining
the fate of a transfer event has largely been absent. Similarly, although the fact that
environment might alter the fitness effect of a horizontally transferred gene may seem
obvious, little attention has been given to it in a systematic experimental manner.
In this study, we developed a systematic experimental approach that consists of
transferring 44 arbitrarily selected Salmonella typhimurium orthologous genes into an
Escherichia coli host, and estimating the fitness effects of these transferred genes at a
constant expression level by performing competition assays against the wild type.
In chapter 2, we performed one-to-one competition assays between a mutant strain
carrying a transferred gene and the wild type strain. By using flow cytometry we
estimated selection coefficients for the transferred genes with a precision level of 10-3,and obtained the DFE of horizontally transferred genes. We then investigated if these
fitness effects could be predicted by any of the intrinsic properties of the genes, namely,
functional category, degree of complexity (protein-protein interactions), GC content,
codon usage and length. Our analyses revealed that the functional category and length
of the genes act as potential selective barriers. Finally, using the same procedure with
the endogenous E. coli orthologs of these 44 genes, we demonstrated that gene dosage is
the most prominent selective barrier to HGT.
In chapter 3, using the same set of genes we investigated the role of environment on the
success of HGT events. Under six different environments with different levels of stress
we performed more complex competition assays, where we mixed all 44 mutant strains
carrying transferred genes with the wild type strain. To estimate the fitness effects of
genes relative to wild type we used next generation sequencing. We found that the DFEs
of horizontally transferred genes are highly dependent on the environment, with
abundant gene–by-environment interactions. Furthermore, we demonstrated a
relationship between average fitness effect of a gene across all environments and its
environmental variance, and thus its predictability. Finally, in spite of the fitness effects
of genes being highly environment-dependent, we still observed a common shape of
DFEs across all tested environments.
AU - Acar, Hande
ID - 1121
TI - Selective barriers to horizontal gene transfer
ER -
TY - THES
AB - Evolution of gene regulation is important for phenotypic evolution and diversity. Sequence-specific binding of regulatory proteins is one of the key regulatory mechanisms determining gene expression. Although there has been intense interest in evolution of regulatory binding sites in the last decades, a theoretical understanding is far from being complete. In this thesis, I aim at a better understanding of the evolution of transcriptional regulatory binding sequences by using biophysical and population genetic models.
In the first part of the thesis, I discuss how to formulate the evolutionary dynamics of binding se- quences in a single isolated binding site and in promoter/enhancer regions. I develop a theoretical framework bridging between a thermodynamical model for transcription and a mutation-selection-drift model for monomorphic populations. I mainly address the typical evolutionary rates, and how they de- pend on biophysical parameters (e.g. binding length and specificity) and population genetic parameters (e.g. population size and selection strength).
In the second part of the thesis, I analyse empirical data for a better evolutionary and biophysical understanding of sequence-specific binding of bacterial RNA polymerase. First, I infer selection on regulatory and non-regulatory binding sites of RNA polymerase in the E. coli K12 genome. Second, I infer the chemical potential of RNA polymerase, an important but unknown physical parameter defining the threshold energy for strong binding. Furthermore, I try to understand the relation between the lac promoter sequence diversity and the LacZ activity variation among 20 bacterial isolates by constructing a simple but biophysically motivated gene expression model. Lastly, I lay out a statistical framework to predict adaptive point mutations in de novo promoter evolution in a selection experiment.
AU - Tugrul, Murat
ID - 1131
TI - Evolution of transcriptional regulatory sequences
ER -
TY - THES
AB - Natural environments are never constant but subject to spatial and temporal change on
all scales, increasingly so due to human activity. Hence, it is crucial to understand the
impact of environmental variation on evolutionary processes. In this thesis, I present
three topics that share the common theme of environmental variation, yet illustrate its
effect from different perspectives.
First, I show how a temporally fluctuating environment gives rise to second-order
selection on a modifier for stress-induced mutagenesis. Without fluctuations, when
populations are adapted to their environment, mutation rates are minimized. I argue
that a stress-induced mutator mechanism may only be maintained if the population is
repeatedly subjected to diverse environmental challenges, and I outline implications of
the presented results to antibiotic treatment strategies.
Second, I discuss my work on the evolution of dispersal. Besides reproducing
known results about the effect of heterogeneous habitats on dispersal, it identifies
spatial changes in dispersal type frequencies as a source for selection for increased
propensities to disperse. This concept contains effects of relatedness that are known
to promote dispersal, and I explain how it identifies other forces selecting for dispersal
and puts them on a common scale.
Third, I analyse genetic variances of phenotypic traits under multivariate stabilizing
selection. For the case of constant environments, I generalize known formulae of
equilibrium variances to multiple traits and discuss how the genetic variance of a focal
trait is influenced by selection on background traits. I conclude by presenting ideas and
preliminary work aiming at including environmental fluctuations in the form of moving
trait optima into the model.
AU - Novak, Sebastian
ID - 1125
TI - Evolutionary proccesses in variable emvironments
ER -
TY - DATA
AB - The data stored here is used in Murat Tugrul's PhD thesis (Chapter 3), which is related to the evolution of bacterial RNA polymerase binding.
Magdalena Steinrueck (PhD Student in Calin Guet's group at IST Austria) performed the experiments and created the data on de novo promoter evolution. Fabienne Jesse (PhD Student in Jon Bollback's group at IST Austria) performed the experiments and created the data on lac promoter evolution.
AU - Tugrul, Murat
ID - 5554
KW - RNAP binding
KW - de novo promoter evolution
KW - lac promoter
TI - Experimental Data for Binding Site Evolution of Bacterial RNA Polymerase
ER -
TY - THES
AU - Morri, Maurizio
ID - 1124
TI - Optical functionalization of human class A orphan G-protein coupled receptors
ER -
TY - JOUR
AB - Branching morphogenesis of the epithelial ureteric bud forms the renal collecting duct system and is critical for normal nephron number, while low nephron number is implicated in hypertension and renal disease. Ureteric bud growth and branching requires GDNF signaling from the surrounding mesenchyme to cells at the ureteric bud tips, via the Ret receptor tyrosine kinase and coreceptor Gfrα1; Ret signaling up-regulates transcription factors Etv4 and Etv5, which are also critical for branching. Despite extensive knowledge of the genetic control of these events, it is not understood, at the cellular level, how renal branching morphogenesis is achieved or how Ret signaling influences epithelial cell behaviors to promote this process. Analysis of chimeric embryos previously suggested a role for Ret signaling in promoting cell rearrangements in the nephric duct, but this method was unsuited to study individual cell behaviors during ureteric bud branching. Here, we use Mosaic Analysis with Double Markers (MADM), combined with organ culture and time-lapse imaging, to trace the movements and divisions of individual ureteric bud tip cells. We first examine wild-type clones and then Ret or Etv4 mutant/wild-type clones in which the mutant and wild-type sister cells are differentially and heritably marked by green and red fluorescent proteins. We find that, in normal kidneys, most individual tip cells behave as self-renewing progenitors, some of whose progeny remain at the tips while others populate the growing UB trunks. In Ret or Etv4 MADM clones, the wild-type cells generated at a UB tip are much more likely to remain at, or move to, the new tips during branching and elongation, while their Ret−/− or Etv4−/− sister cells tend to lag behind and contribute only to the trunks. By tracking successive mitoses in a cell lineage, we find that Ret signaling has little effect on proliferation, in contrast to its effects on cell movement. Our results show that Ret/Etv4 signaling promotes directed cell movements in the ureteric bud tips, and suggest a model in which these cell movements mediate branching morphogenesis.
AU - Riccio, Paul
AU - Cebrián, Cristina
AU - Zong, Hui
AU - Hippenmeyer, Simon
AU - Costantini, Frank
ID - 1488
IS - 2
JF - PLoS Biology
TI - Ret and Etv4 promote directed movements of progenitor cells during renal branching morphogenesis
VL - 14
ER -
TY - JOUR
AB - Emerging infectious diseases (EIDs) have contributed significantly to the current biodiversity crisis, leading to widespread epidemics and population loss. Owing to genetic variation in pathogen virulence, a complete understanding of species decline requires the accurate identification and characterization of EIDs. We explore this issue in the Western honeybee, where increasing mortality of populations in the Northern Hemisphere has caused major concern. Specifically, we investigate the importance of genetic identity of the main suspect in mortality, deformed wing virus (DWV), in driving honeybee loss. Using laboratory experiments and a systematic field survey, we demonstrate that an emerging DWV genotype (DWV-B) is more virulent than the established DWV genotype (DWV-A) and is widespread in the landscape. Furthermore, we show in a simple model that colonies infected with DWV-B collapse sooner than colonies infected with DWV-A. We also identify potential for rapid DWV evolution by revealing extensive genome-wide recombination in vivo. The emergence of DWV-B in naive honeybee populations, including via recombination with DWV-A, could be of significant ecological and economic importance. Our findings emphasize that knowledge of pathogen genetic identity and diversity is critical to understanding drivers of species decline.
AU - Mcmahon, Dino
AU - Natsopoulou, Myrsini
AU - Doublet, Vincent
AU - Fürst, Matthias
AU - Weging, Silvio
AU - Brown, Mark
AU - Gogol Döring, Andreas
AU - Paxton, Robert
ID - 1262
IS - 1833
JF - Proceedings of the Royal Society of London Series B Biological Sciences
TI - Elevated virulence of an emerging viral genotype as a driver of honeybee loss
VL - 283
ER -
TY - GEN
AB - Emerging infectious diseases (EIDs) have contributed significantly to the current biodiversity crisis, leading to widespread epidemics and population loss. Owing to genetic variation in pathogen virulence, a complete understanding of species decline requires the accurate identification and characterization of EIDs. We explore this issue in the Western honeybee, where increasing mortality of populations in the Northern Hemisphere has caused major concern. Specifically, we investigate the importance of genetic identity of the main suspect in mortality, deformed wing virus (DWV), in driving honeybee loss. Using laboratory experiments and a systematic field survey, we demonstrate that an emerging DWV genotype (DWV-B) is more virulent than the established DWV genotype (DWV-A) and is widespread in the landscape. Furthermore, we show in a simple model that colonies infected with DWV-B collapse sooner than colonies infected with DWV-A. We also identify potential for rapid DWV evolution by revealing extensive genome-wide recombination in vivo. The emergence of DWV-B in naive honeybee populations, including via recombination with DWV-A, could be of significant ecological and economic importance. Our findings emphasize that knowledge of pathogen genetic identity and diversity is critical to understanding drivers of species decline.
AU - Mcmahon, Dino
AU - Natsopoulou, Myrsini
AU - Doublet, Vincent
AU - Fürst, Matthias
AU - Weging, Silvio
AU - Brown, Mark
AU - Gogol Döring, Andreas
AU - Paxton, Robert
ID - 9704
TI - Data from: Elevated virulence of an emerging viral genotype as a driver of honeybee loss
ER -
TY - JOUR
AB - Across the nervous system, certain population spiking patterns are observed far more frequently than others. A hypothesis about this structure is that these collective activity patterns function as population codewords–collective modes–carrying information distinct from that of any single cell. We investigate this phenomenon in recordings of ∼150 retinal ganglion cells, the retina’s output. We develop a novel statistical model that decomposes the population response into modes; it predicts the distribution of spiking activity in the ganglion cell population with high accuracy. We found that the modes represent localized features of the visual stimulus that are distinct from the features represented by single neurons. Modes form clusters of activity states that are readily discriminated from one another. When we repeated the same visual stimulus, we found that the same mode was robustly elicited. These results suggest that retinal ganglion cells’ collective signaling is endowed with a form of error-correcting code–a principle that may hold in brain areas beyond retina.
AU - Prentice, Jason
AU - Marre, Olivier
AU - Ioffe, Mark
AU - Loback, Adrianna
AU - Tkacik, Gasper
AU - Berry, Michael
ID - 1197
IS - 11
JF - PLoS Computational Biology
TI - Error-robust modes of the retinal population code
VL - 12
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 - Autism spectrum disorders (ASD) are a group of genetic disorders often overlapping with other neurological conditions. We previously described abnormalities in the branched-chain amino acid (BCAA) catabolic pathway as a cause of ASD. Here, we show that the solute carrier transporter 7a5 (SLC7A5), a large neutral amino acid transporter localized at the blood brain barrier (BBB), has an essential role in maintaining normal levels of brain BCAAs. In mice, deletion of Slc7a5 from the endothelial cells of the BBB leads to atypical brain amino acid profile, abnormal mRNA translation, and severe neurological abnormalities. Furthermore, we identified several patients with autistic traits and motor delay carrying deleterious homozygous mutations in the SLC7A5 gene. Finally, we demonstrate that BCAA intracerebroventricular administration ameliorates abnormal behaviors in adult mutant mice. Our data elucidate a neurological syndrome defined by SLC7A5 mutations and support an essential role for the BCAA in human brain function.
AU - Tarlungeanu, Dora-Clara
AU - Deliu, Elena
AU - Dotter, Christoph
AU - Kara, Majdi
AU - Janiesch, Philipp
AU - Scalise, Mariafrancesca
AU - Galluccio, Michele
AU - Tesulov, Mateja
AU - Morelli, Emanuela
AU - Sönmez, Fatma
AU - Bilgüvar, Kaya
AU - Ohgaki, Ryuichi
AU - Kanai, Yoshikatsu
AU - Johansen, Anide
AU - Esharif, Seham
AU - Ben Omran, Tawfeg
AU - Topcu, Meral
AU - Schlessinger, Avner
AU - Indiveri, Cesare
AU - Duncan, Kent
AU - Caglayan, Ahmet
AU - Günel, Murat
AU - Gleeson, Joseph
AU - Novarino, Gaia
ID - 1183
IS - 6
JF - Cell
TI - Impaired amino acid transport at the blood brain barrier is a cause of autism spectrum disorder
VL - 167
ER -
TY - JOUR
AB - Most migrating cells extrude their front by the force of actin polymerization. Polymerization requires an initial nucleation step, which is mediated by factors establishing either parallel filaments in the case of filopodia or branched filaments that form the branched lamellipodial network. Branches are considered essential for regular cell motility and are initiated by the Arp2/3 complex, which in turn is activated by nucleation-promoting factors of the WASP and WAVE families. Here we employed rapid amoeboid crawling leukocytes and found that deletion of the WAVE complex eliminated actin branching and thus lamellipodia formation. The cells were left with parallel filaments at the leading edge, which translated, depending on the differentiation status of the cell, into a unipolar pointed cell shape or cells with multiple filopodia. Remarkably, unipolar cells migrated with increased speed and enormous directional persistence, while they were unable to turn towards chemotactic gradients. Cells with multiple filopodia retained chemotactic activity but their migration was progressively impaired with increasing geometrical complexity of the extracellular environment. These findings establish that diversified leading edge protrusions serve as explorative structures while they slow down actual locomotion.
AU - Leithner, Alexander F
AU - Eichner, Alexander
AU - Müller, Jan
AU - Reversat, Anne
AU - Brown, Markus
AU - Schwarz, Jan
AU - Merrin, Jack
AU - De Gorter, David
AU - Schur, Florian
AU - Bayerl, Jonathan
AU - De Vries, Ingrid
AU - Wieser, Stefan
AU - Hauschild, Robert
AU - Lai, Frank
AU - Moser, Markus
AU - Kerjaschki, Dontscho
AU - Rottner, Klemens
AU - Small, Victor
AU - Stradal, Theresia
AU - Sixt, Michael K
ID - 1321
JF - Nature Cell Biology
TI - Diversified actin protrusions promote environmental exploration but are dispensable for locomotion of leukocytes
VL - 18
ER -
TY - JOUR
AB - During metazoan development, the temporal pattern of morphogen signaling is critical for organizing cell fates in space and time. Yet, tools for temporally controlling morphogen signaling within the embryo are still scarce. Here, we developed a photoactivatable Nodal receptor to determine how the temporal pattern of Nodal signaling affects cell fate specification during zebrafish gastrulation. By using this receptor to manipulate the duration of Nodal signaling in vivo by light, we show that extended Nodal signaling within the organizer promotes prechordal plate specification and suppresses endoderm differentiation. Endoderm differentiation is suppressed by extended Nodal signaling inducing expression of the transcriptional repressor goosecoid (gsc) in prechordal plate progenitors, which in turn restrains Nodal signaling from upregulating the endoderm differentiation gene sox17 within these cells. Thus, optogenetic manipulation of Nodal signaling identifies a critical role of Nodal signaling duration for organizer cell fate specification during gastrulation.
AU - Sako, Keisuke
AU - Pradhan, Saurabh
AU - Barone, Vanessa
AU - Inglés Prieto, Álvaro
AU - Mueller, Patrick
AU - Ruprecht, Verena
AU - Capek, Daniel
AU - Galande, Sanjeev
AU - Janovjak, Harald L
AU - Heisenberg, Carl-Philipp J
ID - 1100
IS - 3
JF - Cell Reports
TI - Optogenetic control of nodal signaling reveals a temporal pattern of nodal signaling regulating cell fate specification during gastrulation
VL - 16
ER -
TY - CONF
AB - We study algorithmic questions for concurrent systems where the transitions are labeled from a complete, closed semiring, and path properties are algebraic with semiring operations. The algebraic path properties can model dataflow analysis problems, the shortest path problem, and many other natural problems that arise in program analysis. We consider that each component of the concurrent system is a graph with constant treewidth, a property satisfied by the controlflow graphs of most programs. We allow for multiple possible queries, which arise naturally in demand driven dataflow analysis. The study of multiple queries allows us to consider the tradeoff between the resource usage of the one-time preprocessing and for each individual query. The traditional approach constructs the product graph of all components and applies the best-known graph algorithm on the product. In this approach, even the answer to a single query requires the transitive closure (i.e., the results of all possible queries), which provides no room for tradeoff between preprocessing and query time. Our main contributions are algorithms that significantly improve the worst-case running time of the traditional approach, and provide various tradeoffs depending on the number of queries. For example, in a concurrent system of two components, the traditional approach requires hexic time in the worst case for answering one query as well as computing the transitive closure, whereas we show that with one-time preprocessing in almost cubic time, each subsequent query can be answered in at most linear time, and even the transitive closure can be computed in almost quartic time. Furthermore, we establish conditional optimality results showing that the worst-case running time of our algorithms cannot be improved without achieving major breakthroughs in graph algorithms (i.e., improving the worst-case bound for the shortest path problem in general graphs). Preliminary experimental results show that our algorithms perform favorably on several benchmarks.
AU - Chatterjee, Krishnendu
AU - Goharshady, Amir
AU - Ibsen-Jensen, Rasmus
AU - Pavlogiannis, Andreas
ID - 1437
TI - Algorithms for algebraic path properties in concurrent systems of constant treewidth components
VL - 20-22
ER -
TY - CONF
AB - We consider nondeterministic probabilistic programs with the most basic liveness property of termination. We present efficient methods for termination analysis of nondeterministic probabilistic programs with polynomial guards and assignments. Our approach is through synthesis of polynomial ranking supermartingales, that on one hand significantly generalizes linear ranking supermartingales and on the other hand is a counterpart of polynomial ranking-functions for proving termination of nonprobabilistic programs. The approach synthesizes polynomial ranking-supermartingales through Positivstellensatz's, yielding an efficient method which is not only sound, but also semi-complete over a large subclass of programs. We show experimental results to demonstrate that our approach can handle several classical programs with complex polynomial guards and assignments, and can synthesize efficient quadratic ranking-supermartingales when a linear one does not exist even for simple affine programs.
AU - Chatterjee, Krishnendu
AU - Fu, Hongfei
AU - Goharshady, Amir
ID - 1386
TI - Termination analysis of probabilistic programs through Positivstellensatz's
VL - 9779
ER -
TY - JOUR
AB - A class of valued constraint satisfaction problems (VCSPs) is characterised by a valued constraint language, a fixed set of cost functions on a finite domain. Finite-valued constraint languages contain functions that take on rational costs and general-valued constraint languages contain functions that take on rational or infinite costs. An instance of the problem is specified by a sum of functions from the language with the goal to minimise the sum. This framework includes and generalises well-studied constraint satisfaction problems (CSPs) and maximum constraint satisfaction problems (Max-CSPs).
Our main result is a precise algebraic characterisation of valued constraint languages whose instances can be solved exactly by the basic linear programming relaxation (BLP). For a general-valued constraint language Γ, BLP is a decision procedure for Γ if and only if Γ admits a symmetric fractional polymorphism of every arity. For a finite-valued constraint language Γ, BLP is a decision procedure if and only if Γ admits a symmetric fractional polymorphism of some arity, or equivalently, if Γ admits a symmetric fractional polymorphism of arity 2.
Using these results, we obtain tractability of several novel and previously widely-open classes of VCSPs, including problems over valued constraint languages that are: (1) submodular on arbitrary lattices; (2) bisubmodular (also known as k-submodular) on arbitrary finite domains; (3) weakly (and hence strongly) tree-submodular on arbitrary trees.
AU - Kolmogorov, Vladimir
AU - Thapper, Johan
AU - Živný, Stanislav
ID - 2271
IS - 1
JF - SIAM Journal on Computing
TI - The power of linear programming for general-valued CSPs
VL - 44
ER -
TY - JOUR
AB - Guided cell movement is essential for development and integrity of animals and crucially involved in cellular immune responses. Leukocytes are professional migratory cells that can navigate through most types of tissues and sense a wide range of directional cues. The responses of these cells to attractants have been mainly explored in tissue culture settings. How leukocytes make directional decisions in situ, within the challenging environment of a tissue maze, is less understood. Here we review recent advances in how leukocytes sense chemical cues in complex tissue settings and make links with paradigms of directed migration in development and Dictyostelium discoideum amoebae.
AU - Sarris, Milka
AU - Sixt, Michael K
ID - 1687
IS - 10
JF - Current Opinion in Cell Biology
TI - Navigating in tissue mazes: Chemoattractant interpretation in complex environments
VL - 36
ER -
TY - JOUR
AB - We estimate the selection constant in the following geometric selection theorem by Pach: For every positive integer d, there is a constant (Formula presented.) such that whenever (Formula presented.) are n-element subsets of (Formula presented.), we can find a point (Formula presented.) and subsets (Formula presented.) for every i∈[d+1], each of size at least cdn, such that p belongs to all rainbowd-simplices determined by (Formula presented.) simplices with one vertex in each Yi. We show a super-exponentially decreasing upper bound (Formula presented.). The ideas used in the proof of the upper bound also help us to prove Pach’s theorem with (Formula presented.), which is a lower bound doubly exponentially decreasing in d (up to some polynomial in the exponent). For comparison, Pach’s original approach yields a triply exponentially decreasing lower bound. On the other hand, Fox, Pach, and Suk recently obtained a hypergraph density result implying a proof of Pach’s theorem with (Formula presented.). In our construction for the upper bound, we use the fact that the minimum solid angle of every d-simplex is super-exponentially small. This fact was previously unknown and might be of independent interest. For the lower bound, we improve the ‘separation’ part of the argument by showing that in one of the key steps only d+1 separations are necessary, compared to 2d separations in the original proof. We also provide a measure version of Pach’s theorem.
AU - Karasev, Roman
AU - Kynčl, Jan
AU - Paták, Pavel
AU - Patakova, Zuzana
AU - Tancer, Martin
ID - 1688
IS - 3
JF - Discrete & Computational Geometry
TI - Bounds for Pach's selection theorem and for the minimum solid angle in a simplex
VL - 54
ER -
TY - CONF
AB - We consider the problem of computing the set of initial states of a dynamical system such that there exists a control strategy to ensure that the trajectories satisfy a temporal logic specification with probability 1 (almost-surely). We focus on discrete-time, stochastic linear dynamics and specifications given as formulas of the Generalized Reactivity(1) fragment of Linear Temporal Logic over linear predicates in the states of the system. We propose a solution based on iterative abstraction-refinement, and turn-based 2-player probabilistic games. While the theoretical guarantee of our algorithm after any finite number of iterations is only a partial solution, we show that if our algorithm terminates, then the result is the set of satisfying initial states. Moreover, for any (partial) solution our algorithm synthesizes witness control strategies to ensure almost-sure satisfaction of the temporal logic specification. We demonstrate our approach on an illustrative case study.
AU - Svoreňová, Mária
AU - Kretinsky, Jan
AU - Chmelik, Martin
AU - Chatterjee, Krishnendu
AU - Cěrná, Ivana
AU - Belta, Cǎlin
ID - 1689
T2 - Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control
TI - Temporal logic control for stochastic linear systems using abstraction refinement of probabilistic games
ER -
TY - JOUR
AB - Quantum interference between energetically close states is theoretically investigated, with the state structure being observed via laser spectroscopy. In this work, we focus on hyperfine states of selected hydrogenic muonic isotopes, and on how quantum interference affects the measured Lamb shift. The process of photon excitation and subsequent photon decay is implemented within the framework of nonrelativistic second-order perturbation theory. Due to its experimental interest, calculations are performed for muonic hydrogen, deuterium, and helium-3. We restrict our analysis to the case of photon scattering by incident linear polarized photons and the polarization of the scattered photons not being observed. We conclude that while quantum interference effects can be safely neglected in muonic hydrogen and helium-3, in the case of muonic deuterium there are resonances with close proximity, where quantum interference effects can induce shifts up to a few percent of the linewidth, assuming a pointlike detector. However, by taking into account the geometry of the setup used by the CREMA collaboration, this effect is reduced to less than 0.2% of the linewidth in all possible cases, which makes it irrelevant at the present level of accuracy. © 2015 American Physical Society.
AU - Amaro, Pedro
AU - Franke, Beatrice
AU - Krauth, Julian
AU - Diepold, Marc
AU - Fratini, Filippo
AU - Safari, Laleh
AU - Machado, Jorge
AU - Antognini, Aldo
AU - Kottmann, Franz
AU - Indelicato, Paul
AU - Pohl, Randolf
AU - Santos, José
ID - 1693
IS - 2
JF - Physical Review A
TI - Quantum interference effects in laser spectroscopy of muonic hydrogen, deuterium, and helium-3
VL - 92
ER -
TY - JOUR
AB - We give a comprehensive introduction into a diagrammatic method that allows for the evaluation of Gutzwiller wave functions in finite spatial dimensions. We discuss in detail some numerical schemes that turned out to be useful in the real-space evaluation of the diagrams. The method is applied to the problem of d-wave superconductivity in a two-dimensional single-band Hubbard model. Here, we discuss in particular the role of long-range contributions in our diagrammatic expansion. We further reconsider our previous analysis on the kinetic energy gain in the superconducting state.
AU - Kaczmarczyk, Jan
AU - Schickling, Tobias
AU - Bünemann, Jörg
ID - 1695
IS - 9
JF - Physica Status Solidi (B): Basic Solid State Physics
TI - Evaluation techniques for Gutzwiller wave functions in finite dimensions
VL - 252
ER -
TY - JOUR
AB - The recently proposed diagrammatic expansion (DE) technique for the full Gutzwiller wave function (GWF) is applied to the Anderson lattice model. This approach allows for a systematic evaluation of the expectation values with full Gutzwiller wave function in finite-dimensional systems. It introduces results extending in an essential manner those obtained by means of the standard Gutzwiller approximation (GA), which is variationally exact only in infinite dimensions. Within the DE-GWF approach we discuss the principal paramagnetic properties and their relevance to heavy-fermion systems. We demonstrate the formation of an effective, narrow f band originating from atomic f-electron states and subsequently interpret this behavior as a direct itineracy of f electrons; it represents a combined effect of both the hybridization and the correlations induced by the Coulomb repulsive interaction. Such a feature is absent on the level of GA, which is equivalent to the zeroth order of our expansion. Formation of the hybridization- and electron-concentration-dependent narrow f band rationalizes the common assumption of such dispersion of f levels in the phenomenological modeling of the band structure of CeCoIn5. Moreover, it is shown that the emerging f-electron direct itineracy leads in a natural manner to three physically distinct regimes within a single model that are frequently discussed for 4f- or 5f-electron compounds as separate model situations. We identify these regimes as (i) the mixed-valence regime, (ii) Kondo/almost-Kondo insulating regime, and (iii) the Kondo-lattice limit when the f-electron occupancy is very close to the f-state half filling, ⟨nˆf⟩→1. The nonstandard features of the emerging correlated quantum liquid state are stressed.
AU - Wysokiński, Marcin
AU - Kaczmarczyk, Jan
AU - Spałek, Jozef
ID - 1696
IS - 12
JF - Physical Review B
TI - Gutzwiller wave function solution for Anderson lattice model: Emerging universal regimes of heavy quasiparticle states
VL - 92
ER -
TY - JOUR
AB - Motion tracking is a challenge the visual system has to solve by reading out the retinal population. It is still unclear how the information from different neurons can be combined together to estimate the position of an object. Here we recorded a large population of ganglion cells in a dense patch of salamander and guinea pig retinas while displaying a bar moving diffusively. We show that the bar’s position can be reconstructed from retinal activity with a precision in the hyperacuity regime using a linear decoder acting on 100+ cells. We then took advantage of this unprecedented precision to explore the spatial structure of the retina’s population code. The classical view would have suggested that the firing rates of the cells form a moving hill of activity tracking the bar’s position. Instead, we found that most ganglion cells in the salamander fired sparsely and idiosyncratically, so that their neural image did not track the bar. Furthermore, ganglion cell activity spanned an area much larger than predicted by their receptive fields, with cells coding for motion far in their surround. As a result, population redundancy was high, and we could find multiple, disjoint subsets of neurons that encoded the trajectory with high precision. This organization allows for diverse collections of ganglion cells to represent high-accuracy motion information in a form easily read out by downstream neural circuits.
AU - Marre, Olivier
AU - Botella Soler, Vicente
AU - Simmons, Kristina
AU - Mora, Thierry
AU - Tkacik, Gasper
AU - Berry, Michael
ID - 1697
IS - 7
JF - PLoS Computational Biology
TI - High accuracy decoding of dynamical motion from a large retinal population
VL - 11
ER -
TY - JOUR
AB - In mean-payoff games, the objective of the protagonist is to ensure that the limit average of an infinite sequence of numeric weights is nonnegative. In energy games, the objective is to ensure that the running sum of weights is always nonnegative. Multi-mean-payoff and multi-energy games replace individual weights by tuples, and the limit average (resp., running sum) of each coordinate must be (resp., remain) nonnegative. We prove finite-memory determinacy of multi-energy games and show inter-reducibility of multi-mean-payoff and multi-energy games for finite-memory strategies. We improve the computational complexity for solving both classes with finite-memory strategies: we prove coNP-completeness improving the previous known EXPSPACE bound. For memoryless strategies, we show that deciding the existence of a winning strategy for the protagonist is NP-complete. We present the first solution of multi-mean-payoff games with infinite-memory strategies: we show that mean-payoff-sup objectives can be decided in NP∩coNP, whereas mean-payoff-inf objectives are coNP-complete.
AU - Velner, Yaron
AU - Chatterjee, Krishnendu
AU - Doyen, Laurent
AU - Henzinger, Thomas A
AU - Rabinovich, Alexander
AU - Raskin, Jean
ID - 1698
IS - 4
JF - Information and Computation
TI - The complexity of multi-mean-payoff and multi-energy games
VL - 241
ER -
TY - JOUR
AB - By hybridization and backcrossing, alleles can surmount species boundaries and be incorporated into the genome of a related species. This introgression of genes is of particular evolutionary relevance if it involves the transfer of adaptations between populations. However, any beneficial allele will typically be associated with other alien alleles that are often deleterious and hamper the introgression process. In order to describe the introgression of an adaptive allele, we set up a stochastic model with an explicit genetic makeup of linked and unlinked deleterious alleles. Based on the theory of reducible multitype branching processes, we derive a recursive expression for the establishment probability of the beneficial allele after a single hybridization event. We furthermore study the probability that slightly deleterious alleles hitchhike to fixation. The key to the analysis is a split of the process into a stochastic phase in which the advantageous alleles establishes and a deterministic phase in which it sweeps to fixation. We thereafter apply the theory to a set of biologically relevant scenarios such as introgression in the presence of many unlinked or few closely linked deleterious alleles. A comparison to computer simulations shows that the approximations work well over a large parameter range.
AU - Uecker, Hildegard
AU - Setter, Derek
AU - Hermisson, Joachim
ID - 1699
IS - 7
JF - Journal of Mathematical Biology
TI - Adaptive gene introgression after secondary contact
VL - 70
ER -
TY - JOUR
AB - We use the dual boson approach to reveal the phase diagram of the Fermi-Hubbard model with long-range dipole-dipole interactions. By using a large-scale finite-temperature calculation on a 64×64 square lattice we demonstrate the existence of a novel phase, possessing an "ultralong-range" order. The fingerprint of this phase - the density correlation function - features a nontrivial behavior on a scale of tens of lattice sites. We study the properties and the stability of the ultralong-range-ordered phase, and show that it is accessible in modern experiments with ultracold polar molecules and magnetic atoms.
AU - Van Loon, Erik
AU - Katsnelson, Mikhail
AU - Lemeshko, Mikhail
ID - 1700
IS - 8
JF - Physical Review B
TI - Ultralong-range order in the Fermi-Hubbard model with long-range interactions
VL - 92
ER -
TY - JOUR
AB - The activity of a neural network is defined by patterns of spiking and silence from the individual neurons. Because spikes are (relatively) sparse, patterns of activity with increasing numbers of spikes are less probable, but, with more spikes, the number of possible patterns increases. This tradeoff between probability and numerosity is mathematically equivalent to the relationship between entropy and energy in statistical physics. We construct this relationship for populations of up to N = 160 neurons in a small patch of the vertebrate retina, using a combination of direct and model-based analyses of experiments on the response of this network to naturalistic movies. We see signs of a thermodynamic limit, where the entropy per neuron approaches a smooth function of the energy per neuron as N increases. The form of this function corresponds to the distribution of activity being poised near an unusual kind of critical point. We suggest further tests of criticality, and give a brief discussion of its functional significance.
AU - Tkacik, Gasper
AU - Mora, Thierry
AU - Marre, Olivier
AU - Amodei, Dario
AU - Palmer, Stephanie
AU - Berry Ii, Michael
AU - Bialek, William
ID - 1701
IS - 37
JF - PNAS
TI - Thermodynamics and signatures of criticality in a network of neurons
VL - 112
ER -
TY - JOUR
AB - Given a convex function (Formula presented.) and two hermitian matrices A and B, Lewin and Sabin study in (Lett Math Phys 104:691–705, 2014) the relative entropy defined by (Formula presented.). Among other things, they prove that the so-defined quantity is monotone if and only if (Formula presented.) is operator monotone. The monotonicity is then used to properly define (Formula presented.) for bounded self-adjoint operators acting on an infinite-dimensional Hilbert space by a limiting procedure. More precisely, for an increasing sequence of finite-dimensional projections (Formula presented.) with (Formula presented.) strongly, the limit (Formula presented.) is shown to exist and to be independent of the sequence of projections (Formula presented.). The question whether this sequence converges to its "obvious" limit, namely (Formula presented.), has been left open. We answer this question in principle affirmatively and show that (Formula presented.). If the operators A and B are regular enough, that is (A − B), (Formula presented.) and (Formula presented.) are trace-class, the identity (Formula presented.) holds.
AU - Deuchert, Andreas
AU - Hainzl, Christian
AU - Seiringer, Robert
ID - 1704
IS - 10
JF - Letters in Mathematical Physics
TI - Note on a family of monotone quantum relative entropies
VL - 105
ER -
TY - CONF
AB - We consider a problem of learning kernels for use in SVM classification in the multi-task and lifelong scenarios and provide generalization bounds on the error of a large margin classifier. Our results show that, under mild conditions on the family of kernels used for learning, solving several related tasks simultaneously is beneficial over single task learning. In particular, as the number of observed tasks grows, assuming that in the considered family of kernels there exists one that yields low approximation error on all tasks, the overhead associated with learning such a kernel vanishes and the complexity converges to that of learning when this good kernel is given to the learner.
AU - Pentina, Anastasia
AU - Ben David, Shai
ID - 1706
TI - Multi-task and lifelong learning of kernels
VL - 9355
ER -
TY - JOUR
AB - The competition for resources among cells, individuals or species is a fundamental characteristic of evolution. Biological all-pay auctions have been used to model situations where multiple individuals compete for a single resource. However, in many situations multiple resources with various values exist and single reward auctions are not applicable. We generalize the model to multiple rewards and study the evolution of strategies. In biological all-pay auctions the bid of an individual corresponds to its strategy and is equivalent to its payment in the auction. The decreasingly ordered rewards are distributed according to the decreasingly ordered bids of the participating individuals. The reproductive success of an individual is proportional to its fitness given by the sum of the rewards won minus its payments. Hence, successful bidding strategies spread in the population. We find that the results for the multiple reward case are very different from the single reward case. While the mixed strategy equilibrium in the single reward case with more than two players consists of mostly low-bidding individuals, we show that the equilibrium can convert to many high-bidding individuals and a few low-bidding individuals in the multiple reward case. Some reward values lead to a specialization among the individuals where one subpopulation competes for the rewards and the other subpopulation largely avoids costly competitions. Whether the mixed strategy equilibrium is an evolutionarily stable strategy (ESS) depends on the specific values of the rewards.
AU - Reiter, Johannes
AU - Kanodia, Ayush
AU - Gupta, Raghav
AU - Nowak, Martin
AU - Chatterjee, Krishnendu
ID - 1709
IS - 1812
JF - Proceedings of the Royal Society of London Series B Biological Sciences
TI - Biological auctions with multiple rewards
VL - 282
ER -
TY - JOUR
AB - We consider the hollow on the half-plane {(x, y) : y ≤ 0} ⊂ ℝ2 defined by a function u : (-1, 1) → ℝ, u(x) < 0, and a vertical flow of point particles incident on the hollow. It is assumed that u satisfies the so-called single impact condition (SIC): each incident particle is elastically reflected by graph(u) and goes away without hitting the graph of u anymore. We solve the problem: find the function u minimizing the force of resistance created by the flow. We show that the graph of the minimizer is formed by two arcs of parabolas symmetric to each other with respect to the y-axis. Assuming that the resistance of u ≡ 0 equals 1, we show that the minimal resistance equals π/2 - 2arctan(1/2) ≈ 0.6435. This result completes the previously obtained result [SIAM J. Math. Anal., 46 (2014), pp. 2730-2742] stating in particular that the minimal resistance of a hollow in higher dimensions equals 0.5. We additionally consider a similar problem of minimal resistance, where the hollow in the half-space {(x1,...,xd,y) : y ≤ 0} ⊂ ℝd+1 is defined by a radial function U satisfying the SIC, U(x) = u(|x|), with x = (x1,...,xd), u(ξ) < 0 for 0 ≤ ξ < 1, and u(ξ) = 0 for ξ ≥ 1, and the flow is parallel to the y-axis. The minimal resistance is greater than 0.5 (and coincides with 0.6435 when d = 1) and converges to 0.5 as d → ∞.
AU - Akopyan, Arseniy
AU - Plakhov, Alexander
ID - 1710
IS - 4
JF - Society for Industrial and Applied Mathematics
TI - Minimal resistance of curves under the single impact assumption
VL - 47
ER -
TY - JOUR
AB - The majority of immune cells in Drosophila melanogaster are plasmatocytes; they carry out similar functions to vertebrate macrophages, influencing development as well as protecting against infection and cancer. Plasmatocytes, sometimes referred to with the broader term of hemocytes, migrate widely during embryonic development and cycle in the larvae between sessile and circulating positions. Here we discuss the similarities of plasmatocyte developmental migration and its functions to that of vertebrate macrophages, considering the recent controversy regarding the functions of Drosophila PDGF/VEGF related ligands. We also examine recent findings on the significance of adhesion for plasmatocyte migration in the embryo, as well as proliferation, trans-differentiation, and tumor responses in the larva. We spotlight parallels throughout to vertebrate immune responses.
AU - Ratheesh, Aparna
AU - Belyaeva, Vera
AU - Siekhaus, Daria E
ID - 1712
IS - 10
JF - Current Opinion in Cell Biology
TI - Drosophila immune cell migration and adhesion during embryonic development and larval immune responses
VL - 36
ER -
TY - JOUR
AB - How much cutting is needed to simplify the topology of a surface? We provide bounds for several instances of this question, for the minimum length of topologically non-trivial closed curves, pants decompositions, and cut graphs with a given combinatorial map in triangulated combinatorial surfaces (or their dual cross-metric counterpart). Our work builds upon Riemannian systolic inequalities, which bound the minimum length of non-trivial closed curves in terms of the genus and the area of the surface. We first describe a systematic way to translate Riemannian systolic inequalities to a discrete setting, and vice-versa. This implies a conjecture by Przytycka and Przytycki (Graph structure theory. Contemporary Mathematics, vol. 147, 1993), a number of new systolic inequalities in the discrete setting, and the fact that a theorem of Hutchinson on the edge-width of triangulated surfaces and Gromov’s systolic inequality for surfaces are essentially equivalent. We also discuss how these proofs generalize to higher dimensions. Then we focus on topological decompositions of surfaces. Relying on ideas of Buser, we prove the existence of pants decompositions of length O(g^(3/2)n^(1/2)) for any triangulated combinatorial surface of genus g with n triangles, and describe an O(gn)-time algorithm to compute such a decomposition. Finally, we consider the problem of embedding a cut graph (or more generally a cellular graph) with a given combinatorial map on a given surface. Using random triangulations, we prove (essentially) that, for any choice of a combinatorial map, there are some surfaces on which any cellular embedding with that combinatorial map has length superlinear in the number of triangles of the triangulated combinatorial surface. There is also a similar result for graphs embedded on polyhedral triangulations.
AU - Colin De Verdière, Éric
AU - Hubard, Alfredo
AU - De Mesmay, Arnaud N
ID - 1730
IS - 3
JF - Discrete & Computational Geometry
TI - Discrete systolic inequalities and decompositions of triangulated surfaces
VL - 53
ER -
TY - JOUR
AB - We consider two-player zero-sum games on graphs. These games can be classified on the basis of the information of the players and on the mode of interaction between them. On the basis of information the classification is as follows: (a) partial-observation (both players have partial view of the game); (b) one-sided complete-observation (one player has complete observation); and (c) complete-observation (both players have complete view of the game). On the basis of mode of interaction we have the following classification: (a) concurrent (both players interact simultaneously); and (b) turn-based (both players interact in turn). The two sources of randomness in these games are randomness in transition function and randomness in strategies. In general, randomized strategies are more powerful than deterministic strategies, and randomness in transitions gives more general classes of games. In this work we present a complete characterization for the classes of games where randomness is not helpful in: (a) the transition function probabilistic transition can be simulated by deterministic transition); and (b) strategies (pure strategies are as powerful as randomized strategies). As consequence of our characterization we obtain new undecidability results for these games.
AU - Chatterjee, Krishnendu
AU - Doyen, Laurent
AU - Gimbert, Hugo
AU - Henzinger, Thomas A
ID - 1731
IS - 12
JF - Information and Computation
TI - Randomness for free
VL - 245
ER -
TY - CONF
AB - We consider partially observable Markov decision processes (POMDPs), that are a standard framework for robotics applications to model uncertainties present in the real world, with temporal logic specifications. All temporal logic specifications in linear-time temporal logic (LTL) can be expressed as parity objectives. We study the qualitative analysis problem for POMDPs with parity objectives that asks whether there is a controller (policy) to ensure that the objective holds with probability 1 (almost-surely). While the qualitative analysis of POMDPs with parity objectives is undecidable, recent results show that when restricted to finite-memory policies the problem is EXPTIME-complete. While the problem is intractable in theory, we present a practical approach to solve the qualitative analysis problem. We designed several heuristics to deal with the exponential complexity, and have used our implementation on a number of well-known POMDP examples for robotics applications. Our results provide the first practical approach to solve the qualitative analysis of robot motion planning with LTL properties in the presence of uncertainty.
AU - Chatterjee, Krishnendu
AU - Chmelik, Martin
AU - Gupta, Raghav
AU - Kanodia, Ayush
ID - 1732
TI - Qualitative analysis of POMDPs with temporal logic specifications for robotics applications
ER -
TY - JOUR
AB - This work presents a method for efficiently simplifying the pressure projection step in a liquid simulation. We first devise a straightforward dimension reduction technique that dramatically reduces the cost of solving the pressure projection. Next, we introduce a novel change of basis that satisfies free-surface boundary conditions exactly, regardless of the accuracy of the pressure solve. When combined, these ideas greatly reduce the computational complexity of the pressure solve without compromising free surface boundary conditions at the highest level of detail. Our techniques are easy to parallelize, and they effectively eliminate the computational bottleneck for large liquid simulations.
AU - Ando, Ryoichi
AU - Thürey, Nils
AU - Wojtan, Christopher J
ID - 1735
IS - 2
JF - Computer Graphics Forum
TI - A dimension-reduced pressure solver for liquid simulations
VL - 34
ER -
TY - JOUR
AB - Intellectual disability (ID) has an estimated prevalence of 2-3%. Due to its extreme heterogeneity, the genetic basis of ID remains elusive in many cases. Recently, whole exome sequencing (WES) studies revealed that a large proportion of sporadic cases are caused by de novo gene variants. To identify further genes involved in ID, we performed WES in 250 patients with unexplained ID and their unaffected parents and included exomes of 51 previously sequenced child-parents trios in the analysis. Exome analysis revealed de novo intragenic variants in SET domain-containing 5 (SETD5) in two patients. One patient carried a nonsense variant, and the other an 81 bp deletion located across a splice-donor site. Chromosomal microarray diagnostics further identified four de novo non-recurrent microdeletions encompassing SETD5. CRISPR/Cas9 mutation modelling of the two intragenic variants demonstrated nonsense-mediated decay of the resulting transcripts, pointing to a loss-of-function (LoF) and haploinsufficiency as the common disease-causing mechanism of intragenic SETD5 sequence variants and SETD5-containing microdeletions. In silico domain prediction of SETD5, a predicted SET domain-containing histone methyltransferase (HMT), substantiated the presence of a SET domain and identified a novel putative PHD domain, strengthening a functional link to well-known histone-modifying ID genes. All six patients presented with ID and certain facial dysmorphisms, suggesting that SETD5 sequence variants contribute substantially to the microdeletion 3p25.3 phenotype. The present report of two SETD5 LoF variants in 301 patients demonstrates a prevalence of 0.7% and thus SETD5 variants as a relatively frequent cause of ID.
AU - Kuechler, Alma
AU - Zink, Alexander
AU - Wieland, Thomas
AU - Lüdecke, Hermann
AU - Cremer, Kirsten
AU - Salviati, Leonardo
AU - Magini, Pamela
AU - Najafi, Kimia
AU - Zweier, Christiane
AU - Czeschik, Johanna
AU - Aretz, Stefan
AU - Endele, Sabine
AU - Tamburrino, Federica
AU - Pinato, Claudia
AU - Clementi, Maurizio
AU - Gundlach, Jasmin
AU - Maylahn, Carina
AU - Mazzanti, Laura
AU - Wohlleber, Eva
AU - Schwarzmayr, Thomas
AU - Kariminejad, Roxana
AU - Schlessinger, Avner
AU - Wieczorek, Dagmar
AU - Strom, Tim
AU - Novarino, Gaia
AU - Engels, Hartmut
ID - 1789
IS - 6
JF - European Journal of Human Genetics
TI - Loss-of-function variants of SETD5 cause intellectual disability and the core phenotype of microdeletion 3p25.3 syndrome
VL - 23
ER -
TY - JOUR
AB - It is known that in classical fluids turbulence typically occurs at high Reynolds numbers. But can turbulence occur at low Reynolds numbers? Here we investigate the transition to turbulence in the classic Taylor-Couette system in which the rotating fluids are manufactured ferrofluids with magnetized nanoparticles embedded in liquid carriers. We find that, in the presence of a magnetic field transverse to the symmetry axis of the system, turbulence can occur at Reynolds numbers that are at least one order of magnitude smaller than those in conventional fluids. This is established by extensive computational ferrohydrodynamics through a detailed investigation of transitions in the flow structure, and characterization of behaviors of physical quantities such as the energy, the wave number, and the angular momentum through the bifurcations. A finding is that, as the magnetic field is increased, onset of turbulence can be determined accurately and reliably. Our results imply that experimental investigation of turbulence may be feasible by using ferrofluids. Our study of transition to and evolution of turbulence in the Taylor-Couette ferrofluidic flow system provides insights into the challenging problem of turbulence control.
AU - Altmeyer, Sebastian
AU - Do, Younghae
AU - Lai, Ying
ID - 1804
JF - Scientific Reports
TI - Transition to turbulence in Taylor-Couette ferrofluidic flow
VL - 5
ER -
TY - JOUR
AB - We study a double Cahn-Hilliard type functional related to the Gross-Pitaevskii energy of two-components Bose-Einstein condensates. In the case of large but same order intercomponent and intracomponent coupling strengths, we prove Γ-convergence to a perimeter minimisation functional with an inhomogeneous surface tension. We study the asymptotic behavior of the surface tension as the ratio between the intercomponent and intracomponent coupling strengths becomes very small or very large and obtain good agreement with the physical literature. We obtain as a consequence, symmetry breaking of the minimisers for the harmonic potential.
AU - Goldman, Michael
AU - Royo-Letelier, Jimena
ID - 1807
IS - 3
JF - ESAIM - Control, Optimisation and Calculus of Variations
TI - Sharp interface limit for two components Bose-Einstein condensates
VL - 21
ER -
TY - JOUR
AB - Combining antibiotics is a promising strategy for increasing treatment efficacy and for controlling resistance evolution. When drugs are combined, their effects on cells may be amplified or weakened, that is the drugs may show synergistic or antagonistic interactions. Recent work revealed the underlying mechanisms of such drug interactions by elucidating the drugs'; joint effects on cell physiology. Moreover, new treatment strategies that use drug combinations to exploit evolutionary tradeoffs were shown to affect the rate of resistance evolution in predictable ways. High throughput studies have further identified drug candidates based on their interactions with established antibiotics and general principles that enable the prediction of drug interactions were suggested. Overall, the conceptual and technical foundation for the rational design of potent drug combinations is rapidly developing.
AU - Bollenbach, Mark Tobias
ID - 1810
JF - Current Opinion in Microbiology
TI - Antimicrobial interactions: Mechanisms and implications for drug discovery and resistance evolution
VL - 27
ER -
TY - JOUR
AB - Atomic form factors are widely used for the characterization of targets and specimens, from crystallography to biology. By using recent mathematical results, here we derive an analytical expression for the atomic form factor within the independent particle model constructed from nonrelativistic screened hydrogenic wave functions. The range of validity of this analytical expression is checked by comparing the analytically obtained form factors with the ones obtained within the Hartee-Fock method. As an example, we apply our analytical expression for the atomic form factor to evaluate the differential cross section for Rayleigh scattering off neutral atoms.
AU - Safari, Laleh
AU - Santos, José
AU - Amaro, Pedro
AU - Jänkälä, Kari
AU - Fratini, Filippo
ID - 1811
IS - 5
JF - Journal of Mathematical Physics
TI - Analytical evaluation of atomic form factors: Application to Rayleigh scattering
VL - 56
ER -