TY - JOUR
AB - Animal social networks are shaped by multiple selection pressures, including the need to ensure efficient communication and functioning while simultaneously limiting disease transmission. Social animals could potentially further reduce epidemic risk by altering their social networks in the presence of pathogens, yet there is currently no evidence for such pathogen-triggered responses. We tested this hypothesis experimentally in the ant Lasius niger using a combination of automated tracking, controlled pathogen exposure, transmission quantification, and temporally explicit simulations. Pathogen exposure induced behavioral changes in both exposed ants and their nestmates, which helped contain the disease by reinforcing key transmission-inhibitory properties of the colony's contact network. This suggests that social network plasticity in response to pathogens is an effective strategy for mitigating the effects of disease in social groups.
AU - Stroeymeyt, Nathalie
AU - Grasse, Anna V
AU - Crespi, Alessandro
AU - Mersch, Danielle
AU - Cremer, Sylvia
AU - Keller, Laurent
ID - 7
IS - 6417
JF - Science
SN - 10959203
TI - Social network plasticity decreases disease transmission in a eusocial insect
VL - 362
ER -
TY - DATA
AB - Supporting material to the article
STATISTICAL MECHANICS FOR METABOLIC NETWORKS IN STEADY-STATE GROWTH
boundscoli.dat
Flux Bounds of the E. coli catabolic core model iAF1260 in a glucose limited minimal medium.
polcoli.dat
Matrix enconding the polytope of the E. coli catabolic core model iAF1260 in a glucose limited minimal medium,
obtained from the soichiometric matrix by standard linear algebra (reduced row echelon form).
ellis.dat
Approximate Lowner-John ellipsoid rounding the polytope of the E. coli catabolic core model iAF1260 in a glucose limited minimal medium
obtained with the Lovasz method.
point0.dat
Center of the approximate Lowner-John ellipsoid rounding the polytope of the E. coli catabolic core model iAF1260 in a glucose limited minimal medium
obtained with the Lovasz method.
lovasz.cpp
This c++ code file receives in input the polytope of the feasible steady states of a metabolic network,
(matrix and bounds), and it gives in output an approximate Lowner-John ellipsoid rounding the polytope
with the Lovasz method
NB inputs are referred by defaults to the catabolic core of the E.Coli network iAF1260.
For further details we refer to PLoS ONE 10.4 e0122670 (2015).
sampleHRnew.cpp
This c++ code file receives in input the polytope of the feasible steady states of a metabolic network,
(matrix and bounds), the ellipsoid rounding the polytope, a point inside and
it gives in output a max entropy sampling at fixed average growth rate
of the steady states by performing an Hit-and-Run Monte Carlo Markov chain.
NB inputs are referred by defaults to the catabolic core of the E.Coli network iAF1260.
For further details we refer to PLoS ONE 10.4 e0122670 (2015).
AU - De Martino, Daniele
AU - Tkacik, Gasper
ID - 5587
KW - metabolic networks
KW - e.coli core
KW - maximum entropy
KW - monte carlo markov chain sampling
KW - ellipsoidal rounding
TI - Supporting materials "STATISTICAL MECHANICS FOR METABOLIC NETWORKS IN STEADY-STATE GROWTH"
ER -
TY - GEN
AB - Dataset for manuscript 'Social network plasticity decreases disease transmission in a eusocial insect'
Compared to previous versions: - raw image files added
- correction of URLs within README.txt file
AU - Stroeymeyt, Nathalie
AU - Grasse, Anna V
AU - Crespi, Alessandro
AU - Mersch, Danielle
AU - Cremer, Sylvia
AU - Keller, Laurent
ID - 13055
TI - Social network plasticity decreases disease transmission in a eusocial insect
ER -
TY - CONF
AB - Graph games played by two players over finite-state graphs are central in many problems in computer science. In particular, graph games with ω -regular winning conditions, specified as parity objectives, which can express properties such as safety, liveness, fairness, are the basic framework for verification and synthesis of reactive systems. The decisions for a player at various states of the graph game are represented as strategies. While the algorithmic problem for solving graph games with parity objectives has been widely studied, the most prominent data-structure for strategy representation in graph games has been binary decision diagrams (BDDs). However, due to the bit-level representation, BDDs do not retain the inherent flavor of the decisions of strategies, and are notoriously hard to minimize to obtain succinct representation. In this work we propose decision trees for strategy representation in graph games. Decision trees retain the flavor of decisions of strategies and allow entropy-based minimization to obtain succinct trees. However, decision trees work in settings (e.g., probabilistic models) where errors are allowed, and overfitting of data is typically avoided. In contrast, for strategies in graph games no error is allowed, and the decision tree must represent the entire strategy. We develop new techniques to extend decision trees to overcome the above obstacles, while retaining the entropy-based techniques to obtain succinct trees. We have implemented our techniques to extend the existing decision tree solvers. We present experimental results for problems in reactive synthesis to show that decision trees provide a much more efficient data-structure for strategy representation as compared to BDDs.
AU - Brázdil, Tomáš
AU - Chatterjee, Krishnendu
AU - Kretinsky, Jan
AU - Toman, Viktor
ID - 297
TI - Strategy representation by decision trees in reactive synthesis
VL - 10805
ER -
TY - CONF
AB - Given a model and a specification, the fundamental model-checking problem asks for algorithmic verification of whether the model satisfies the specification. We consider graphs and Markov decision processes (MDPs), which are fundamental models for reactive systems. One of the very basic specifications that arise in verification of reactive systems is the strong fairness (aka Streett) objective. Given different types of requests and corresponding grants, the objective requires that for each type, if the request event happens infinitely often, then the corresponding grant event must also happen infinitely often. All ω -regular objectives can be expressed as Streett objectives and hence they are canonical in verification. To handle the state-space explosion, symbolic algorithms are required that operate on a succinct implicit representation of the system rather than explicitly accessing the system. While explicit algorithms for graphs and MDPs with Streett objectives have been widely studied, there has been no improvement of the basic symbolic algorithms. The worst-case numbers of symbolic steps required for the basic symbolic algorithms are as follows: quadratic for graphs and cubic for MDPs. In this work we present the first sub-quadratic symbolic algorithm for graphs with Streett objectives, and our algorithm is sub-quadratic even for MDPs. Based on our algorithmic insights we present an implementation of the new symbolic approach and show that it improves the existing approach on several academic benchmark examples.
AU - Chatterjee, Krishnendu
AU - Henzinger, Monika H
AU - Loitzenbauer, Veronika
AU - Oraee, Simin
AU - Toman, Viktor
ID - 141
TI - Symbolic algorithms for graphs and Markov decision processes with fairness objectives
VL - 10982
ER -
TY - CONF
AB - Memory-hard functions (MHF) are functions whose evaluation cost is dominated by memory cost. MHFs are egalitarian, in the sense that evaluating them on dedicated hardware (like FPGAs or ASICs) is not much cheaper than on off-the-shelf hardware (like x86 CPUs). MHFs have interesting cryptographic applications, most notably to password hashing and securing blockchains.
Alwen and Serbinenko [STOC’15] define the cumulative memory complexity (cmc) of a function as the sum (over all time-steps) of the amount of memory required to compute the function. They advocate that a good MHF must have high cmc. Unlike previous notions, cmc takes into account that dedicated hardware might exploit amortization and parallelism. Still, cmc has been critizised as insufficient, as it fails to capture possible time-memory trade-offs; as memory cost doesn’t scale linearly, functions with the same cmc could still have very different actual hardware cost.
In this work we address this problem, and introduce the notion of sustained-memory complexity, which requires that any algorithm evaluating the function must use a large amount of memory for many steps. We construct functions (in the parallel random oracle model) whose sustained-memory complexity is almost optimal: our function can be evaluated using n steps and O(n/log(n)) memory, in each step making one query to the (fixed-input length) random oracle, while any algorithm that can make arbitrary many parallel queries to the random oracle, still needs Ω(n/log(n)) memory for Ω(n) steps.
As has been done for various notions (including cmc) before, we reduce the task of constructing an MHFs with high sustained-memory complexity to proving pebbling lower bounds on DAGs. Our main technical contribution is the construction is a family of DAGs on n nodes with constant indegree with high “sustained-space complexity”, meaning that any parallel black-pebbling strategy requires Ω(n/log(n)) pebbles for at least Ω(n) steps.
Along the way we construct a family of maximally “depth-robust” DAGs with maximum indegree O(logn) , improving upon the construction of Mahmoody et al. [ITCS’13] which had maximum indegree O(log2n⋅
AU - Alwen, Joel F
AU - Blocki, Jeremiah
AU - Pietrzak, Krzysztof Z
ID - 298
TI - Sustained space complexity
VL - 10821
ER -
TY - JOUR
AB - Wheat (Triticum ssp.) is one of the most important human food sources. However, this crop is very sensitive to temperature changes. Specifically, processes during wheat leaf, flower, and seed development and photosynthesis, which all contribute to the yield of this crop, are affected by high temperature. While this has to some extent been investigated on physiological, developmental, and molecular levels, very little is known about early signalling events associated with an increase in temperature. Phosphorylation-mediated signalling mechanisms, which are quick and dynamic, are associated with plant growth and development, also under abiotic stress conditions. Therefore, we probed the impact of a short-term and mild increase in temperature on the wheat leaf and spikelet phosphoproteome. In total, 3822 (containing 5178 phosphosites) and 5581 phosphopeptides (containing 7023 phosphosites) were identified in leaf and spikelet samples, respectively. Following statistical analysis, the resulting data set provides the scientific community with a first large-scale plant phosphoproteome under the control of higher ambient temperature. This community resource on the high temperature-mediated wheat phosphoproteome will be valuable for future studies. Our analyses also revealed a core set of common proteins between leaf and spikelet, suggesting some level of conserved regulatory mechanisms. Furthermore, we observed temperature-regulated interconversion of phosphoforms, which probably impacts protein activity.
AU - Vu, Lam
AU - Zhu, Tingting
AU - Verstraeten, Inge
AU - Van De Cotte, Brigitte
AU - Gevaert, Kris
AU - De Smet, Ive
ID - 36
IS - 19
JF - Journal of Experimental Botany
TI - Temperature-induced changes in the wheat phosphoproteome reveal temperature-regulated interconversion of phosphoforms
VL - 69
ER -
TY - JOUR
AB - Three-dimensional (3D) super-resolution microscopy technique structured illumination microscopy (SIM) imaging of dendritic spines along the dendrite has not been previously performed in fixed tissues, mainly due to deterioration of the stripe pattern of the excitation laser induced by light scattering and optical aberrations. To address this issue and solve these optical problems, we applied a novel clearing reagent, LUCID, to fixed brains. In SIM imaging, the penetration depth and the spatial resolution were improved in LUCID-treated slices, and 160-nm spatial resolution was obtained in a large portion of the imaging volume on a single apical dendrite. Furthermore, in a morphological analysis of spine heads of layer V pyramidal neurons (L5PNs) in the medial prefrontal cortex (mPFC) of chronic dexamethasone (Dex)-treated mice, SIM imaging revealed an altered distribution of spine forms that could not be detected by high-NA confocal imaging. Thus, super-resolution SIM imaging represents a promising high-throughput method for revealing spine morphologies in single dendrites.
AU - Sawada, Kazuaki
AU - Kawakami, Ryosuke
AU - Shigemoto, Ryuichi
AU - Nemoto, Tomomi
ID - 326
IS - 9
JF - European Journal of Neuroscience
TI - Super resolution structural analysis of dendritic spines using three-dimensional structured illumination microscopy in cleared mouse brain slices
VL - 47
ER -
TY - JOUR
AB - Retroviruses assemble and bud from infected cells in an immature form and require proteolytic maturation for infectivity. The CA (capsid) domains of the Gag polyproteins assemble a protein lattice as a truncated sphere in the immature virion. Proteolytic cleavage of Gag induces dramatic structural rearrangements; a subset of cleaved CA subsequently assembles into the mature core, whose architecture varies among retroviruses. Murine leukemia virus (MLV) is the prototypical γ-retrovirus and serves as the basis of retroviral vectors, but the structure of the MLV CA layer is unknown. Here we have combined X-ray crystallography with cryoelectron tomography to determine the structures of immature and mature MLV CA layers within authentic viral particles. This reveals the structural changes associated with maturation, and, by comparison with HIV-1, uncovers conserved and variable features. In contrast to HIV-1, most MLV CA is used for assembly of the mature core, which adopts variable, multilayered morphologies and does not form a closed structure. Unlike in HIV-1, there is similarity between protein–protein interfaces in the immature MLV CA layer and those in the mature CA layer, and structural maturation of MLV could be achieved through domain rotations that largely maintain hexameric interactions. Nevertheless, the dramatic architectural change on maturation indicates that extensive disassembly and reassembly are required for mature core growth. The core morphology suggests that wrapping of the genome in CA sheets may be sufficient to protect the MLV ribonucleoprotein during cell entry.
AU - Qu, Kun
AU - Glass, Bärbel
AU - Doležal, Michal
AU - Schur, Florian
AU - Murciano, Brice
AU - Rein, Alan
AU - Rumlová, Michaela
AU - Ruml, Tomáš
AU - Kräusslich, Hans-Georg
AU - Briggs, John A. G.
ID - 5770
IS - 50
JF - Proceedings of the National Academy of Sciences
SN - 00278424
TI - Structure and architecture of immature and mature murine leukemia virus capsids
VL - 115
ER -
TY - JOUR
AB - Synthesis is the automated construction of a system from its specification. In real life, hardware and software systems are rarely constructed from scratch. Rather, a system is typically constructed from a library of components. Lustig and Vardi formalized this intuition and studied LTL synthesis from component libraries. In real life, designers seek optimal systems. In this paper we add optimality considerations to the setting. We distinguish between quality considerations (for example, size - the smaller a system is, the better it is), and pricing (for example, the payment to the company who manufactured the component). We study the problem of designing systems with minimal quality-cost and price. A key point is that while the quality cost is individual - the choices of a designer are independent of choices made by other designers that use the same library, pricing gives rise to a resource-allocation game - designers that use the same component share its price, with the share being proportional to the number of uses (a component can be used several times in a design). We study both closed and open settings, and in both we solve the problem of finding an optimal design. In a setting with multiple designers, we also study the game-theoretic problems of the induced resource-allocation game.
AU - Avni, Guy
AU - Kupferman, Orna
ID - 608
JF - Theoretical Computer Science
TI - Synthesis from component libraries with costs
VL - 712
ER -
TY - JOUR
AB - Although dopamine receptors D1 and D2 play key roles in hippocampal function, their synaptic localization within the hippocampus has not been fully elucidated. In order to understand precise functions of pre- or postsynaptic dopamine receptors (DRs), the development of protocols to differentiate pre- and postsynaptic DRs is essential. So far, most studies on determination and quantification of DRs did not discriminate between subsynaptic localization. Therefore, the aim of the study was to generate a robust workflow for the localization of DRs. This work provides the basis for future work on hippocampal DRs, in light that DRs may have different functions at pre- or postsynaptic sites. Synaptosomes from rat hippocampi isolated by a sucrose gradient protocol were prepared for super-resolution direct stochastic optical reconstruction microscopy (dSTORM) using Bassoon as a presynaptic zone and Homer1 as postsynaptic density marker. Direct labeling of primary validated antibodies against dopamine receptors D1 (D1R) and D2 (D2R) with Alexa Fluor 594 enabled unequivocal assignment of D1R and D2R to both, pre- and postsynaptic sites. D1R immunoreactivity clusters were observed within the presynaptic active zone as well as at perisynaptic sites at the edge of the presynaptic active zone. The results may be useful for the interpretation of previous studies and the design of future work on DRs in the hippocampus. Moreover, the reduction of the complexity of brain tissue by the use of synaptosomal preparations and dSTORM technology may represent a useful tool for synaptic localization of brain proteins.
AU - Miklosi, Andras
AU - Del Favero, Giorgia
AU - Bulat, Tanja
AU - Höger, Harald
AU - Shigemoto, Ryuichi
AU - Marko, Doris
AU - Lubec, Gert
ID - 705
IS - 6
JF - Molecular Neurobiology
TI - Super resolution microscopical localization of dopamine receptors 1 and 2 in rat hippocampal synaptosomes
VL - 55
ER -
TY - JOUR
AB - Land plants evolved from charophytic algae, among which Charophyceae possess the most complex body plans. We present the genome of Chara braunii; comparison of the genome to those of land plants identified evolutionary novelties for plant terrestrialization and land plant heritage genes. C. braunii employs unique xylan synthases for cell wall biosynthesis, a phragmoplast (cell separation) mechanism similar to that of land plants, and many phytohormones. C. braunii plastids are controlled via land-plant-like retrograde signaling, and transcriptional regulation is more elaborate than in other algae. The morphological complexity of this organism may result from expanded gene families, with three cases of particular note: genes effecting tolerance to reactive oxygen species (ROS), LysM receptor-like kinases, and transcription factors (TFs). Transcriptomic analysis of sexual reproductive structures reveals intricate control by TFs, activity of the ROS gene network, and the ancestral use of plant-like storage and stress protection proteins in the zygote.
AU - Nishiyama, Tomoaki
AU - Sakayama, Hidetoshi
AU - De Vries, Jan
AU - Buschmann, Henrik
AU - Saint Marcoux, Denis
AU - Ullrich, Kristian
AU - Haas, Fabian
AU - Vanderstraeten, Lisa
AU - Becker, Dirk
AU - Lang, Daniel
AU - Vosolsobě, Stanislav
AU - Rombauts, Stephane
AU - Wilhelmsson, Per
AU - Janitza, Philipp
AU - Kern, Ramona
AU - Heyl, Alexander
AU - Rümpler, Florian
AU - Calderón Villalobos, Luz
AU - Clay, John
AU - Skokan, Roman
AU - Toyoda, Atsushi
AU - Suzuki, Yutaka
AU - Kagoshima, Hiroshi
AU - Schijlen, Elio
AU - Tajeshwar, Navindra
AU - Catarino, Bruno
AU - Hetherington, Alexander
AU - Saltykova, Assia
AU - Bonnot, Clemence
AU - Breuninger, Holger
AU - Symeonidi, Aikaterini
AU - Radhakrishnan, Guru
AU - Van Nieuwerburgh, Filip
AU - Deforce, Dieter
AU - Chang, Caren
AU - Karol, Kenneth
AU - Hedrich, Rainer
AU - Ulvskov, Peter
AU - Glöckner, Gernot
AU - Delwiche, Charles
AU - Petrášek, Jan
AU - Van De Peer, Yves
AU - Friml, Jirí
AU - Beilby, Mary
AU - Dolan, Liam
AU - Kohara, Yuji
AU - Sugano, Sumio
AU - Fujiyama, Asao
AU - Delaux, Pierre Marc
AU - Quint, Marcel
AU - Theissen, Gunter
AU - Hagemann, Martin
AU - Harholt, Jesper
AU - Dunand, Christophe
AU - Zachgo, Sabine
AU - Langdale, Jane
AU - Maumus, Florian
AU - Van Der Straeten, Dominique
AU - Gould, Sven B
AU - Rensing, Stefan
ID - 148
IS - 2
JF - Cell
TI - The Chara genome: Secondary complexity and implications for plant terrestrialization
VL - 174
ER -
TY - JOUR
AB - The ability to adapt growth and development to temperature variations is crucial to generate plant varieties resilient to predicted temperature changes. However, the mechanisms underlying plant response to progressive increases in temperature have just started to be elucidated. Here, we report that the Cyclin-dependent Kinase G1 (CDKG1) is a central element in a thermo-sensitive mRNA splicing cascade that transduces changes in ambient temperature into differential expression of the fundamental spliceosome component, ATU2AF65A. CDKG1 is alternatively spliced in a temperature-dependent manner. We found that this process is partly dependent on both the Cyclin-dependent Kinase G2 (CDKG2) and the interacting co-factor CYCLIN L1 resulting in two distinct messenger RNAs. Relative abundance of both CDKG1 transcripts correlates with ambient temperature and possibly with different expression levels of the associated protein isoforms. Both CDKG1 alternative transcripts are necessary to fully complement the expression of ATU2AF65A across the temperature range. Our data support a previously unidentified temperature-dependent mechanism based on the alternative splicing of CDKG1 and regulated by CDKG2 and CYCLIN L1. We propose that changes in ambient temperature affect the relative abundance of CDKG1 transcripts and this in turn translates into differential CDKG1 protein expression coordinating the alternative splicing of ATU2AF65A. This article is protected by copyright. All rights reserved.
AU - Cavallari, Nicola
AU - Nibau, Candida
AU - Fuchs, Armin
AU - Dadarou, Despoina
AU - Barta, Andrea
AU - Doonan, John
ID - 403
IS - 6
JF - The Plant Journal
TI - The cyclin‐dependent kinase G group defines a thermo‐sensitive alternative splicing circuit modulating the expression of Arabidopsis ATU 2AF 65A
VL - 94
ER -
TY - CONF
AB - Imprecision in timing can sometimes be beneficial: Metric interval temporal logic (MITL), disabling the expression of punctuality constraints, was shown to translate to timed automata, yielding an elementary decision procedure. We show how this principle extends to other forms of dense-time specification using regular expressions. By providing a clean, automaton-based formal framework for non-punctual languages, we are able to recover and extend several results in timed systems. Metric interval regular expressions (MIRE) are introduced, providing regular expressions with non-singular duration constraints. We obtain that MIRE are expressively complete relative to a class of one-clock timed automata, which can be determinized using additional clocks. Metric interval dynamic logic (MIDL) is then defined using MIRE as temporal modalities. We show that MIDL generalizes known extensions of MITL, while translating to timed automata at comparable cost.
AU - Ferrere, Thomas
ID - 156
TI - The compound interest in relaxing punctuality
VL - 10951
ER -
TY - JOUR
AB - The biotrophic pathogen Ustilago maydis, the causative agent of corn smut disease, infects one of the most important crops worldwide – Zea mays. To successfully colonize its host, U. maydis secretes proteins, known as effectors, that suppress plant defense responses and facilitate the establishment of biotrophy. In this work, we describe the U. maydis effector protein Cce1. Cce1 is essential for virulence and is upregulated during infection. Through microscopic analysis and in vitro assays, we show that Cce1 is secreted from hyphae during filamentous growth of the fungus. Strikingly, Δcce1 mutants are blocked at early stages of infection and induce callose deposition as a plant defense response. Cce1 is highly conserved among smut fungi and the Ustilago bromivora ortholog complemented the virulence defect of the SG200Δcce1 deletion strain. These data indicate that Cce1 is a core effector with apoplastic localization that is essential for U. maydis to infect its host.
AU - Seitner, Denise
AU - Uhse, Simon
AU - Gallei, Michelle C
AU - Djamei, Armin
ID - 104
IS - 10
JF - Molecular Plant Pathology
TI - The core effector Cce1 is required for early infection of maize by Ustilago maydis
VL - 19
ER -
TY - JOUR
AB - Hanemaaijer et al. (Molecular Ecology, 27, 2018) describe the genetic consequences of the introgression of an insecticide resistance allele into a mosquito population. Linked alleles initially increased, but many of these later declined. It is hard to determine whether this decline was due to counter‐selection, rather than simply to chance.
AU - Barton, Nicholas H
ID - 40
IS - 24
JF - Molecular Ecology
SN - 1365294X
TI - The consequences of an introgression event
VL - 27
ER -
TY - JOUR
AB - In zebrafish larvae, it is the cell type that determines how the cell responds to a chemokine signal.
AU - Alanko, Jonna H
AU - Sixt, Michael K
ID - 5861
JF - eLife
SN - 2050084X
TI - The cell sets the tone
VL - 7
ER -
TY - JOUR
AB - Genome-scale diversity data are increasingly available in a variety of biological systems, and can be used to reconstruct the past evolutionary history of species divergence. However, extracting the full demographic information from these data is not trivial, and requires inferential methods that account for the diversity of coalescent histories throughout the genome. Here, we evaluate the potential and limitations of one such approach. We reexamine a well-known system of mussel sister species, using the joint site frequency spectrum (jSFS) of synonymousmutations computed either fromexome capture or RNA-seq, in an Approximate Bayesian Computation (ABC) framework. We first assess the best sampling strategy (number of: individuals, loci, and bins in the jSFS), and show that model selection is robust to variation in the number of individuals and loci. In contrast, different binning choices when summarizing the jSFS, strongly affect the results: including classes of low and high frequency shared polymorphisms can more effectively reveal recent migration events. We then take advantage of the flexibility of ABC to compare more realistic models of speciation, including variation in migration rates through time (i.e., periodic connectivity) and across genes (i.e., genome-wide heterogeneity in migration rates). We show that these models were consistently selected as the most probable, suggesting that mussels have experienced a complex history of gene flow during divergence and that the species boundary is semi-permeable. Our work provides a comprehensive evaluation of ABC demographic inference in mussels based on the coding jSFS, and supplies guidelines for employing different sequencing techniques and sampling strategies. We emphasize, perhaps surprisingly, that inferences are less limited by the volume of data, than by the way in which they are analyzed.
AU - Fraisse, Christelle
AU - Roux, Camille
AU - Gagnaire, Pierre
AU - Romiguier, Jonathan
AU - Faivre, Nicolas
AU - Welch, John
AU - Bierne, Nicolas
ID - 139
IS - 7
JF - PeerJ
TI - The divergence history of European blue mussel species reconstructed from Approximate Bayesian Computation: The effects of sequencing techniques and sampling strategies
VL - 2018
ER -
TY - JOUR
AB - The trafficking of subcellular cargos in eukaryotic cells crucially depends on vesicle budding, a process mediated by ARF-GEFs (ADP-ribosylation factor guanine nucleotide exchange factors). In plants, ARF-GEFs play essential roles in endocytosis, vacuolar trafficking, recycling, secretion, and polar trafficking. Moreover, they are important for plant development, mainly through controlling the polar subcellular localization of PIN-FORMED (PIN) transporters of the plant hormone auxin. Here, using a chemical genetics screen in Arabidopsis thaliana, we identified Endosidin 4 (ES4), an inhibitor of eukaryotic ARF-GEFs. ES4 acts similarly to and synergistically with the established ARF-GEF inhibitor Brefeldin A and has broad effects on intracellular trafficking, including endocytosis, exocytosis, and vacuolar targeting. Additionally, Arabidopsis and yeast (Sacharomyces cerevisiae) mutants defective in ARF-GEF show altered sensitivity to ES4. ES4 interferes with the activation-based membrane association of the ARF1 GTPases, but not of their mutant variants that are activated independently of ARF-GEF activity. Biochemical approaches and docking simulations confirmed that ES4 specifically targets the SEC7 domain-containing ARF-GEFs. These observations collectively identify ES4 as a chemical tool enabling the study of ARF-GEF-mediated processes, including ARF-GEF-mediated plant development.
AU - Kania, Urszula
AU - Nodzyński, Tomasz
AU - Lu, Qing
AU - Hicks, Glenn R
AU - Nerinckx, Wim
AU - Mishev, Kiril
AU - Peurois, Francois
AU - Cherfils, Jacqueline
AU - De, Rycke Riet Maria
AU - Grones, Peter
AU - Robert, Stéphanie
AU - Russinova, Eugenia
AU - Friml, Jirí
ID - 147
IS - 10
JF - The Plant Cell
SN - 1040-4651
TI - The inhibitor Endosidin 4 targets SEC7 domain-type ARF GTPase exchange factors and interferes with sub cellular trafficking in eukaryotes
VL - 30
ER -
TY - JOUR
AB - The root cap protects the stem cell niche of angiosperm roots from damage. In Arabidopsis, lateral root cap (LRC) cells covering the meristematic zone are regularly lost through programmed cell death, while the outermost layer of the root cap covering the tip is repeatedly sloughed. Efficient coordination with stem cells producing new layers is needed to maintain a constant size of the cap. We present a signalling pair, the peptide IDA-LIKE1 (IDL1) and its receptor HAESA-LIKE2 (HSL2), mediating such communication. Live imaging over several days characterized this process from initial fractures in LRC cell files to full separation of a layer. Enhanced expression of IDL1 in the separating root cap layers resulted in increased frequency of sloughing, balanced with generation of new layers in a HSL2-dependent manner. Transcriptome analyses linked IDL1-HSL2 signalling to the transcription factors BEARSKIN1/2 and genes associated with programmed cell death. Mutations in either IDL1 or HSL2 slowed down cell division, maturation and separation. Thus, IDL1-HSL2 signalling potentiates dynamic regulation of the homeostatic balance between stem cell division and sloughing activity.
AU - Shi, Chun Lin
AU - Von Wangenheim, Daniel
AU - Herrmann, Ullrich
AU - Wildhagen, Mari
AU - Kulik, Ivan
AU - Kopf, Andreas
AU - Ishida, Takashi
AU - Olsson, Vilde
AU - Anker, Mari Kristine
AU - Albert, Markus
AU - Butenko, Melinka A
AU - Felix, Georg
AU - Sawa, Shinichiro
AU - Claassen, Manfred
AU - Friml, Jirí
AU - Aalen, Reidunn B
ID - 146
IS - 8
JF - Nature Plants
TI - The dynamics of root cap sloughing in Arabidopsis is regulated by peptide signalling
VL - 4
ER -
TY - JOUR
AB - People sometimes make their admirable deeds and accomplishments hard to spot, such as by giving anonymously or avoiding bragging. Such ‘buried’ signals are hard to reconcile with standard models of signalling or indirect reciprocity, which motivate costly pro-social behaviour by reputational gains. To explain these phenomena, we design a simple game theory model, which we call the signal-burying game. This game has the feature that senders can bury their signal by deliberately reducing the probability of the signal being observed. If the signal is observed, however, it is identified as having been buried. We show under which conditions buried signals can be maintained, using static equilibrium concepts and calculations of the evolutionary dynamics. We apply our analysis to shed light on a number of otherwise puzzling social phenomena, including modesty, anonymous donations, subtlety in art and fashion, and overeagerness.
AU - Hoffman, Moshe
AU - Hilbe, Christian
AU - Nowak, Martin
ID - 293
JF - Nature Human Behaviour
TI - The signal-burying game can explain why we obscure positive traits and good deeds
VL - 2
ER -
TY - JOUR
AB - The derivation of effective evolution equations is central to the study of non-stationary quantum many-body systems, and widely used in contexts such as superconductivity, nuclear physics, Bose–Einstein condensation and quantum chemistry. We reformulate the Dirac–Frenkel approximation principle in terms of reduced density matrices and apply it to fermionic and bosonic many-body systems. We obtain the Bogoliubov–de Gennes and Hartree–Fock–Bogoliubov equations, respectively. While we do not prove quantitative error estimates, our formulation does show that the approximation is optimal within the class of quasifree states. Furthermore, we prove well-posedness of the Bogoliubov–de Gennes equations in energy space and discuss conserved quantities
AU - Benedikter, Niels P
AU - Sok, Jérémy
AU - Solovej, Jan
ID - 455
IS - 4
JF - Annales Henri Poincare
TI - The Dirac–Frenkel principle for reduced density matrices and the Bogoliubov–de Gennes equations
VL - 19
ER -
TY - JOUR
AB - The interface of physics and biology pro-vides a fruitful environment for generatingnew concepts and exciting ways forwardto understanding living matter. Examplesof successful studies include the estab-lishment and readout of morphogen gra-dients during development, signal pro-cessing in protein and genetic networks,the role of ﬂuctuations in determining thefates of cells and tissues, and collectiveeffects in proteins and in tissues. It is nothard to envision that signiﬁcant further ad-vances will translate to societal beneﬁtsby initiating the development of new de-vices and strategies for curing disease.However, research at the interface posesvarious challenges, in particular for youngscientists, and current institutions arerarely designed to facilitate such scientiﬁcprograms. In this Letter, we propose aninternational initiative that addressesthese challenges through the establish-ment of a worldwide network of platformsfor cross-disciplinary training and incuba-tors for starting new collaborations.
AU - Bauer, Guntram
AU - Fakhri, Nikta
AU - Kicheva, Anna
AU - Kondev, Jané
AU - Kruse, Karsten
AU - Noji, Hiroyuki
AU - Riveline, Daniel
AU - Saunders, Timothy
AU - Thatta, Mukund
AU - Wieschaus, Eric
ID - 314
IS - 4
JF - Cell Systems
TI - The science of living matter for tomorrow
VL - 6
ER -
TY - JOUR
AB - We re-examine the model of Kirkpatrick and Barton for the spread of an inversion into a local population. This model assumes that local selection maintains alleles at two or more loci, despite immigration of alternative alleles at these loci from another population. We show that an inversion is favored because it prevents the breakdown of linkage disequilibrium generated by migration; the selective advantage of an inversion is proportional to the amount of recombination between the loci involved, as in other cases where inversions are selected for. We derive expressions for the rate of spread of an inversion; when the loci covered by the inversion are tightly linked, these conditions deviate substantially from those proposed previously, and imply that an inversion can then have only a small advantage.
AU - Charlesworth, Brian
AU - Barton, Nicholas H
ID - 565
IS - 1
JF - Genetics
TI - The spread of an inversion with migration and selection
VL - 208
ER -
TY - JOUR
AB - We prove that in Thomas–Fermi–Dirac–von Weizsäcker theory, a nucleus of charge Z > 0 can bind at most Z + C electrons, where C is a universal constant. This result is obtained through a comparison with Thomas-Fermi theory which, as a by-product, gives bounds on the screened nuclear potential and the radius of the minimizer. A key ingredient of the proof is a novel technique to control the particles in the exterior region, which also applies to the liquid drop model with a nuclear background potential.
AU - Frank, Rupert
AU - Phan Thanh, Nam
AU - Van Den Bosch, Hanne
ID - 446
IS - 3
JF - Communications on Pure and Applied Mathematics
TI - The ionization conjecture in Thomas–Fermi–Dirac–von Weizsäcker theory
VL - 71
ER -
TY - JOUR
AB - In this issue of GENETICS, a new method for detecting natural selection on polygenic traits is developed and applied to sev- eral human examples ( Racimo et al. 2018 ). By de fi nition, many loci contribute to variation in polygenic traits, and a challenge for evolutionary ge neticists has been that these traits can evolve by small, nearly undetectable shifts in allele frequencies across each of many, typically unknown, loci. Recently, a helpful remedy has arisen. Genome-wide associ- ation studies (GWAS) have been illuminating sets of loci that can be interrogated jointly for c hanges in allele frequencies. By aggregating small signal s of change across many such loci, directional natural selection is now in principle detect- able using genetic data, even for highly polygenic traits. This is an exciting arena of progress – with these methods, tests can be made for selection associated with traits, and we can now study selection in what may be its most prevalent mode. The continuing fast pace of GWAS publications suggest there will be many more polygenic tests of selection in the near future, as every new GWAS is an opportunity for an accom- panying test of polygenic selection. However, it is important to be aware of complications th at arise in interpretation, especially given that these studies may easily be misinter- preted both in and outside the evolutionary genetics commu- nity. Here, we provide context for understanding polygenic tests and urge caution regarding how these results are inter- preted and reported upon more broadly.
AU - Novembre, John
AU - Barton, Nicholas H
ID - 430
IS - 4
JF - Genetics
TI - Tread lightly interpreting polygenic tests of selection
VL - 208
ER -
TY - JOUR
AB - Sex-biased genes are central to the study of sexual selection, sexual antagonism, and sex chromosome evolution. We describe a comprehensive de novo assembled transcriptome in the common frog Rana temporaria based on five developmental stages and three adult tissues from both sexes, obtained from a population with karyotypically homomorphic but genetically differentiated sex chromosomes. This allows the study of sex-biased gene expression throughout development, and its effect on the rate of gene evolution while accounting for pleiotropic expression, which is known to negatively correlate with the evolutionary rate. Overall, sex-biased genes had little overlap among developmental stages and adult tissues. Late developmental stages and gonad tissues had the highest numbers of stage-or tissue-specific genes. We find that pleiotropic gene expression is a better predictor than sex bias for the evolutionary rate of genes, though it often interacts with sex bias. Although genetically differentiated, the sex chromosomes were not enriched in sex-biased genes, possibly due to a very recent arrest of XY recombination. These results extend our understanding of the developmental dynamics, tissue specificity, and genomic localization of sex-biased genes.
AU - Ma, Wen
AU - Veltsos, Paris
AU - Toups, Melissa A
AU - Rodrigues, Nicolas
AU - Sermier, Roberto
AU - Jeffries, Daniel
AU - Perrin, Nicolas
ID - 199
IS - 6
JF - Genes
TI - Tissue specificity and dynamics of sex biased gene expression in a common frog population with differentiated, yet homomorphic, sex chromosomes
VL - 9
ER -
TY - JOUR
AB - We consider the totally asymmetric simple exclusion process in a critical scaling parametrized by a≥0, which creates a shock in the particle density of order aT−1/3, T the observation time. When starting from step initial data, we provide bounds on the limiting law which in particular imply that in the double limit lima→∞limT→∞ one recovers the product limit law and the degeneration of the correlation length observed at shocks of order 1. This result is shown to apply to a general last-passage percolation model. We also obtain bounds on the two-point functions of several airy processes.
AU - Nejjar, Peter
ID - 70
IS - 2
JF - Latin American Journal of Probability and Mathematical Statistics
SN - 1980-0436
TI - Transition to shocks in TASEP and decoupling of last passage times
VL - 15
ER -
TY - JOUR
AB - A central goal in theoretical neuroscience is to predict the response properties of sensory neurons from first principles. To this end, “efficient coding” posits that sensory neurons encode maximal information about their inputs given internal constraints. There exist, however, many variants of efficient coding (e.g., redundancy reduction, different formulations of predictive coding, robust coding, sparse coding, etc.), differing in their regimes of applicability, in the relevance of signals to be encoded, and in the choice of constraints. It is unclear how these types of efficient coding relate or what is expected when different coding objectives are combined. Here we present a unified framework that encompasses previously proposed efficient coding models and extends to unique regimes. We show that optimizing neural responses to encode predictive information can lead them to either correlate or decorrelate their inputs, depending on the stimulus statistics; in contrast, at low noise, efficiently encoding the past always predicts decorrelation. Later, we investigate coding of naturalistic movies and show that qualitatively different types of visual motion tuning and levels of response sparsity are predicted, depending on whether the objective is to recover the past or predict the future. Our approach promises a way to explain the observed diversity of sensory neural responses, as due to multiple functional goals and constraints fulfilled by different cell types and/or circuits.
AU - Chalk, Matthew J
AU - Marre, Olivier
AU - Tkacik, Gasper
ID - 543
IS - 1
JF - PNAS
TI - Toward a unified theory of efficient, predictive, and sparse coding
VL - 115
ER -
TY - JOUR
AB - Cell shape is determined by a balance of intrinsic properties of the cell as well as its mechanochemical environment. Inhomogeneous shape changes underlie many morphogenetic events and involve spatial gradients in active cellular forces induced by complex chemical signaling. Here, we introduce a mechanochemical model based on the notion that cell shape changes may be induced by external diffusible biomolecules that influence cellular contractility (or equivalently, adhesions) in a concentration-dependent manner—and whose spatial profile in turn is affected by cell shape. We map out theoretically the possible interplay between chemical concentration and cellular structure. Besides providing a direct route to spatial gradients in cell shape profiles in tissues, we show that the dependence on cell shape helps create robust mechanochemical gradients.
AU - Dasbiswas, Kinjal
AU - Hannezo, Claude-Edouard B
AU - Gov, Nir
ID - 421
IS - 4
JF - Biophysical Journal
TI - Theory of eppithelial cell shape transitions induced by mechanoactive chemical gradients
VL - 114
ER -
TY - JOUR
AB - The current state of the art in real-time two-dimensional water wave simulation requires developers to choose between efficient Fourier-based methods, which lack interactions with moving obstacles, and finite-difference or finite element methods, which handle environmental interactions but are significantly more expensive. This paper attempts to bridge this long-standing gap between complexity and performance, by proposing a new wave simulation method that can faithfully simulate wave interactions with moving obstacles in real time while simultaneously preserving minute details and accommodating very large simulation domains.
Previous methods for simulating 2D water waves directly compute the change in height of the water surface, a strategy which imposes limitations based on the CFL condition (fast moving waves require small time steps) and Nyquist's limit (small wave details require closely-spaced simulation variables). This paper proposes a novel wavelet transformation that discretizes the liquid motion in terms of amplitude-like functions that vary over space, frequency, and direction, effectively generalizing Fourier-based methods to handle local interactions. Because these new variables change much more slowly over space than the original water height function, our change of variables drastically reduces the limitations of the CFL condition and Nyquist limit, allowing us to simulate highly detailed water waves at very large visual resolutions. Our discretization is amenable to fast summation and easy to parallelize. We also present basic extensions like pre-computed wave paths and two-way solid fluid coupling. Finally, we argue that our discretization provides a convenient set of variables for artistic manipulation, which we illustrate with a novel wave-painting interface.
AU - Jeschke, Stefan
AU - Skrivan, Tomas
AU - Mueller Fischer, Matthias
AU - Chentanez, Nuttapong
AU - Macklin, Miles
AU - Wojtan, Christopher J
ID - 134
IS - 4
JF - ACM Transactions on Graphics
TI - Water surface wavelets
VL - 37
ER -
TY - JOUR
AB - African cichlids display a remarkable assortment of jaw morphologies, pigmentation patterns, and mating behaviors. In addition to this previously documented diversity, recent studies have documented a rich diversity of sex chromosomes within these fishes. Here we review the known sex-determination network within vertebrates, and the extraordinary number of sex chromosomes systems segregating in African cichlids. We also propose a model for understanding the unusual number of sex chromosome systems within this clade.
AU - Gammerdinger, William J
AU - Kocher, Thomas
ID - 63
IS - 10
JF - Genes
TI - Unusual diversity of sex chromosomes in African cichlid fishes
VL - 9
ER -
TY - JOUR
AB - The thermodynamic description of many-particle systems rests on the assumption of ergodicity, the ability of a system to explore all allowed configurations in the phase space. Recent studies on many-body localization have revealed the existence of systems that strongly violate ergodicity in the presence of quenched disorder. Here, we demonstrate that ergodicity can be weakly broken by a different mechanism, arising from the presence of special eigenstates in the many-body spectrum that are reminiscent of quantum scars in chaotic non-interacting systems. In the single-particle case, quantum scars correspond to wavefunctions that concentrate in the vicinity of unstable periodic classical trajectories. We show that many-body scars appear in the Fibonacci chain, a model with a constrained local Hilbert space that has recently been experimentally realized in a Rydberg-atom quantum simulator. The quantum scarred eigenstates are embedded throughout the otherwise thermalizing many-body spectrum but lead to direct experimental signatures, as we show for periodic recurrences that reproduce those observed in the experiment. Our results suggest that scarred many-body bands give rise to a new universality class of quantum dynamics, opening up opportunities for the creation of novel states with long-lived coherence in systems that are now experimentally realizable.
AU - Turner, Christopher
AU - Michailidis, Alexios
AU - Abanin, Dmitry
AU - Serbyn, Maksym
AU - Papić, Zlatko
ID - 296
JF - Nature Physics
TI - Weak ergodicity breaking from quantum many-body scars
VL - 14
ER -
TY - JOUR
AB - We study the Fokker-Planck equation derived in the large system limit of the Markovian process describing the dynamics of quantitative traits. The Fokker-Planck equation is posed on a bounded domain and its transport and diffusion coefficients vanish on the domain's boundary. We first argue that, despite this degeneracy, the standard no-flux boundary condition is valid. We derive the weak formulation of the problem and prove the existence and uniqueness of its solutions by constructing the corresponding contraction semigroup on a suitable function space. Then, we prove that for the parameter regime with high enough mutation rate the problem exhibits a positive spectral gap, which implies exponential convergence to equilibrium.Next, we provide a simple derivation of the so-called Dynamic Maximum Entropy (DynMaxEnt) method for approximation of observables (moments) of the Fokker-Planck solution, which can be interpreted as a nonlinear Galerkin approximation. The limited applicability of the DynMaxEnt method inspires us to introduce its modified version that is valid for the whole range of admissible parameters. Finally, we present several numerical experiments to demonstrate the performance of both the original and modified DynMaxEnt methods. We observe that in the parameter regimes where both methods are valid, the modified one exhibits slightly better approximation properties compared to the original one.
AU - Bodova, Katarina
AU - Haskovec, Jan
AU - Markowich, Peter
ID - 607
JF - Physica D: Nonlinear Phenomena
TI - Well posedness and maximum entropy approximation for the dynamics of quantitative traits
VL - 376-377
ER -
TY - JOUR
AB - We developed a method to calculate two-photon processes in quantum mechanics that replaces the infinite summation over the intermediate states by a perturbation expansion. This latter consists of a series of commutators that involve position, momentum, and Hamiltonian quantum operators. We analyzed several single- and many-particle cases for which a closed-form solution to the perturbation expansion exists, as well as more complicated cases for which a solution is found by convergence. Throughout the article, Rayleigh and Raman scattering are taken as examples of two-photon processes. The present method provides a clear distinction between the Thomson scattering, regarded as classical scattering, and quantum contributions. Such a distinction lets us derive general results concerning light scattering. Finally, possible extensions to the developed formalism are discussed.
AU - Fratini, Filippo
AU - Safari, Laleh
AU - Amaro, Pedro
AU - Santos, José
ID - 294
IS - 4
JF - Physical Review A - Atomic, Molecular, and Optical Physics
TI - Two-photon processes based on quantum commutators
VL - 97
ER -
TY - JOUR
AB - Recent studies suggest that unstable, nonchaotic solutions of the Navier-Stokes equation may provide deep insights into fluid turbulence. In this article, we present a combined experimental and numerical study exploring the dynamical role of unstable equilibrium solutions and their invariant manifolds in a weakly turbulent, electromagnetically driven, shallow fluid layer. Identifying instants when turbulent evolution slows down, we compute 31 unstable equilibria of a realistic two-dimensional model of the flow. We establish the dynamical relevance of these unstable equilibria by showing that they are closely visited by the turbulent flow. We also establish the dynamical relevance of unstable manifolds by verifying that they are shadowed by turbulent trajectories departing from the neighborhoods of unstable equilibria over large distances in state space.
AU - Suri, Balachandra
AU - Tithof, Jeffrey
AU - Grigoriev, Roman
AU - Schatz, Michael
ID - 136
IS - 2
JF - Physical Review E
TI - Unstable equilibria and invariant manifolds in quasi-two-dimensional Kolmogorov-like flow
VL - 98
ER -
TY - JOUR
AB - We establish the existence of a global solution for a new family of fluid-like equations, which are obtained in certain regimes in as the mean-field evolution of the supercurrent density in a (2D section of a) type-II superconductor with pinning and with imposed electric current. We also consider general vortex-sheet initial data, and investigate the uniqueness and regularity properties of the solution. For some choice of parameters, the equation under investigation coincides with the so-called lake equation from 2D shallow water fluid dynamics, and our analysis then leads to a new existence result for rough initial data.
AU - Duerinckx, Mitia
AU - Fischer, Julian L
ID - 606
IS - 5
JF - Annales de l'Institut Henri Poincare (C) Non Linear Analysis
TI - Well-posedness for mean-field evolutions arising in superconductivity
VL - 35
ER -
TY - CONF
AB - Formalizing properties of systems with continuous dynamics is a challenging task. In this paper, we propose a formal framework for specifying and monitoring rich temporal properties of real-valued signals. We introduce signal first-order logic (SFO) as a specification language that combines first-order logic with linear-real arithmetic and unary function symbols interpreted as piecewise-linear signals. We first show that while the satisfiability problem for SFO is undecidable, its membership and monitoring problems are decidable. We develop an offline monitoring procedure for SFO that has polynomial complexity in the size of the input trace and the specification, for a fixed number of quantifiers and function symbols. We show that the algorithm has computation time linear in the size of the input trace for the important fragment of bounded-response specifications interpreted over input traces with finite variability. We can use our results to extend signal temporal logic with first-order quantifiers over time and value parameters, while preserving its efficient monitoring. We finally demonstrate the practical appeal of our logic through a case study in the micro-electronics domain.
AU - Bakhirkin, Alexey
AU - Ferrere, Thomas
AU - Henzinger, Thomas A
AU - Nickovicl, Deian
ID - 5959
SN - 9781538655603
T2 - 2018 International Conference on Embedded Software
TI - Keynote: The first-order logic of signals
ER -
TY - CONF
AB - Stochastic Gradient Descent (SGD) is a fundamental algorithm in machine learning, representing the optimization backbone for training several classic models, from regression to neural networks. Given the recent practical focus on distributed machine learning, significant work has been dedicated to the convergence properties of this algorithm under the inconsistent and noisy updates arising from execution in a distributed environment. However, surprisingly, the convergence properties of this classic algorithm in the standard shared-memory model are still not well-understood. In this work, we address this gap, and provide new convergence bounds for lock-free concurrent stochastic gradient descent, executing in the classic asynchronous shared memory model, against a strong adaptive adversary. Our results give improved upper and lower bounds on the "price of asynchrony'' when executing the fundamental SGD algorithm in a concurrent setting. They show that this classic optimization tool can converge faster and with a wider range of parameters than previously known under asynchronous iterations. At the same time, we exhibit a fundamental trade-off between the maximum delay in the system and the rate at which SGD can converge, which governs the set of parameters under which this algorithm can still work efficiently.
AU - Alistarh, Dan-Adrian
AU - De Sa, Christopher
AU - Konstantinov, Nikola H
ID - 5962
SN - 9781450357951
T2 - Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing - PODC '18
TI - The convergence of stochastic gradient descent in asynchronous shared memory
ER -
TY - JOUR
AB - A major problem for evolutionary theory is understanding the so-called open-ended nature of evolutionary change, from its definition to its origins. Open-ended evolution (OEE) refers to the unbounded increase in complexity that seems to characterize evolution on multiple scales. This property seems to be a characteristic feature of biological and technological evolution and is strongly tied to the generative potential associated with combinatorics, which allows the system to grow and expand their available state spaces. Interestingly, many complex systems presumably displaying OEE, from language to proteins, share a common statistical property: the presence of Zipf's Law. Given an inventory of basic items (such as words or protein domains) required to build more complex structures (sentences or proteins) Zipf's Law tells us that most of these elements are rare whereas a few of them are extremely common. Using algorithmic information theory, in this paper we provide a fundamental definition for open-endedness, which can be understood as postulates. Its statistical counterpart, based on standard Shannon information theory, has the structure of a variational problem which is shown to lead to Zipf's Law as the expected consequence of an evolutionary process displaying OEE. We further explore the problem of information conservation through an OEE process and we conclude that statistical information (standard Shannon information) is not conserved, resulting in the paradoxical situation in which the increase of information content has the effect of erasing itself. We prove that this paradox is solved if we consider non-statistical forms of information. This last result implies that standard information theory may not be a suitable theoretical framework to explore the persistence and increase of the information content in OEE systems.
AU - Corominas-Murtra, Bernat
AU - Seoane, Luís F.
AU - Solé, Ricard
ID - 5860
IS - 149
JF - Journal of the Royal Society Interface
SN - 17425689
TI - Zipf's Law, unbounded complexity and open-ended evolution
VL - 15
ER -
TY - CONF
AB - The area of machine learning has made considerable progress over the past decade, enabled by the widespread availability of large datasets, as well as by improved algorithms and models. Given the large computational demands of machine learning workloads, parallelism, implemented either through single-node concurrency or through multi-node distribution, has been a third key ingredient to advances in machine learning.
The goal of this tutorial is to provide the audience with an overview of standard distribution techniques in machine learning, with an eye towards the intriguing trade-offs between synchronization and communication costs of distributed machine learning algorithms, on the one hand, and their convergence, on the other.The tutorial will focus on parallelization strategies for the fundamental stochastic gradient descent (SGD) algorithm, which is a key tool when training machine learning models, from classical instances such as linear regression, to state-of-the-art neural network architectures.
The tutorial will describe the guarantees provided by this algorithm in the sequential case, and then move on to cover both shared-memory and message-passing parallelization strategies, together with the guarantees they provide, and corresponding trade-offs. The presentation will conclude with a broad overview of ongoing research in distributed and concurrent machine learning. The tutorial will assume no prior knowledge beyond familiarity with basic concepts in algebra and analysis.
AU - Alistarh, Dan-Adrian
ID - 5961
SN - 9781450357951
T2 - Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing - PODC '18
TI - A brief tutorial on distributed and concurrent machine learning
ER -
TY - JOUR
AB - In this paper we present a reliable method to verify the existence of loops along the uncertain trajectory of a robot, based on proprioceptive measurements only, within a bounded-error context. The loop closure detection is one of the key points in simultaneous localization and mapping (SLAM) methods, especially in homogeneous environments with difficult scenes recognitions. The proposed approach is generic and could be coupled with conventional SLAM algorithms to reliably reduce their computing burden, thus improving the localization and mapping processes in the most challenging environments such as unexplored underwater extents. To prove that a robot performed a loop whatever the uncertainties in its evolution, we employ the notion of topological degree that originates in the field of differential topology. We show that a verification tool based on the topological degree is an optimal method for proving robot loops. This is demonstrated both on datasets from real missions involving autonomous underwater vehicles and by a mathematical discussion.
AU - Rohou, Simon
AU - Franek, Peter
AU - Aubry, Clément
AU - Jaulin, Luc
ID - 5960
IS - 12
JF - The International Journal of Robotics Research
SN - 0278-3649
TI - Proving the existence of loops in robot trajectories
VL - 37
ER -
TY - CONF
AB - There has been significant progress in understanding the parallelism inherent to iterative sequential algorithms: for many classic algorithms, the depth of the dependence structure is now well understood, and scheduling techniques have been developed to exploit this shallow dependence structure for efficient parallel implementations. A related, applied research strand has studied methods by which certain iterative task-based algorithms can be efficiently parallelized via relaxed concurrent priority schedulers. These allow for high concurrency when inserting and removing tasks, at the cost of executing superfluous work due to the relaxed semantics of the scheduler. In this work, we take a step towards unifying these two research directions, by showing that there exists a family of relaxed priority schedulers that can efficiently and deterministically execute classic iterative algorithms such as greedy maximal independent set (MIS) and matching. Our primary result shows that, given a randomized scheduler with an expected relaxation factor of k in terms of the maximum allowed priority inversions on a task, and any graph on n vertices, the scheduler is able to execute greedy MIS with only an additive factor of \poly(k) expected additional iterations compared to an exact (but not scalable) scheduler. This counter-intuitive result demonstrates that the overhead of relaxation when computing MIS is not dependent on the input size or structure of the input graph. Experimental results show that this overhead can be clearly offset by the gain in performance due to the highly scalable scheduler. In sum, we present an efficient method to deterministically parallelize iterative sequential algorithms, with provable runtime guarantees in terms of the number of executed tasks to completion.
AU - Alistarh, Dan-Adrian
AU - Brown, Trevor A
AU - Kopinsky, Justin
AU - Nadiradze, Giorgi
ID - 5963
SN - 9781450357951
T2 - Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing - PODC '18
TI - Relaxed schedulers can efficiently parallelize iterative algorithms
ER -
TY - CONF
AB - Relaxed concurrent data structures have become increasingly popular, due to their scalability in graph processing and machine learning applications (\citeNguyen13, gonzalez2012powergraph ). Despite considerable interest, there exist families of natural, high performing randomized relaxed concurrent data structures, such as the popular MultiQueue~\citeMQ pattern for implementing relaxed priority queue data structures, for which no guarantees are known in the concurrent setting~\citeAKLN17. Our main contribution is in showing for the first time that, under a set of analytic assumptions, a family of relaxed concurrent data structures, including variants of MultiQueues, but also a new approximate counting algorithm we call the MultiCounter, provides strong probabilistic guarantees on the degree of relaxation with respect to the sequential specification, in arbitrary concurrent executions. We formalize these guarantees via a new correctness condition called distributional linearizability, tailored to concurrent implementations with randomized relaxations. Our result is based on a new analysis of an asynchronous variant of the classic power-of-two-choices load balancing algorithm, in which placement choices can be based on inconsistent, outdated information (this result may be of independent interest). We validate our results empirically, showing that the MultiCounter algorithm can implement scalable relaxed timestamps.
AU - Alistarh, Dan-Adrian
AU - Brown, Trevor A
AU - Kopinsky, Justin
AU - Li, Jerry Z.
AU - Nadiradze, Giorgi
ID - 5965
SN - 9781450357999
T2 - Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures - SPAA '18
TI - Distributionally linearizable data structures
ER -
TY - CONF
AB - The Big Match is a multi-stage two-player game. In each stage Player 1 hides one or two pebbles in his hand, and his opponent has to guess that number; Player 1 loses a point if Player 2 is correct, and otherwise he wins a point. As soon as Player 1 hides one pebble, the players cannot change their choices in any future stage.
Blackwell and Ferguson (1968) give an ε-optimal strategy for Player 1 that hides, in each stage, one pebble with a probability that depends on the entire past history. Any strategy that depends just on the clock or on a finite memory is worthless. The long-standing natural open problem has been whether every strategy that depends just on the clock and a finite memory is worthless. We prove that there is such a strategy that is ε-optimal. In fact, we show that just two states of memory are sufficient.
AU - Hansen, Kristoffer Arnsfelt
AU - Ibsen-Jensen, Rasmus
AU - Neyman, Abraham
ID - 5967
SN - 9781450358293
T2 - Proceedings of the 2018 ACM Conference on Economics and Computation - EC '18
TI - The Big Match with a clock and a bit of memory
ER -
TY - CONF
AB - The transactional conflict problem arises in transactional systems whenever two or more concurrent transactions clash on a data item. While the standard solution to such conflicts is to immediately abort one of the transactions, some practical systems consider the alternative of delaying conflict resolution for a short interval, which may allow one of the transactions to commit. The challenge in the transactional conflict problem is to choose the optimal length of this delay interval so as to minimize the overall running time penalty for the conflicting transactions. In this paper, we propose a family of optimal online algorithms for the transactional conflict problem. Specifically, we consider variants of this problem which arise in different implementations of transactional systems, namely "requestor wins'' and "requestor aborts'' implementations: in the former, the recipient of a coherence request is aborted, whereas in the latter, it is the requestor which has to abort. Both strategies are implemented by real systems. We show that the requestor aborts case can be reduced to a classic instance of the ski rental problem, while the requestor wins case leads to a new version of this classical problem, for which we derive optimal deterministic and randomized algorithms. Moreover, we prove that, under a simplified adversarial model, our algorithms are constant-competitive with the offline optimum in terms of throughput. We validate our algorithmic results empirically through a hardware simulation of hardware transactional memory (HTM), showing that our algorithms can lead to non-trivial performance improvements for classic concurrent data structures.
AU - Alistarh, Dan-Adrian
AU - Haider, Syed Kamran
AU - Kübler, Raphael
AU - Nadiradze, Giorgi
ID - 5966
SN - 9781450357999
T2 - Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures - SPAA '18
TI - The transactional conflict problem
ER -
TY - JOUR
AB - We consider the recent formulation of the algorithmic Lov ́asz Local Lemma [N. Har-vey and J. Vondr ́ak, inProceedings of FOCS, 2015, pp. 1327–1345; D. Achlioptas and F. Iliopoulos,inProceedings of SODA, 2016, pp. 2024–2038; D. Achlioptas, F. Iliopoulos, and V. Kolmogorov,ALocal Lemma for Focused Stochastic Algorithms, arXiv preprint, 2018] for finding objects that avoid“bad features,” or “flaws.” It extends the Moser–Tardos resampling algorithm [R. A. Moser andG. Tardos,J. ACM, 57 (2010), 11] to more general discrete spaces. At each step the method picks aflaw present in the current state and goes to a new state according to some prespecified probabilitydistribution (which depends on the current state and the selected flaw). However, the recent formu-lation is less flexible than the Moser–Tardos method since it requires a specific flaw selection rule,whereas the algorithm of Moser and Tardos allows an arbitrary rule (and thus can potentially beimplemented more efficiently). We formulate a new “commutativity” condition and prove that it issufficient for an arbitrary rule to work. It also enables an efficient parallelization under an additionalassumption. We then show that existing resampling oracles for perfect matchings and permutationsdo satisfy this condition.
AU - Kolmogorov, Vladimir
ID - 5975
IS - 6
JF - SIAM Journal on Computing
SN - 0097-5397
TI - Commutativity in the algorithmic Lovász local lemma
VL - 47
ER -
TY - CONF
AB - A standard design pattern found in many concurrent data structures, such as hash tables or ordered containers, is an alternation of parallelizable sections that incur no data conflicts and critical sections that must run sequentially and are protected with locks. A lock can be viewed as a queue that arbitrates the order in which the critical sections are executed, and a natural question is whether we can use stochastic analysis to predict the resulting throughput. As a preliminary evidence to the affirmative, we describe a simple model that can be used to predict the throughput of coarse-grained lock-based algorithms. We show that our model works well for CLH lock, and we expect it to work for other popular lock designs such as TTAS, MCS, etc.
AU - Aksenov, Vitaly
AU - Alistarh, Dan-Adrian
AU - Kuznetsov, Petr
ID - 5964
SN - 9781450357951
T2 - Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing - PODC '18
TI - Brief Announcement: Performance prediction for coarse-grained locking
ER -
TY - JOUR
AB - We consider a Wigner-type ensemble, i.e. large hermitian N×N random matrices H=H∗ with centered independent entries and with a general matrix of variances Sxy=𝔼∣∣Hxy∣∣2. The norm of H is asymptotically given by the maximum of the support of the self-consistent density of states. We establish a bound on this maximum in terms of norms of powers of S that substantially improves the earlier bound 2∥S∥1/2∞ given in [O. Ajanki, L. Erdős and T. Krüger, Universality for general Wigner-type matrices, Prob. Theor. Rel. Fields169 (2017) 667–727]. The key element of the proof is an effective Markov chain approximation for the contributions of the weighted Dyck paths appearing in the iterative solution of the corresponding Dyson equation.
AU - Erdös, László
AU - Mühlbacher, Peter
ID - 5971
JF - Random matrices: Theory and applications
SN - 2010-3263
TI - Bounds on the norm of Wigner-type random matrices
ER -
TY - JOUR
AB - G-protein-coupled receptors (GPCRs) form the largest receptor family, relay environmental stimuli to changes in cell behavior and represent prime drug targets. Many GPCRs are classified as orphan receptors because of the limited knowledge on their ligands and coupling to cellular signaling machineries. Here, we engineer a library of 63 chimeric receptors that contain the signaling domains of human orphan and understudied GPCRs functionally linked to the light-sensing domain of rhodopsin. Upon stimulation with visible light, we identify activation of canonical cell signaling pathways, including cAMP-, Ca2+-, MAPK/ERK-, and Rho-dependent pathways, downstream of the engineered receptors. For the human pseudogene GPR33, we resurrect a signaling function that supports its hypothesized role as a pathogen entry site. These results demonstrate that substituting unknown chemical activators with a light switch can reveal information about protein function and provide an optically controlled protein library for exploring the physiology and therapeutic potential of understudied GPCRs.
AU - Morri, Maurizio
AU - Sanchez-Romero, Inmaculada
AU - Tichy, Alexandra-Madelaine
AU - Kainrath, Stephanie
AU - Gerrard, Elliot J.
AU - Hirschfeld, Priscila
AU - Schwarz, Jan
AU - Janovjak, Harald L
ID - 5984
IS - 1
JF - Nature Communications
SN - 2041-1723
TI - Optical functionalization of human class A orphan G-protein-coupled receptors
VL - 9
ER -
TY - JOUR
AB - We propose FlexMaps, a novel framework for fabricating smooth shapes out of flat, flexible panels with tailored mechanical properties. We start by mapping the 3D surface onto a 2D domain as in traditional UV mapping to design a set of deformable flat panels called FlexMaps. For these panels, we design and obtain specific mechanical properties such that, once they are assembled, the static equilibrium configuration matches the desired 3D shape. FlexMaps can be fabricated from an almost rigid material, such as wood or plastic, and are made flexible in a controlled way by using computationally designed spiraling microstructures.
AU - Malomo, Luigi
AU - Perez Rodriguez, Jesus
AU - Iarussi, Emmanuel
AU - Pietroni, Nico
AU - Miguel, Eder
AU - Cignoni, Paolo
AU - Bickel, Bernd
ID - 5976
IS - 6
JF - ACM Transactions on Graphics
SN - 0730-0301
TI - FlexMaps: Computational design of flat flexible shells for shaping 3D objects
VL - 37
ER -
TY - JOUR
AB - We study a quantum impurity possessing both translational and internal rotational degrees of freedom interacting with a bosonic bath. Such a system corresponds to a “rotating polaron,” which can be used to model, e.g., a rotating molecule immersed in an ultracold Bose gas or superfluid helium. We derive the Hamiltonian of the rotating polaron and study its spectrum in the weak- and strong-coupling regimes using a combination of variational, diagrammatic, and mean-field approaches. We reveal how the coupling between linear and angular momenta affects stable quasiparticle states, and demonstrate that internal rotation leads to an enhanced self-localization in the translational degrees of freedom.
AU - Yakaboylu, Enderalp
AU - Midya, Bikashkali
AU - Deuchert, Andreas
AU - Leopold, Nikolai K
AU - Lemeshko, Mikhail
ID - 5983
IS - 22
JF - Physical Review B
SN - 2469-9950
TI - Theory of the rotating polaron: Spectrum and self-localization
VL - 98
ER -
TY - JOUR
AB - In the present work, we detail a fast and simple solution-based method to synthesize hexagonal SnSe2 nanoplates (NPLs) and their use to produce crystallographically textured SnSe2 nanomaterials. We also demonstrate that the same strategy can be used to produce orthorhombic SnSe nanostructures and nanomaterials. NPLs are grown through a screw dislocation-driven mechanism. This mechanism typically results in pyramidal structures, but we demonstrate here that the growth from multiple dislocations results in flower-like structures. Crystallographically textured SnSe2 bulk nanomaterials obtained from the hot pressing of these SnSe2 structures display highly anisotropic charge and heat transport properties and thermoelectric (TE) figures of merit limited by relatively low electrical conductivities. To improve this parameter, SnSe2 NPLs are blended here with metal nanoparticles. The electrical conductivities of the blends are significantly improved with respect to bare SnSe2 NPLs, what translates into a three-fold increase of the TE Figure of merit, reaching unprecedented ZT values up to 0.65.
AU - Zhang, Yu
AU - Liu, Yu
AU - Lim, Khak Ho
AU - Xing, Congcong
AU - Li, Mengyao
AU - Zhang, Ting
AU - Tang, Pengyi
AU - Arbiol, Jordi
AU - Llorca, Jordi
AU - Ng, Ka Ming
AU - Ibáñez, Maria
AU - Guardia, Pablo
AU - Prato, Mirko
AU - Cadavid, Doris
AU - Cabot, Andreu
ID - 5982
IS - 52
JF - Angewandte Chemie International Edition
SN - 1433-7851
TI - Tin diselenide molecular precursor for solution-processable thermoelectric materials
VL - 57
ER -
TY - CONF
AB - We consider the MAP-inference problem for graphical models,which is a valued constraint satisfaction problem defined onreal numbers with a natural summation operation. We proposea family of relaxations (different from the famous Sherali-Adams hierarchy), which naturally define lower bounds for itsoptimum. This family always contains a tight relaxation andwe give an algorithm able to find it and therefore, solve theinitial non-relaxed NP-hard problem.The relaxations we consider decompose the original probleminto two non-overlapping parts: an easy LP-tight part and adifficult one. For the latter part a combinatorial solver must beused. As we show in our experiments, in a number of applica-tions the second, difficult part constitutes only a small fractionof the whole problem. This property allows to significantlyreduce the computational time of the combinatorial solver andtherefore solve problems which were out of reach before.
AU - Haller, Stefan
AU - Swoboda, Paul
AU - Savchynskyy, Bogdan
ID - 5978
T2 - Proceedings of the 32st AAAI Conference on Artificial Intelligence
TI - Exact MAP-inference by confining combinatorial search with LP relaxation
ER -
TY - JOUR
AB - A Ge–Si core–shell nanowire is used to realize a Josephson field‐effect transistor with highly transparent contacts to superconducting leads. By changing the electric field, access to two distinct regimes, not combined before in a single device, is gained: in the accumulation mode the device is highly transparent and the supercurrent is carried by multiple subbands, while near depletion, the supercurrent is carried by single‐particle levels of a strongly coupled quantum dot operating in the few‐hole regime. These results establish Ge–Si nanowires as an important platform for hybrid superconductor–semiconductor physics and Majorana fermions.
AU - Ridderbos, Joost
AU - Brauns, Matthias
AU - Shen, Jie
AU - de Vries, Folkert K.
AU - Li, Ang
AU - Bakkers, Erik P. A. M.
AU - Brinkman, Alexander
AU - Zwanenburg, Floris A.
ID - 5990
IS - 44
JF - Advanced Materials
SN - 0935-9648
TI - Josephson effect in a few-hole quantum dot
VL - 30
ER -
TY - JOUR
AB - The problem of private set-intersection (PSI) has been traditionally treated as an instance of the more general problem of multi-party computation (MPC). Consequently, in order to argue security, or compose these protocols one has to rely on the general theory that was developed for the purpose of MPC. The pursuit of efficient protocols, however, has resulted in designs that exploit properties pertaining to PSI. In almost all practical applications where a PSI protocol is deployed, it is expected to be executed multiple times, possibly on related inputs. In this work we initiate a dedicated study of PSI in the multi-interaction (MI) setting. In this model a server sets up the common system parameters and executes set-intersection multiple times with potentially different clients. We discuss a few attacks that arise when protocols are naïvely composed in this manner and, accordingly, craft security definitions for the MI setting and study their inter-relation. Finally, we suggest a set of protocols that are MI-secure, at the same time almost as efficient as their parent, stand-alone, protocols.
AU - Chatterjee, Sanjit
AU - Kamath Hosdurg, Chethan
AU - Kumar, Vikas
ID - 5980
IS - 1
JF - American Institute of Mathematical Sciences
TI - Private set-intersection with common set-up
VL - 12
ER -
TY - JOUR
AB - Genome amplification and cellular senescence are commonly associated with pathological processes. While physiological roles for polyploidization and senescence have been described in mouse development, controversy exists over their significance in humans. Here, we describe tetraploidization and senescence as phenomena of normal human placenta development. During pregnancy, placental extravillous trophoblasts (EVTs) invade the pregnant endometrium, termed decidua, to establish an adapted microenvironment required for the developing embryo. This process is critically dependent on continuous cell proliferation and differentiation, which is thought to follow the classical model of cell cycle arrest prior to terminal differentiation. Strikingly, flow cytometry and DNAseq revealed that EVT formation is accompanied with a genome-wide polyploidization, independent of mitotic cycles. DNA replication in these cells was analysed by a fluorescent cell-cycle indicator reporter system, cell cycle marker expression and EdU incorporation. Upon invasion into the decidua, EVTs widely lose their replicative potential and enter a senescent state characterized by high senescence-associated (SA) β-galactosidase activity, induction of a SA secretory phenotype as well as typical metabolic alterations. Furthermore, we show that the shift from endocycle-dependent genome amplification to growth arrest is disturbed in androgenic complete hydatidiform moles (CHM), a hyperplastic pregnancy disorder associated with increased risk of developing choriocarinoma. Senescence is decreased in CHM-EVTs, accompanied by exacerbated endoreduplication and hyperploidy. We propose induction of cellular senescence as a ploidy-limiting mechanism during normal human placentation and unravel a link between excessive polyploidization and reduced senescence in CHM.
AU - Velicky, Philipp
AU - Meinhardt, Gudrun
AU - Plessl, Kerstin
AU - Vondra, Sigrid
AU - Weiss, Tamara
AU - Haslinger, Peter
AU - Lendl, Thomas
AU - Aumayr, Karin
AU - Mairhofer, Mario
AU - Zhu, Xiaowei
AU - Schütz, Birgit
AU - Hannibal, Roberta L.
AU - Lindau, Robert
AU - Weil, Beatrix
AU - Ernerudh, Jan
AU - Neesen, Jürgen
AU - Egger, Gerda
AU - Mikula, Mario
AU - Röhrl, Clemens
AU - Urban, Alexander E.
AU - Baker, Julie
AU - Knöfler, Martin
AU - Pollheimer, Jürgen
ID - 5998
IS - 10
JF - PLOS Genetics
SN - 1553-7404
TI - Genome amplification and cellular senescence are hallmarks of human placenta development
VL - 14
ER -
TY - JOUR
AB - Motivation
Computational prediction of the effect of mutations on protein stability is used by researchers in many fields. The utility of the prediction methods is affected by their accuracy and bias. Bias, a systematic shift of the predicted change of stability, has been noted as an issue for several methods, but has not been investigated systematically. Presence of the bias may lead to misleading results especially when exploring the effects of combination of different mutations.
Results
Here we use a protocol to measure the bias as a function of the number of introduced mutations. It is based on a self-consistency test of the reciprocity the effect of a mutation. An advantage of the used approach is that it relies solely on crystal structures without experimentally measured stability values. We applied the protocol to four popular algorithms predicting change of protein stability upon mutation, FoldX, Eris, Rosetta and I-Mutant, and found an inherent bias. For one program, FoldX, we manage to substantially reduce the bias using additional relaxation by Modeller. Authors using algorithms for predicting effects of mutations should be aware of the bias described here.
AU - Usmanova, Dinara R
AU - Bogatyreva, Natalya S
AU - Ariño Bernad, Joan
AU - Eremina, Aleksandra A
AU - Gorshkova, Anastasiya A
AU - Kanevskiy, German M
AU - Lonishin, Lyubov R
AU - Meister, Alexander V
AU - Yakupova, Alisa G
AU - Kondrashov, Fyodor
AU - Ivankov, Dmitry
ID - 5995
IS - 21
JF - Bioinformatics
SN - 1367-4803
TI - Self-consistency test reveals systematic bias in programs for prediction change of stability upon mutation
VL - 34
ER -
TY - JOUR
AB - Lamellipodia are flat membrane protrusions formed during mesenchymal motion. Polymerization at the leading edge assembles the actin filament network and generates protrusion force. How this force is supported by the network and how the assembly rate is shared between protrusion and network retrograde flow determines the protrusion rate. We use mathematical modeling to understand experiments changing the F-actin density in lamellipodia of B16-F1 melanoma cells by modulation of Arp2/3 complex activity or knockout of the formins FMNL2 and FMNL3. Cells respond to a reduction of density with a decrease of protrusion velocity, an increase in the ratio of force to filament number, but constant network assembly rate. The relation between protrusion force and tension gradient in the F-actin network and the density dependency of friction, elasticity, and viscosity of the network explain the experimental observations. The formins act as filament nucleators and elongators with differential rates. Modulation of their activity suggests an effect on network assembly rate. Contrary to these expectations, the effect of changes in elongator composition is much weaker than the consequences of the density change. We conclude that the force acting on the leading edge membrane is the force required to drive F-actin network retrograde flow.
AU - Dolati, Setareh
AU - Kage, Frieda
AU - Mueller, Jan
AU - Müsken, Mathias
AU - Kirchner, Marieluise
AU - Dittmar, Gunnar
AU - Sixt, Michael K
AU - Rottner, Klemens
AU - Falcke, Martin
ID - 5992
IS - 22
JF - Molecular Biology of the Cell
TI - On the relation between filament density, force generation, and protrusion rate in mesenchymal cell motility
VL - 29
ER -
TY - JOUR
AB - The optic tectum (TeO), or superior colliculus, is a multisensory midbrain center that organizes spatially orienting responses to relevant stimuli. To define the stimulus with the highest priority at each moment, a network of reciprocal connections between the TeO and the isthmi promotes competition between concurrent tectal inputs. In the avian midbrain, the neurons mediating enhancement and suppression of tectal inputs are located in separate isthmic nuclei, facilitating the analysis of the neural processes that mediate competition. A specific subset of radial neurons in the intermediate tectal layers relay retinal inputs to the isthmi, but at present it is unclear whether separate neurons innervate individual nuclei or a single neural type sends a common input to several of them. In this study, we used in vitro neural tracing and cell-filling experiments in chickens to show that single neurons innervate, via axon collaterals, the three nuclei that comprise the isthmotectal network. This demonstrates that the input signals representing the strength of the incoming stimuli are simultaneously relayed to the mechanisms promoting both enhancement and suppression of the input signals. By performing in vivo recordings in anesthetized chicks, we also show that this common input generates synchrony between both antagonistic mechanisms, demonstrating that activity enhancement and suppression are closely coordinated. From a computational point of view, these results suggest that these tectal neurons constitute integrative nodes that combine inputs from different sources to drive in parallel several concurrent neural processes, each performing complementary functions within the network through different firing patterns and connectivity.
AU - Garrido-Charad, Florencia
AU - Vega Zuniga, Tomas A
AU - Gutiérrez-Ibáñez, Cristián
AU - Fernandez, Pedro
AU - López-Jury, Luciana
AU - González-Cabrera, Cristian
AU - Karten, Harvey J.
AU - Luksch, Harald
AU - Marín, Gonzalo J.
ID - 6010
IS - 32
JF - Proceedings of the National Academy of Sciences
SN - 0027-8424
TI - “Shepherd’s crook” neurons drive and synchronize the enhancing and suppressive mechanisms of the midbrain stimulus selection network
VL - 115
ER -
TY - JOUR
AB - Digital fabrication devices are powerful tools for creating tangible reproductions of 3D digital models. Most available printing technologies aim at producing an accurate copy of a tridimensional shape. However, fabrication technologies can also be used to create a stylistic representation of a digital shape. We refer to this class of methods as ‘stylized fabrication methods’. These methods abstract geometric and physical features of a given shape to create an unconventional representation, to produce an optical illusion or to devise a particular interaction with the fabricated model. In this state‐of‐the‐art report, we classify and overview this broad and emerging class of approaches and also propose possible directions for future research.
AU - Bickel, Bernd
AU - Cignoni, Paolo
AU - Malomo, Luigi
AU - Pietroni, Nico
ID - 6003
IS - 6
JF - Computer Graphics Forum
SN - 0167-7055
TI - State of the art on stylized fabrication
VL - 37
ER -
TY - JOUR
AB - The Bogoliubov free energy functional is analysed. The functional serves as a model of a translation-invariant Bose gas at positive temperature. We prove the existence of minimizers in the case of repulsive interactions given by a sufficiently regular two-body potential. Furthermore, we prove the existence of a phase transition in this model and provide its phase diagram.
AU - Napiórkowski, Marcin M
AU - Reuvers, Robin
AU - Solovej, Jan Philip
ID - 6002
IS - 3
JF - Archive for Rational Mechanics and Analysis
SN - 0003-9527
TI - The Bogoliubov free energy functional I: Existence of minimizers and phase diagram
VL - 229
ER -
TY - JOUR
AB - In pipes, turbulence sets in despite the linear stability of the laminar Hagen–Poiseuille flow. The Reynolds number ( ) for which turbulence first appears in a given experiment – the ‘natural transition point’ – depends on imperfections of the set-up, or, more precisely, on the magnitude of finite amplitude perturbations. At onset, turbulence typically only occupies a certain fraction of the flow, and this fraction equally is found to differ from experiment to experiment. Despite these findings, Reynolds proposed that after sufficiently long times, flows may settle to steady conditions: below a critical velocity, flows should (regardless of initial conditions) always return to laminar, while above this velocity, eddying motion should persist. As will be shown, even in pipes several thousand diameters long, the spatio-temporal intermittent flow patterns observed at the end of the pipe strongly depend on the initial conditions, and there is no indication that different flow patterns would eventually settle to a (statistical) steady state. Exploiting the fact that turbulent puffs do not age (i.e. they are memoryless), we continuously recreate the puff sequence exiting the pipe at the pipe entrance, and in doing so introduce periodic boundary conditions for the puff pattern. This procedure allows us to study the evolution of the flow patterns for arbitrary long times, and we find that after times in excess of advective time units, indeed a statistical steady state is reached. Although the resulting flows remain spatio-temporally intermittent, puff splitting and decay rates eventually reach a balance, so that the turbulent fraction fluctuates around a well-defined level which only depends on . In accordance with Reynolds’ proposition, we find that at lower (here 2020), flows eventually always resume to laminar, while for higher ( ), turbulence persists. The critical point for pipe flow hence falls in the interval of $2020 , which is in very good agreement with the recently proposed value of . The latter estimate was based on single-puff statistics and entirely neglected puff interactions. Unlike in typical contact processes where such interactions strongly affect the percolation threshold, in pipe flow, the critical point is only marginally influenced. Interactions, on the other hand, are responsible for the approach to the statistical steady state. As shown, they strongly affect the resulting flow patterns, where they cause ‘puff clustering’, and these regions of large puff densities are observed to travel across the puff pattern in a wave-like fashion.
AU - Vasudevan, Mukund
AU - Hof, Björn
ID - 5996
JF - Journal of Fluid Mechanics
SN - 0022-1120
TI - The critical point of the transition to turbulence in pipe flow
VL - 839
ER -
TY - JOUR
AB - In this article, we consider the termination problem of probabilistic programs with real-valued variables. Thequestions concerned are: qualitative ones that ask (i) whether the program terminates with probability 1(almost-sure termination) and (ii) whether the expected termination time is finite (finite termination); andquantitative ones that ask (i) to approximate the expected termination time (expectation problem) and (ii) tocompute a boundBsuch that the probability not to terminate afterBsteps decreases exponentially (con-centration problem). To solve these questions, we utilize the notion of ranking supermartingales, which isa powerful approach for proving termination of probabilistic programs. In detail, we focus on algorithmicsynthesis of linear ranking-supermartingales over affine probabilistic programs (Apps) with both angelic anddemonic non-determinism. An important subclass of Apps is LRApp which is defined as the class of all Appsover which a linear ranking-supermartingale exists.Our main contributions are as follows. Firstly, we show that the membership problem of LRApp (i) canbe decided in polynomial time for Apps with at most demonic non-determinism, and (ii) isNP-hard and inPSPACEfor Apps with angelic non-determinism. Moreover, theNP-hardness result holds already for Appswithout probability and demonic non-determinism. Secondly, we show that the concentration problem overLRApp can be solved in the same complexity as for the membership problem of LRApp. Finally, we show thatthe expectation problem over LRApp can be solved in2EXPTIMEand isPSPACE-hard even for Apps withoutprobability and non-determinism (i.e., deterministic programs). Our experimental results demonstrate theeffectiveness of our approach to answer the qualitative and quantitative questions over Apps with at mostdemonic non-determinism.
AU - Chatterjee, Krishnendu
AU - Fu, Hongfei
AU - Novotný, Petr
AU - Hasheminezhad, Rouzbeh
ID - 5993
IS - 2
JF - ACM Transactions on Programming Languages and Systems
SN - 0164-0925
TI - Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs
VL - 40
ER -
TY - JOUR
AB - We introduce for each quiver Q and each algebraic oriented cohomology theory A, the cohomological Hall algebra (CoHA) of Q, as the A-homology of the moduli of representations of the preprojective algebra of Q. This generalizes the K-theoretic Hall algebra of commuting varieties defined by Schiffmann-Vasserot. When A is the Morava K-theory, we show evidence that this algebra is a candidate for Lusztig's reformulated conjecture on modular representations of algebraic groups.
We construct an action of the preprojective CoHA on the A-homology of Nakajima quiver varieties. We compare this with the action of the Borel subalgebra of Yangian when A is the intersection theory. We also give a shuffle algebra description of this CoHA in terms of the underlying formal group law of A. As applications, we obtain a shuffle description of the Yangian.
AU - Yang, Yaping
AU - Zhao, Gufang
ID - 5999
IS - 5
JF - Proceedings of the London Mathematical Society
SN - 0024-6115
TI - The cohomological Hall algebra of a preprojective algebra
VL - 116
ER -
TY - JOUR
AB - Schistosomes are the causative agents of schistosomiasis, a neglected tropical disease affecting over 230 million people worldwide.Additionally to their major impact on human health, they are also models of choice in evolutionary biology. These parasitic flatwormsare unique among the common hermaphroditic trematodes as they have separate sexes. This so-called “evolutionary scandal”displays a female heterogametic genetic sex-determination system (ZZ males and ZW females), as well as a pronounced adult sexualdimorphism. These phenotypic differences are determined by a shared set of genes in both sexes, potentially leading to intralocussexual conflicts. To resolve these conflicts in sexually selected traits, molecular mechanisms such as sex-biased gene expression couldoccur, but parent-of-origin gene expression also provides an alternative. In this work we investigated the latter mechanism, that is,genes expressed preferentially from either the maternal or the paternal allele, inSchistosoma mansonispecies. To this end, tran-scriptomes from male and female hybrid adults obtained by strain crosses were sequenced. Strain-specific single nucleotide poly-morphism (SNP) markers allowed us to discriminate the parental origin, while reciprocal crosses helped to differentiate parentalexpression from strain-specific expression. We identified genes containing SNPs expressed in a parent-of-origin manner consistentwith paternal and maternal imprints. Although the majority of the SNPs was identified in mitochondrial and Z-specific loci, theremaining SNPs found in male and female transcriptomes were situated in genes that have the potential to explain sexual differencesin schistosome parasites. Furthermore, we identified and validated four new Z-specific scaffolds.
AU - Kincaid-Smith, Julien
AU - Picard, Marion A L
AU - Cosseau, Céline
AU - Boissier, Jérôme
AU - Severac, Dany
AU - Grunau, Christoph
AU - Toulza, Eve
ID - 5989
IS - 3
JF - Genome Biology and Evolution
SN - 1759-6653
TI - Parent-of-Origin-Dependent Gene Expression in Male and Female Schistosome Parasites
VL - 10
ER -
TY - CONF
AB - We present an approach to identify concise equations from data using a shallow neural network approach. In contrast to ordinary black-box regression, this approach allows understanding functional relations and generalizing them from observed data to unseen parts of the parameter space. We show how to extend the class of learnable equations for a recently proposed equation learning network to include divisions, and we improve the learning and model selection strategy to be useful for challenging real-world data. For systems governed by analytical expressions, our method can in many cases identify the true underlying equation and extrapolate to unseen domains. We demonstrate its effectiveness by experiments on a cart-pendulum system, where only 2 random rollouts are required to learn the forward dynamics and successfully achieve the swing-up task.
AU - Sahoo, Subham
AU - Lampert, Christoph
AU - Martius, Georg S
ID - 6012
T2 - Proceedings of the 35th International Conference on Machine Learning
TI - Learning equations for extrapolation and control
VL - 80
ER -
TY - CONF
AB - We establish a data-dependent notion of algorithmic stability for Stochastic Gradient Descent (SGD), and employ it to develop novel generalization bounds. This is in contrast to previous distribution-free algorithmic stability results for SGD which depend on the worst-case constants. By virtue of the data-dependent argument, our bounds provide new insights into learning with SGD on convex and non-convex problems. In the convex case, we show that the bound on the generalization error depends on the risk at the initialization point. In the non-convex case, we prove that the expected curvature of the objective function around the initialization point has crucial influence on the generalization error. In both cases, our results suggest a simple data-driven strategy to stabilize SGD by pre-screening its initialization. As a corollary, our results allow us to show optimistic generalization bounds that exhibit fast convergence rates for SGD subject to a vanishing empirical risk and low noise of stochastic gradient.
AU - Kuzborskij, Ilja
AU - Lampert, Christoph
ID - 6011
T2 - Proceedings of the 35 th International Conference on Machine Learning
TI - Data-dependent stability of stochastic gradient descent
VL - 80
ER -
TY - CONF
AB - We introduce Clover, a new library for efficient computation using low-precision data, providing mathematical routines required by fundamental methods in optimization and sparse recovery. Our library faithfully implements variants of stochastic quantization that guarantee convergence at low precision, and supports data formats from 4-bit quantized to 32-bit IEEE-754 on current Intel processors. In particular, we show that 4-bit can be implemented efficiently using Intel AVX despite the lack of native support for this data format. Experimental results with dot product, matrix-vector multiplication (MVM), gradient descent (GD), and iterative hard thresholding (IHT) demonstrate that the attainable speedups are in many cases close to linear with respect to the reduction of precision due to reduced data movement. Finally, for GD and IHT, we show examples of absolute speedup achieved by 4-bit versus 32-bit, by iterating until a given target error is achieved.
AU - Stojanov, Alen
AU - Smith, Tyler Michael
AU - Alistarh, Dan-Adrian
AU - Puschel, Markus
ID - 6031
T2 - 2018 IEEE International Workshop on Signal Processing Systems
TI - Fast quantized arithmetic on x86: Trading compute for data movement
VL - 2018-October
ER -
TY - CONF
AB - Partially observable Markov decision processes (POMDPs) are the standard models for planning under uncertainty with both finite and infinite horizon. Besides the well-known discounted-sum objective, indefinite-horizon objective (aka Goal-POMDPs) is another classical objective for POMDPs. In this case, given a set of target states and a positive cost for each transition, the optimization objective is to minimize the expected total cost until a target state is reached. In the literature, RTDP-Bel or heuristic search value iteration (HSVI) have been used for solving Goal-POMDPs. Neither of these algorithms has theoretical convergence guarantees, and HSVI may even fail to terminate its trials. We give the following contributions: (1) We discuss the challenges introduced in Goal-POMDPs and illustrate how they prevent the original HSVI from converging. (2) We present a novel algorithm inspired by HSVI, termed Goal-HSVI, and show that our algorithm has convergence guarantees. (3) We show that Goal-HSVI outperforms RTDP-Bel on a set of well-known examples.
AU - Horák, Karel
AU - Bošanský, Branislav
AU - Chatterjee, Krishnendu
ID - 25
T2 - Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
TI - Goal-HSVI: Heuristic search value iteration for goal-POMDPs
VL - 2018-July
ER -
TY - CONF
AB - Partially-observable Markov decision processes (POMDPs) with discounted-sum payoff are a standard framework to model a wide range of problems related to decision making under uncertainty. Traditionally, the goal has been to obtain policies that optimize the expectation of the discounted-sum payoff. A key drawback of the expectation measure is that even low probability events with extreme payoff can significantly affect the expectation, and thus the obtained policies are not necessarily risk-averse. An alternate approach is to optimize the probability that the payoff is above a certain threshold, which allows obtaining risk-averse policies, but ignores optimization of the expectation. We consider the expectation optimization with probabilistic guarantee (EOPG) problem, where the goal is to optimize the expectation ensuring that the payoff is above a given threshold with at least a specified probability. We present several results on the EOPG problem, including the first algorithm to solve it.
AU - Chatterjee, Krishnendu
AU - Elgyütt, Adrian
AU - Novotny, Petr
AU - Rouillé, Owen
ID - 24
TI - Expectation optimization with probabilistic guarantees in POMDPs with discounted-sum objectives
VL - 2018
ER -
TY - CONF
AB - Partially observable Markov decision processes (POMDPs) are widely used in probabilistic planning problems in which an agent interacts with an environment using noisy and imprecise sensors. We study a setting in which the sensors are only partially defined and the goal is to synthesize “weakest” additional sensors, such that in the resulting POMDP, there is a small-memory policy for the agent that almost-surely (with probability 1) satisfies a reachability objective. We show that the problem is NP-complete, and present a symbolic algorithm by encoding the problem into SAT instances. We illustrate trade-offs between the amount of memory of the policy and the number of additional sensors on a simple example. We have implemented our approach and consider three classical POMDP examples from the literature, and show that in all the examples the number of sensors can be significantly decreased (as compared to the existing solutions in the literature) without increasing the complexity of the policies.
AU - Chatterjee, Krishnendu
AU - Chemlík, Martin
AU - Topcu, Ufuk
ID - 34
TI - Sensor synthesis for POMDPs with reachability objectives
VL - 2018
ER -
TY - CONF
AB - We consider planning problems for graphs, Markov decision processes (MDPs), and games on graphs. While graphs represent the most basic planning model, MDPs represent interaction with nature and games on graphs represent interaction with an adversarial environment. We consider two planning problems where there are k different target sets, and the problems are as follows: (a) the coverage problem asks whether there is a plan for each individual target set; and (b) the sequential target reachability problem asks whether the targets can be reached in sequence. For the coverage problem, we present a linear-time algorithm for graphs, and quadratic conditional lower bound for MDPs and games on graphs. For the sequential target problem, we present a linear-time algorithm for graphs, a sub-quadratic algorithm for MDPs, and a quadratic conditional lower bound for games on graphs. Our results with conditional lower bounds establish (i) model-separation results showing that for the coverage problem MDPs and games on graphs are harder than graphs and for the sequential reachability problem games on graphs are harder than MDPs and graphs; and (ii) objective-separation results showing that for MDPs the coverage problem is harder than the sequential target problem.
AU - Chatterjee, Krishnendu
AU - Dvorák, Wolfgang
AU - Henzinger, Monika H
AU - Svozil, Alexander
ID - 35
T2 - 28th International Conference on Automated Planning and Scheduling
TI - Algorithms and conditional lower bounds for planning problems
ER -
TY - JOUR
AB - An N-superconcentrator is a directed, acyclic graph with N input nodes and N output nodes such that every subset of the inputs and every subset of the outputs of same cardinality can be connected by node-disjoint paths. It is known that linear-size and bounded-degree superconcentrators exist. We prove the existence of such superconcentrators with asymptotic density 25.3 (where the density is the number of edges divided by N). The previously best known densities were 28 [12] and 27.4136 [17].
AU - Kolmogorov, Vladimir
AU - Rolinek, Michal
ID - 18
IS - 10
JF - Ars Combinatoria
SN - 0381-7032
TI - Superconcentrators of density 25.3
VL - 141
ER -
TY - THES
AB - The eigenvalue density of many large random matrices is well approximated by a deterministic measure, the self-consistent density of states. In the present work, we show this behaviour for several classes of random matrices. In fact, we establish that, in each of these classes, the self-consistent density of states approximates the eigenvalue density of the random matrix on all scales slightly above the typical eigenvalue spacing. For large classes of random matrices, the self-consistent density of states exhibits several universal features. We prove that, under suitable assumptions, random Gram matrices and Hermitian random matrices with decaying correlations have a 1/3-Hölder continuous self-consistent density of states ρ on R, which is analytic, where it is positive, and has either a square root edge or a cubic root cusp, where it vanishes. We, thus, extend the validity of the corresponding result for Wigner-type matrices from [4, 5, 7]. We show that ρ is determined as the inverse Stieltjes transform of the normalized trace of the unique solution m(z) to the Dyson equation −m(z) −1 = z − a + S[m(z)] on C N×N with the constraint Im m(z) ≥ 0. Here, z lies in the complex upper half-plane, a is a self-adjoint element of C N×N and S is a positivity-preserving operator on C N×N encoding the first two moments of the random matrix. In order to analyze a possible limit of ρ for N → ∞ and address some applications in free probability theory, we also consider the Dyson equation on infinite dimensional von Neumann algebras. We present two applications to random matrices. We first establish that, under certain assumptions, large random matrices with independent entries have a rotationally symmetric self-consistent density of states which is supported on a centered disk in C. Moreover, it is infinitely often differentiable apart from a jump on the boundary of this disk. Second, we show edge universality at all regular (not necessarily extreme) spectral edges for Hermitian random matrices with decaying correlations.
AU - Alt, Johannes
ID - 149
SN - 2663-337X
TI - Dyson equation and eigenvalue statistics of random matrices
ER -
TY - JOUR
AB - We prove that any cyclic quadrilateral can be inscribed in any closed convex C1-curve. The smoothness condition is not required if the quadrilateral is a rectangle.
AU - Akopyan, Arseniy
AU - Avvakumov, Sergey
ID - 6355
JF - Forum of Mathematics, Sigma
SN - 2050-5094
TI - Any cyclic quadrilateral can be inscribed in any closed convex smooth curve
VL - 6
ER -
TY - CONF
AB - In the context of robotic manipulation and grasping, the shift from a view that is static (force closure of a single posture) and contact-deprived (only contact for force closure is allowed, everything else is obstacle) towards a view that is dynamic and contact-rich (soft manipulation) has led to an increased interest in soft hands. These hands can easily exploit environmental constraints and object surfaces without risk, and safely interact with humans, but present also some challenges. Designing them is difficult, as well as predicting, modelling, and “programming” their interactions with the objects and the environment. This paper tackles the problem of simulating them in a fast and effective way, leveraging on novel and existing simulation technologies. We present a triple-layered simulation framework where dynamic properties such as stiffness are determined from slow but accurate FEM simulation data once, and then condensed into a lumped parameter model that can be used to fast simulate soft fingers and soft hands. We apply our approach to the simulation of soft pneumatic fingers.
AU - Pozzi, Maria
AU - Miguel Villalba, Eder
AU - Deimel, Raphael
AU - Malvezzi, Monica
AU - Bickel, Bernd
AU - Brock, Oliver
AU - Prattichizzo, Domenico
ID - 6195
SN - 9781538630815
TI - Efficient FEM-based simulation of soft robots modeled as kinematic chains
ER -
TY - JOUR
AB - We introduce a diagrammatic Monte Carlo approach to angular momentum properties of quantum many-particle systems possessing a macroscopic number of degrees of freedom. The treatment is based on a diagrammatic expansion that merges the usual Feynman diagrams with the angular momentum diagrams known from atomic and nuclear structure theory, thereby incorporating the non-Abelian algebra inherent to quantum rotations. Our approach is applicable at arbitrary coupling, is free of systematic errors and of finite-size effects, and naturally provides access to the impurity Green function. We exemplify the technique by obtaining an all-coupling solution of the angulon model; however, the method is quite general and can be applied to a broad variety of systems in which particles exchange quantum angular momentum with their many-body environment.
AU - Bighin, Giacomo
AU - Tscherbul, Timur
AU - Lemeshko, Mikhail
ID - 6339
IS - 16
JF - Physical Review Letters
TI - Diagrammatic Monte Carlo approach to angular momentum in quantum many-particle systems
VL - 121
ER -
TY - CONF
AB - Bitcoin has become the most successful cryptocurrency ever deployed, and its most distinctive feature is that it is decentralized. Its underlying protocol (Nakamoto consensus) achieves this by using proof of work, which has the drawback that it causes the consumption of vast amounts of energy to maintain the ledger. Moreover, Bitcoin mining dynamics have become less distributed over time.
Towards addressing these issues, we propose SpaceMint, a cryptocurrency based on proofs of space instead of proofs of work. Miners in SpaceMint dedicate disk space rather than computation. We argue that SpaceMint’s design solves or alleviates several of Bitcoin’s issues: most notably, its large energy consumption. SpaceMint also rewards smaller miners fairly according to their contribution to the network, thus incentivizing more distributed participation.
This paper adapts proof of space to enable its use in cryptocurrency, studies the attacks that can arise against a Bitcoin-like blockchain that uses proof of space, and proposes a new blockchain format and transaction types to address these attacks. Our prototype shows that initializing 1 TB for mining takes about a day (a one-off setup cost), and miners spend on average just a fraction of a second per block mined. Finally, we provide a game-theoretic analysis modeling SpaceMint as an extensive game (the canonical game-theoretic notion for games that take place over time) and show that this stylized game satisfies a strong equilibrium notion, thereby arguing for SpaceMint ’s stability and consensus.
AU - Park, Sunoo
AU - Kwon, Albert
AU - Fuchsbauer, Georg
AU - Gazi, Peter
AU - Alwen, Joel F
AU - Pietrzak, Krzysztof Z
ID - 6941
SN - 0302-9743
T2 - 22nd International Conference on Financial Cryptography and Data Security
TI - SpaceMint: A cryptocurrency based on proofs of space
VL - 10957
ER -
TY - JOUR
AB - T cells are actively scanning pMHC-presenting cells in lymphoid organs and nonlymphoid tissues (NLTs) with divergent topologies and confinement. How the T cell actomyosin cytoskeleton facilitates this task in distinct environments is incompletely understood. Here, we show that lack of Myosin IXb (Myo9b), a negative regulator of the small GTPase Rho, led to increased Rho-GTP levels and cell surface stiffness in primary T cells. Nonetheless, intravital imaging revealed robust motility of Myo9b−/− CD8+ T cells in lymphoid tissue and similar expansion and differentiation during immune responses. In contrast, accumulation of Myo9b−/− CD8+ T cells in NLTs was strongly impaired. Specifically, Myo9b was required for T cell crossing of basement membranes, such as those which are present between dermis and epidermis. As consequence, Myo9b−/− CD8+ T cells showed impaired control of skin infections. In sum, we show that Myo9b is critical for the CD8+ T cell adaptation from lymphoid to NLT surveillance and the establishment of protective tissue–resident T cell populations.
AU - Moalli, Federica
AU - Ficht, Xenia
AU - Germann, Philipp
AU - Vladymyrov, Mykhailo
AU - Stolp, Bettina
AU - de Vries, Ingrid
AU - Lyck, Ruth
AU - Balmer, Jasmin
AU - Fiocchi, Amleto
AU - Kreutzfeldt, Mario
AU - Merkler, Doron
AU - Iannacone, Matteo
AU - Ariga, Akitaka
AU - Stoffel, Michael H.
AU - Sharpe, James
AU - Bähler, Martin
AU - Sixt, Michael K
AU - Diz-Muñoz, Alba
AU - Stein, Jens V.
ID - 6497
IS - 7
JF - The Journal of Experimental Medicine
SN - 0022-1007
TI - The Rho regulator Myosin IXb enables nonlymphoid tissue seeding of protective CD8+T cells
VL - 2015
ER -
TY - JOUR
AB - Because of the intrinsic randomness of the evolutionary process, a mutant with a fitness advantage has some chance to be selected but no certainty. Any experiment that searches for advantageous mutants will lose many of them due to random drift. It is therefore of great interest to find population structures that improve the odds of advantageous mutants. Such structures are called amplifiers of natural selection: they increase the probability that advantageous mutants are selected. Arbitrarily strong amplifiers guarantee the selection of advantageous mutants, even for very small fitness advantage. Despite intensive research over the past decade, arbitrarily strong amplifiers have remained rare. Here we show how to construct a large variety of them. Our amplifiers are so simple that they could be useful in biotechnology, when optimizing biological molecules, or as a diagnostic tool, when searching for faster dividing cells or viruses. They could also occur in natural population structures.
AU - Pavlogiannis, Andreas
AU - Tkadlec, Josef
AU - Chatterjee, Krishnendu
AU - Nowak, Martin A.
ID - 5751
IS - 1
JF - Communications Biology
SN - 2399-3642
TI - Construction of arbitrarily strong amplifiers of natural selection using evolutionary graph theory
VL - 1
ER -
TY - JOUR
AB - Expansion microscopy is a recently introduced imaging technique that achieves super‐resolution through physically expanding the specimen by ~4×, after embedding into a swellable gel. The resolution attained is, correspondingly, approximately fourfold better than the diffraction limit, or ~70 nm. This is a major improvement over conventional microscopy, but still lags behind modern STED or STORM setups, whose resolution can reach 20–30 nm. We addressed this issue here by introducing an improved gel recipe that enables an expansion factor of ~10× in each dimension, which corresponds to an expansion of the sample volume by more than 1,000‐fold. Our protocol, which we termed X10 microscopy, achieves a resolution of 25–30 nm on conventional epifluorescence microscopes. X10 provides multi‐color images similar or even superior to those produced with more challenging methods, such as STED, STORM, and iterative expansion microscopy (iExM). X10 is therefore the cheapest and easiest option for high‐quality super‐resolution imaging currently available. X10 should be usable in any laboratory, irrespective of the machinery owned or of the technical knowledge.
AU - Truckenbrodt, Sven M
AU - Maidorn, Manuel
AU - Crzan, Dagmar
AU - Wildhagen, Hanna
AU - Kabatas, Selda
AU - Rizzoli, Silvio O
ID - 6499
IS - 9
JF - EMBO reports
SN - 1469-221X
TI - X10 expansion microscopy enables 25‐nm resolution on conventional microscopes
VL - 19
ER -
TY - CONF
AB - Population protocols are a popular model of distributed computing, in which n agents with limited local state interact randomly, and cooperate to collectively compute global predicates. Inspired by recent developments in DNA programming, an extensive series of papers, across different communities, has examined the computability and complexity characteristics of this model. Majority, or consensus, is a central task in this model, in which agents need to collectively reach a decision as to which one of two states A or B had a higher initial count. Two metrics are important: the time that a protocol requires to stabilize to an output decision, and the state space size that each agent requires to do so. It is known that majority requires Ω(log log n) states per agent to allow for fast (poly-logarithmic time) stabilization, and that O(log2 n) states are sufficient. Thus, there is an exponential gap between the space upper and lower bounds for this problem. This paper addresses this question.
On the negative side, we provide a new lower bound of Ω(log n) states for any protocol which stabilizes in O(n1–c) expected time, for any constant c > 0. This result is conditional on monotonicity and output assumptions, satisfied by all known protocols. Technically, it represents a departure from previous lower bounds, in that it does not rely on the existence of dense configurations. Instead, we introduce a new generalized surgery technique to prove the existence of incorrect executions for any algorithm which would contradict the lower bound. Subsequently, our lower bound also applies to general initial configurations, including ones with a leader. On the positive side, we give a new algorithm for majority which uses O(log n) states, and stabilizes in O(log2 n) expected time. Central to the algorithm is a new leaderless phase clock technique, which allows agents to synchronize in phases of Θ(n log n) consecutive interactions using O(log n) states per agent, exploiting a new connection between population protocols and power-of-two-choices load balancing mechanisms. We also employ our phase clock to build a leader election algorithm with a state space of size O(log n), which stabilizes in O(log2 n) expected time.
AU - Alistarh, Dan-Adrian
AU - Aspnes, James
AU - Gelashvili, Rati
ID - 7123
SN - 9781611975031
T2 - Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms
TI - Space-optimal majority in population protocols
ER -
TY - CONF
AB - Distributed training of massive machine learning models, in particular deep neural networks, via Stochastic Gradient Descent (SGD) is becoming commonplace. Several families of communication-reduction methods, such as quantization, large-batch methods, and gradient sparsification, have been proposed. To date, gradient sparsification methods--where each node sorts gradients by magnitude, and only communicates a subset of the components, accumulating the rest locally--are known to yield some of the largest practical gains. Such methods can reduce the amount of communication per step by up to \emph{three orders of magnitude}, while preserving model accuracy. Yet, this family of methods currently has no theoretical justification. This is the question we address in this paper. We prove that, under analytic assumptions, sparsifying gradients by magnitude with local error correction provides convergence guarantees, for both convex and non-convex smooth objectives, for data-parallel SGD. The main insight is that sparsification methods implicitly maintain bounds on the maximum impact of stale updates, thanks to selection by magnitude. Our analysis and empirical validation also reveal that these methods do require analytical conditions to converge well, justifying existing heuristics.
AU - Alistarh, Dan-Adrian
AU - Hoefler, Torsten
AU - Johansson, Mikael
AU - Konstantinov, Nikola H
AU - Khirirat, Sarit
AU - Renggli, Cedric
ID - 6589
T2 - Advances in Neural Information Processing Systems 31
TI - The convergence of sparsified gradient methods
VL - Volume 2018
ER -
TY - JOUR
AB - Adaptive divergence and speciation may happen despite opposition by gene flow. Identifying the genomic basis underlying divergence with gene flow is a major task in evolutionary genomics. Most approaches (e.g., outlier scans) focus on genomic regions of high differentiation. However, not all genomic architectures potentially underlying divergence are expected to show extreme differentiation. Here, we develop an approach that combines hybrid zone analysis (i.e., focuses on spatial patterns of allele frequency change) with system-specific simulations to identify loci inconsistent with neutral evolution. We apply this to a genome-wide SNP set from an ideally suited study organism, the intertidal snail Littorina saxatilis, which shows primary divergence between ecotypes associated with different shore habitats. We detect many SNPs with clinal patterns, most of which are consistent with neutrality. Among non-neutral SNPs, most are located within three large putative inversions differentiating ecotypes. Many non-neutral SNPs show relatively low levels of differentiation. We discuss potential reasons for this pattern, including loose linkage to selected variants, polygenic adaptation and a component of balancing selection within populations (which may be expected for inversions). Our work is in line with theory predicting a role for inversions in divergence, and emphasizes that genomic regions contributing to divergence may not always be accessible with methods purely based on allele frequency differences. These conclusions call for approaches that take spatial patterns of allele frequency change into account in other systems.
AU - Westram, Anja M
AU - Rafajlović, Marina
AU - Chaube, Pragya
AU - Faria, Rui
AU - Larsson, Tomas
AU - Panova, Marina
AU - Ravinet, Mark
AU - Blomberg, Anders
AU - Mehlig, Bernhard
AU - Johannesson, Kerstin
AU - Butlin, Roger
ID - 9917
IS - 4
JF - Evolution Letters
SN - 2056-3744
TI - Clines on the seashore: The genomic architecture underlying rapid divergence in the face of gene flow
VL - 2
ER -
TY - JOUR
AB - The evolution of assortative mating is a key part of the speciation process. Stronger assortment, or greater divergence in mating traits, between species pairs with overlapping ranges is commonly observed, but possible causes of this pattern of reproductive character displacement are difficult to distinguish. We use a multidisciplinary approach to provide a rare example where it is possible to distinguish among hypotheses concerning the evolution of reproductive character displacement. We build on an earlier comparative analysis that illustrated a strong pattern of greater divergence in penis form between pairs of sister species with overlapping ranges than between allopatric sister-species pairs, in a large clade of marine gastropods (Littorinidae). We investigate both assortative mating and divergence in male genitalia in one of the sister-species pairs, discriminating among three contrasting processes each of which can generate a pattern of reproductive character displacement: reinforcement, reproductive interference and the Templeton effect. We demonstrate reproductive character displacement in assortative mating, but not in genital form between this pair of sister species and use demographic models to distinguish among the different processes. Our results support a model with no gene flow since secondary contact and thus favor reproductive interference as the cause of reproductive character displacement for mate choice, rather than reinforcement. High gene flow within species argues against the Templeton effect. Secondary contact appears to have had little impact on genital divergence.
AU - Hollander, Johan
AU - Montaño-Rendón, Mauricio
AU - Bianco, Giuseppe
AU - Yang, Xi
AU - Westram, Anja M
AU - Duvaux, Ludovic
AU - Reid, David G.
AU - Butlin, Roger K.
ID - 9915
IS - 6
JF - Evolution Letters
SN - 2056-3744
TI - Are assortative mating and genital divergence driven by reinforcement?
VL - 2
ER -
TY - JOUR
AB - The reversibly switchable fluorescent proteins (RSFPs) commonly used for RESOLFT nanoscopy have been developed from fluorescent proteins of the GFP superfamily. These proteins are bright, but exhibit several drawbacks such as relatively large size, oxygen-dependence, sensitivity to low pH, and limited switching speed. Therefore, RSFPs from other origins with improved properties need to be explored. Here, we report the development of two RSFPs based on the LOV domain of the photoreceptor protein YtvA from Bacillus subtilis. LOV domains obtain their fluorescence by association with the abundant cellular cofactor flavin mononucleotide (FMN). Under illumination with blue and ultraviolet light, they undergo a photocycle, making these proteins inherently photoswitchable. Our first improved variant, rsLOV1, can be used for RESOLFT imaging, whereas rsLOV2 proved useful for STED nanoscopy of living cells with a resolution of down to 50 nm. In addition to their smaller size compared to GFP-related proteins (17 kDa instead of 27 kDa) and their usability at low pH, rsLOV1 and rsLOV2 exhibit faster switching kinetics, switching on and off 3 times faster than rsEGFP2, the fastest-switching RSFP reported to date. Therefore, LOV-domain-based RSFPs have potential for applications where the switching speed of GFP-based proteins is limiting.
AU - Gregor, Carola
AU - Sidenstein, Sven C.
AU - Andresen, Martin
AU - Sahl, Steffen J.
AU - Danzl, Johann G
AU - Hell, Stefan W.
ID - 8618
JF - Scientific Reports
KW - Multidisciplinary
SN - 2045-2322
TI - Novel reversibly switchable fluorescent proteins for RESOLFT and STED nanoscopy engineered from the bacterial photoreceptor YtvA
VL - 8
ER -
TY - JOUR
AB - Strigolactones (SLs) are a relatively recent addition to the list of plant hormones that control different aspects of plant development. SL signalling is perceived by an α/β hydrolase, DWARF 14 (D14). A close homolog of D14, KARRIKIN INSENSTIVE2 (KAI2), is involved in perception of an uncharacterized molecule called karrikin (KAR). Recent studies in Arabidopsis identified the SUPPRESSOR OF MAX2 1 (SMAX1) and SMAX1-LIKE 7 (SMXL7) to be potential SCF–MAX2 complex-mediated proteasome targets of KAI2 and D14, respectively. Genetic studies on SMXL7 and SMAX1 demonstrated distinct developmental roles for each, but very little is known about these repressors in terms of their sequence features. In this study, we performed an extensive comparative analysis of SMXLs and determined their phylogenetic and evolutionary history in the plant lineage. Our results show that SMXL family members can be sub-divided into four distinct phylogenetic clades/classes, with an ancient SMAX1. Further, we identified the clade-specific motifs that have evolved and that might act as determinants of SL-KAR signalling specificity. These specificities resulted from functional diversities among the clades. Our results suggest that a gradual co-evolution of SMXL members with their upstream receptors D14/KAI2 provided an increased specificity to both the SL perception and response in land plants.
AU - Moturu, Taraka Ramji
AU - Thula, Sravankumar
AU - Singh, Ravi Kumar
AU - Nodzyński, Tomasz
AU - Vařeková, Radka Svobodová
AU - Friml, Jiří
AU - Simon, Sibu
ID - 10881
IS - 9
JF - Journal of Experimental Botany
KW - Plant Science
KW - Physiology
SN - 0022-0957
TI - Molecular evolution and diversification of the SMXL gene family
VL - 69
ER -
TY - JOUR
AB - Acquisition of evolutionary novelties is a fundamental process for adapting to the external environment and invading new niches and results in the diversification of life, which we can see in the world today. How such novel phenotypic traits are acquired in the course of evolution and are built up in developing embryos has been a central question in biology. Whole-genome duplication (WGD) is a process of genome doubling that supplies raw genetic materials and increases genome complexity. Recently, it has been gradually revealed that WGD and subsequent fate changes of duplicated genes can facilitate phenotypic evolution. Here, we review the current understanding of the relationship between WGD and the acquisition of evolutionary novelties. We show some examples of this link and discuss how WGD and subsequent duplicated genes can facilitate phenotypic evolution as well as when such genomic doubling can be advantageous for adaptation.
AU - Yuuta, Moriyama
AU - Koshiba-Takeuchi, Kazuko
ID - 10880
IS - 5
JF - Briefings in Functional Genomics
KW - Genetics
KW - Molecular Biology
KW - Biochemistry
KW - General Medicine
SN - 2041-2649
TI - Significance of whole-genome duplications on the emergence of evolutionary novelties
VL - 17
ER -
TY - GEN
AB - Adaptive divergence and speciation may happen despite opposition by gene flow. Identifying the genomic basis underlying divergence with gene flow is a major task in evolutionary genomics. Most approaches (e.g. outlier scans) focus on genomic regions of high differentiation. However, not all genomic architectures potentially underlying divergence are expected to show extreme differentiation. Here, we develop an approach that combines hybrid zone analysis (i.e. focuses on spatial patterns of allele frequency change) with system-specific simulations to identify loci inconsistent with neutral evolution. We apply this to a genome-wide SNP set from an ideally-suited study organism, the intertidal snail Littorina saxatilis, which shows primary divergence between ecotypes associated with different shore habitats. We detect many SNPs with clinal patterns, most of which are consistent with neutrality. Among non-neutral SNPs, most are located within three large putative inversions differentiating ecotypes. Many non-neutral SNPs show relatively low levels of differentiation. We discuss potential reasons for this pattern, including loose linkage to selected variants, polygenic adaptation and a component of balancing selection within populations (which may be expected for inversions). Our work is in line with theory predicting a role for inversions in divergence, and emphasises that genomic regions contributing to divergence may not always be accessible with methods purely based on allele frequency differences. These conclusions call for approaches that take spatial patterns of allele frequency change into account in other systems.
AU - Westram, Anja M
AU - Rafajlović, Marina
AU - Chaube, Pragya
AU - Faria, Rui
AU - Larsson, Tomas
AU - Panova, Marina
AU - Ravinet, Mark
AU - Blomberg, Anders
AU - Mehlig, Bernhard
AU - Johannesson, Kerstin
AU - Butlin, Roger
ID - 9930
TI - Data from: Clines on the seashore: the genomic architecture underlying rapid divergence in the face of gene flow
ER -
TY - GEN
AB - The evolution of assortative mating is a key part of the speciation process. Stronger assortment, or greater divergence in mating traits, between species pairs with overlapping ranges is commonly observed, but possible causes of this pattern of reproductive character displacement are difficult to distinguish. We use a multidisciplinary approach to provide a rare example where it is possible to distinguish among hypotheses concerning the evolution of reproductive character displacement. We build on an earlier comparative analysis that illustrated a strong pattern of greater divergence in penis form between pairs of sister species with overlapping ranges than between allopatric sister-species pairs, in a large clade of marine gastropods (Littorinidae). We investigate both assortative mating and divergence in male genitalia in one of the sister-species pairs, discriminating among three contrasting processes each of which can generate a pattern of reproductive character displacement: reinforcement, reproductive interference and the Templeton effect. We demonstrate reproductive character displacement in assortative mating, but not in genital form between this pair of sister species and use demographic models to distinguish among the different processes. Our results support a model with no gene flow since secondary contact and thus favour reproductive interference as the cause of reproductive character displacement for mate choice, rather than reinforcement. High gene flow within species argues against the Templeton effect. Secondary contact appears to have had little impact on genital divergence.
AU - Hollander, Johan
AU - Montaño-Rendón, Mauricio
AU - Bianco, Giuseppe
AU - Yang, Xi
AU - Westram, Anja M
AU - Duvaux, Ludovic
AU - Reid, David G.
AU - Butlin, Roger K.
ID - 9929
TI - Data from: Are assortative mating and genital divergence driven by reinforcement?
ER -
TY - CONF
AB - We introduce Intelligent Annotation Dialogs for bounding box annotation. We train an agent to automatically choose a sequence of actions for a human annotator to produce a bounding box in a minimal amount of time. Specifically, we consider two actions: box verification [34], where the annotator verifies a box generated by an object detector, and manual box drawing. We explore two kinds of agents, one based on predicting the probability that a box will be positively verified, and the other based on reinforcement learning. We demonstrate that (1) our agents are able to learn efficient annotation strategies in several scenarios, automatically adapting to the image difficulty, the desired quality of the boxes, and the detector strength; (2) in all scenarios the resulting annotation dialogs speed up annotation compared to manual box drawing alone and box verification alone, while also outperforming any fixed combination of verification and drawing in most scenarios; (3) in a realistic scenario where the detector is iteratively re-trained, our agents evolve a series of strategies that reflect the shifting trade-off between verification and drawing as the detector grows stronger.
AU - Uijlings, Jasper
AU - Konyushkova, Ksenia
AU - Lampert, Christoph
AU - Ferrari, Vittorio
ID - 10882
SN - 9781538664209
T2 - 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition
TI - Learning intelligent dialogs for bounding box annotation
ER -
TY - CONF
AB - This paper studies the problem of distributed stochastic optimization in an adversarial setting where, out of m machines which allegedly compute stochastic gradients every iteration, an α-fraction are Byzantine, and may behave adversarially. Our main result is a variant of stochastic gradient descent (SGD) which finds ε-approximate minimizers of convex functions in T=O~(1/ε²m+α²/ε²) iterations. In contrast, traditional mini-batch SGD needs T=O(1/ε²m) iterations, but cannot tolerate Byzantine failures. Further, we provide a lower bound showing that, up to logarithmic factors, our algorithm is information-theoretically optimal both in terms of sample complexity and time complexity.
AU - Alistarh, Dan-Adrian
AU - Allen-Zhu, Zeyuan
AU - Li, Jerry
ID - 6558
T2 - Advances in Neural Information Processing Systems
TI - Byzantine stochastic gradient descent
VL - 2018
ER -
TY - THES
AB - In this thesis we will discuss systems of point interacting fermions, their stability and other spectral properties. Whereas for bosons a point interacting system is always unstable this ques- tion is more subtle for a gas of two species of fermions. In particular the answer depends on the mass ratio between these two species. Most of this work will be focused on the N + M model which consists of two species of fermions with N, M particles respectively which interact via point interactions. We will introduce this model using a formal limit and discuss the N + 1 system in more detail. In particular, we will show that for mass ratios above a critical one, which does not depend on the particle number, the N + 1 system is stable. In the context of this model we will prove rigorous versions of Tan relations which relate various quantities of the point-interacting model. By restricting the N + 1 system to a box we define a finite density model with point in- teractions. In the context of this system we will discuss the energy change when introducing a point-interacting impurity into a system of non-interacting fermions. We will see that this change in energy is bounded independently of the particle number and in particular the bound only depends on the density and the scattering length. As another special case of the N + M model we will show stability of the 2 + 2 model for mass ratios in an interval around one. Further we will investigate a different model of point interactions which was discussed before in the literature and which is, contrary to the N + M model, not given by a limiting procedure but is based on a Dirichlet form. We will show that this system behaves trivially in the thermodynamic limit, i.e. the free energy per particle is the same as the one of the non-interacting system.
AU - Moser, Thomas
ID - 52
SN - 2663-337X
TI - Point interactions in systems of fermions
ER -
TY - JOUR
AB - The main result of this article is a generalization of the classical blossom algorithm for finding perfect matchings. Our algorithm can efficiently solve Boolean CSPs where each variable appears in exactly two constraints (we call it edge CSP) and all constraints are even Δ-matroid relations (represented by lists of tuples). As a consequence of this, we settle the complexity classification of planar Boolean CSPs started by Dvorak and Kupec. Using a reduction to even Δ-matroids, we then extend the tractability result to larger classes of Δ-matroids that we call efficiently coverable. It properly includes classes that were known to be tractable before, namely, co-independent, compact, local, linear, and binary, with the following caveat:We represent Δ-matroids by lists of tuples, while the last two use a representation by matrices. Since an n ×n matrix can represent exponentially many tuples, our tractability result is not strictly stronger than the known algorithm for linear and binary Δ-matroids.
AU - Kazda, Alexandr
AU - Kolmogorov, Vladimir
AU - Rolinek, Michal
ID - 6032
IS - 2
JF - ACM Transactions on Algorithms
TI - Even delta-matroids and the complexity of planar boolean CSPs
VL - 15
ER -
TY - THES
AB - Neuronal networks in the brain consist of two main types of neuron, glutamatergic principal neurons and GABAergic interneurons. Although these interneurons only represent 10–20% of the whole population, they mediate feedback and feedforward inhibition and are involved in the generation of high-frequency network oscillations. A hallmark functional property of GABAergic interneurons, especially of the parvalbumin‑expressing (PV+) subtypes, is the speed of signaling at their output synapse across species and brain regions. Several molecular and subcellular factors may underlie the submillisecond signaling at GABAergic synapses. Such as the selective use of P/Q type Ca2+ channels and the tight coupling between Ca2+ channels and Ca2+ sensors of exocytosis. However, whether the molecular identity of the release sensor contributes to these signaling properties remains unclear. Besides, these interneurons are mainly show depression in response to train of stimuli. How could they keep sufficient release to control the activity of postsynaptic principal neurons during high network activity, is largely elusive. For my Ph.D. work, we firstly examined the Ca2+ sensor of exocytosis at the GABAergic basket cell (BC) to Purkinje cell (PC) synapse in the 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% compared to the wild-type control, identifying Syt2 as the major Ca2+ sensor at BC‑PC synapses. Differential adenovirus-mediated rescue revealed 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 the release sensor at BC–PC synapse ensures fast feedforward inhibition in cerebellar microcircuits. Additionally, we tested the function of another synaptotagmin member, Syt7, for inhibitory synaptic transmission at the BC–PC synapse. Syt7 is thought to be a Ca2+ sensor that mediates asynchronous transmitter release and facilitation at synapses. However, it is strongly expressed in fast-spiking, PV+ GABAergic interneurons and the output synapses of these neurons produce only minimal asynchronous release and show depression rather than facilitation. How could Syt7, a facilitation sensor, contribute to the depressed inhibitory synaptic transmission needs to be further investigated and understood. Our results indicated 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. Taken together, our results confirmed that Syt2, which has the fastest kinetic properties among all synaptotagmin members, is mainly used by the inhibitory BC‑PC synapse for synaptic transmission, contributing to the speed and temporal precision of transmitter release. Furthermore, we showed that Syt7, another highly expressed synaptotagmin member in the output synapses of cerebellar BCs, is used for ensuring efficient inhibitor synaptic transmission during high activity.
AU - Chen, Chong
ID - 324
SN - 2663-337X
TI - Synaptotagmins ensure speed and efficiency of inhibitory neurotransmitter release
ER -
TY - THES
AB - This thesis is concerned with the inference of current population structure based on geo-referenced genetic data. The underlying idea is that population structure affects its spatial genetic structure. Therefore, genotype information can be utilized to estimate important demographic parameters such as migration rates. These indirect estimates of population structure have become very attractive, as genotype data is now widely available. However, there also has been much concern about these approaches. Importantly, genetic structure can be influenced by many complex patterns, which often cannot be disentangled. Moreover, many methods merely fit heuristic patterns of genetic structure, and do not build upon population genetics theory. Here, I describe two novel inference methods that address these shortcomings. In Chapter 2, I introduce an inference scheme based on a new type of signal, identity by descent (IBD) blocks. Recently, it has become feasible to detect such long blocks of genome shared between pairs of samples. These blocks are direct traces of recent coalescence events. As such, they contain ample signal for inferring recent demography. I examine sharing of IBD blocks in two-dimensional populations with local migration. Using a diffusion approximation, I derive formulas for an isolation by distance pattern of long IBD blocks and show that sharing of long IBD blocks approaches rapid exponential decay for growing sample distance. I describe an inference scheme based on these results. It can robustly estimate the dispersal rate and population density, which is demonstrated on simulated data. I also show an application to estimate mean migration and the rate of recent population growth within Eastern Europe. Chapter 3 is about a novel method to estimate barriers to gene flow in a two dimensional population. This inference scheme utilizes geographically localized allele frequency fluctuations - a classical isolation by distance signal. The strength of these local fluctuations increases on average next to a barrier, and there is less correlation across it. I again use a framework of diffusion of ancestral lineages to model this effect, and provide an efficient numerical implementation to fit the results to geo-referenced biallelic SNP data. This inference scheme is able to robustly estimate strong barriers to gene flow, as tests on simulated data confirm.
AU - Ringbauer, Harald
ID - 200
SN - 2663-337X
TI - Inferring recent demography from spatial genetic structure
ER -
TY - JOUR
AB - In 1945, A.W. Goodman and R.E. Goodman proved the following conjecture by P. Erdős: Given a family of (round) disks of radii r1, … , rn in the plane, it is always possible to cover them by a disk of radius R= ∑ ri, provided they cannot be separated into two subfamilies by a straight line disjoint from the disks. In this note we show that essentially the same idea may work for different analogues and generalizations of their result. In particular, we prove the following: Given a family of positive homothetic copies of a fixed convex body K⊂ Rd with homothety coefficients τ1, … , τn> 0 , it is always possible to cover them by a translate of d+12(∑τi)K, provided they cannot be separated into two subfamilies by a hyperplane disjoint from the homothets.
AU - Akopyan, Arseniy
AU - Balitskiy, Alexey
AU - Grigorev, Mikhail
ID - 1064
IS - 4
JF - Discrete & Computational Geometry
SN - 01795376
TI - On the circle covering theorem by A.W. Goodman and R.E. Goodman
VL - 59
ER -
TY - JOUR
AB - SETD5 gene mutations have been identified as a frequent cause of idiopathic intellectual disability. Here we show that Setd5-haploinsufficient mice present developmental defects such as abnormal brain-to-body weight ratios and neural crest defect-associated phenotypes. Furthermore, Setd5-mutant mice show impairments in cognitive tasks, enhanced long-term potentiation, delayed ontogenetic profile of ultrasonic vocalization, and behavioral inflexibility. Behavioral issues are accompanied by abnormal expression of postsynaptic density proteins previously associated with cognition. Our data additionally indicate that Setd5 regulates RNA polymerase II dynamics and gene transcription via its interaction with the Hdac3 and Paf1 complexes, findings potentially explaining the gene expression defects observed in Setd5-haploinsufficient mice. Our results emphasize the decisive role of Setd5 in a biological pathway found to be disrupted in humans with intellectual disability and autism spectrum disorder.
AU - Deliu, Elena
AU - Arecco, Niccoló
AU - Morandell, Jasmin
AU - Dotter, Christoph
AU - Contreras, Ximena
AU - Girardot, Charles
AU - Käsper, Eva
AU - Kozlova, Alena
AU - Kishi, Kasumi
AU - Chiaradia, Ilaria
AU - Noh, Kyung
AU - Novarino, Gaia
ID - 3
IS - 12
JF - Nature Neuroscience
TI - Haploinsufficiency of the intellectual disability gene SETD5 disturbs developmental gene expression and cognition
VL - 21
ER -
TY - THES
AB - Antibiotic resistance can emerge spontaneously through genomic mutation and render treatment ineffective. To counteract this process, in addition to the discovery and description of resistance mechanisms,a deeper understanding of resistanceevolvabilityand its determinantsis needed. To address this challenge, this thesisuncoversnew genetic determinants of resistance evolvability using a customized robotic setup, exploressystematic ways in which resistance evolution is perturbed due to dose-responsecharacteristics of drugs and mutation rate differences,and mathematically investigates the evolutionary fate of one specific type of evolvability modifier -a stress-induced mutagenesis allele.We find severalgenes which strongly inhibit or potentiate resistance evolution. In order to identify them, we first developedan automated high-throughput feedback-controlled protocol whichkeeps the population size and selection pressure approximately constant for hundreds of cultures by dynamically re-diluting the cultures and adjusting the antibiotic concentration. We implementedthis protocol on a customized liquid handling robot and propagated 100 different gene deletion strains of Escherichia coliin triplicate for over 100 generations in tetracycline and in chloramphenicol, and comparedtheir adaptation rates.We find a diminishing returns pattern, where initially sensitive strains adapted more compared to less sensitive ones. Our data uncover that deletions of certain genes which do not affect mutation rate,including efflux pump components, a chaperone and severalstructural and regulatory genes can strongly and reproducibly alterresistance evolution. Sequencing analysis of evolved populations indicates that epistasis with resistance mutations is the most likelyexplanation. This work could inspire treatment strategies in which targeted inhibitors of evolvability mechanisms will be given alongside antibiotics to slow down resistance evolution and extend theefficacy of antibiotics.We implemented astochasticpopulation genetics model, toverifyways in which general properties, namely, dose-response characteristics of drugs and mutation rates, influence evolutionary dynamics. In particular, under the exposure to antibiotics with shallow dose-response curves,bacteria have narrower distributions of fitness effects of new mutations. We show that in silicothis also leads to slower resistance evolution. We see and confirm with experiments that increased mutation rates, apart from speeding up evolution, also leadto high reproducibility of phenotypic adaptation in a context of continually strong selection pressure.Knowledge of these patterns can aid in predicting the dynamics of antibiotic resistance evolutionand adapting treatment schemes accordingly.Focusing on a previously described type of evolvability modifier –a stress-induced mutagenesis allele –we find conditions under which it can persist in a population under periodic selectionakin to clinical treatment. We set up a deterministic infinite populationcontinuous time model tracking the frequencies of a mutator and resistance allele and evaluate various treatment schemes in how well they maintain a stress-induced mutator allele. In particular,a high diversity of stresses is crucial for the persistence of the mutator allele. This leads to a general trade-off where exactly those diversifying treatment schemes which are likely to decrease levels of resistance could lead to stronger selection of highly evolvable genotypes.In the long run, this work will lead to a deeper understanding of the genetic and cellular mechanisms involved in antibiotic resistance evolution and could inspire new strategies for slowing down its rate.
AU - Lukacisinova, Marta
ID - 6263
SN - 2663-337X
TI - Genetic determinants of antibiotic resistance evolution
ER -