TY - JOUR
AB - Actin filaments polymerizing against membranes power endocytosis, vesicular traffic, and cell motility. In vitro reconstitution studies suggest that the structure and the dynamics of actin networks respond to mechanical forces. We demonstrate that lamellipodial actin of migrating cells responds to mechanical load when membrane tension is modulated. In a steady state, migrating cell filaments assume the canonical dendritic geometry, defined by Arp2/3-generated 70° branch points. Increased tension triggers a dense network with a broadened range of angles, whereas decreased tension causes a shift to a sparse configuration dominated by filaments growing perpendicularly to the plasma membrane. We show that these responses emerge from the geometry of branched actin: when load per filament decreases, elongation speed increases and perpendicular filaments gradually outcompete others because they polymerize the shortest distance to the membrane, where they are protected from capping. This network-intrinsic geometrical adaptation mechanism tunes protrusive force in response to mechanical load.
AU - Mueller, Jan
AU - Szep, Gregory
AU - Nemethova, Maria
AU - De Vries, Ingrid
AU - Lieber, Arnon
AU - Winkler, Christoph
AU - Kruse, Karsten
AU - Small, John
AU - Schmeiser, Christian
AU - Keren, Kinneret
AU - Hauschild, Robert
AU - Sixt, Michael K
ID - 727
IS - 1
JF - Cell
SN - 00928674
TI - Load adaptation of lamellipodial actin networks
VL - 171
ER -
TY - JOUR
AB - During animal development, cell-fate-specific changes in gene expression can modify the material properties of a tissue and drive tissue morphogenesis. While mechanistic insights into the genetic control of tissue-shaping events are beginning to emerge, how tissue morphogenesis and mechanics can reciprocally impact cell-fate specification remains relatively unexplored. Here we review recent findings reporting how multicellular morphogenetic events and their underlying mechanical forces can feed back into gene regulatory pathways to specify cell fate. We further discuss emerging techniques that allow for the direct measurement and manipulation of mechanical signals in vivo, offering unprecedented access to study mechanotransduction during development. Examination of the mechanical control of cell fate during tissue morphogenesis will pave the way to an integrated understanding of the design principles that underlie robust tissue patterning in embryonic development.
AU - Chan, Chii
AU - Heisenberg, Carl-Philipp J
AU - Hiiragi, Takashi
ID - 728
IS - 18
JF - Current Biology
SN - 09609822
TI - Coordination of morphogenesis and cell fate specification in development
VL - 27
ER -
TY - JOUR
AB - The cellular mechanisms allowing tissues to efficiently regenerate are not fully understood. In this issue of Developmental Cell, Cao et al. (2017)) discover that during zebrafish heart regeneration, epicardial cells at the leading edge of regenerating tissue undergo endoreplication, possibly due to increased tissue tension, thereby boosting their regenerative capacity.
AU - Spiro, Zoltan P
AU - Heisenberg, Carl-Philipp J
ID - 729
IS - 6
JF - Developmental Cell
SN - 15345807
TI - Regeneration tensed up polyploidy takes the lead
VL - 42
ER -
TY - JOUR
AB - Neural responses are highly structured, with population activity restricted to a small subset of the astronomical range of possible activity patterns. Characterizing these statistical regularities is important for understanding circuit computation, but challenging in practice. Here we review recent approaches based on the maximum entropy principle used for quantifying collective behavior in neural activity. We highlight recent models that capture population-level statistics of neural data, yielding insights into the organization of the neural code and its biological substrate. Furthermore, the MaxEnt framework provides a general recipe for constructing surrogate ensembles that preserve aspects of the data, but are otherwise maximally unstructured. This idea can be used to generate a hierarchy of controls against which rigorous statistical tests are possible.
AU - Savin, Cristina
AU - Tkacik, Gasper
ID - 730
JF - Current Opinion in Neurobiology
SN - 09594388
TI - Maximum entropy models as a tool for building precise neural controls
VL - 46
ER -
TY - JOUR
AB - Genetic variations in the oxytocin receptor gene affect patients with ASD and ADHD differently.
AU - Novarino, Gaia
ID - 731
IS - 411
JF - Science Translational Medicine
SN - 19466234
TI - The science of love in ASD and ADHD
VL - 9
ER -
TY - JOUR
AB - Background: Social insects form densely crowded societies in environments with high pathogen loads, but have evolved collective defences that mitigate the impact of disease. However, colony-founding queens lack this protection and suffer high rates of mortality. The impact of pathogens may be exacerbated in species where queens found colonies together, as healthy individuals may contract pathogens from infectious co-founders. Therefore, we tested whether ant queens avoid founding colonies with pathogen-exposed conspecifics and how they might limit disease transmission from infectious individuals. Results: Using Lasius Niger queens and a naturally infecting fungal pathogen Metarhizium brunneum, we observed that queens were equally likely to found colonies with another pathogen-exposed or sham-treated queen. However, when one queen died, the surviving individual performed biting, burial and removal of the corpse. These undertaking behaviours were performed prophylactically, i.e. targeted equally towards non-infected and infected corpses, as well as carried out before infected corpses became infectious. Biting and burial reduced the risk of the queens contracting and dying from disease from an infectious corpse of a dead co-foundress. Conclusions: We show that co-founding ant queens express undertaking behaviours that, in mature colonies, are performed exclusively by workers. Such infection avoidance behaviours act before the queens can contract the disease and will therefore improve the overall chance of colony founding success in ant queens.
AU - Pull, Christopher
AU - Cremer, Sylvia
ID - 732
IS - 1
JF - BMC Evolutionary Biology
SN - 14712148
TI - Co-founding ant queens prevent disease by performing prophylactic undertaking behaviour
VL - 17
ER -
TY - JOUR
AB - Let A and B be two N by N deterministic Hermitian matrices and let U be an N by N Haar distributed unitary matrix. It is well known that the spectral distribution of the sum H = A + UBU∗ converges weakly to the free additive convolution of the spectral distributions of A and B, as N tends to infinity. We establish the optimal convergence rate in the bulk of the spectrum.
AU - Bao, Zhigang
AU - Erdös, László
AU - Schnelli, Kevin
ID - 733
JF - Advances in Mathematics
TI - Convergence rate for spectral distribution of addition of random matrices
VL - 319
ER -
TY - JOUR
AB - Social insect societies are long-standing models for understanding social behaviour and evolution. Unlike other advanced biological societies (such as the multicellular body), the component parts of social insect societies can be easily deconstructed and manipulated. Recent methodological and theoretical innovations have exploited this trait to address an expanded range of biological questions. We illustrate the broadening range of biological insight coming from social insect biology with four examples. These new frontiers promote open-minded, interdisciplinary exploration of one of the richest and most complex of biological phenomena: sociality.
AU - Kennedy, Patrick
AU - Baron, Gemma
AU - Qiu, Bitao
AU - Freitak, Dalial
AU - Helantera, Heikki
AU - Hunt, Edmund
AU - Manfredini, Fabio
AU - O'Shea Wheller, Thomas
AU - Patalano, Solenn
AU - Pull, Christopher
AU - Sasaki, Takao
AU - Taylor, Daisy
AU - Wyatt, Christopher
AU - Sumner, Seirian
ID - 734
IS - 11
JF - Trends in Ecology and Evolution
SN - 01695347
TI - Deconstructing superorganisms and societies to address big questions in biology
VL - 32
ER -
TY - JOUR
AB - The neurotransmitter receptor subtype, number, density, and distribution relative to the location of transmitter release sites are key determinants of signal transmission. AMPA-type ionotropic glutamate receptors (AMPARs) containing GluA3 and GluA4 subunits are prominently expressed in subsets of neurons capable of firing action potentials at high frequencies, such as auditory relay neurons. The auditory nerve (AN) forms glutamatergic synapses on two types of relay neurons, bushy cells (BCs) and fusiform cells (FCs) of the cochlear nucleus. AN-BC and AN-FC synapses have distinct kinetics; thus, we investigated whether the number, density, and localization of GluA3 and GluA4 subunits in these synapses are differentially organized using quantitative freeze-fracture replica immunogold labeling. We identify a positive correlation between the number of AMPARs and the size of AN-BC and AN-FC synapses. Both types of AN synapses have similar numbers of AMPARs; however, the AN-BC have a higher density of AMPARs than AN-FC synapses, because the AN-BC synapses are smaller. A higher number and density of GluA3 subunits are observed at AN-BC synapses, whereas a higher number and density of GluA4 subunits are observed at AN-FC synapses. The intrasynaptic distribution of immunogold labeling revealed that AMPAR subunits, particularly GluA3, are concentrated at the center of the AN-BC synapses. The central distribution of AMPARs is absent in GluA3-knockout mice, and gold particles are evenly distributed along the postsynaptic density. GluA4 gold labeling was homogenously distributed along both synapse types. Thus, GluA3 and GluA4 subunits are distributed at AN synapses in a target-cell-dependent manner.
AU - Rubio, María
AU - Matsui, Ko
AU - Fukazawa, Yugo
AU - Kamasawa, Naomi
AU - Harada, Harumi
AU - Itakura, Makoto
AU - Molnár, Elek
AU - Abe, Manabu
AU - Sakimura, Kenji
AU - Shigemoto, Ryuichi
ID - 736
IS - 8
JF - Brain Structure and Function
SN - 18632653
TI - The number and distribution of AMPA receptor channels containing fast kinetic GluA3 and GluA4 subunits at auditory nerve synapses depend on the target cells
VL - 222
ER -
TY - JOUR
AB - Inflammation, which is a highly regulated host response against danger signals, may be harmful if it is excessive and deregulated. Ideally, anti-inflammatory therapy should autonomously commence as soon as possible after the onset of inflammation, should be controllable by a physician, and should not systemically block beneficial immune response in the long term. We describe a genetically encoded anti-inflammatory mammalian cell device based on a modular engineered genetic circuit comprising a sensor, an amplifier, a “thresholder” to restrict activation of a positive-feedback loop, a combination of advanced clinically used biopharmaceutical proteins, and orthogonal regulatory elements that linked modules into the functional device. This genetic circuit was autonomously activated by inflammatory signals, including endogenous cecal ligation and puncture (CLP)-induced inflammation in mice and serum from a systemic juvenile idiopathic arthritis (sIJA) patient, and could be reset externally by a chemical signal. The microencapsulated anti-inflammatory device significantly reduced the pathology in dextran sodium sulfate (DSS)-induced acute murine colitis, demonstrating a synthetic immunological approach for autonomous anti-inflammatory therapy.
AU - Smole, Anže
AU - Lainšček, Duško
AU - Bezeljak, Urban
AU - Horvat, Simon
AU - Jerala, Roman
ID - 7360
IS - 1
JF - Molecular Therapy
SN - 1525-0016
TI - A synthetic mammalian therapeutic gene circuit for sensing and suppressing inflammation
VL - 25
ER -
TY - JOUR
AB - We generalize Brazas’ topology on the fundamental group to the whole universal path space X˜ i.e., to the set of homotopy classes of all based paths. We develop basic properties of the new notion and provide a complete comparison of the obtained topology with the established topologies, in particular with the Lasso topology and the CO topology, i.e., the topology that is induced by the compact-open topology. It turns out that the new topology is the finest topology contained in the CO topology, for which the action of the fundamental group on the universal path space is a continuous group action.
AU - Virk, Ziga
AU - Zastrow, Andreas
ID - 737
JF - Topology and its Applications
SN - 01668641
TI - A new topology on the universal path space
VL - 231
ER -
TY - JOUR
AB - We study the norm approximation to the Schrödinger dynamics of N bosons in with an interaction potential of the form . Assuming that in the initial state the particles outside of the condensate form a quasi-free state with finite kinetic energy, we show that in the large N limit, the fluctuations around the condensate can be effectively described using Bogoliubov approximation for all . The range of β is expected to be optimal for this large class of initial states.
AU - Nam, Phan
AU - Napiórkowski, Marcin M
ID - 739
IS - 5
JF - Journal de Mathématiques Pures et Appliquées
SN - 00217824
TI - A note on the validity of Bogoliubov correction to mean field dynamics
VL - 108
ER -
TY - JOUR
AB - Developments in bioengineering and molecular biology have introduced a palette of genetically encoded probes for identification of specific cell populations in electron microscopy. These probes can be targeted to distinct cellular compartments, rendering them electron dense through a subsequent chemical reaction. These electron densities strongly increase the local contrast in samples prepared for electron microscopy, allowing three major advances in ultrastructural mapping of circuits: genetic identification of circuit components, targeted imaging of regions of interest and automated analysis of the tagged circuits. Together, the gains from these advances can decrease the time required for the analysis of targeted circuit motifs by over two orders of magnitude. These genetic encoded tags for electron microscopy promise to simplify the analysis of circuit motifs and become a central tool for structure‐function studies of synaptic connections in the brain. We review the current state‐of‐the‐art with an emphasis on connectomics, the quantitative analysis of neuronal structures and motifs.
AU - Shigemoto, Ryuichi
AU - Jösch, Maximilian A
ID - 740
IS - 6
JF - WIREs Developmental Biology
SN - 17597684
TI - The genetic encoded toolbox for electron microscopy and connectomics
VL - 6
ER -
TY - JOUR
AB - We prove that a system of N fermions interacting with an additional particle via point interactions is stable if the ratio of the mass of the additional particle to the one of the fermions is larger than some critical m*. The value of m* is independent of N and turns out to be less than 1. This fact has important implications for the stability of the unitary Fermi gas. We also characterize the domain of the Hamiltonian of this model, and establish the validity of the Tan relations for all wave functions in the domain.
AU - Moser, Thomas
AU - Seiringer, Robert
ID - 741
IS - 1
JF - Communications in Mathematical Physics
SN - 00103616
TI - Stability of a fermionic N+1 particle system with point interactions
VL - 356
ER -
TY - JOUR
AB - This special issue of the Journal on Formal Methods in System Design is dedicated to Prof. Helmut Veith, who unexpectedly passed away in March 2016. Helmut Veith was a brilliant researcher, inspiring collaborator, passionate mentor, generous friend, and valued member of the formal methods community. Helmut was not only known for his numerous and influential contributions in the field of automated verification (most prominently his work on Counterexample-Guided Abstraction Refinement [1,2]), but also for his untiring and passionate efforts for the logic community: he co-organized the Vienna Summer of Logic (an event comprising twelve conferences and numerous workshops which attracted thousands of researchers from all over the world), he initiated the Vienna Center for Logic and Algorithms (which promotes international collaboration on logic and algorithms and organizes outreach events such as the LogicLounge), and he coordinated the Doctoral Program on Logical Methods in Computer Science at TU Wien (currently educating more than 40 doctoral students) and a National Research Network on Rigorous Systems Engineering (uniting fifteen researchers in Austria to address the challenge of building reliable and safe computer
systems). With his enthusiasm and commitment, Helmut completely reshaped the Austrian research landscape in the field of logic and verification in his few years as a full professor at TU Wien.
AU - Gottlob, Georg
AU - Henzinger, Thomas A
AU - Weißenbacher, Georg
ID - 743
IS - 2
JF - Formal Methods in System Design
TI - Preface of the special issue in memoriam Helmut Veith
VL - 51
ER -
TY - JOUR
AB - In evolutionary game theory interactions between individuals are often assumed obligatory. However, in many real-life situations, individuals can decide to opt out of an interaction depending on the information they have about the opponent. We consider a simple evolutionary game theoretic model to study such a scenario, where at each encounter between two individuals the type of the opponent (cooperator/defector) is known with some probability, and where each individual either accepts or opts out of the interaction. If the type of the opponent is unknown, a trustful individual accepts the interaction, whereas a suspicious individual opts out of the interaction. If either of the two individuals opt out both individuals remain without an interaction. We show that in the prisoners dilemma optional interactions along with suspicious behaviour facilitates the emergence of trustful cooperation.
AU - Priklopil, Tadeas
AU - Chatterjee, Krishnendu
AU - Nowak, Martin
ID - 744
JF - Journal of Theoretical Biology
SN - 00225193
TI - Optional interactions and suspicious behaviour facilitates trustful cooperation in prisoners dilemma
VL - 433
ER -
TY - JOUR
AB - Fluid flows in nature and applications are frequently subject to periodic velocity modulations. Surprisingly, even for the generic case of flow through a straight pipe, there is little consensus regarding the influence of pulsation on the transition threshold to turbulence: while most studies predict a monotonically increasing threshold with pulsation frequency (i.e. Womersley number, ), others observe a decreasing threshold for identical parameters and only observe an increasing threshold at low . In the present study we apply recent advances in the understanding of transition in steady shear flows to pulsating pipe flow. For moderate pulsation amplitudes we find that the first instability encountered is subcritical (i.e. requiring finite amplitude disturbances) and gives rise to localized patches of turbulence ('puffs') analogous to steady pipe flow. By monitoring the impact of pulsation on the lifetime of turbulence we map the onset of turbulence in parameter space. Transition in pulsatile flow can be separated into three regimes. At small Womersley numbers the dynamics is dominated by the decay turbulence suffers during the slower part of the cycle and hence transition is delayed significantly. As shown in this regime thresholds closely agree with estimates based on a quasi-steady flow assumption only taking puff decay rates into account. The transition point predicted in the zero limit equals to the critical point for steady pipe flow offset by the oscillation Reynolds number (i.e. the dimensionless oscillation amplitude). In the high frequency limit on the other hand, puff lifetimes are identical to those in steady pipe flow and hence the transition threshold appears to be unaffected by flow pulsation. In the intermediate frequency regime the transition threshold sharply drops (with increasing ) from the decay dominated (quasi-steady) threshold to the steady pipe flow level.
AU - Xu, Duo
AU - Warnecke, Sascha
AU - Song, Baofang
AU - Ma, Xingyu
AU - Hof, Björn
ID - 745
JF - Journal of Fluid Mechanics
SN - 00221120
TI - Transition to turbulence in pulsating pipe flow
VL - 831
ER -
TY - JOUR
AB - Metabotropic glutamate receptor subtype 5 (mGluR5) is crucially implicated in the pathophysiology of Fragile X Syndrome (FXS); however, its dysfunction at the sub-cellular level, and related synaptic and cognitive phenotypes are unexplored. Here, we probed the consequences of mGluR5/Homer scaffold disruption for mGluR5 cell-surface mobility, synaptic N-methyl-D-Aspartate receptor (NMDAR) function, and behavioral phenotypes in the second-generation Fmr1 knockout (KO) mouse. Using single-molecule tracking, we found that mGluR5 was significantly more mobile at synapses in hippocampal Fmr1 KO neurons, causing an increased synaptic surface co-clustering of mGluR5 and NMDAR. This correlated with a reduced amplitude of synaptic NMDAR currents, a lack of their mGluR5-Activated long-Term depression, and NMDAR/hippocampus dependent cognitive deficits. These synaptic and behavioral phenomena were reversed by knocking down Homer1a in Fmr1 KO mice. Our study provides a mechanistic link between changes of mGluR5 dynamics and pathological phenotypes of FXS, unveiling novel targets for mGluR5-based therapeutics.
AU - Aloisi, Elisabetta
AU - Le Corf, Katy
AU - Dupuis, Julien
AU - Zhang, Pei
AU - Ginger, Melanie
AU - Labrousse, Virginie
AU - Spatuzza, Michela
AU - Georg Haberl, Matthias
AU - Costa, Lara
AU - Shigemoto, Ryuichi
AU - Tappe Theodor, Anke
AU - Drago, Fillippo
AU - Vincenzo Piazza, Pier
AU - Mulle, Christophe
AU - Groc, Laurent
AU - Ciranna, Lucia
AU - Catania, Maria
AU - Frick, Andreas
ID - 746
IS - 1
JF - Nature Communications
SN - 20411723
TI - Altered surface mGluR5 dynamics provoke synaptic NMDAR dysfunction and cognitive defects in Fmr1 knockout mice
VL - 8
ER -
TY - JOUR
AB - Bradykinin (BK), a component of the kallikrein-kininogen-kinin system exerts multiple effects via B1 and B2 receptor activation. In the cardiovascular system, bradykinin has cardioprotective and vasodilator properties. We investigated the effect of BK on cardiac-projecting neurons of nucleus ambiguus, a key site for the parasympathetic cardiac regulation. BK produced a dose-dependent increase in cytosolic Ca2+ concentration. Pretreatment with HOE140, a B2 receptor antagonist, but not with R715, a B1 receptor antagonist, abolished the response to BK. A selective B2 receptor agonist, but not a B1 receptor agonist, elicited an increase in cytosolic Ca2+ similarly to BK. Inhibition of N-type voltage-gated Ca2+ channels with ω-conotoxin GVIA had no effect on the Ca2+ signal produced by BK, while pretreatment with ω-conotoxin MVIIC, a blocker of P/Q-type of Ca2+ channels, significantly diminished the effect of BK. Pretreatment with xestospongin C and 2-aminoethoxydiphenyl borate, antagonists of inositol 1,4,5-trisphosphate receptors, abolished the response to BK. Inhibition of ryanodine receptors reduced the BK-induced Ca2+ increase, while disruption of lysosomal Ca2+ stores with bafilomycin A1 did not affect the response. BK produced a dose-dependent depolarization of nucleus ambiguus neurons, which was prevented by the B2 receptor antagonist. In vivo studies indicate that microinjection of BK into nucleus ambiguus elicited bradycardia in conscious rats via B2 receptors. In summary, in cardiac vagal neurons of nucleus ambiguus, BK activates B2 receptors promoting Ca2+ influx and Ca2+ release from endoplasmic reticulum, and membrane depolarization; these effects are translated in vivo by bradycardia.
AU - Brǎiloiu, Eugen
AU - Mcguire, Matthew
AU - Shuler, Shadaria
AU - Deliu, Elena
AU - Barr, Jeffrey
AU - Abood, Mary
AU - Brailoiu, Gabriela
ID - 747
JF - Neuroscience
SN - 03064522
TI - Modulation of cardiac vagal tone by bradykinin acting on nucleus ambiguus
VL - 365
ER -
TY - JOUR
AB - Synaptotagmin 7 (Syt7) is thought to be a Ca2+ sensor that mediates asynchronous transmitter release and facilitation at synapses. However, Syt7 is strongly expressed in fast-spiking, parvalbumin-expressing GABAergic interneurons, and the output synapses of these neurons produce only minimal asynchronous release and show depression rather than facilitation. To resolve this apparent contradiction, we examined the effects of genetic elimination of Syt7 on synaptic transmission at the GABAergic basket cell (BC)-Purkinje cell (PC) synapse in cerebellum. Our results indicate that at the BC-PC synapse, Syt7 contributes to asynchronous release, pool replenishment, and facilitation. In combination, these three effects ensure efficient transmitter release during high-frequency activity and guarantee frequency independence of inhibition. Our results identify a distinct function of Syt7: ensuring the efficiency of high-frequency inhibitory synaptic transmission
AU - Chen, Chong
AU - Satterfield, Rachel
AU - Young, Samuel
AU - Jonas, Peter M
ID - 749
IS - 8
JF - Cell Reports
SN - 22111247
TI - Triple function of Synaptotagmin 7 ensures efficiency of high-frequency transmission at central GABAergic synapses
VL - 21
ER -
TY - CONF
AB - Modern communication technologies allow first responders to contact thousands of potential volunteers simultaneously for support during a crisis or disaster event. However, such volunteer efforts must be well coordinated and monitored, in order to offer an effective relief to the professionals. In this paper we extend earlier work on optimally assigning volunteers to selected landmark locations. In particular, we emphasize the aspect that obtaining good assignments requires not only advanced computational tools, but also a realistic measure of distance between volunteers and landmarks. Specifically, we propose the use of the Open Street Map (OSM) driving distance instead of he previously used flight distance. We find the OSM driving distance to be better aligned with the interests of volunteers and first responders. Furthermore, we show that relying on the flying distance leads to a substantial underestimation of the number of required volunteers, causing negative side effects in case of an actual crisis situation.
AU - Pielorz, Jasmin
AU - Prandtstetter, Matthias
AU - Straub, Markus
AU - Lampert, Christoph
ID - 750
SN - 978-153862714-3
T2 - 2017 IEEE International Conference on Big Data
TI - Optimal geospatial volunteer allocation needs realistic distances
ER -
TY - JOUR
AB - The basement membrane (BM) is a thin layer of extracellular matrix (ECM) beneath nearly all epithelial cell types that is critical for cellular and tissue function. It is composed of numerous components conserved among all bilaterians [1]; however, it is unknown how all of these components are generated and subsequently constructed to form a fully mature BM in the living animal. Although BM formation is thought to simply involve a process of self-assembly [2], this concept suffers from a number of logistical issues when considering its construction in vivo. First, incorporation of BM components appears to be hierarchical [3-5], yet it is unclear whether their production during embryogenesis must also be regulated in a temporal fashion. Second, many BM proteins are produced not only by the cells residing on the BM but also by surrounding cell types [6-9], and it is unclear how large, possibly insoluble protein complexes [10] are delivered into the matrix. Here we exploit our ability to live image and genetically dissect de novo BM formation during Drosophila development. This reveals that there is a temporal hierarchy of BM protein production that is essential for proper component incorporation. Furthermore, we show that BM components require secretion by migrating macrophages (hemocytes) during their developmental dispersal, which is critical for embryogenesis. Indeed, hemocyte migration is essential to deliver a subset of ECM components evenly throughout the embryo. This reveals that de novo BM construction requires a combination of both production and distribution logistics allowing for the timely delivery of core components.
AU - Matsubayashi, Yutaka
AU - Louani, Adam
AU - Dragu, Anca
AU - Sanchez Sanchez, Besaiz
AU - Serna Morales, Eduardo
AU - Yolland, Lawrence
AU - György, Attila
AU - Vizcay, Gema
AU - Fleck, Roland
AU - Heddleston, John
AU - Chew, Teng
AU - Siekhaus, Daria E
AU - Stramer, Brian
ID - 751
IS - 22
JF - Current Biology
SN - 09609822
TI - A moving source of matrix components is essential for De Novo basement membrane formation
VL - 27
ER -
TY - JOUR
AB - Severe environmental change can drive a population extinct unless the population adapts in time to the new conditions (“evolutionary rescue”). How does biparental sexual reproduction influence the chances of population persistence compared to clonal reproduction or selfing? In this article, we set up a one‐locus two‐allele model for adaptation in diploid species, where rescue is contingent on the establishment of the mutant homozygote. Reproduction can occur by random mating, selfing, or clonally. Random mating generates and destroys the rescue mutant; selfing is efficient at generating it but at the same time depletes the heterozygote, which can lead to a low mutant frequency in the standing genetic variation. Due to these (and other) antagonistic effects, we find a nontrivial dependence of population survival on the rate of sex/selfing, which is strongly influenced by the dominance coefficient of the mutation before and after the environmental change. Importantly, since mating with the wild‐type breaks the mutant homozygote up, a slow decay of the wild‐type population size can impede rescue in randomly mating populations.
AU - Uecker, Hildegard
ID - 1063
IS - 4
JF - Evolution
SN - 00143820
TI - Evolutionary rescue in randomly mating, selfing, and clonal populations
VL - 71
ER -
TY - JOUR
AB - We consider the problem of reachability in pushdown graphs. We study the problem for pushdown graphs with constant treewidth. Even for pushdown graphs with treewidth 1, for the reachability problem we establish the following: (i) the problem is PTIME-complete, and (ii) any subcubic algorithm for the problem would contradict the k-clique conjecture and imply faster combinatorial algorithms for cliques in graphs.
AU - Chatterjee, Krishnendu
AU - Osang, Georg F
ID - 1065
JF - Information Processing Letters
SN - 00200190
TI - Pushdown reachability with constant treewidth
VL - 122
ER -
TY - JOUR
AB - Simulation is an attractive alternative to language inclusion for automata as it is an under-approximation of language inclusion, but usually has much lower complexity. Simulation has also been extended in two orthogonal directions, namely, (1) fair simulation, for simulation over specified set of infinite runs; and (2) quantitative simulation, for simulation between weighted automata. While fair trace inclusion is PSPACE-complete, fair simulation can be computed in polynomial time. For weighted automata, the (quantitative) language inclusion problem is undecidable in general, whereas the (quantitative) simulation reduces to quantitative games, which admit pseudo-polynomial time algorithms.
In this work, we study (quantitative) simulation for weighted automata with Büchi acceptance conditions, i.e., we generalize fair simulation from non-weighted automata to weighted automata. We show that imposing Büchi acceptance conditions on weighted automata changes many fundamental properties of the simulation games, yet they still admit pseudo-polynomial time algorithms.
AU - Chatterjee, Krishnendu
AU - Henzinger, Thomas A
AU - Otop, Jan
AU - Velner, Yaron
ID - 1066
IS - 2
JF - Information and Computation
TI - Quantitative fair simulation games
VL - 254
ER -
TY - JOUR
AB - Embryo morphogenesis relies on highly coordinated movements of different tissues. However, remarkably little is known about how tissues coordinate their movements to shape the embryo. In zebrafish embryogenesis, coordinated tissue movements first become apparent during “doming,” when the blastoderm begins to spread over the yolk sac, a process involving coordinated epithelial surface cell layer expansion and mesenchymal deep cell intercalations. Here, we find that active surface cell expansion represents the key process coordinating tissue movements during doming. By using a combination of theory and experiments, we show that epithelial surface cells not only trigger blastoderm expansion by reducing tissue surface tension, but also drive blastoderm thinning by inducing tissue contraction through radial deep cell intercalations. Thus, coordinated tissue expansion and thinning during doming relies on surface cells simultaneously controlling tissue surface tension and radial tissue contraction.
AU - Morita, Hitoshi
AU - Grigolon, Silvia
AU - Bock, Martin
AU - Krens, Gabriel
AU - Salbreux, Guillaume
AU - Heisenberg, Carl-Philipp J
ID - 1067
IS - 4
JF - Developmental Cell
SN - 15345807
TI - The physical basis of coordinated tissue spreading in zebrafish gastrulation
VL - 40
ER -
TY - JOUR
AB - Given a finite set of points in Rn and a radius parameter, we study the Čech, Delaunay–Čech, Delaunay (or alpha), and Wrap complexes in the light of generalized discrete Morse theory. Establishing the Čech and Delaunay complexes as sublevel sets of generalized discrete Morse functions, we prove that the four complexes are simple-homotopy equivalent by a sequence of simplicial collapses, which are explicitly described by a single discrete gradient field.
AU - Bauer, Ulrich
AU - Edelsbrunner, Herbert
ID - 1072
IS - 5
JF - Transactions of the American Mathematical Society
TI - The Morse theory of Čech and delaunay complexes
VL - 369
ER -
TY - JOUR
AB - Let X and Y be finite simplicial sets (e.g. finite simplicial complexes), both equipped with a free simplicial action of a finite group G. Assuming that Y is d-connected and dimX≤2d, for some d≥1, we provide an algorithm that computes the set of all equivariant homotopy classes of equivariant continuous maps |X|→|Y|; the existence of such a map can be decided even for dimX≤2d+1. This yields the first algorithm for deciding topological embeddability of a k-dimensional finite simplicial complex into Rn under the condition k≤23n−1. More generally, we present an algorithm that, given a lifting-extension problem satisfying an appropriate stability assumption, computes the set of all homotopy classes of solutions. This result is new even in the non-equivariant situation.
AU - Čadek, Martin
AU - Krcál, Marek
AU - Vokřínek, Lukáš
ID - 1073
IS - 4
JF - Discrete & Computational Geometry
SN - 01795376
TI - Algorithmic solvability of the lifting extension problem
VL - 54
ER -
TY - JOUR
AB - Recently it has become feasible to detect long blocks of nearly identical sequence shared between pairs of genomes. These IBD blocks are direct traces of recent coalescence events and, as such, contain ample signal to infer recent demography. Here, we examine sharing of such blocks in two-dimensional populations with local migration. Using a diffusion approximation to trace genetic ancestry, we derive analytical formulae for patterns of isolation by distance of IBD blocks, which can also incorporate recent population density changes. We introduce an inference scheme that uses a composite likelihood approach to fit these formulae. We then extensively evaluate our theory and inference method on a range of scenarios using simulated data. We first validate the diffusion approximation by showing that the theoretical results closely match the simulated block sharing patterns. We then demonstrate that our inference scheme can accurately and robustly infer dispersal rate and effective density, as well as bounds on recent dynamics of population density. To demonstrate an application, we use our estimation scheme to explore the fit of a diffusion model to Eastern European samples in the POPRES data set. We show that ancestry diffusing with a rate of σ ≈ 50–100 km/√gen during the last centuries, combined with accelerating population growth, can explain the observed exponential decay of block sharing with increasing pairwise sample distance.
AU - Ringbauer, Harald
AU - Coop, Graham
AU - Barton, Nicholas H
ID - 1074
IS - 3
JF - Genetics
SN - 00166731
TI - Inferring recent demography from isolation by distance of long shared sequence blocks
VL - 205
ER -
TY - JOUR
AB - Signatures of the Coulomb corrections in the photoelectron momentum distribution during laser-induced ionization of atoms or ions in tunneling and multiphoton regimes are investigated analytically in the case of a one-dimensional problem. A high-order Coulomb-corrected strong-field approximation is applied, where the exact continuum state in the S matrix is approximated by the eikonal Coulomb-Volkov state including the second-order corrections to the eikonal. Although without high-order corrections our theory coincides with the known analytical R-matrix (ARM) theory, we propose a simplified procedure for the matrix element derivation. Rather than matching the eikonal Coulomb-Volkov wave function with the bound state as in the ARM theory to remove the Coulomb singularity, we calculate the matrix element via the saddle-point integration method by time as well as by coordinate, and in this way avoiding the Coulomb singularity. The momentum shift in the photoelectron momentum distribution with respect to the ARM theory due to high-order corrections is analyzed for tunneling and multiphoton regimes. The relation of the quantum corrections to the tunneling delay time is discussed.
AU - Klaiber, Michael
AU - Daněk, Jiří
AU - Yakaboylu, Enderalp
AU - Hatsagortsyan, Karen
AU - Keitel, Christoph
ID - 1076
IS - 2
JF - Physical Review A - Atomic, Molecular, and Optical Physics
SN - 24699926
TI - Strong-field ionization via a high-order Coulomb-corrected strong-field approximation
VL - 95
ER -
TY - JOUR
AB - Viral capsids are structurally constrained by interactions among the amino acids (AAs) of their constituent proteins. Therefore, epistasis is expected to evolve among physically interacting sites and to influence the rates of substitution. To study the evolution of epistasis, we focused on the major structural protein of the fX174 phage family by first reconstructing the ancestral protein sequences of 18 species using a Bayesian statistical framework. The inferred ancestral reconstruction differed at eight AAs, for a total of 256 possible ancestral haplotypes. For each ancestral haplotype and the extant species, we estimated, in silico, the distribution of free energies and epistasis of the capsid structure. We found that free energy has not significantly increased but epistasis has. We decomposed epistasis up to fifth order and found that higher-order epistasis sometimes compensates pairwise interactions making the free energy seem additive. The dN/dS ratio is low, suggesting strong purifying selection, and that structure is under stabilizing selection. We synthesized phages carrying ancestral haplotypes of the coat protein gene and measured their fitness experimentally. Our findings indicate that stabilizing mutations can have higher fitness, and that fitness optima do not necessarily coincide with energy minima.
AU - Fernandes Redondo, Rodrigo A
AU - Vladar, Harold
AU - Włodarski, Tomasz
AU - Bollback, Jonathan P
ID - 1077
IS - 126
JF - Journal of the Royal Society Interface
SN - 17425689
TI - Evolutionary interplay between structure, energy and epistasis in the coat protein of the ϕX174 phage family
VL - 14
ER -
TY - JOUR
AB - One of the key questions in understanding plant development is how single cells behave in a larger context of the tissue. Therefore, it requires the observation of the whole organ with a high spatial- as well as temporal resolution over prolonged periods of time, which may cause photo-toxic effects. This protocol shows a plant sample preparation method for light-sheet microscopy, which is characterized by mounting the plant vertically on the surface of a gel. The plant is mounted in such a way that the roots are submerged in a liquid medium while the leaves remain in the air. In order to ensure photosynthetic activity of the plant, a custom-made lighting system illuminates the leaves. To keep the roots in darkness the water surface is covered with sheets of black plastic foil. This method allows long-term imaging of plant organ development in standardized conditions.
AU - Von Wangenheim, Daniel
AU - Hauschild, Robert
AU - Friml, Jirí
ID - 1078
IS - 119
JF - Journal of visualized experiments JoVE
TI - Light sheet fluorescence microscopy of plant roots growing on the surface of a gel
VL - 2017
ER -
TY - JOUR
AB - We study the ionization problem in the Thomas-Fermi-Dirac-von Weizsäcker theory for atoms and molecules. We prove the nonexistence of minimizers for the energy functional when the number of electrons is large and the total nuclear charge is small. This nonexistence result also applies to external potentials decaying faster than the Coulomb potential. In the case of arbitrary nuclear charges, we obtain the nonexistence of stable minimizers and radial minimizers.
AU - Nam, Phan
AU - Van Den Bosch, Hanne
ID - 1079
IS - 2
JF - Mathematical Physics, Analysis and Geometry
SN - 13850172
TI - Nonexistence in Thomas Fermi-Dirac-von Weizsäcker theory with small nuclear charges
VL - 20
ER -
TY - JOUR
AB - Reconstructing the evolutionary history of metastases is critical for understanding their basic biological principles and has profound clinical implications. Genome-wide sequencing data has enabled modern phylogenomic methods to accurately dissect subclones and their phylogenies from noisy and impure bulk tumour samples at unprecedented depth. However, existing methods are not designed to infer metastatic seeding patterns. Here we develop a tool, called Treeomics, to reconstruct the phylogeny of metastases and map subclones to their anatomic locations. Treeomics infers comprehensive seeding patterns for pancreatic, ovarian, and prostate cancers. Moreover, Treeomics correctly disambiguates true seeding patterns from sequencing artifacts; 7% of variants were misclassified by conventional statistical methods. These artifacts can skew phylogenies by creating illusory tumour heterogeneity among distinct samples. In silico benchmarking on simulated tumour phylogenies across a wide range of sample purities (15–95%) and sequencing depths (25-800 × ) demonstrates the accuracy of Treeomics compared with existing methods.
AU - Reiter, Johannes
AU - Makohon Moore, Alvin
AU - Gerold, Jeffrey
AU - Božić, Ivana
AU - Chatterjee, Krishnendu
AU - Iacobuzio Donahue, Christine
AU - Vogelstein, Bert
AU - Nowak, Martin
ID - 1080
JF - Nature Communications
SN - 20411723
TI - Reconstructing metastatic seeding patterns of human cancers
VL - 8
ER -
TY - JOUR
AB - BceRS and PsdRS are paralogous two-component systems in Bacillus subtilis controlling the response to antimicrobial peptides. In the presence of extracellular bacitracin and nisin, respectively, the two response regulators (RRs) bind their target promoters, PbceA or PpsdA, resulting in a strong up-regulation of target gene expression and ultimately antibiotic resistance. Despite high sequence similarity between the RRs BceR and PsdR and their known binding sites, no cross-regulation has been observed between them. We therefore investigated the specificity determinants of PbceA and PpsdA that ensure the insulation of these two paralogous pathways at the RR–promoter interface. In vivo and in vitro analyses demonstrate that the regulatory regions within these two promoters contain three important elements: in addition to the known (main) binding site, we identified a linker region and a secondary binding site that are crucial for functionality. Initial binding to the high-affinity, low-specificity main binding site is a prerequisite for the subsequent highly specific binding of a second RR dimer to the low-affinity secondary binding site. In addition to this hierarchical cooperative binding, discrimination requires a competition of the two RRs for their respective binding site mediated by only slight differences in binding affinities.
AU - Fang, Chong
AU - Nagy-Staron, Anna A
AU - Grafe, Martin
AU - Heermann, Ralf
AU - Jung, Kirsten
AU - Gebhard, Susanne
AU - Mascher, Thorsten
ID - 1084
IS - 1
JF - Molecular Microbiology
SN - 0950382X
TI - Insulation and wiring specificity of BceR like response regulators and their target promoters in Bacillus subtilis
VL - 104
ER -
TY - JOUR
AB - Sex chromosomes evolve once recombination is halted between a homologous pair of chromosomes. The dominant model of sex chromosome evolution posits that recombination is suppressed between emerging X and Y chromosomes in order to resolve sexual conflict. Here we test this model using whole genome and transcriptome resequencing data in the guppy, a model for sexual selection with many Y-linked colour traits. We show that although the nascent Y chromosome encompasses nearly half of the linkage group, there has been no perceptible degradation of Y chromosome gene content or activity. Using replicate wild populations with differing levels of sexually antagonistic selection for colour, we also show that sexual selection leads to greater expansion of the non-recombining region and increased Y chromosome divergence. These results provide empirical support for longstanding models of sex chromosome catalysis, and suggest an important role for sexual selection and sexual conflict in genome evolution.
AU - Wright, Alison
AU - Darolti, Iulia
AU - Bloch, Natasha
AU - Oostra, Vicencio
AU - Sandkam, Benjamin
AU - Buechel, Séverine
AU - Kolm, Niclas
AU - Breden, Felix
AU - Vicoso, Beatriz
AU - Mank, Judith
ID - 1085
JF - Nature Communications
SN - 20411723
TI - Convergent recombination suppression suggests role of sexual selection in guppy sex chromosome formation
VL - 8
ER -
TY - JOUR
AB - Using extensive direct numerical simulations, the dynamics of laminar-turbulent fronts in pipe flow is investigated for Reynolds numbers between and 5500. We here investigate the physical distinction between the fronts of weak and strong slugs both by analysing the turbulent kinetic energy budget and by comparing the downstream front motion to the advection speed of bulk turbulent structures. Our study shows that weak downstream fronts travel slower than turbulent structures in the bulk and correspond to decaying turbulence at the front. At the downstream front speed becomes faster than the advection speed, marking the onset of strong fronts. In contrast to weak fronts, turbulent eddies are generated at strong fronts by feeding on the downstream laminar flow. Our study also suggests that temporal fluctuations of production and dissipation at the downstream laminar-turbulent front drive the dynamical switches between the two types of front observed up to.
AU - Song, Baofang
AU - Barkley, Dwight
AU - Hof, Björn
AU - Avila, Marc
ID - 1087
JF - Journal of Fluid Mechanics
SN - 00221120
TI - Speed and structure of turbulent fronts in pipe flow
VL - 813
ER -
TY - JOUR
AB - We discuss properties of distributions that are multivariate totally positive of order two (MTP2) related to conditional independence. In particular, we show that any independence model generated by an MTP2 distribution is a compositional semigraphoid which is upward-stable and singleton-transitive. In addition, we prove that any MTP2 distribution satisfying an appropriate support condition is faithful to its concentration graph. Finally, we analyze factorization properties of MTP2 distributions and discuss ways of constructing MTP2 distributions; in particular we give conditions on the log-linear parameters of a discrete distribution which ensure MTP2 and characterize conditional Gaussian distributions which satisfy MTP2.
AU - Fallat, Shaun
AU - Lauritzen, Steffen
AU - Sadeghi, Kayvan
AU - Uhler, Caroline
AU - Wermuth, Nanny
AU - Zwiernik, Piotr
ID - 1089
IS - 3
JF - Annals of Statistics
SN - 00905364
TI - Total positivity in Markov structures
VL - 45
ER -
TY - JOUR
AB - In the early visual system, cells of the same type perform the same computation in different places of the visual field. How these cells code together a complex visual scene is unclear. A common assumption is that cells of a single-type extract a single-stimulus feature to form a feature map, but this has rarely been observed directly. Using large-scale recordings in the rat retina, we show that a homogeneous population of fast OFF ganglion cells simultaneously encodes two radically different features of a visual scene. Cells close to a moving object code quasilinearly for its position, while distant cells remain largely invariant to the object's position and, instead, respond nonlinearly to changes in the object's speed. We develop a quantitative model that accounts for this effect and identify a disinhibitory circuit that mediates it. Ganglion cells of a single type thus do not code for one, but two features simultaneously. This richer, flexible neural map might also be present in other sensory systems.
AU - Deny, Stephane
AU - Ferrari, Ulisse
AU - Mace, Emilie
AU - Yger, Pierre
AU - Caplette, Romain
AU - Picaud, Serge
AU - Tkacik, Gasper
AU - Marre, Olivier
ID - 1104
IS - 1
JF - Nature Communications
SN - 20411723
TI - Multiplexed computations in retinal ganglion cells of a single type
VL - 8
ER -
TY - CONF
AB - In this work we study the learnability of stochastic processes with respect to the conditional risk, i.e. the existence of a learning algorithm that improves its next-step performance with the amount of observed data. We introduce a notion of pairwise discrepancy between conditional distributions at different times steps and show how certain properties of these discrepancies can be used to construct a successful learning algorithm. Our main results are two theorems that establish criteria for learnability for many classes of stochastic processes, including all special cases studied previously in the literature.
AU - Zimin, Alexander
AU - Lampert, Christoph
ID - 1108
TI - Learning theory for conditional risk minimization
VL - 54
ER -
TY - JOUR
AB - Rotation of molecules embedded in He nanodroplets is explored by a combination of fs laser-induced alignment experiments and angulon quasiparticle theory. We demonstrate that at low fluence of the fs alignment pulse, the molecule and its solvation shell can be set into coherent collective rotation lasting long enough to form revivals. With increasing fluence, however, the revivals disappear -- instead, rotational dynamics as rapid as for an isolated molecule is observed during the first few picoseconds. Classical calculations trace this phenomenon to transient decoupling of the molecule from its He shell. Our results open novel opportunities for studying non-equilibrium solute-solvent dynamics and quantum thermalization.
AU - Shepperson, Benjamin
AU - Søndergaard, Anders
AU - Christiansen, Lars
AU - Kaczmarczyk, Jan
AU - Zillich, Robert
AU - Lemeshko, Mikhail
AU - Stapelfeldt, Henrik
ID - 1109
IS - 20
JF - Physical Review Letters
TI - Laser-induced rotation of iodine molecules in helium nanodroplets: Revivals and breaking-free
VL - 118
ER -
TY - JOUR
AB - The phytohormone auxin is a major determinant and regulatory component important for plant development. Auxin transport between cells is mediated by a complex system of transporters such as AUX1/LAX, PIN, and ABCB proteins, and their localization and activity is thought to be influenced by phosphatases and kinases. Flavonols have been shown to alter auxin transport activity and changes in flavonol accumulation in the Arabidopsis thaliana rol1-2 mutant cause defects in auxin transport and seedling development. A new mutation in ROOTS CURL IN NPA 1 (RCN1), encoding a regulatory subunit of the phosphatase PP2A, was found to suppress the growth defects of rol1-2 without changing the flavonol content. rol1-2 rcn1-3 double mutants show wild type-like auxin transport activity while levels of free auxin are not affected by rcn1-3. In the rol1-2 mutant, PIN2 shows a flavonol-induced basal-to-apical shift in polar localization which is reversed in the rol1-2 rcn1-3 to basal localization. In vivo analysis of PINOID action, a kinase known to influence PIN protein localization in a PP2A-antagonistic manner, revealed a negative impact of flavonols on PINOID activity. Together, these data suggest that flavonols affect auxin transport by modifying the antagonistic kinase/phosphatase equilibrium.
AU - Kuhn, Benjamin
AU - Nodzyński, Tomasz
AU - Errafi, Sanae
AU - Bucher, Rahel
AU - Gupta, Shibu
AU - Aryal, Bibek
AU - Dobrev, Petre
AU - Bigler, Laurent
AU - Geisler, Markus
AU - Zažímalová, Eva
AU - Friml, Jirí
AU - Ringli, Christoph
ID - 1110
JF - Scientific Reports
SN - 20452322
TI - Flavonol-induced changes in PIN2 polarity and auxin transport in the Arabidopsis thaliana rol1-2 mutant require phosphatase activity
VL - 7
ER -
TY - JOUR
AB - Adaptation depends critically on the effects of new mutations and their dependency on the genetic background in which they occur. These two factors can be summarized by the fitness landscape. However, it would require testing all mutations in all backgrounds, making the definition and analysis of fitness landscapes mostly inaccessible. Instead of postulating a particular fitness landscape, we address this problem by considering general classes of landscapes and calculating an upper limit for the time it takes for a population to reach a fitness peak, circumventing the need to have full knowledge about the fitness landscape. We analyze populations in the weak-mutation regime and characterize the conditions that enable them to quickly reach the fitness peak as a function of the number of sites under selection. We show that for additive landscapes there is a critical selection strength enabling populations to reach high-fitness genotypes, regardless of the distribution of effects. This threshold scales with the number of sites under selection, effectively setting a limit to adaptation, and results from the inevitable increase in deleterious mutational pressure as the population adapts in a space of discrete genotypes. Furthermore, we show that for the class of all unimodal landscapes this condition is sufficient but not necessary for rapid adaptation, as in some highly epistatic landscapes the critical strength does not depend on the number of sites under selection; effectively removing this barrier to adaptation.
AU - Heredia, Jorge
AU - Trubenova, Barbora
AU - Sudholt, Dirk
AU - Paixao, Tiago
ID - 1111
IS - 2
JF - Genetics
SN - 00166731
TI - Selection limits to adaptive walks on correlated landscapes
VL - 205
ER -
TY - CONF
AB - There has been renewed interest in modelling the behaviour of evolutionary algorithms by more traditional mathematical objects, such as ordinary differential equations or Markov chains. The advantage is that the analysis becomes greatly facilitated due to the existence of well established methods. However, this typically comes at the cost of disregarding information about the process. Here, we introduce the use of stochastic differential equations (SDEs) for the study of EAs. SDEs can produce simple analytical results for the dynamics of stochastic processes, unlike Markov chains which can produce rigorous but unwieldy expressions about the dynamics. On the other hand, unlike ordinary differential equations (ODEs), they do not discard information about the stochasticity of the process. We show that these are especially suitable for the analysis of fixed budget scenarios and present analogs of the additive and multiplicative drift theorems for SDEs. We exemplify the use of these methods for two model algorithms ((1+1) EA and RLS) on two canonical problems(OneMax and LeadingOnes).
AU - Paixao, Tiago
AU - Pérez Heredia, Jorge
ID - 1112
SN - 978-145034651-1
T2 - Proceedings of the 14th ACM/SIGEVO Conference on Foundations of Genetic Algorithms
TI - An application of stochastic differential equations to evolutionary algorithms
ER -
TY - JOUR
AB - A drawing of a graph G is radial if the vertices of G are placed on concentric circles C 1 , . . . , C k with common center c , and edges are drawn radially : every edge intersects every circle centered at c at most once. G is radial planar if it has a radial embedding, that is, a crossing-free radial drawing. If the vertices of G are ordered or partitioned into ordered levels (as they are for leveled graphs), we require that the assignment of vertices to circles corresponds to the given ordering or leveling. We show that a graph G is radial planar if G has a radial drawing in which every two edges cross an even number of times; the radial embedding has the same leveling as the radial drawing. In other words, we establish the weak variant of the Hanani-Tutte theorem for radial planarity. This generalizes a result by Pach and Toth.
AU - Fulek, Radoslav
AU - Pelsmajer, Michael
AU - Schaefer, Marcus
ID - 1113
IS - 1
JF - Journal of Graph Algorithms and Applications
TI - Hanani-Tutte for radial planarity
VL - 21
ER -
TY - JOUR
AB - Nonequilibrium phase transitions exist in damped-driven open quantum systems when the continuous tuning of an external parameter leads to a transition between two robust steady states. In second-order transitions this change is abrupt at a critical point, whereas in first-order transitions the two phases can coexist in a critical hysteresis domain. Here, we report the observation of a first-order dissipative quantum phase transition in a driven circuit quantum electrodynamics system. It takes place when the photon blockade of the driven cavity-atom system is broken by increasing the drive power. The observed experimental signature is a bimodal phase space distribution with varying weights controlled by the drive strength. Our measurements show an improved stabilization of the classical attractors up to the millisecond range when the size of the quantum system is increased from one to three artificial atoms. The formation of such robust pointer states could be used for new quantum measurement schemes or to investigate multiphoton phases of finite-size, nonlinear, open quantum systems.
AU - Fink, Johannes M
AU - Dombi, András
AU - Vukics, András
AU - Wallraff, Andreas
AU - Domokos, Peter
ID - 1114
IS - 1
JF - Physical Review X
SN - 21603308
TI - Observation of the photon blockade breakdown phase transition
VL - 7
ER -
TY - CONF
AB - Time-triggered switched networks are a deterministic communication infrastructure used by real-time distributed embedded systems. Due to the criticality of the applications running over them, developers need to ensure that end-to-end communication is dependable and predictable. Traditional approaches assume static networks that are not flexible to changes caused by reconfigurations or, more importantly, faults, which are dealt with in the application using redundancy. We adopt the concept of handling faults in the switches from non-real-time networks while maintaining the required predictability.
We study a class of forwarding schemes that can handle various types of failures. We consider probabilistic failures. We study a class of forwarding schemes that can handle various types of failures. We consider probabilistic failures. For a given network with a forwarding scheme and a constant ℓ, we compute the {\em score} of the scheme, namely the probability (induced by faults) that at least ℓ messages arrive on time. We reduce the scoring problem to a reachability problem on a Markov chain with a "product-like" structure. Its special structure allows us to reason about it symbolically, and reduce the scoring problem to #SAT. Our solution is generic and can be adapted to different networks and other contexts. Also, we show the computational complexity of the scoring problem is #P-complete, and we study methods to estimate the score. We evaluate the effectiveness of our techniques with an implementation.
AU - Avni, Guy
AU - Goel, Shubham
AU - Henzinger, Thomas A
AU - Rodríguez Navas, Guillermo
ID - 1116
SN - 03029743
TI - Computing scores of forwarding schemes in switched networks with probabilistic faults
VL - 10206
ER -
TY - JOUR
AB - GABAergic synapses in brain circuits generate inhibitory output signals with submillisecond latency and temporal precision. Whether the molecular identity of the release sensor contributes to these signaling properties remains unclear. Here, we examined the Ca^2+ sensor of exocytosis at GABAergic basket cell (BC) to Purkinje cell (PC) synapses in cerebellum. Immunolabeling suggested that BC terminals selectively expressed synaptotagmin 2 (Syt2), whereas synaptotagmin 1 (Syt1) was enriched in excitatory terminals. Genetic elimination of Syt2 reduced action potential-evoked release to ∼10%, identifying Syt2 as the major Ca^2+ sensor at BC-PC synapses. Differential adenovirus-mediated rescue revealed that Syt2 triggered release with shorter latency and higher temporal precision and mediated faster vesicle pool replenishment than Syt1. Furthermore, deletion of Syt2 severely reduced and delayed disynaptic inhibition following parallel fiber stimulation. Thus, the selective use of Syt2 as release sensor at BC-PC synapses ensures fast and efficient feedforward inhibition in cerebellar microcircuits. #bioimagingfacility-author
AU - Chen, Chong
AU - Arai, Itaru
AU - Satterield, Rachel
AU - Young, Samuel
AU - Jonas, Peter M
ID - 1117
IS - 3
JF - Cell Reports
SN - 22111247
TI - Synaptotagmin 2 is the fast Ca2+ sensor at a central inhibitory synapse
VL - 18
ER -
TY - JOUR
AB - Sharp wave-ripple (SWR) oscillations play a key role in memory consolidation during non-rapid eye movement sleep, immobility, and consummatory behavior. However, whether temporally modulated synaptic excitation or inhibition underlies the ripples is controversial. To address this question, we performed simultaneous recordings of excitatory and inhibitory postsynaptic currents (EPSCs and IPSCs) and local field potentials (LFPs) in the CA1 region of awake mice in vivo. During SWRs, inhibition dominated over excitation, with a peak conductance ratio of 4.1 ± 0.5. Furthermore, the amplitude of SWR-associated IPSCs was positively correlated with SWR magnitude, whereas that of EPSCs was not. Finally, phase analysis indicated that IPSCs were phase-locked to individual ripple cycles, whereas EPSCs were uniformly distributed in phase space. Optogenetic inhibition indicated that PV+ interneurons provided a major contribution to SWR-associated IPSCs. Thus, phasic inhibition, but not excitation, shapes SWR oscillations in the hippocampal CA1 region in vivo.
AU - Gan, Jian
AU - Weng, Shih-Ming
AU - Pernia-Andrade, Alejandro
AU - Csicsvari, Jozsef L
AU - Jonas, Peter M
ID - 1118
IS - 2
JF - Neuron
TI - Phase-locked inhibition, but not excitation, underlies hippocampal ripple oscillations in awake mice in vivo
VL - 93
ER -
TY - JOUR
AB - Understanding the behavior of molecules interacting with superfluid helium represents a formidable challenge and, in general, requires approaches relying on large-scale numerical simulations. Here we demonstrate that experimental data collected over the last 20 years provide evidence that molecules immersed in superfluid helium form recently-predicted angulon quasiparticles [Phys. Rev. Lett. 114, 203001 (2015)]. Most importantly, casting the many-body problem in terms of angulons amounts to a drastic simplification and yields effective molecular moments of inertia as straightforward analytic solutions of a simple microscopic Hamiltonian. The outcome of the angulon theory is in good agreement with experiment for a broad range of molecular impurities, from heavy to medium-mass to light species. These results pave the way to understanding molecular rotation in liquid and crystalline phases in terms of the angulon quasiparticle.
AU - Lemeshko, Mikhail
ID - 1119
IS - 9
JF - Physical Review Letters
SN - 00319007
TI - Quasiparticle approach to molecules interacting with quantum solvents
VL - 118
ER -
TY - JOUR
AB - The existence of a self-localization transition in the polaron problem has been under an active debate ever since Landau suggested it 83 years ago. Here we reveal the self-localization transition for the rotational analogue of the polaron -- the angulon quasiparticle. We show that, unlike for the polarons, self-localization of angulons occurs at finite impurity-bath coupling already at the mean-field level. The transition is accompanied by the spherical-symmetry breaking of the angulon ground state and a discontinuity in the first derivative of the ground-state energy. Moreover, the type of the symmetry breaking is dictated by the symmetry of the microscopic impurity-bath interaction, which leads to a number of distinct self-localized states. The predicted effects can potentially be addressed in experiments on cold molecules trapped in superfluid helium droplets and ultracold quantum gases, as well as on electronic excitations in solids and Bose-Einstein condensates.
AU - Li, Xiang
AU - Seiringer, Robert
AU - Lemeshko, Mikhail
ID - 1120
IS - 3
JF - Physical Review A
SN - 24699926
TI - Angular self-localization of impurities rotating in a bosonic bath
VL - 95
ER -
TY - THES
AB - Plant hormone auxin and its transport between cells belong to the most important
mechanisms controlling plant development. Auxin itself could change localization of PINs and
thereby control direction of its own flow. We performed an expression profiling experiment
in Arabidopsis roots to identify potential regulators of PIN polarity which are transcriptionally
regulated by auxin signalling. We identified several novel regulators and performed a detailed
characterization of the transcription factor WRKY23 (At2g47260) and its role in auxin
feedback on PIN polarity. Gain-of-function and dominant-negative mutants revealed that
WRKY23 plays a crucial role in mediating the auxin effect on PIN polarity. In concordance,
typical polar auxin transport processes such as gravitropism and leaf vascular pattern
formation were disturbed by interfering with WRKY23 function.
In order to identify direct targets of WRKY23, we performed consequential expression
profiling experiments using a WRKY23 inducible gain-of-function line and dominant-negative
WRKY23 line that is defunct in PIN re-arrangement. Among several genes mostly related to
the groups of cell wall and defense process regulators, we identified LYSINE-HISTIDINE
TRANSPORTER 1 (LHT1; At5g40780), a small amino acid permease gene from the amino
acid/auxin permease family (AAAP), we present its detailed characterisation in auxin feedback
on PIN repolarization, identified its transcriptional regulation, we propose a potential
mechanism of its action. Moreover, we identified also a member of receptor-like protein
kinase LRR-RLK (LEUCINE-RICH REPEAT TRANSMEMBRANE PROTEIN KINASE PROTEIN 1;
LRRK1; At1g05700), which also affects auxin-dependent PIN re-arrangement. We described
its transcriptional behaviour, subcellular localization. Based on global expression data, we
tried to identify ligand responsible for mechanism of signalling and suggest signalling partner
and interactors. Additionally, we described role of novel phytohormone group, strigolactone,
in auxin-dependent PIN re-arrangement, that could be a fundament for future studies in this
field.
Our results provide first insights into an auxin transcriptional network targeting PIN
localization and thus regulating plant development. We highlighted WRKY23 transcriptional
network and characterised its mediatory role in plant development. We identified direct
effectors of this network, LHT1 and LRRK1, and describe their roles in PIN re-arrangement and
PIN-dependent auxin transport processes.
AU - Prat, Tomas
ID - 1127
TI - Identification of novel regulators of PIN polarity and development of novel auxin sensor
ER -
TY - JOUR
AB - The hippocampus is thought to initiate systems-wide mnemonic processes through the reactivation of previously acquired spatial and episodic memory traces, which can recruit the entorhinal cortex as a first stage of memory redistribution to other brain areas. Hippocampal reactivation occurs during sharp wave-ripples, in which synchronous network firing encodes sequences of places.We investigated the coordination of this replay by recording assembly activity simultaneously in the CA1 region of the hippocampus and superficial layers of the medial entorhinal cortex. We found that entorhinal cell assemblies can replay trajectories independently of the hippocampus and sharp wave-ripples. This suggests that the hippocampus is not the sole initiator of spatial and episodic memory trace reactivation. Memory systems involved in these processes may include nonhierarchical, parallel components.
AU - O'Neill, Joseph
AU - Boccara, Charlotte
AU - Stella, Federico
AU - Schönenberger, Philipp
AU - Csicsvari, Jozsef L
ID - 1132
IS - 6321
JF - Science
SN - 00368075
TI - Superficial layers of the medial entorhinal cortex replay independently of the hippocampus
VL - 355
ER -
TY - JOUR
AB - It is a common knowledge that an effective interaction of a quantum impurity with an electromagnetic field can be screened by surrounding charge carriers, whether mobile or static. Here we demonstrate that very strong, "anomalous" screening can take place in the presence of a neutral, weakly polarizable environment, due to an exchange of orbital angular momentum between the impurity and the bath. Furthermore, we show that it is possible to generalize all phenomena related to isolated impurities in an external field to the case when a many-body environment is present, by casting the problem in terms of the angulon quasiparticle. As a result, the relevant observables such as the effective Rabi frequency, geometric phase, and impurity spatial alignment are straightforward to evaluate in terms of a single parameter: the angular-momentum-dependent screening factor.
AU - Yakaboylu, Enderalp
AU - Lemeshko, Mikhail
ID - 1133
IS - 8
JF - Physical Review Letters
SN - 00319007
TI - Anomalous screening of quantum impurities by a neutral environment
VL - 118
ER -
TY - JOUR
AB - We show that matrix elements of functions of N × N Wigner matrices fluctuate on a scale of order N−1/2 and we identify the limiting fluctuation. Our result holds for any function f of the matrix that has bounded variation thus considerably relaxing the regularity requirement imposed in [7, 11].
AU - Erdös, László
AU - Schröder, Dominik J
ID - 1144
JF - Electronic Communications in Probability
TI - Fluctuations of functions of Wigner matrices
VL - 21
ER -
TY - JOUR
AB - Aim: The present study was to compare the effects of nicotinic acid and nicotinamide on the plasma methyl donors, choline and betaine. Methods: Thirty adult subjects were randomly divided into three groups of equal size, and orally received purified water (C group), nicotinic acid (300 mg, NA group) or nicotinamide (300 mg, NM group). Plasma nicotinamide, N 1-methylnicotinamide, homocysteine, betaine and choline levels before and 1.5-h and 3-h post-dosing, plasma normetanephrine and metanephrine concentrations at 3-h post-dosing, and the urinary excretion of N 1-methyl-2-pyridone-5-carboxamide during the test period were examined. Results: The level of 3-h plasma nicotinamide, N 1-methylnicotinamide, homocysteine, the urinary excretion of N 1-methyl-2-pyridone-5-carboxamide and pulse pressure (PP) in the NM group was 221%, 3972%, 61%, 1728% and 21.2% higher than that of the control group (P < 0.01, except homocysteine and PP P < 0.05), while the 3-h plasma betaine, normetanephrine and metanephrine level in the NM group was 24.4%, 9.4% and 11.7% lower (P < 0.05, except betaine P < 0.01), without significant difference in choline levels. Similar but less pronounced changes were observed in the NA group, with a lower level of 3-h plasma N 1-methylnicotinamide (1.90 ± 0.20 μmol/l vs. 3.62 ± 0.27 μmol/l, P < 0.01) and homocysteine (12.85 ± 1.39 μmol/l vs. 18.08 ± 1.02 μmol/l, P < 0.05) but a higher level of betaine (27.44 ± 0.71 μmol/l vs. 23.52 ± 0.61 μmol/l, P < 0.05) than that of the NM group. Conclusion: The degradation of nicotinamide consumes more betaine than that of nicotinic acid at identical doses. This difference should be taken into consideration in niacin fortification. © 2016 Elsevier Ltd and European Society for Clinical Nutrition and Metabolism.
AU - Sun, Wuping
AU - Zhai, Ming-Zhu
AU - Li, Da
AU - Zhou, Yiming
AU - Chen, Nana
AU - Guo, Ming
AU - Zhou, Shisheng
ID - 1146
IS - 4
JF - Clinical Nutrition
TI - Comparison of the effects of nicotinic acid and nicotinamide degradation on plasma betaine and choline levels
VL - 36
ER -
TY - JOUR
AB - We propose a new memetic strategy that can solve the multi-physics, complex inverse problems, formulated as the multi-objective optimization ones, in which objectives are misfits between the measured and simulated states of various governing processes. The multi-deme structure of the strategy allows for both, intensive, relatively cheap exploration with a moderate accuracy and more accurate search many regions of Pareto set in parallel. The special type of selection operator prefers the coherent alternative solutions, eliminating artifacts appearing in the particular processes. The additional accuracy increment is obtained by the parallel convex searches applied to the local scalarizations of the misfit vector. The strategy is dedicated for solving ill-conditioned problems, for which inverting the single physical process can lead to the ambiguous results. The skill of the selection in artifact elimination is shown on the benchmark problem, while the whole strategy was applied for identification of oil deposits, where the misfits are related to various frequencies of the magnetic and electric waves of the magnetotelluric measurements. 2016 Elsevier B.V.
AU - Gajda-Zagorska, Ewa P
AU - Schaefer, Robert
AU - Smołka, Maciej
AU - Pardo, David
AU - Alvarez Aramberri, Julen
ID - 1152
JF - Journal of Computational Science
SN - 18777503
TI - A multi objective memetic inverse solver reinforced by local optimization methods
VL - 18
ER -
TY - THES
AB - This dissertation concerns the automatic verification of probabilistic systems and programs with arrays by statistical and logical methods. Although statistical and logical methods are different in nature, we show that they can be successfully combined for system analysis. In the first part of the dissertation we present a new statistical algorithm for the verification of probabilistic systems with respect to unbounded properties, including linear temporal logic. Our algorithm often performs faster than the previous approaches, and at the same time requires less information about the system. In addition, our method can be generalized to unbounded quantitative properties such as mean-payoff bounds. In the second part, we introduce two techniques for comparing probabilistic systems. Probabilistic systems are typically compared using the notion of equivalence, which requires the systems to have the equal probability of all behaviors. However, this notion is often too strict, since probabilities are typically only empirically estimated, and any imprecision may break the relation between processes. On the one hand, we propose to replace the Boolean notion of equivalence by a quantitative distance of similarity. For this purpose, we introduce a statistical framework for estimating distances between Markov chains based on their simulation runs, and we investigate which distances can be approximated in our framework. On the other hand, we propose to compare systems with respect to a new qualitative logic, which expresses that behaviors occur with probability one or a positive probability. This qualitative analysis is robust with respect to modeling errors and applicable to many domains. In the last part, we present a new quantifier-free logic for integer arrays, which allows us to express counting. Counting properties are prevalent in array-manipulating programs, however they cannot be expressed in the quantified fragments of the theory of arrays. We present a decision procedure for our logic, and provide several complexity results.
AU - Daca, Przemyslaw
ID - 1155
TI - Statistical and logical methods for property checking
ER -
TY - JOUR
AB - We investigate fundamental nonlinear dynamics of ferrofluidic Taylor-Couette flow - flow confined be-tween two concentric independently rotating cylinders - consider small aspect ratio by solving the ferro-hydrodynamical equations, carrying out systematic bifurcation analysis. Without magnetic field, we find steady flow patterns, previously observed with a simple fluid, such as those containing normal one- or two vortex cells, as well as anomalous one-cell and twin-cell flow states. However, when a symmetry-breaking transverse magnetic field is present, all flow states exhibit stimulated, finite two-fold mode. Various bifurcations between steady and unsteady states can occur, corresponding to the transitions between the two-cell and one-cell states. While unsteady, axially oscillating flow states can arise, we also detect the emergence of new unsteady flow states. In particular, we uncover two new states: one contains only the azimuthally oscillating solution in the configuration of the twin-cell flow state, and an-other a rotating flow state. Topologically, these flow states are a limit cycle and a quasiperiodic solution on a two-torus, respectively. Emergence of new flow states in addition to observed ones with classical fluid, indicates that richer but potentially more controllable dynamics in ferrofluidic flows, as such flow states depend on the external magnetic field.
AU - Altmeyer, Sebastian
AU - Do, Younghae
AU - Lai, Ying
ID - 1160
JF - Scientific Reports
SN - 20452322
TI - Dynamics of ferrofluidic flow in the Taylor-Couette system with a small aspect ratio
VL - 7
ER -
TY - JOUR
AB - Coordinated changes of cell shape are often the result of the excitable, wave-like dynamics of the actin cytoskeleton. New work shows that, in migrating cells, protrusion waves arise from mechanochemical crosstalk between adhesion sites, membrane tension and the actin protrusive machinery.
AU - Müller, Jan
AU - Sixt, Michael K
ID - 1161
IS - 1
JF - Current Biology
SN - 09609822
TI - Cell migration: Making the waves
VL - 27
ER -
TY - JOUR
AB - Selected universal experimental properties of high-temperature superconducting (HTS) cuprates have been singled out in the last decade. One of the pivotal challenges in this field is the designation of a consistent interpretation framework within which we can describe quantitatively the universal features of those systems. Here we analyze in a detailed manner the principal experimental data and compare them quantitatively with the approach based on a single-band model of strongly correlated electrons supplemented with strong antiferromagnetic (super)exchange interaction (the so-called t−J−U model). The model rationale is provided by estimating its microscopic parameters on the basis of the three-band approach for the Cu-O plane. We use our original full Gutzwiller wave-function solution by going beyond the renormalized mean-field theory (RMFT) in a systematic manner. Our approach reproduces very well the observed hole doping (δ) dependence of the kinetic-energy gain in the superconducting phase, one of the principal non-Bardeen-Cooper-Schrieffer features of the cuprates. The calculated Fermi velocity in the nodal direction is practically δ-independent and its universal value agrees very well with that determined experimentally. Also, a weak doping dependence of the Fermi wave vector leads to an almost constant value of the effective mass in a pure superconducting phase which is both observed in experiment and reproduced within our approach. An assessment of the currently used models (t−J, Hubbard) is carried out and the results of the canonical RMFT as a zeroth-order solution are provided for comparison to illustrate the necessity of the introduced higher-order contributions.
AU - Spałek, Jozef
AU - Zegrodnik, Michał
AU - Kaczmarczyk, Jan
ID - 1162
IS - 2
JF - Physical Review B - Condensed Matter and Materials Physics
SN - 24699950
TI - Universal properties of high temperature superconductors from real space pairing t-J-U model and its quantitative comparison with experiment
VL - 95
ER -
TY - JOUR
AB - We investigate the effect of the electron-hole (e-h) symmetry breaking on d-wave superconductivity induced by non-local effects of correlations in the generalized Hubbard model. The symmetry breaking is introduced in a two-fold manner: by the next-to-nearest neighbor hopping of electrons and by the charge-bond interaction - the off-diagonal term of the Coulomb potential. Both terms lead to a pronounced asymmetry of the superconducting order parameter. The next-to-nearest neighbor hopping enhances superconductivity for h-doping, while diminishes it for e-doping. The charge-bond interaction alone leads to the opposite effect and, additionally, to the kinetic-energy gain upon condensation in the underdoped regime. With both terms included, with similar amplitudes, the height of the superconducting dome and the critical doping remain in favor of h-doping. The influence of the charge-bond interaction on deviations from symmetry of the shape of the gap at the Fermi surface in the momentum space is briefly discussed.
AU - Wysokiński, Marcin
AU - Kaczmarczyk, Jan
ID - 1163
IS - 8
JF - Journal of Physics: Condensed Matter
SN - 09538984
TI - Unconventional superconductivity in generalized Hubbard model role of electron–hole symmetry breaking terms
VL - 29
ER -
TY - JOUR
AB - Optimum experimental design theory has recently been extended for parameter estimation in copula models. The use of these models allows one to gain in flexibility by considering the model parameter set split into marginal and dependence parameters. However, this separation also leads to the natural issue of estimating only a subset of all model parameters. In this work, we treat this problem with the application of the (Formula presented.)-optimality to copula models. First, we provide an extension of the corresponding equivalence theory. Then, we analyze a wide range of flexible copula models to highlight the usefulness of (Formula presented.)-optimality in many possible scenarios. Finally, we discuss how the usage of the introduced design criterion also relates to the more general issue of copula selection and optimal design for model discrimination.
AU - Perrone, Elisa
AU - Rappold, Andreas
AU - Müller, Werner
ID - 1168
IS - 3
JF - Statistical Methods and Applications
TI - D inf s optimality in copula models
VL - 26
ER -
TY - JOUR
AB - Dispersal is a crucial factor in natural evolution, since it determines the habitat experienced by any population and defines the spatial scale of interactions between individuals. There is compelling evidence for systematic differences in dispersal characteristics within the same population, i.e., genotype-dependent dispersal. The consequences of genotype-dependent dispersal on other evolutionary phenomena, however, are poorly understood. In this article we investigate the effect of genotype-dependent dispersal on spatial gene frequency patterns, using a generalization of the classical diffusion model of selection and dispersal. Dispersal is characterized by the variance of dispersal (diffusion coefficient) and the mean displacement (directional advection term). We demonstrate that genotype-dependent dispersal may change the qualitative behavior of Fisher waves, which change from being “pulled” to being “pushed” wave fronts as the discrepancy in dispersal between genotypes increases. The speed of any wave is partitioned into components due to selection, genotype-dependent variance of dispersal, and genotype-dependent mean displacement. We apply our findings to wave fronts maintained by selection against heterozygotes. Furthermore, we identify a benefit of increased variance of dispersal, quantify its effect on the speed of the wave, and discuss the implications for the evolution of dispersal strategies.
AU - Novak, Sebastian
AU - Kollár, Richard
ID - 1169
IS - 1
JF - Genetics
SN - 00166731
TI - Spatial gene frequency waves under genotype dependent dispersal
VL - 205
ER -
TY - CONF
AB - Several cryptographic schemes and applications are based on functions that are both reasonably efficient to compute and moderately hard to invert, including client puzzles for Denial-of-Service protection, password protection via salted hashes, or recent proof-of-work blockchain systems. Despite their wide use, a definition of this concept has not yet been distilled and formalized explicitly. Instead, either the applications are proven directly based on the assumptions underlying the function, or some property of the function is proven, but the security of the application is argued only informally. The goal of this work is to provide a (universal) definition that decouples the efforts of designing new moderately hard functions and of building protocols based on them, serving as an interface between the two. On a technical level, beyond the mentioned definitions, we instantiate the model for four different notions of hardness. We extend the work of Alwen and Serbinenko (STOC 2015) by providing a general tool for proving security for the first notion of memory-hard functions that allows for provably secure applications. The tool allows us to recover all of the graph-theoretic techniques developed for proving security under the older, non-composable, notion of security used by Alwen and Serbinenko. As an application of our definition of moderately hard functions, we prove the security of two different schemes for proofs of effort (PoE). We also formalize and instantiate the concept of a non-interactive proof of effort (niPoE), in which the proof is not bound to a particular communication context but rather any bit-string chosen by the prover.
AU - Alwen, Joel F
AU - Tackmann, Björn
ED - Kalai, Yael
ED - Reyzin, Leonid
ID - 609
SN - 978-331970499-9
TI - Moderately hard functions: Definition, instantiations, and applications
VL - 10677
ER -
TY - JOUR
AB - The fact that the complete graph K5 does not embed in the plane has been generalized in two independent directions. On the one hand, the solution of the classical Heawood problem for graphs on surfaces established that the complete graph Kn embeds in a closed surface M (other than the Klein bottle) if and only if (n−3)(n−4) ≤ 6b1(M), where b1(M) is the first Z2-Betti number of M. On the other hand, van Kampen and Flores proved that the k-skeleton of the n-dimensional simplex (the higher-dimensional analogue of Kn+1) embeds in R2k if and only if n ≤ 2k + 1. Two decades ago, Kühnel conjectured that the k-skeleton of the n-simplex embeds in a compact, (k − 1)-connected 2k-manifold with kth Z2-Betti number bk only if the following generalized Heawood inequality holds: (k+1 n−k−1) ≤ (k+1 2k+1)bk. This is a common generalization of the case of graphs on surfaces as well as the van Kampen–Flores theorem. In the spirit of Kühnel’s conjecture, we prove that if the k-skeleton of the n-simplex embeds in a compact 2k-manifold with kth Z2-Betti number bk, then n ≤ 2bk(k 2k+2)+2k+4. This bound is weaker than the generalized Heawood inequality, but does not require the assumption that M is (k−1)-connected. Our results generalize to maps without q-covered points, in the spirit of Tverberg’s theorem, for q a prime power. Our proof uses a result of Volovikov about maps that satisfy a certain homological triviality condition.
AU - Goaoc, Xavier
AU - Mabillard, Isaac
AU - Paták, Pavel
AU - Patakova, Zuzana
AU - Tancer, Martin
AU - Wagner, Uli
ID - 610
IS - 2
JF - Israel Journal of Mathematics
TI - On generalized Heawood inequalities for manifolds: A van Kampen–Flores type nonembeddability result
VL - 222
ER -
TY - JOUR
AB - Small RNAs (sRNAs) regulate genes in plants and animals. Here, we show that population-wide differences in color patterns in snapdragon flowers are caused by an inverted duplication that generates sRNAs. The complexity and size of the transcripts indicate that the duplication represents an intermediate on the pathway to microRNA evolution. The sRNAs repress a pigment biosynthesis gene, creating a yellow highlight at the site of pollinator entry. The inverted duplication exhibits steep clines in allele frequency in a natural hybrid zone, showing that the allele is under selection. Thus, regulatory interactions of evolutionarily recent sRNAs can be acted upon by selection and contribute to the evolution of phenotypic diversity.
AU - Bradley, Desmond
AU - Xu, Ping
AU - Mohorianu, Irina
AU - Whibley, Annabel
AU - Field, David
AU - Tavares, Hugo
AU - Couchman, Matthew
AU - Copsey, Lucy
AU - Carpenter, Rosemary
AU - Li, Miaomiao
AU - Li, Qun
AU - Xue, Yongbiao
AU - Dalmay, Tamas
AU - Coen, Enrico
ID - 611
IS - 6365
JF - Science
SN - 00368075
TI - Evolution of flower color pattern through selection on regulatory small RNAs
VL - 358
ER -
TY - JOUR
AB - Bacteria in groups vary individually, and interact with other bacteria and the environment to produce population-level patterns of gene expression. Investigating such behavior in detail requires measuring and controlling populations at the single-cell level alongside precisely specified interactions and environmental characteristics. Here we present an automated, programmable platform that combines image-based gene expression and growth measurements with on-line optogenetic expression control for hundreds of individual Escherichia coli cells over days, in a dynamically adjustable environment. This integrated platform broadly enables experiments that bridge individual and population behaviors. We demonstrate: (i) population structuring by independent closed-loop control of gene expression in many individual cells, (ii) cell-cell variation control during antibiotic perturbation, (iii) hybrid bio-digital circuits in single cells, and freely specifiable digital communication between individual bacteria. These examples showcase the potential for real-time integration of theoretical models with measurement and control of many individual cells to investigate and engineer microbial population behavior.
AU - Chait, Remy P
AU - Ruess, Jakob
AU - Bergmiller, Tobias
AU - Tkacik, Gasper
AU - Guet, Calin C
ID - 613
IS - 1
JF - Nature Communications
SN - 20411723
TI - Shaping bacterial population behavior through computer interfaced control of individual cells
VL - 8
ER -
TY - JOUR
AB - Moths and butterflies (Lepidoptera) usually have a pair of differentiated WZ sex chromosomes. However, in most lineages outside of the division Ditrysia, as well as in the sister order Trichoptera, females lack a W chromosome. The W is therefore thought to have been acquired secondarily. Here we compare the genomes of three Lepidoptera species (one Dytrisia and two non-Dytrisia) to test three models accounting for the origin of the W: (1) a Z-autosome fusion; (2) a sex chromosome turnover; and (3) a non-canonical mechanism (e.g., through the recruitment of a B chromosome). We show that the gene content of the Z is highly conserved across Lepidoptera (rejecting a sex chromosome turnover) and that very few genes moved onto the Z in the common ancestor of the Ditrysia (arguing against a Z-autosome fusion). Our comparative genomics analysis therefore supports the secondary acquisition of the Lepidoptera W by a non-canonical mechanism, and it confirms the extreme stability of well-differentiated sex chromosomes.
AU - Fraisse, Christelle
AU - Picard, Marion A
AU - Vicoso, Beatriz
ID - 614
IS - 1
JF - Nature Communications
SN - 20411723
TI - The deep conservation of the Lepidoptera Z chromosome suggests a non canonical origin of the W
VL - 8
ER -
TY - JOUR
AB - We show that the Dyson Brownian Motion exhibits local universality after a very short time assuming that local rigidity and level repulsion of the eigenvalues hold. These conditions are verified, hence bulk spectral universality is proven, for a large class of Wigner-like matrices, including deformed Wigner ensembles and ensembles with non-stochastic variance matrices whose limiting densities differ from Wigner's semicircle law.
AU - Erdös, László
AU - Schnelli, Kevin
ID - 615
IS - 4
JF - Annales de l'institut Henri Poincare (B) Probability and Statistics
SN - 02460203
TI - Universality for random matrix flows with time dependent density
VL - 53
ER -
TY - JOUR
AB - PMAC is a simple and parallel block-cipher mode of operation, which was introduced by Black and Rogaway at Eurocrypt 2002. If instantiated with a (pseudo)random permutation over n-bit strings, PMAC constitutes a provably secure variable input-length (pseudo)random function. For adversaries making q queries, each of length at most l (in n-bit blocks), and of total length σ ≤ ql, the original paper proves an upper bound on the distinguishing advantage of Ο(σ2/2n), while the currently best bound is Ο (qσ/2n).In this work we show that this bound is tight by giving an attack with advantage Ω (q2l/2n). In the PMAC construction one initially XORs a mask to every message block, where the mask for the ith block is computed as τi := γi·L, where L is a (secret) random value, and γi is the i-th codeword of the Gray code. Our attack applies more generally to any sequence of γi’s which contains a large coset of a subgroup of GF(2n). We then investigate if the security of PMAC can be further improved by using τi’s that are k-wise independent, for k > 1 (the original distribution is only 1-wise independent). We observe that the security of PMAC will not increase in general, even if the masks are chosen from a 2-wise independent distribution, and then prove that the security increases to O(q<2/2n), if the τi are 4-wise independent. Due to simple extension attacks, this is the best bound one can hope for, using any distribution on the masks. Whether 3-wise independence is already sufficient to get this level of security is left as an open problem.
AU - Gazi, Peter
AU - Pietrzak, Krzysztof Z
AU - Rybar, Michal
ID - 6196
IS - 2
JF - IACR Transactions on Symmetric Cryptology
TI - The exact security of PMAC
VL - 2016
ER -
TY - JOUR
AB - The mammalian cerebral cortex is responsible for higher cognitive functions such as perception, consciousness, and acquiring and processing information. The neocortex is organized into six distinct laminae, each composed of a rich diversity of cell types which assemble into highly complex cortical circuits. Radial glia progenitors (RGPs) are responsible for producing all neocortical neurons and certain glia lineages. Here, we discuss recent discoveries emerging from clonal lineage analysis at the single RGP cell level that provide us with an inaugural quantitative framework of RGP lineage progression. We further discuss the importance of the relative contribution of intrinsic gene functions and non-cell-autonomous or community effects in regulating RGP proliferation behavior and lineage progression.
AU - Beattie, Robert J
AU - Hippenmeyer, Simon
ID - 621
IS - 24
JF - FEBS letters
SN - 00145793
TI - Mechanisms of radial glia progenitor cell lineage progression
VL - 591
ER -
TY - CHAP
AB - Genetic factors might be largely responsible for the development of autism spectrum disorder (ASD) that alone or in combination with specific environmental risk factors trigger the pathology. Multiple mutations identified in ASD patients that impair synaptic function in the central nervous system are well studied in animal models. How these mutations might interact with other risk factors is not fully understood though. Additionally, how systems outside of the brain are altered in the context of ASD is an emerging area of research. Extracerebral influences on the physiology could begin in utero and contribute to changes in the brain and in the development of other body systems and further lead to epigenetic changes. Therefore, multiple recent studies have aimed at elucidating the role of gene-environment interactions in ASD. Here we provide an overview on the extracerebral systems that might play an important associative role in ASD and review evidence regarding the potential roles of inflammation, trace metals, metabolism, genetic susceptibility, enteric nervous system function and the microbiota of the gastrointestinal (GI) tract on the development of endophenotypes in animal models of ASD. By influencing environmental conditions, it might be possible to reduce or limit the severity of ASD pathology.
AU - Hill Yardin, Elisa
AU - Mckeown, Sonja
AU - Novarino, Gaia
AU - Grabrucker, Andreas
ED - Schmeisser, Michael
ED - Boekers, Tobias
ID - 623
SN - 03015556
T2 - Translational Anatomy and Cell Biology of Autism Spectrum Disorder
TI - Extracerebral dysfunction in animal models of autism spectrum disorder
VL - 224
ER -
TY - JOUR
AB - Bacteria adapt to adverse environmental conditions by altering gene expression patterns. Recently, a novel stress adaptation mechanism has been described that allows Escherichia coli to alter gene expression at the post-transcriptional level. The key player in this regulatory pathway is the endoribonuclease MazF, the toxin component of the toxin-antitoxin module mazEF that is triggered by various stressful conditions. In general, MazF degrades the majority of transcripts by cleaving at ACA sites, which results in the retardation of bacterial growth. Furthermore, MazF can process a small subset of mRNAs and render them leaderless by removing their ribosome binding site. MazF concomitantly modifies ribosomes, making them selective for the translation of leaderless mRNAs. In this study, we employed fluorescent reporter-systems to investigate mazEF expression during stressful conditions, and to infer consequences of the mRNA processing mediated by MazF on gene expression at the single-cell level. Our results suggest that mazEF transcription is maintained at low levels in single cells encountering adverse conditions, such as antibiotic stress or amino acid starvation. Moreover, using the grcA mRNA as a model for MazF-mediated mRNA processing, we found that MazF activation promotes heterogeneity in the grcA reporter expression, resulting in a subpopulation of cells with increased levels of GrcA reporter protein.
AU - Nikolic, Nela
AU - Didara, Zrinka
AU - Moll, Isabella
ID - 624
IS - 9
JF - PeerJ
SN - 21678359
TI - MazF activation promotes translational heterogeneity of the grcA mRNA in Escherichia coli populations
VL - 2017
ER -
TY - JOUR
AB - Our focus here is on the infinitesimal model. In this model, one or several quantitative traits are described as the sum of a genetic and a non-genetic component, the first being distributed within families as a normal random variable centred at the average of the parental genetic components, and with a variance independent of the parental traits. Thus, the variance that segregates within families is not perturbed by selection, and can be predicted from the variance components. This does not necessarily imply that the trait distribution across the whole population should be Gaussian, and indeed selection or population structure may have a substantial effect on the overall trait distribution. One of our main aims is to identify some general conditions on the allelic effects for the infinitesimal model to be accurate. We first review the long history of the infinitesimal model in quantitative genetics. Then we formulate the model at the phenotypic level in terms of individual trait values and relationships between individuals, but including different evolutionary processes: genetic drift, recombination, selection, mutation, population structure, …. We give a range of examples of its application to evolutionary questions related to stabilising selection, assortative mating, effective population size and response to selection, habitat preference and speciation. We provide a mathematical justification of the model as the limit as the number M of underlying loci tends to infinity of a model with Mendelian inheritance, mutation and environmental noise, when the genetic component of the trait is purely additive. We also show how the model generalises to include epistatic effects. We prove in particular that, within each family, the genetic components of the individual trait values in the current generation are indeed normally distributed with a variance independent of ancestral traits, up to an error of order 1∕M. Simulations suggest that in some cases the convergence may be as fast as 1∕M.
AU - Barton, Nicholas H
AU - Etheridge, Alison
AU - Véber, Amandine
ID - 626
JF - Theoretical Population Biology
SN - 00405809
TI - The infinitesimal model: Definition derivation and implications
VL - 118
ER -
TY - JOUR
AB - Beige adipocytes are a new type of recruitable brownish adipocytes, with highly mitochondrial membrane uncoupling protein 1 expression and thermogenesis. Beige adipocytes were found among white adipocytes, especially in subcutaneous white adipose tissue (sWAT). Therefore, beige adipocytes may be involved in the regulation of energy metabolism and fat deposition. Transient receptor potential melastatin 8 (TRPM8), a Ca2+-permeable non-selective cation channel, plays vital roles in the regulation of various cellular functions. It has been reported that TRPM8 activation enhanced the thermogenic function of brown adiposytes. However, the involvement of TRPM8 in the thermogenic function of WAT remains unexplored. Our data revealed that TRPM8 was expressed in mouse white adipocytes at mRNA, protein and functional levels. The mRNA expression of Trpm8 was significantly increased in the differentiated white adipocytes than pre-adipocytes. Moreover, activation of TRPM8 by menthol enhanced the expression of thermogenic genes in cultured white aidpocytes. And menthol-induced increases of the thermogenic genes in white adipocytes was inhibited by either KT5720 (a protein kinase A inhibitor) or BAPTA-AM. In addition, high fat diet (HFD)-induced obesity in mice was significantly recovered by co-treatment with menthol. Dietary menthol enhanced WAT "browning" and improved glucose metabolism in HFD-induced obesity mice as well. Therefore, we concluded that TRPM8 might be involved in WAT "browning" by increasing the expression levels of genes related to thermogenesis and energy metabolism. And dietary menthol could be a novel approach for combating human obesity and related metabolic diseases.
AU - Jiang, Changyu
AU - Zhai, Ming-Zhu
AU - Yan, Dong
AU - Li, Da
AU - Li, Chen
AU - Zhang, Yonghong
AU - Xiao, Lizu
AU - Xiong, Donglin
AU - Deng, Qiwen
AU - Sun, Wuping
ID - 627
IS - 43
JF - Oncotarget
SN - 19492553
TI - Dietary menthol-induced TRPM8 activation enhances WAT “browning” and ameliorates diet-induced obesity
VL - 8
ER -
TY - CONF
AB - We consider the problem of developing automated techniques for solving recurrence relations to aid the expected-runtime analysis of programs. The motivation is that several classical textbook algorithms have quite efficient expected-runtime complexity, whereas the corresponding worst-case bounds are either inefficient (e.g., Quick-Sort), or completely ineffective (e.g., Coupon-Collector). Since the main focus of expected-runtime analysis is to obtain efficient bounds, we consider bounds that are either logarithmic, linear or almost-linear (O(log n), O(n), O(n · log n), respectively, where n represents the input size). Our main contribution is an efficient (simple linear-time algorithm) sound approach for deriving such expected-runtime bounds for the analysis of recurrence relations induced by randomized algorithms. The experimental results show that our approach can efficiently derive asymptotically optimal expected-runtime bounds for recurrences of classical randomized algorithms, including Randomized-Search, Quick-Sort, Quick-Select, Coupon-Collector, where the worst-case bounds are either inefficient (such as linear as compared to logarithmic expected-runtime complexity, or quadratic as compared to linear or almost-linear expected-runtime complexity), or ineffective.
AU - Chatterjee, Krishnendu
AU - Fu, Hongfei
AU - Murhekar, Aniket
ED - Majumdar, Rupak
ED - Kunčak, Viktor
ID - 628
SN - 978-331963386-2
TI - Automated recurrence analysis for almost linear expected runtime bounds
VL - 10426
ER -
TY - THES
AB - The main objects considered in the present work are simplicial and CW-complexes with vertices forming a random point cloud. In particular, we consider a Poisson point process in R^n and study Delaunay and Voronoi complexes of the first and higher orders and weighted Delaunay complexes obtained as sections of Delaunay complexes, as well as the Čech complex. Further, we examine theDelaunay complex of a Poisson point process on the sphere S^n, as well as of a uniform point cloud, which is equivalent to the convex hull, providing a connection to the theory of random polytopes. Each of the complexes in question can be endowed with a radius function, which maps its cells to the radii of appropriately chosen circumspheres, called the radius of the cell. Applying and developing discrete Morse theory for these functions, joining it together with probabilistic and sometimes analytic machinery, and developing several integral geometric tools, we aim at getting the distributions of circumradii of typical cells. For all considered complexes, we are able to generalize and obtain up to constants the distribution of radii of typical intervals of all types. In low dimensions the constants can be computed explicitly, thus providing the explicit expressions for the expected numbers of cells. In particular, it allows to find the expected density of simplices of every dimension for a Poisson point process in R^4, whereas the result for R^3 was known already in 1970's.
AU - Nikitenko, Anton
ID - 6287
TI - Discrete Morse theory for random complexes
ER -
TY - CHAP
AB - Even simple cells like bacteria have precisely regulated cellular anatomies, which allow them to grow, divide and to respond to internal or external cues with high fidelity. How spatial and temporal intracellular organization in prokaryotic cells is achieved and maintained on the basis of locally interacting proteins still remains largely a mystery. Bulk biochemical assays with purified components and in vivo experiments help us to approach key cellular processes from two opposite ends, in terms of minimal and maximal complexity. However, to understand how cellular phenomena emerge, that are more than the sum of their parts, we have to assemble cellular subsystems step by step from the bottom up. Here, we review recent in vitro reconstitution experiments with proteins of the bacterial cell division machinery and illustrate how they help to shed light on fundamental cellular mechanisms that constitute spatiotemporal order and regulate cell division.
AU - Loose, Martin
AU - Zieske, Katja
AU - Schwille, Petra
ID - 629
T2 - Prokaryotic Cytoskeletons
TI - Reconstitution of protein dynamics involved in bacterial cell division
VL - 84
ER -
TY - THES
AB - Bacteria and their pathogens – phages – are the most abundant living entities on Earth. Throughout their coevolution, bacteria have evolved multiple immune systems to overcome the ubiquitous threat from the phages. Although the molecu- lar details of these immune systems’ functions are relatively well understood, their epidemiological consequences for the phage-bacterial communities have been largely neglected. In this thesis we employed both experimental and theoretical methods to explore whether herd and social immunity may arise in bacterial popu- lations. Using our experimental system consisting of Escherichia coli strains with a CRISPR based immunity to the T7 phage we show that herd immunity arises in phage-bacterial communities and that it is accentuated when the populations are spatially structured. By fitting a mathematical model, we inferred expressions for the herd immunity threshold and the velocity of spread of a phage epidemic in partially resistant bacterial populations, which both depend on the bacterial growth rate, phage burst size and phage latent period. We also investigated the poten- tial for social immunity in Streptococcus thermophilus and its phage 2972 using a bioinformatic analysis of potentially coding short open reading frames with a signalling signature, encoded within the CRISPR associated genes. Subsequently, we tested one identified potentially signalling peptide and found that its addition to a phage-challenged culture increases probability of survival of bacteria two fold, although the results were only marginally significant. Together, these results demonstrate that the ubiquitous arms races between bacteria and phages have further consequences at the level of the population.
AU - Payne, Pavel
ID - 6291
TI - Bacterial herd and social immunity to phages
ER -
TY - CONF
AB - Background: Standards have become available to share semantically encoded vital parameters from medical devices, as required for example by personal healthcare records. Standardised sharing of biosignal data largely remains open. Objectives: The goal of this work is to explore available biosignal file format and data exchange standards and profiles, and to conceptualise end-To-end solutions. Methods: The authors reviewed and discussed available biosignal file format standards with other members of international standards development organisations (SDOs). Results: A raw concept for standards based acquisition, storage, archiving and sharing of biosignals was developed. The GDF format may serve for storing biosignals. Signals can then be shared using FHIR resources and may be stored on FHIR servers or in DICOM archives, with DICOM waveforms as one possible format. Conclusion: Currently a group of international SDOs (e.g. HL7, IHE, DICOM, IEEE) is engaged in intensive discussions. This discussion extends existing work that already was adopted by large implementer communities. The concept presented here only reports the current status of the discussion in Austria. The discussion will continue internationally, with results to be expected over the coming years.
AU - Sauermann, Stefan
AU - David, Veronika
AU - Schlögl, Alois
AU - Egelkraut, Reinhard
AU - Frohner, Matthias
AU - Pohn, Birgit
AU - Urbauer, Philipp
AU - Mense, Alexander
ID - 630
SN - 978-161499758-0
TI - Biosignals standards and FHIR: The way to go
VL - 236
ER -
TY - CONF
AB - Template polyhedra generalize intervals and octagons to polyhedra whose facets are orthogonal to a given set of arbitrary directions. They have been employed in the abstract interpretation of programs and, with particular success, in the reachability analysis of hybrid automata. While previously, the choice of directions has been left to the user or a heuristic, we present a method for the automatic discovery of directions that generalize and eliminate spurious counterexamples. We show that for the class of convex hybrid automata, i.e., hybrid automata with (possibly nonlinear) convex constraints on derivatives, such directions always exist and can be found using convex optimization. We embed our method inside a CEGAR loop, thus enabling the time-unbounded reachability analysis of an important and richer class of hybrid automata than was previously possible. We evaluate our method on several benchmarks, demonstrating also its superior efficiency for the special case of linear hybrid automata.
AU - Bogomolov, Sergiy
AU - Frehse, Goran
AU - Giacobbe, Mirco
AU - Henzinger, Thomas A
ID - 631
SN - 978-366254576-8
TI - Counterexample guided refinement of template polyhedra
VL - 10205
ER -
TY - JOUR
AB - We consider a 2D quantum system of N bosons in a trapping potential |x|s, interacting via a pair potential of the form N2β−1 w(Nβ x). We show that for all 0 < β < (s + 1)/(s + 2), the leading order behavior of ground states of the many-body system is described in the large N limit by the corresponding cubic nonlinear Schrödinger energy functional. Our result covers the focusing case (w < 0) where even the stability of the many-body system is not obvious. This answers an open question mentioned by X. Chen and J. Holmer for harmonic traps (s = 2). Together with the BBGKY hierarchy approach used by these authors, our result implies the convergence of the many-body quantum dynamics to the focusing NLS equation with harmonic trap for all 0 < β < 3/4.
AU - Lewin, Mathieu
AU - Nam, Phan
AU - Rougerie, Nicolas
ID - 632
IS - 6
JF - Proceedings of the American Mathematical Society
TI - A note on 2D focusing many boson systems
VL - 145
ER -
TY - CONF
AB - A Rapidly-exploring Random Tree (RRT) is an algorithm which can search a non-convex region of space by incrementally building a space-filling tree. The tree is constructed from random points drawn from system’s state space and is biased to grow towards large unexplored areas in the system. RRT can provide better coverage of a system’s possible behaviors compared with random simulations, but is more lightweight than full reachability analysis. In this paper, we explore some of the design decisions encountered while implementing a hybrid extension of the RRT algorithm, which have not been elaborated on before. In particular, we focus on handling non-determinism, which arises due to discrete transitions. We introduce the notion of important points to account for this phenomena. We showcase our ideas using heater and navigation benchmarks.
AU - Bak, Stanley
AU - Bogomolov, Sergiy
AU - Henzinger, Thomas A
AU - Kumar, Aviral
ED - Abate, Alessandro
ED - Bodo, Sylvie
ID - 633
SN - 978-331963500-2
TI - Challenges and tool implementation of hybrid rapidly exploring random trees
VL - 10381
ER -
TY - CHAP
AB - As autism spectrum disorder (ASD) is largely regarded as a neurodevelopmental condition, long-time consensus was that its hallmark features are irreversible. However, several studies from recent years using defined mouse models of ASD have provided clear evidence that in mice neurobiological and behavioural alterations can be ameliorated or even reversed by genetic restoration or pharmacological treatment either before or after symptom onset. Here, we review findings on genetic and pharmacological reversibility of phenotypes in mouse models of ASD. Our review should give a comprehensive overview on both aspects and encourage future studies to better understand the underlying molecular mechanisms that might be translatable from animals to humans.
AU - Schroeder, Jan
AU - Deliu, Elena
AU - Novarino, Gaia
AU - Schmeisser, Michael
ED - Schmeisser, Michael
ED - Boekers, Tobias
ID - 634
T2 - Translational Anatomy and Cell Biology of Autism Spectrum Disorder
TI - Genetic and pharmacological reversibility of phenotypes in mouse models of autism spectrum disorder
VL - 224
ER -
TY - CONF
AB - Memory-hard functions (MHFs) are hash algorithms whose evaluation cost is dominated by memory cost. As memory, unlike computation, costs about the same across different platforms, MHFs cannot be evaluated at significantly lower cost on dedicated hardware like ASICs. MHFs have found widespread applications including password hashing, key derivation, and proofs-of-work. This paper focuses on scrypt, a simple candidate MHF designed by Percival, and described in RFC 7914. It has been used within a number of cryptocurrencies (e.g., Litecoin and Dogecoin) and has been an inspiration for Argon2d, one of the winners of the recent password-hashing competition. Despite its popularity, no rigorous lower bounds on its memory complexity are known. We prove that scrypt is optimally memory-hard, i.e., its cumulative memory complexity (cmc) in the parallel random oracle model is Ω(n2w), where w and n are the output length and number of invocations of the underlying hash function, respectively. High cmc is a strong security target for MHFs introduced by Alwen and Serbinenko (STOC’15) which implies high memory cost even for adversaries who can amortize the cost over many evaluations and evaluate the underlying hash functions many times in parallel. Our proof is the first showing optimal memory-hardness for any MHF. Our result improves both quantitatively and qualitatively upon the recent work by Alwen et al. (EUROCRYPT’16) who proved a weaker lower bound of Ω(n2w/ log2 n) for a restricted class of adversaries.
AU - Alwen, Joel F
AU - Chen, Binchi
AU - Pietrzak, Krzysztof Z
AU - Reyzin, Leonid
AU - Tessaro, Stefano
ED - Coron, Jean-Sébastien
ED - Buus Nielsen, Jesper
ID - 635
SN - 978-331956616-0
TI - Scrypt is maximally memory hard
VL - 10212
ER -
TY - CONF
AB - Signal regular expressions can specify sequential properties of real-valued signals based on threshold conditions, regular operations, and duration constraints. In this paper we endow them with a quantitative semantics which indicates how robustly a signal matches or does not match a given expression. First, we show that this semantics is a safe approximation of a distance between the signal and the language defined by the expression. Then, we consider the robust matching problem, that is, computing the quantitative semantics of every segment of a given signal relative to an expression. We present an algorithm that solves this problem for piecewise-constant and piecewise-linear signals and show that for such signals the robustness map is a piecewise-linear function. The availability of an indicator describing how robustly a signal segment matches some regular pattern provides a general framework for quantitative monitoring of cyber-physical systems.
AU - Bakhirkin, Alexey
AU - Ferrere, Thomas
AU - Maler, Oded
AU - Ulus, Dogan
ED - Abate, Alessandro
ED - Geeraerts, Gilles
ID - 636
SN - 978-331965764-6
TI - On the quantitative semantics of regular expressions over real-valued signals
VL - 10419
ER -
TY - CONF
AB - For many cryptographic primitives, it is relatively easy to achieve selective security (where the adversary commits a-priori to some of the choices to be made later in the attack) but appears difficult to achieve the more natural notion of adaptive security (where the adversary can make all choices on the go as the attack progresses). A series of several recent works shows how to cleverly achieve adaptive security in several such scenarios including generalized selective decryption (Panjwani, TCC ’07 and Fuchsbauer et al., CRYPTO ’15), constrained PRFs (Fuchsbauer et al., ASIACRYPT ’14), and Yao garbled circuits (Jafargholi and Wichs, TCC ’16b). Although the above works expressed vague intuition that they share a common technique, the connection was never made precise. In this work we present a new framework that connects all of these works and allows us to present them in a unified and simplified fashion. Moreover, we use the framework to derive a new result for adaptively secure secret sharing over access structures defined via monotone circuits. We envision that further applications will follow in the future. Underlying our framework is the following simple idea. It is well known that selective security, where the adversary commits to n-bits of information about his future choices, automatically implies adaptive security at the cost of amplifying the adversary’s advantage by a factor of up to 2n. However, in some cases the proof of selective security proceeds via a sequence of hybrids, where each pair of adjacent hybrids locally only requires some smaller partial information consisting of m ≪ n bits. The partial information needed might be completely different between different pairs of hybrids, and if we look across all the hybrids we might rely on the entire n-bit commitment. Nevertheless, the above is sufficient to prove adaptive security, at the cost of amplifying the adversary’s advantage by a factor of only 2m ≪ 2n. In all of our examples using the above framework, the different hybrids are captured by some sort of a graph pebbling game and the amount of information that the adversary needs to commit to in each pair of hybrids is bounded by the maximum number of pebbles in play at any point in time. Therefore, coming up with better strategies for proving adaptive security translates to various pebbling strategies for different types of graphs.
AU - Jafargholi, Zahra
AU - Kamath Hosdurg, Chethan
AU - Klein, Karen
AU - Komargodski, Ilan
AU - Pietrzak, Krzysztof Z
AU - Wichs, Daniel
ED - Katz, Jonathan
ED - Shacham, Hovav
ID - 637
SN - 978-331963687-0
TI - Be adaptive avoid overcommitting
VL - 10401
ER -
TY - CONF
AB - Data-independent Memory Hard Functions (iMHFS) are finding a growing number of applications in security; especially in the domain of password hashing. An important property of a concrete iMHF is specified by fixing a directed acyclic graph (DAG) Gn on n nodes. The quality of that iMHF is then captured by the following two pebbling complexities of Gn: – The parallel cumulative pebbling complexity Π∥cc(Gn) must be as high as possible (to ensure that the amortized cost of computing the function on dedicated hardware is dominated by the cost of memory). – The sequential space-time pebbling complexity Πst(Gn) should be as close as possible to Π∥cc(Gn) (to ensure that using many cores in parallel and amortizing over many instances does not give much of an advantage). In this paper we construct a family of DAGs with best possible parameters in an asymptotic sense, i.e., where Π∥cc(Gn) = Ω(n2/ log(n)) (which matches a known upper bound) and Πst(Gn) is within a constant factor of Π∥cc(Gn). Our analysis relies on a new connection between the pebbling complexity of a DAG and its depth-robustness (DR) – a well studied combinatorial property. We show that high DR is sufficient for high Π∥cc. Alwen and Blocki (CRYPTO’16) showed that high DR is necessary and so, together, these results fully characterize DAGs with high Π∥cc in terms of DR. Complementing these results, we provide new upper and lower bounds on the Π∥cc of several important candidate iMHFs from the literature. We give the first lower bounds on the memory hardness of the Catena and Balloon Hashing functions in a parallel model of computation and we give the first lower bounds of any kind for (a version) of Argon2i. Finally we describe a new class of pebbling attacks improving on those of Alwen and Blocki (CRYPTO’16). By instantiating these attacks we upperbound the Π∥cc of the Password Hashing Competition winner Argon2i and one of the Balloon Hashing functions by O (n1.71). We also show an upper bound of O(n1.625) for the Catena functions and the two remaining Balloon Hashing functions.
AU - Alwen, Joel F
AU - Blocki, Jeremiah
AU - Pietrzak, Krzysztof Z
ED - Coron, Jean-Sébastien
ED - Buus Nielsen, Jesper
ID - 640
SN - 978-331956616-0
TI - Depth-robust graphs and their cumulative memory complexity
VL - 10212
ER -
TY - CONF
AB - We introduce two novel methods for learning parameters of graphical models for image labelling. The following two tasks underline both methods: (i) perturb model parameters based on given features and ground truth labelings, so as to exactly reproduce these labelings as optima of the local polytope relaxation of the labelling problem; (ii) train a predictor for the perturbed model parameters so that improved model parameters can be applied to the labelling of novel data. Our first method implements task (i) by inverse linear programming and task (ii) using a regressor e.g. a Gaussian process. Our second approach simultaneously solves tasks (i) and (ii) in a joint manner, while being restricted to linearly parameterised predictors. Experiments demonstrate the merits of both approaches.
AU - Trajkovska, Vera
AU - Swoboda, Paul
AU - Åström, Freddie
AU - Petra, Stefanie
ED - Lauze, François
ED - Dong, Yiqiu
ED - Bjorholm Dahl, Anders
ID - 641
SN - 978-331958770-7
TI - Graphical model parameter learning by inverse linear programming
VL - 10302
ER -
TY - JOUR
AB - Cauchy problems with SPDEs on the whole space are localized to Cauchy problems on a ball of radius R. This localization reduces various kinds of spatial approximation schemes to finite dimensional problems. The error is shown to be exponentially small. As an application, a numerical scheme is presented which combines the localization and the space and time discretization, and thus is fully implementable.
AU - Gerencser, Mate
AU - Gyöngy, István
ID - 642
IS - 307
JF - Mathematics of Computation
SN - 00255718
TI - Localization errors in solving stochastic partial differential equations in the whole space
VL - 86
ER -
TY - GEN
AB - Synchronous programs are easy to specify because the side effects of an operation are finished by the time the invocation of the operation returns to the caller. Asynchronous programs, on the other hand, are difficult to specify because there are side effects due to pending computation scheduled as a result of the invocation of an operation. They are also difficult to verify because of the large number of possible interleavings of concurrent asynchronous computation threads. We show that specifications and correctness proofs for asynchronous programs can be structured by introducing the fiction, for proof purposes, that intermediate, non-quiescent states of asynchronous operations can be ignored. Then, the task of specification becomes relatively simple and the task of verification can be naturally decomposed into smaller sub-tasks. The sub-tasks iteratively summarize, guided by the structure of an asynchronous program, the atomic effect of non-atomic operations and the synchronous effect of asynchronous operations. This structuring of specifications and proofs corresponds to the introduction of multiple layers of stepwise refinement for asynchronous programs. We present the first proof rule, called synchronization, to reduce asynchronous invocations on a lower layer to synchronous invocations on a higher layer. We implemented our proof method in CIVL and evaluated it on a collection of benchmark programs.
AU - Henzinger, Thomas A
AU - Kragl, Bernhard
AU - Qadeer, Shaz
ID - 6426
SN - 2664-1690
TI - Synchronizing the asynchronous
ER -
TY - JOUR
AB - It has been reported that nicotinamide-overload induces oxidative stress associated with insulin resistance, the key feature of type 2 diabetes mellitus (T2DM). This study aimed to investigate the effects of B vitamins in T2DM. Glucose tolerance tests (GTT) were carried out in adult Sprague-Dawley rats treated with or without cumulative doses of B vitamins. More specifically, insulin tolerance tests (ITT) were also carried out in adult Sprague-Dawley rats treated with or without cumulative doses of Vitamin B3. We found that cumulative Vitamin B1 and Vitamin B3 administration significantly increased the plasma H2O2 levels associated with high insulin levels. Only Vitamin B3 reduced muscular and hepatic glycogen contents. Cumulative administration of nicotinic acid, another form of Vitamin B3, also significantly increased plasma insulin level and H2O2 generation. Moreover, cumulative administration of nicotinic acid or nicotinamide impaired glucose metabolism. This study suggested that excess Vitamin B1 and Vitamin B3 caused oxidative stress and insulin resistance.
AU - Sun, Wuping
AU - Zhai, Ming-Zhu
AU - Zhou, Qian
AU - Qian, Chengrui
AU - Jiang, Changyu
ID - 643
IS - 4
JF - Chinese Journal of Physiology
SN - 03044920
TI - Effects of B vitamins overload on plasma insulin level and hydrogen peroxide generation in rats
VL - 60
ER -
TY - JOUR
AB - An instance of the valued constraint satisfaction problem (VCSP) is given by a finite set of variables, a finite domain of labels, and a sum of functions, each function depending on a subset of the variables. Each function can take finite values specifying costs of assignments of labels to its variables or the infinite value, which indicates an infeasible assignment. The goal is to find an assignment of labels to the variables that minimizes the sum. We study, assuming that P 6= NP, how the complexity of this very general problem depends on the set of functions allowed in the instances, the so-called constraint language. The case when all allowed functions take values in f0;1g corresponds to ordinary CSPs, where one deals only with the feasibility issue, and there is no optimization. This case is the subject of the algebraic CSP dichotomy conjecture predicting for which constraint languages CSPs are tractable (i.e., solvable in polynomial time) and for which they are NP-hard. The case when all allowed functions take only finite values corresponds to a finitevalued CSP, where the feasibility aspect is trivial and one deals only with the optimization issue. The complexity of finite-valued CSPs was fully classified by Thapper and Živný. An algebraic necessary condition for tractability of a general-valued CSP with a fixed constraint language was recently given by Kozik and Ochremiak. As our main result, we prove that if a constraint language satisfies this algebraic necessary condition, and the feasibility CSP (i.e., the problem of deciding whether a given instance has a feasible solution) corresponding to the VCSP with this language is tractable, then the VCSP is tractable. The algorithm is a simple combination of the assumed algorithm for the feasibility CSP and the standard LP relaxation. As a corollary, we obtain that a dichotomy for ordinary CSPs would imply a dichotomy for general-valued CSPs.
AU - Kolmogorov, Vladimir
AU - Krokhin, Andrei
AU - Rolinek, Michal
ID - 644
IS - 3
JF - SIAM Journal on Computing
TI - The complexity of general-valued CSPs
VL - 46
ER -
TY - CONF
AB - Markov decision processes (MDPs) are standard models for probabilistic systems with non-deterministic behaviours. Long-run average rewards provide a mathematically elegant formalism for expressing long term performance. Value iteration (VI) is one of the simplest and most efficient algorithmic approaches to MDPs with other properties, such as reachability objectives. Unfortunately, a naive extension of VI does not work for MDPs with long-run average rewards, as there is no known stopping criterion. In this work our contributions are threefold. (1) We refute a conjecture related to stopping criteria for MDPs with long-run average rewards. (2) We present two practical algorithms for MDPs with long-run average rewards based on VI. First, we show that a combination of applying VI locally for each maximal end-component (MEC) and VI for reachability objectives can provide approximation guarantees. Second, extending the above approach with a simulation-guided on-demand variant of VI, we present an anytime algorithm that is able to deal with very large models. (3) Finally, we present experimental results showing that our methods significantly outperform the standard approaches on several benchmarks.
AU - Ashok, Pranav
AU - Chatterjee, Krishnendu
AU - Daca, Przemyslaw
AU - Kretinsky, Jan
AU - Meggendorfer, Tobias
ED - Majumdar, Rupak
ED - Kunčak, Viktor
ID - 645
SN - 978-331963386-2
TI - Value iteration for long run average reward in markov decision processes
VL - 10426
ER -
TY - CONF
AB - We present a novel convex relaxation and a corresponding inference algorithm for the non-binary discrete tomography problem, that is, reconstructing discrete-valued images from few linear measurements. In contrast to state of the art approaches that split the problem into a continuous reconstruction problem for the linear measurement constraints and a discrete labeling problem to enforce discrete-valued reconstructions, we propose a joint formulation that addresses both problems simultaneously, resulting in a tighter convex relaxation. For this purpose a constrained graphical model is set up and evaluated using a novel relaxation optimized by dual decomposition. We evaluate our approach experimentally and show superior solutions both mathematically (tighter relaxation) and experimentally in comparison to previously proposed relaxations.
AU - Kuske, Jan
AU - Swoboda, Paul
AU - Petra, Stefanie
ED - Lauze, François
ED - Dong, Yiqiu
ED - Bjorholm Dahl, Anders
ID - 646
SN - 978-331958770-7
TI - A novel convex relaxation for non binary discrete tomography
VL - 10302
ER -
TY - CONF
AB - Despite researchers’ efforts in the last couple of decades, reachability analysis is still a challenging problem even for linear hybrid systems. Among the existing approaches, the most practical ones are mainly based on bounded-time reachable set over-approximations. For the purpose of unbounded-time analysis, one important strategy is to abstract the original system and find an invariant for the abstraction. In this paper, we propose an approach to constructing a new kind of abstraction called conic abstraction for affine hybrid systems, and to computing reachable sets based on this abstraction. The essential feature of a conic abstraction is that it partitions the state space of a system into a set of convex polyhedral cones which is derived from a uniform conic partition of the derivative space. Such a set of polyhedral cones is able to cut all trajectories of the system into almost straight segments so that every segment of a reach pipe in a polyhedral cone tends to be straight as well, and hence can be over-approximated tightly by polyhedra using similar techniques as HyTech or PHAVer. In particular, for diagonalizable affine systems, our approach can guarantee to find an invariant for unbounded reachable sets, which is beyond the capability of bounded-time reachability analysis tools. We implemented the approach in a tool and experiments on benchmarks show that our approach is more powerful than SpaceEx and PHAVer in dealing with diagonalizable systems.
AU - Bogomolov, Sergiy
AU - Giacobbe, Mirco
AU - Henzinger, Thomas A
AU - Kong, Hui
ID - 647
SN - 978-331965764-6
TI - Conic abstractions for hybrid systems
VL - 10419
ER -
TY - CONF
AB - Pseudoentropy has found a lot of important applications to cryptography and complexity theory. In this paper we focus on the foundational problem that has not been investigated so far, namely by how much pseudoentropy (the amount seen by computationally bounded attackers) diﬀers from its information-theoretic counterpart (seen by unbounded observers), given certain limits on attacker’s computational power? We provide the following answer for HILL pseudoentropy, which exhibits a threshold behavior around the size exponential in the entropy amount:– If the attacker size (s) and advantage () satisfy s (formula presented) where k is the claimed amount of pseudoentropy, then the pseudoentropy boils down to the information-theoretic smooth entropy. – If s (formula presented) then pseudoentropy could be arbitrarily bigger than the information-theoretic smooth entropy. Besides answering the posted question, we show an elegant application of our result to the complexity theory, namely that it implies the clas-sical result on the existence of functions hard to approximate (due to Pippenger). In our approach we utilize non-constructive techniques: the duality of linear programming and the probabilistic method.
AU - Skórski, Maciej
ED - Jäger, Gerhard
ED - Steila, Silvia
ID - 648
SN - 978-331955910-0
TI - On the complexity of breaking pseudoentropy
VL - 10185
ER -
TY - CONF
AB - In this work we present a short and unified proof for the Strong and Weak Regularity Lemma, based on the cryptographic tech-nique called low-complexity approximations. In short, both problems reduce to a task of finding constructively an approximation for a certain target function under a class of distinguishers (test functions), where dis-tinguishers are combinations of simple rectangle-indicators. In our case these approximations can be learned by a simple iterative procedure, which yields a unified and simple proof, achieving for any graph with density d and any approximation parameter the partition size. The novelty in our proof is: (a) a simple approach which yields both strong and weaker variant, and (b) improvements when d = o(1). At an abstract level, our proof can be seen a refinement and simplification of the “analytic” proof given by Lovasz and Szegedy.
AU - Skórski, Maciej
ED - Jäger, Gerhard
ED - Steila, Silvia
ID - 650
SN - 03029743
TI - A cryptographic view of regularity lemmas: Simpler unified proofs and refined bounds
VL - 10185
ER -
TY - JOUR
AB - Superhydrophobic surfaces reduce the frictional drag between water and solid materials, but this effect is often temporary. The realization of sustained drag reduction has applications for water vehicles and pipeline flows.
AU - Hof, Björn
ID - 651
IS - 7636
JF - Nature
SN - 00280836
TI - Fluid dynamics: Water flows out of touch
VL - 541
ER -