TY - JOUR
AB - Cell division, movement and differentiation contribute to pattern formation in developing tissues. This is the case in the vertebrate neural tube, in which neurons differentiate in a characteristic pattern from a highly dynamic proliferating pseudostratified epithelium. To investigate how progenitor proliferation and differentiation affect cell arrangement and growth of the neural tube, we used experimental measurements to develop a mechanical model of the apical surface of the neuroepithelium that incorporates the effect of interkinetic nuclear movement and spatially varying rates of neuronal differentiation. Simulations predict that tissue growth and the shape of lineage-related clones of cells differ with the rate of differentiation. Growth is isotropic in regions of high differentiation, but dorsoventrally biased in regions of low differentiation. This is consistent with experimental observations. The absence of directional signalling in the simulations indicates that global mechanical constraints are sufficient to explain the observed differences in anisotropy. This provides insight into how the tissue growth rate affects cell dynamics and growth anisotropy and opens up possibilities to study the coupling between mechanics, pattern formation and growth in the neural tube.
AU - Guerrero, Pilar
AU - Perez-Carrasco, Ruben
AU - Zagórski, Marcin P
AU - Page, David
AU - Kicheva, Anna
AU - Briscoe, James
AU - Page, Karen M.
ID - 7165
IS - 23
JF - Development
SN - 0950-1991
TI - Neuronal differentiation influences progenitor arrangement in the vertebrate neuroepithelium
VL - 146
ER -
TY - JOUR
AB - We propose a novel generic shape optimization method for CAD models based on the eXtended Finite Element Method (XFEM). Our method works directly on the intersection between the model and a regular simulation grid, without the need to mesh or remesh, thus removing a bottleneck of classical shape optimization strategies. This is made possible by a novel hierarchical integration scheme that accurately integrates finite element quantities with sub-element precision. For optimization, we efficiently compute analytical shape derivatives of the entire framework, from model intersection to integration rule generation and XFEM simulation. Moreover, we describe a differentiable projection of shape parameters onto a constraint manifold spanned by user-specified shape preservation, consistency, and manufacturability constraints. We demonstrate the utility of our approach by optimizing mass distribution, strength-to-weight ratio, and inverse elastic shape design objectives directly on parameterized 3D CAD models.
AU - Hafner, Christian
AU - Schumacher, Christian
AU - Knoop, Espen
AU - Auzinger, Thomas
AU - Bickel, Bernd
AU - Bächer, Moritz
ID - 7117
IS - 6
JF - ACM Transactions on Graphics
SN - 0730-0301
TI - X-CAD: Optimizing CAD Models with Extended Finite Elements
VL - 38
ER -
TY - CONF
AB - A probabilistic vector addition system with states (pVASS) is a finite state Markov process augmented with non-negative integer counters that can be incremented or decremented during each state transition, blocking any behaviour that would cause a counter to decrease below zero. The pVASS can be used as abstractions of probabilistic programs with many decidable properties. The use of pVASS as abstractions requires the presence of nondeterminism in the model. In this paper, we develop techniques for checking fast termination of pVASS with nondeterminism. That is, for every initial configuration of size n, we consider the worst expected number of transitions needed to reach a configuration with some counter negative (the expected termination time). We show that the problem whether the asymptotic expected termination time is linear is decidable in polynomial time for a certain natural class of pVASS with nondeterminism. Furthermore, we show the following dichotomy: if the asymptotic expected termination time is not linear, then it is at least quadratic, i.e., in Ω(n2).
AU - Brázdil, Tomás
AU - Chatterjee, Krishnendu
AU - Kucera, Antonín
AU - Novotný, Petr
AU - Velan, Dominik
ID - 7183
SN - 03029743
T2 - International Symposium on Automated Technology for Verification and Analysis
TI - Deciding fast termination for probabilistic VASS with nondeterminism
VL - 11781
ER -
TY - JOUR
AB - During infection pathogens secrete small molecules, termed effectors, to manipulate and control the interaction with their specific hosts. Both the pathogen and the plant are under high selective pressure to rapidly adapt and co-evolve in what is usually referred to as molecular arms race. Components of the host’s immune system form a network that processes information about molecules with a foreign origin and damage-associated signals, integrating them with developmental and abiotic cues to adapt the plant’s responses. Both in the case of nucleotide-binding leucine-rich repeat receptors and leucine-rich repeat receptor kinases interaction networks have been extensively characterized. However, little is known on whether pathogenic effectors form complexes to overcome plant immunity and promote disease. Ustilago maydis, a biotrophic fungal pathogen that infects maize plants, produces effectors that target hubs in the immune network of the host cell. Here we assess the capability of U. maydis effector candidates to interact with each other, which may play a crucial role during the infection process. Using a systematic yeast-two-hybrid approach and based on a preliminary pooled screen, we selected 63 putative effectors for one-on-one matings with a library of nearly 300 effector candidates. We found that 126 of these effector candidates interacted either with themselves or other predicted effectors. Although the functional relevance of the observed interactions remains elusive, we propose that the observed abundance in complex formation between effectors adds an additional level of complexity to effector research and should be taken into consideration when studying effector evolution and function. Based on this fundamental finding, we suggest various scenarios which could evolutionarily drive the formation and stabilization of an effector interactome.
AU - Alcântara, André
AU - Bosch, Jason
AU - Nazari, Fahimeh
AU - Hoffmann, Gesa
AU - Gallei, Michelle C
AU - Uhse, Simon
AU - Darino, Martin A.
AU - Olukayode, Toluwase
AU - Reumann, Daniel
AU - Baggaley, Laura
AU - Djamei, Armin
ID - 7182
IS - 11
JF - Frontiers in Plant Science
TI - Systematic Y2H screening reveals extensive effector-complex formation
VL - 10
ER -
TY - JOUR
AB - Arabidopsis PIN2 protein directs transport of the phytohormone auxin from the root tip into the root elongation zone. Variation in hormone transport, which depends on a delicate interplay between PIN2 sorting to and from polar plasma membrane domains, determines root growth. By employing a constitutively degraded version of PIN2, we identify brassinolides as antagonists of PIN2 endocytosis. This response does not require de novo protein synthesis, but involves early events in canonical brassinolide signaling. Brassinolide-controlled adjustments in PIN2 sorting and intracellular distribution governs formation of a lateral PIN2 gradient in gravistimulated roots, coinciding with adjustments in auxin signaling and directional root growth. Strikingly, simulations indicate that PIN2 gradient formation is no prerequisite for root bending but rather dampens asymmetric auxin flow and signaling. Crosstalk between brassinolide signaling and endocytic PIN2 sorting, thus, appears essential for determining the rate of gravity-induced root curvature via attenuation of differential cell elongation.
AU - Retzer, Katarzyna
AU - Akhmanova, Maria
AU - Konstantinova, Nataliia
AU - Malínská, Kateřina
AU - Leitner, Johannes
AU - Petrášek, Jan
AU - Luschnig, Christian
ID - 7180
JF - Nature Communications
TI - Brassinosteroid signaling delimits root gravitropism via sorting of the Arabidopsis PIN2 auxin transporter
VL - 10
ER -
TY - JOUR
AB - Multiple sequence alignments (MSAs) are used for structural1,2 and evolutionary predictions1,2, but the complexity of aligning large datasets requires the use of approximate solutions3, including the progressive algorithm4. Progressive MSA methods start by aligning the most similar sequences and subsequently incorporate the remaining sequences, from leaf-to-root, based on a guide-tree. Their accuracy declines substantially as the number of sequences is scaled up5. We introduce a regressive algorithm that enables MSA of up to 1.4 million sequences on a standard workstation and substantially improves accuracy on datasets larger than 10,000 sequences. Our regressive algorithm works the other way around to the progressive algorithm and begins by aligning the most dissimilar sequences. It uses an efficient divide-and-conquer strategy to run third-party alignment methods in linear time, regardless of their original complexity. Our approach will enable analyses of extremely large genomic datasets such as the recently announced Earth BioGenome Project, which comprises 1.5 million eukaryotic genomes6.
AU - Garriga, Edgar
AU - Di Tommaso, Paolo
AU - Magis, Cedrik
AU - Erb, Ionas
AU - Mansouri, Leila
AU - Baltzis, Athanasios
AU - Laayouni, Hafid
AU - Kondrashov, Fyodor
AU - Floden, Evan
AU - Notredame, Cedric
ID - 7181
IS - 12
JF - Nature Biotechnology
SN - 10870156
TI - Large multiple sequence alignments with a root-to-leaf regressive method
VL - 37
ER -
TY - JOUR
AB - The cerebral cortex contains multiple areas with distinctive cytoarchitectonical patterns, but the cellular mechanisms underlying the emergence of this diversity remain unclear. Here, we have investigated the neuronal output of individual progenitor cells in the developing mouse neocortex using a combination of methods that together circumvent the biases and limitations of individual approaches. Our experimental results indicate that progenitor cells generate pyramidal cell lineages with a wide range of sizes and laminar configurations. Mathematical modelling indicates that these outcomes are compatible with a stochastic model of cortical neurogenesis in which progenitor cells undergo a series of probabilistic decisions that lead to the specification of very heterogeneous progenies. Our findings support a mechanism for cortical neurogenesis whose flexibility would make it capable to generate the diverse cytoarchitectures that characterize distinct neocortical areas.
AU - Llorca, Alfredo
AU - Ciceri, Gabriele
AU - Beattie, Robert J
AU - Wong, Fong Kuan
AU - Diana, Giovanni
AU - Serafeimidou-Pouliou, Eleni
AU - Fernández-Otero, Marian
AU - Streicher, Carmen
AU - Arnold, Sebastian J.
AU - Meyer, Martin
AU - Hippenmeyer, Simon
AU - Maravall, Miguel
AU - Marín, Oscar
ID - 7202
JF - eLife
TI - A stochastic framework of neurogenesis underlies the assembly of neocortical cytoarchitecture
VL - 8
ER -
TY - JOUR
AB - Glutamate is the major excitatory neurotransmitter in the CNS binding to a variety of glutamate receptors. Metabotropic glutamate receptors (mGluR1 to mGluR8) can act excitatory or inhibitory, depending on associated signal cascades. Expression and localization of inhibitory acting mGluRs at inner hair cells (IHCs) in the cochlea are largely unknown. Here, we analyzed expression of mGluR2, mGluR3, mGluR4, mGluR6, mGluR7, and mGluR8 and investigated their localization with respect to the presynaptic ribbon of IHC synapses. We detected transcripts for mGluR2, mGluR3, and mGluR4 as well as for mGluR7a, mGluR7b, mGluR8a, and mGluR8b splice variants. Using receptor-specific antibodies in cochlear wholemounts, we found expression of mGluR2, mGluR4, and mGluR8b close to presynaptic ribbons. Super resolution and confocal microscopy in combination with 3-dimensional reconstructions indicated a postsynaptic localization of mGluR2 that overlaps with postsynaptic density protein 95 on dendrites of afferent type I spiral ganglion neurons. In contrast, mGluR4 and mGluR8b were expressed at the presynapse close to IHC ribbons. In summary, we localized in detail 3 mGluR types at IHC ribbon synapses, providing a fundament for new therapeutical strategies that could protect the cochlea against noxious stimuli and excitotoxicity.
AU - Klotz, Lisa
AU - Wendler, Olaf
AU - Frischknecht, Renato
AU - Shigemoto, Ryuichi
AU - Schulze, Holger
AU - Enz, Ralf
ID - 7179
IS - 12
JF - FASEB Journal
TI - Localization of group II and III metabotropic glutamate receptors at pre- and postsynaptic sites of inner hair cell ribbon synapses
VL - 33
ER -
TY - CONF
AB - Applying machine learning techniques to the quickly growing data in science and industry requires highly-scalable algorithms. Large datasets are most commonly processed "data parallel" distributed across many nodes. Each node's contribution to the overall gradient is summed using a global allreduce. This allreduce is the single communication and thus scalability bottleneck for most machine learning workloads. We observe that frequently, many gradient values are (close to) zero, leading to sparse of sparsifyable communications. To exploit this insight, we analyze, design, and implement a set of communication-efficient protocols for sparse input data, in conjunction with efficient machine learning algorithms which can leverage these primitives. Our communication protocols generalize standard collective operations, by allowing processes to contribute arbitrary sparse input data vectors. Our generic communication library, SparCML1, extends MPI to support additional features, such as non-blocking (asynchronous) operations and low-precision data representations. As such, SparCML and its techniques will form the basis of future highly-scalable machine learning frameworks.
AU - Renggli, Cedric
AU - Ashkboos, Saleh
AU - Aghagolzadeh, Mehdi
AU - Alistarh, Dan-Adrian
AU - Hoefler, Torsten
ID - 7201
SN - 21674329
T2 - International Conference for High Performance Computing, Networking, Storage and Analysis, SC
TI - SparCML: High-performance sparse communication for machine learning
ER -
TY - JOUR
AB - Recent scanning tunneling microscopy experiments in NbN thin disordered superconducting films found an emergent inhomogeneity at the scale of tens of nanometers. This inhomogeneity is mirrored by an apparent dimensional crossover in the paraconductivity measured in transport above the superconducting critical temperature Tc. This behavior was interpreted in terms of an anomalous diffusion of fluctuating Cooper pairs that display a quasiconfinement (i.e., a slowing down of their diffusive dynamics) on length scales shorter than the inhomogeneity identified by tunneling experiments. Here, we assume this anomalous diffusive behavior of fluctuating Cooper pairs and calculate the effect of these fluctuations on the electron density of states above Tc. We find that the density of states is substantially suppressed up to temperatures well above Tc. This behavior, which is closely reminiscent of a pseudogap, only arises from the anomalous diffusion of fluctuating Cooper pairs in the absence of stable preformed pairs, setting the stage for an intermediate behavior between the two common paradigms in the superconducting-insulator transition, namely, the localization of Cooper pairs (the so-called bosonic scenario) and the breaking of Cooper pairs into unpaired electrons due to strong disorder (the so-called fermionic scenario).
AU - Brighi, Pietro
AU - Grilli, Marco
AU - Leridon, Brigitte
AU - Caprara, Sergio
ID - 7200
IS - 17
JF - Physical Review B
SN - 24699950
TI - Effect of anomalous diffusion of fluctuating Cooper pairs on the density of states of superconducting NbN thin films
VL - 100
ER -
TY - GEN
AB - Genetic incompatibilities contribute to reproductive isolation between many diverging populations, but it is still unclear to what extent they play a role if divergence happens with gene flow. In contact zones between the "Crab" and "Wave" ecotypes of the snail Littorina saxatilis divergent selection forms strong barriers to gene flow, while the role of postzygotic barriers due to selection against hybrids remains unclear. High embryo abortion rates in this species could indicate the presence of such barriers. Postzygotic barriers might include genetic incompatibilities (e.g. Dobzhansky-Muller incompatibilities) but also maladaptation, both expected to be most pronounced in contact zones. In addition, embryo abortion might reflect physiological stress on females and embryos independent of any genetic stress. We examined all embryos of >500 females sampled outside and inside contact zones of three populations in Sweden. Females' clutch size ranged from 0 to 1011 embryos (mean 130±123) and abortion rates varied between 0 and100% (mean 12%). We described female genotypes by using a hybrid index based on hundreds of SNPs differentiated between ecotypes with which we characterised female genotypes. We also calculated female SNP heterozygosity and inversion karyotype. Clutch size did not vary with female hybrid index and abortion rates were only weakly related to hybrid index in two sites but not at all in a third site. No additional variation in abortion rate was explained by female SNP heterozygosity, but increased female inversion heterozygosity added slightly to increased abortion. Our results show only weak and probably biologically insignificant postzygotic barriers contributing to ecotype divergence and the high and variable abortion rates were marginally, if at all, explained by hybrid index of females.
AU - Johannesson, Kerstin
AU - Zagrodzka, Zuzanna
AU - Faria, Rui
AU - Westram, Anja M
AU - Butlin, Roger
ID - 13067
TI - Data from: Is embryo abortion a postzygotic barrier to gene flow between Littorina ecotypes?
ER -
TY - CONF
AB - Persistent homology is a powerful tool in Topological Data Analysis (TDA) to capture the topological properties of data succinctly at different spatial resolutions. For graphical data, the shape, and structure of the neighborhood of individual data items (nodes) are an essential means of characterizing their properties. We propose the use of persistent homology methods to capture structural and topological properties of graphs and use it to address the problem of link prediction. We achieve encouraging results on nine different real-world datasets that attest to the potential of persistent homology-based methods for network analysis.
AU - Bhatia, Sumit
AU - Chatterjee, Bapi
AU - Nathani, Deepak
AU - Kaul, Manohar
ID - 7213
SN - 1860949X
T2 - Complex Networks and their applications VIII
TI - A persistent homology perspective to the link prediction problem
VL - 881
ER -
TY - JOUR
AB - Background: Many cancer genomes are extensively rearranged with highly aberrant chromosomal karyotypes. Structural and copy number variations in cancer genomes can be determined via abnormal mapping of sequenced reads to the reference genome. Recently it became possible to reconcile both of these types of large-scale variations into a karyotype graph representation of the rearranged cancer genomes. Such a representation, however, does not directly describe the linear and/or circular structure of the underlying rearranged cancer chromosomes, thus limiting possible analysis of cancer genomes somatic evolutionary process as well as functional genomic changes brought by the large-scale genome rearrangements.
Results: Here we address the aforementioned limitation by introducing a novel methodological framework for recovering rearranged cancer chromosomes from karyotype graphs. For a cancer karyotype graph we formulate an Eulerian Decomposition Problem (EDP) of finding a collection of linear and/or circular rearranged cancer chromosomes that are determined by the graph. We derive and prove computational complexities for several variations of the EDP. We then demonstrate that Eulerian decomposition of the cancer karyotype graphs is not always unique and present the Consistent Contig Covering Problem (CCCP) of recovering unambiguous cancer contigs from the cancer karyotype graph, and describe a novel algorithm CCR capable of solving CCCP in polynomial time. We apply CCR on a prostate cancer dataset and demonstrate that it is capable of consistently recovering large cancer contigs even when underlying cancer genomes are highly rearranged.
Conclusions: CCR can recover rearranged cancer contigs from karyotype graphs thereby addressing existing limitation in inferring chromosomal structures of rearranged cancer genomes and advancing our understanding of both patient/cancer-specific as well as the overall genetic instability in cancer.
AU - Aganezov, Sergey
AU - Zban, Ilya
AU - Aksenov, Vitalii
AU - Alexeev, Nikita
AU - Schatz, Michael C.
ID - 7214
JF - BMC Bioinformatics
TI - Recovering rearranged cancer chromosomes from karyotype graphs
VL - 20
ER -
TY - JOUR
AB - This is a literature teaching resource review for biologically inspired microfluidics courses
or exploring the diverse applications of microfluidics. The structure is around key papers and model
organisms. While courses gradually change over time, a focus remains on understanding how
microfluidics has developed as well as what it can and cannot do for researchers. As a primary
starting point, we cover micro-fluid mechanics principles and microfabrication of devices. A variety
of applications are discussed using model prokaryotic and eukaryotic organisms from the set
of bacteria (Escherichia coli), trypanosomes (Trypanosoma brucei), yeast (Saccharomyces cerevisiae),
slime molds (Physarum polycephalum), worms (Caenorhabditis elegans), flies (Drosophila melangoster),
plants (Arabidopsis thaliana), and mouse immune cells (Mus musculus). Other engineering and
biochemical methods discussed include biomimetics, organ on a chip, inkjet, droplet microfluidics,
biotic games, and diagnostics. While we have not yet reached the end-all lab on a chip,
microfluidics can still be used effectively for specific applications.
AU - Merrin, Jack
ID - 7225
IS - 4
JF - Bioengineering
TI - Frontiers in microfluidics, a teaching resource review
VL - 6
ER -
TY - JOUR
AU - Jaksic, Vojkan
AU - Seiringer, Robert
ID - 7226
IS - 12
JF - Journal of Mathematical Physics
SN - 00222488
TI - Introduction to the Special Collection: International Congress on Mathematical Physics (ICMP) 2018
VL - 60
ER -
TY - CONF
AB - Piecewise Barrier Tubes (PBT) is a new technique for flowpipe overapproximation for nonlinear systems with polynomial dynamics, which leverages a combination of barrier certificates. PBT has advantages over traditional time-step based methods in dealing with those nonlinear dynamical systems in which there is a large difference in speed between trajectories, producing an overapproximation that is time independent. However, the existing approach for PBT is not efficient due to the application of interval methods for enclosure-box computation, and it can only deal with continuous dynamical systems without uncertainty. In this paper, we extend the approach with the ability to handle both continuous and hybrid dynamical systems with uncertainty that can reside in parameters and/or noise. We also improve the efficiency of the method significantly, by avoiding the use of interval-based methods for the enclosure-box computation without loosing soundness. We have developed a C++ prototype implementing the proposed approach and we evaluate it on several benchmarks. The experiments show that our approach is more efficient and precise than other methods in the literature.
AU - Kong, Hui
AU - Bartocci, Ezio
AU - Jiang, Yu
AU - Henzinger, Thomas A
ID - 7231
SN - 0302-9743
T2 - 17th International Conference on Formal Modeling and Analysis of Timed Systems
TI - Piecewise robust barrier tubes for nonlinear hybrid systems with uncertainty
VL - 11750
ER -
TY - JOUR
AB - Coupling of endoplasmic reticulum stress to dimerisation‑dependent activation of the UPR transducer IRE1 is incompletely understood. Whilst the luminal co-chaperone ERdj4 promotes a complex between the Hsp70 BiP and IRE1's stress-sensing luminal domain (IRE1LD) that favours the latter's monomeric inactive state and loss of ERdj4 de-represses IRE1, evidence linking these cellular and in vitro observations is presently lacking. We report that enforced loading of endogenous BiP onto endogenous IRE1α repressed UPR signalling in CHO cells and deletions in the IRE1α locus that de-repressed the UPR in cells, encode flexible regions of IRE1LD that mediated BiP‑induced monomerisation in vitro. Changes in the hydrogen exchange mass spectrometry profile of IRE1LD induced by ERdj4 and BiP confirmed monomerisation and were consistent with active destabilisation of the IRE1LD dimer. Together, these observations support a competition model whereby waning ER stress passively partitions ERdj4 and BiP to IRE1LD to initiate active repression of UPR signalling.
AU - Amin-Wetzel, Niko Paresh
AU - Neidhardt, Lisa
AU - Yan, Yahui
AU - Mayer, Matthias P.
AU - Ron, David
ID - 7340
JF - eLife
TI - Unstructured regions in IRE1α specify BiP-mediated destabilisation of the luminal domain dimer and repression of the UPR
VL - 8
ER -
TY - JOUR
AB - Biochemical reactions often occur at low copy numbers but at once in crowded and diverse environments. Space and stochasticity therefore play an essential role in biochemical networks. Spatial-stochastic simulations have become a prominent tool for understanding how stochasticity at the microscopic level influences the macroscopic behavior of such systems. While particle-based models guarantee the level of detail necessary to accurately describe the microscopic dynamics at very low copy numbers, the algorithms used to simulate them typically imply trade-offs between computational efficiency and biochemical accuracy. eGFRD (enhanced Green’s Function Reaction Dynamics) is an exact algorithm that evades such trade-offs by partitioning the N-particle system into M ≤ N analytically tractable one- and two-particle systems; the analytical solutions (Green’s functions) then are used to implement an event-driven particle-based scheme that allows particles to make large jumps in time and space while retaining access to their state variables at arbitrary simulation times. Here we present “eGFRD2,” a new eGFRD version that implements the principle of eGFRD in all dimensions, thus enabling efficient particle-based simulation of biochemical reaction-diffusion processes in the 3D cytoplasm, on 2D planes representing membranes, and on 1D elongated cylinders representative of, e.g., cytoskeletal tracks or DNA; in 1D, it also incorporates convective motion used to model active transport. We find that, for low particle densities, eGFRD2 is up to 6 orders of magnitude faster than conventional Brownian dynamics. We exemplify the capabilities of eGFRD2 by simulating an idealized model of Pom1 gradient formation, which involves 3D diffusion, active transport on microtubules, and autophosphorylation on the membrane, confirming recent experimental and theoretical results on this system to hold under genuinely stochastic conditions.
AU - Sokolowski, Thomas R
AU - Paijmans, Joris
AU - Bossen, Laurens
AU - Miedema, Thomas
AU - Wehrens, Martijn
AU - Becker, Nils B.
AU - Kaizu, Kazunari
AU - Takahashi, Koichi
AU - Dogterom, Marileen
AU - ten Wolde, Pieter Rein
ID - 7422
IS - 5
JF - The Journal of Chemical Physics
SN - 0021-9606
TI - eGFRD in all dimensions
VL - 150
ER -
TY - CONF
AB - Simple drawings of graphs are those in which each pair of edges share at most one point, either a common endpoint or a proper crossing. In this paper we study the problem of extending a simple drawing D(G) of a graph G by inserting a set of edges from the complement of G into D(G) such that the result is a simple drawing. In the context of rectilinear drawings, the problem is trivial. For pseudolinear drawings, the existence of such an extension follows from Levi’s enlargement lemma. In contrast, we prove that deciding if a given set of edges can be inserted into a simple drawing is NP-complete. Moreover, we show that the maximization version of the problem is APX-hard. We also present a polynomial-time algorithm for deciding whether one edge uv can be inserted into D(G) when {u,v} is a dominating set for the graph G.
AU - Arroyo Guevara, Alan M
AU - Derka, Martin
AU - Parada, Irene
ID - 7230
SN - 0302-9743
T2 - 27th International Symposium on Graph Drawing and Network Visualization
TI - Extending simple drawings
VL - 11904
ER -
TY - JOUR
AB - For an ordinary K3 surface over an algebraically closed field of positive characteristic we show that every automorphism lifts to characteristic zero. Moreover, we show that the Fourier-Mukai partners of an ordinary K3 surface are in one-to-one correspondence with the Fourier-Mukai partners of the geometric generic fiber of its canonical lift. We also prove that the explicit counting formula for Fourier-Mukai partners of the K3 surfaces with Picard rank two and with discriminant equal to minus of a prime number, in terms of the class number of the prime, holds over a field of positive characteristic as well. We show that the image of the derived autoequivalence group of a K3 surface of finite height in the group of isometries of its crystalline cohomology has index at least two. Moreover, we provide a conditional upper bound on the kernel of this natural cohomological descent map. Further, we give an extended remark in the appendix on the possibility of an F-crystal structure on the crystalline cohomology of a K3 surface over an algebraically closed field of positive characteristic and show that the naive F-crystal structure fails in being compatible with inner product.
AU - Srivastava, Tanya K
ID - 7436
JF - Documenta Mathematica
SN - 14310635
TI - On derived equivalences of k3 surfaces in positive characteristic
VL - 24
ER -
TY - JOUR
AB - β1-integrins mediate cell–matrix interactions and their trafficking is important in the dynamic regulation of cell adhesion, migration and malignant processes, including cancer cell invasion. Here, we employ an RNAi screen to characterize regulators of integrin traffic and identify the association of Golgi-localized gamma ear-containing Arf-binding protein 2 (GGA2) with β1-integrin, and its role in recycling of active but not inactive β1-integrin receptors. Silencing of GGA2 limits active β1-integrin levels in focal adhesions and decreases cancer cell migration and invasion, which is in agreement with its ability to regulate the dynamics of active integrins. By using the proximity-dependent biotin identification (BioID) method, we identified two RAB family small GTPases, i.e. RAB13 and RAB10, as novel interactors of GGA2. Functionally, RAB13 silencing triggers the intracellular accumulation of active β1-integrin, and reduces integrin activity in focal adhesions and cell migration similarly to GGA2 depletion, indicating that both facilitate active β1-integrin recycling to the plasma membrane. Thus, GGA2 and RAB13 are important specificity determinants for integrin activity-dependent traffic.
AU - Sahgal, Pranshu
AU - Alanko, Jonna H
AU - Icha, Jaroslav
AU - Paatero, Ilkka
AU - Hamidi, Hellyeh
AU - Arjonen, Antti
AU - Pietilä, Mika
AU - Rokka, Anne
AU - Ivaska, Johanna
ID - 7420
IS - 11
JF - Journal of Cell Science
SN - 0021-9533
TI - GGA2 and RAB13 promote activity-dependent β1-integrin recycling
VL - 132
ER -
TY - JOUR
AB - We compare finite rank perturbations of the following three ensembles of complex rectangular random matrices: First, a generalised Wishart ensemble with one random and two fixed correlation matrices introduced by Borodin and Péché, second, the product of two independent random matrices where one has correlated entries, and third, the case when the two random matrices become also coupled through a fixed matrix. The singular value statistics of all three ensembles is shown to be determinantal and we derive double contour integral representations for their respective kernels. Three different kernels are found in the limit of infinite matrix dimension at the origin of the spectrum. They depend on finite rank perturbations of the correlation and coupling matrices and are shown to be integrable. The first kernel (I) is found for two independent matrices from the second, and two weakly coupled matrices from the third ensemble. It generalises the Meijer G-kernel for two independent and uncorrelated matrices. The third kernel (III) is obtained for the generalised Wishart ensemble and for two strongly coupled matrices. It further generalises the perturbed Bessel kernel of Desrosiers and Forrester. Finally, kernel (II), found for the ensemble of two coupled matrices, provides an interpolation between the kernels (I) and (III), generalising previous findings of part of the authors.
AU - Akemann, Gernot
AU - Checinski, Tomasz
AU - Liu, Dangzheng
AU - Strahov, Eugene
ID - 7423
IS - 1
JF - Annales de l'Institut Henri Poincaré, Probabilités et Statistiques
SN - 0246-0203
TI - Finite rank perturbations in products of coupled random matrices: From one correlated to two Wishart ensembles
VL - 55
ER -
TY - CONF
AB - Proofs of sequential work (PoSW) are proof systems where a prover, upon receiving a statement χ and a time parameter T computes a proof ϕ(χ,T) which is efficiently and publicly verifiable. The proof can be computed in T sequential steps, but not much less, even by a malicious party having large parallelism. A PoSW thus serves as a proof that T units of time have passed since χ
was received.
PoSW were introduced by Mahmoody, Moran and Vadhan [MMV11], a simple and practical construction was only recently proposed by Cohen and Pietrzak [CP18].
In this work we construct a new simple PoSW in the random permutation model which is almost as simple and efficient as [CP18] but conceptually very different. Whereas the structure underlying [CP18] is a hash tree, our construction is based on skip lists and has the interesting property that computing the PoSW is a reversible computation.
The fact that the construction is reversible can potentially be used for new applications like constructing proofs of replication. We also show how to “embed” the sloth function of Lenstra and Weselowski [LW17] into our PoSW to get a PoSW where one additionally can verify correctness of the output much more efficiently than recomputing it (though recent constructions of “verifiable delay functions” subsume most of the applications this construction was aiming at).
AU - Abusalah, Hamza M
AU - Kamath Hosdurg, Chethan
AU - Klein, Karen
AU - Pietrzak, Krzysztof Z
AU - Walter, Michael
ID - 7411
SN - 0302-9743
T2 - Advances in Cryptology – EUROCRYPT 2019
TI - Reversible proofs of sequential work
VL - 11477
ER -
TY - CONF
AB - Most of today's distributed machine learning systems assume reliable networks: whenever two machines exchange information (e.g., gradients or models), the network should guarantee the delivery of the message. At the same time, recent work exhibits the impressive tolerance of machine learning algorithms to errors or noise arising from relaxed communication or synchronization. In this paper, we connect these two trends, and consider the following question: Can we design machine learning systems that are tolerant to network unreliability during training? With this motivation, we focus on a theoretical problem of independent interest-given a standard distributed parameter server architecture, if every communication between the worker and the server has a non-zero probability p of being dropped, does there exist an algorithm that still converges, and at what speed? The technical contribution of this paper is a novel theoretical analysis proving that distributed learning over unreliable network can achieve comparable convergence rate to centralized or distributed learning over reliable networks. Further, we prove that the influence of the packet drop rate diminishes with the growth of the number of parameter servers. We map this theoretical result onto a real-world scenario, training deep neural networks over an unreliable network layer, and conduct network simulation to validate the system improvement by allowing the networks to be unreliable.
AU - Yu, Chen
AU - Tang, Hanlin
AU - Renggli, Cedric
AU - Kassing, Simon
AU - Singla, Ankit
AU - Alistarh, Dan-Adrian
AU - Zhang, Ce
AU - Liu, Ji
ID - 7437
SN - 9781510886988
T2 - 36th International Conference on Machine Learning, ICML 2019
TI - Distributed learning over unreliable networks
VL - 2019-June
ER -
TY - JOUR
AB - We develop a framework for the rigorous analysis of focused stochastic local search algorithms. These algorithms search a state space by repeatedly selecting some constraint that is violated in the current state and moving to a random nearby state that addresses the violation, while (we hope) not introducing many new violations. An important class of focused local search algorithms with provable performance guarantees has recently arisen from algorithmizations of the Lovász local lemma (LLL), a nonconstructive tool for proving the existence of satisfying states by introducing a background measure on the state space. While powerful, the state transitions of algorithms in this class must be, in a precise sense, perfectly compatible with the background measure. In many applications this is a very restrictive requirement, and one needs to step outside the class. Here we introduce the notion of measure distortion and develop a framework for analyzing arbitrary focused stochastic local search algorithms, recovering LLL algorithmizations as the special case of no distortion. Our framework takes as input an arbitrary algorithm of such type and an arbitrary probability measure and shows how to use the measure as a yardstick of algorithmic progress, even for algorithms designed independently of the measure.
AU - Achlioptas, Dimitris
AU - Iliopoulos, Fotis
AU - Kolmogorov, Vladimir
ID - 7412
IS - 5
JF - SIAM Journal on Computing
SN - 0097-5397
TI - A local lemma for focused stochastical algorithms
VL - 48
ER -
TY - JOUR
AB - We consider Bose gases consisting of N particles trapped in a box with volume one and interacting through a repulsive potential with scattering length of order N−1 (Gross–Pitaevskii regime). We determine the ground state energy and the low-energy excitation spectrum, up to errors vanishing as N→∞. Our results confirm Bogoliubov’s predictions.
AU - Boccato, Chiara
AU - Brennecke, Christian
AU - Cenatiempo, Serena
AU - Schlein, Benjamin
ID - 7413
IS - 2
JF - Acta Mathematica
SN - 0001-5962
TI - Bogoliubov theory in the Gross–Pitaevskii limit
VL - 222
ER -
TY - JOUR
AB - The study of parallel ecological divergence provides important clues to the operation of natural selection. Parallel divergence often occurs in heterogeneous environments with different kinds of environmental gradients in different locations, but the genomic basis underlying this process is unknown. We investigated the genomics of rapid parallel adaptation in the marine snail Littorina saxatilis in response to two independent environmental axes (crab-predation versus wave-action and low-shore versus high-shore). Using pooled whole-genome resequencing, we show that sharing of genomic regions of high differentiation between environments is generally low but increases at smaller spatial scales. We identify different shared genomic regions of divergence for each environmental axis and show that most of these regions overlap with candidate chromosomal inversions. Several inversion regions are divergent and polymorphic across many localities. We argue that chromosomal inversions could store shared variation that fuels rapid parallel adaptation to heterogeneous environments, possibly as balanced polymorphism shared by adaptive gene flow.
AU - Morales, Hernán E.
AU - Faria, Rui
AU - Johannesson, Kerstin
AU - Larsson, Tomas
AU - Panova, Marina
AU - Westram, Anja M
AU - Butlin, Roger K.
ID - 7393
IS - 12
JF - Science Advances
SN - 2375-2548
TI - Genomic architecture of parallel ecological divergence: Beyond a single environmental contrast
VL - 5
ER -
TY - JOUR
AB - Polymer additives can substantially reduce the drag of turbulent flows and the upperlimit, the so called “maximum drag reduction” (MDR) asymptote is universal, i.e. inde-pendent of the type of polymer and solvent used. Until recently, the consensus was that,in this limit, flows are in a marginal state where only a minimal level of turbulence activ-ity persists. Observations in direct numerical simulations using minimal sized channelsappeared to support this view and reported long “hibernation” periods where turbu-lence is marginalized. In simulations of pipe flow we find that, indeed, with increasingWeissenberg number (Wi), turbulence expresses long periods of hibernation if the domainsize is small. However, with increasing pipe length, the temporal hibernation continuouslyalters to spatio-temporal intermittency and here the flow consists of turbulent puffs sur-rounded by laminar flow. Moreover, upon an increase in Wi, the flow fully relaminarises,in agreement with recent experiments. At even larger Wi, a different instability is en-countered causing a drag increase towards MDR. Our findings hence link earlier minimalflow unit simulations with recent experiments and confirm that the addition of polymersinitially suppresses Newtonian turbulence and leads to a reverse transition. The MDRstate on the other hand results from a separate instability and the underlying dynamicscorresponds to the recently proposed state of elasto-inertial-turbulence (EIT).
AU - Lopez Alonso, Jose M
AU - Choueiri, George H
AU - Hof, Björn
ID - 7397
JF - Journal of Fluid Mechanics
SN - 0022-1120
TI - Dynamics of viscoelastic pipe flow at low Reynolds numbers in the maximum drag reduction limit
VL - 874
ER -
TY - JOUR
AB - The order-k Voronoi tessellation of a locally finite set 𝑋⊆ℝ𝑛 decomposes ℝ𝑛 into convex domains whose points have the same k nearest neighbors in X. Assuming X is a stationary Poisson point process, we give explicit formulas for the expected number and total area of faces of a given dimension per unit volume of space. We also develop a relaxed version of discrete Morse theory and generalize by counting only faces, for which the k nearest points in X are within a given distance threshold.
AU - Edelsbrunner, Herbert
AU - Nikitenko, Anton
ID - 5678
IS - 4
JF - Discrete and Computational Geometry
SN - 01795376
TI - Poisson–Delaunay Mosaics of Order k
VL - 62
ER -
TY - JOUR
AB - Hippocampus is needed for both spatial working and reference memories. Here, using a radial eight-arm maze, we examined how the combined demand on these memories influenced CA1 place cell assemblies while reference memories were partially updated. This was contrasted with control tasks requiring only working memory or the update of reference memory. Reference memory update led to the reward-directed place field shifts at newly rewarded arms and to the gradual strengthening of firing in passes between newly rewarded arms but not between those passes that included a familiar-rewarded arm. At the maze center, transient network synchronization periods preferentially replayed trajectories of the next chosen arm in reference memory tasks but the previously visited arm in the working memory task. Hence, reference memory demand was uniquely associated with a gradual, goal novelty-related reorganization of place cell assemblies and with trajectory replay that reflected the animal's decision of which arm to visit next.
AU - Xu, Haibing
AU - Baracskay, Peter
AU - O'Neill, Joseph
AU - Csicsvari, Jozsef L
ID - 5828
IS - 1
JF - Neuron
SN - 10974199
TI - Assembly responses of hippocampal CA1 place cells predict learned behavior in goal-directed spatial tasks on the radial eight-arm maze
VL - 101
ER -
TY - JOUR
AB - We give a bound on the ground-state energy of a system of N non-interacting fermions in a three-dimensional cubic box interacting with an impurity particle via point interactions. We show that the change in energy compared to the system in the absence of the impurity is bounded in terms of the gas density and the scattering length of the interaction, independently of N. Our bound holds as long as the ratio of the mass of the impurity to the one of the gas particles is larger than a critical value m∗ ∗≈ 0.36 , which is the same regime for which we recently showed stability of the system.
AU - Moser, Thomas
AU - Seiringer, Robert
ID - 5856
IS - 4
JF - Annales Henri Poincare
SN - 14240637
TI - Energy contribution of a point-interacting impurity in a Fermi gas
VL - 20
ER -
TY - JOUR
AB - For a general class of large non-Hermitian random block matrices X we prove that there are no eigenvalues away from a deterministic set with very high probability. This set is obtained from the Dyson equation of the Hermitization of X as the self-consistent approximation of the pseudospectrum. We demonstrate that the analysis of the matrix Dyson equation from (Probab. Theory Related Fields (2018)) offers a unified treatment of many structured matrix ensembles.
AU - Alt, Johannes
AU - Erdös, László
AU - Krüger, Torben H
AU - Nemish, Yuriy
ID - 6240
IS - 2
JF - Annales de l'institut Henri Poincare
SN - 02460203
TI - Location of the spectrum of Kronecker random matrices
VL - 55
ER -
TY - THES
AB - In many shear flows like pipe flow, plane Couette flow, plane Poiseuille flow, etc. turbulence emerges subcritically. Here, when subjected to strong enough perturbations, the flow becomes turbulent in spite of the laminar base flow being linearly stable. The nature of this instability has puzzled the scientific community for decades. At onset, turbulence appears in localized patches and flows are spatio-temporally intermittent. In pipe flow the localized turbulent structures are referred to as puffs and in planar flows like plane Couette and channel flow, patches arise in the form of localized oblique bands. In this thesis, we study the onset of turbulence in channel flow in direct numerical simulations from a dynamical system theory perspective, as well as by performing experiments in a large aspect ratio channel.
The aim of the experimental work is to determine the critical Reynolds number where turbulence first becomes sustained. Recently, the onset of turbulence has been described in analogy to absorbing state phase transition (i.e. directed percolation). In particular, it has been shown that the critical point can be estimated from the competition between spreading and decay processes. Here, by performing experiments, we identify the mechanisms underlying turbulence proliferation in channel flow and find the critical Reynolds number, above which turbulence becomes sustained. Above the critical point, the continuous growth at the tip of the stripes outweighs the stochastic shedding of turbulent patches at the tail and the stripes expand. For growing stripes, the probability to decay decreases while the probability of stripe splitting increases. Consequently, and unlike for the puffs in pipe flow, neither of these two processes is time-independent i.e. memoryless. Coupling between stripe expansion and creation of new stripes via splitting leads to a significantly lower critical point ($Re_c=670+/-10$) than most earlier studies suggest.
While the above approach sheds light on how turbulence first becomes sustained, it provides no insight into the origin of the stripes themselves. In the numerical part of the thesis we investigate how turbulent stripes form from invariant solutions of the Navier-Stokes equations. The origin of these turbulent stripes can be identified by applying concepts from the dynamical system theory. In doing so, we identify the exact coherent structures underlying stripes and their bifurcations and how they give rise to the turbulent attractor in phase space. We first report a family of localized nonlinear traveling wave solutions of the Navier-Stokes equations in channel flow. These solutions show structural similarities with turbulent stripes in experiments like obliqueness, quasi-streamwise streaks and vortices, etc. A parametric study of these traveling wave solution is performed, with parameters like Reynolds number, stripe tilt angle and domain size, including the stability of the solutions. These solutions emerge through saddle-node bifurcations and form a phase space skeleton for the turbulent stripes observed in the experiments. The lower branches of these TW solutions at different tilt angles undergo Hopf bifurcation and new solutions branches of relative periodic orbits emerge. These RPO solutions do not belong to the same family and therefore the routes to chaos for different angles are different.
In shear flows, turbulence at onset is transient in nature. Consequently,turbulence can not be tracked to lower Reynolds numbers, where the dynamics may simplify. Before this happens, turbulence becomes short-lived and laminarizes. In the last part of the thesis, we show that using numerical simulations we can continue turbulent stripes in channel flow past the 'relaminarization barrier' all the way to their origin. Here, turbulent stripe dynamics simplifies and the fluctuations are no longer stochastic and the stripe settles down to a relative periodic orbit. This relative periodic orbit originates from the aforementioned traveling wave solutions. Starting from the relative periodic orbit, a small increase in speed i.e. Reynolds number gives rise to chaos and the attractor dimension sharply increases in contrast to the classical transition scenario where the instabilities affect the flow globally and give rise to much more gradual route to turbulence.
AU - Paranjape, Chaitanya S
ID - 6957
KW - Instabilities
KW - Turbulence
KW - Nonlinear dynamics
TI - Onset of turbulence in plane Poiseuille flow
ER -
TY - THES
AB - Transcription factors, by binding to specific sequences on the DNA, control the precise spatio-temporal expression of genes inside a cell. However, this specificity is limited, leading to frequent incorrect binding of transcription factors that might have deleterious consequences on the cell. By constructing a biophysical model of TF-DNA binding in the context of gene regulation, I will first explore how regulatory constraints can strongly shape the distribution of a population in sequence space. Then, by directly linking this to a picture of multiple types of transcription factors performing their functions simultaneously inside the cell, I will explore the extent of regulatory crosstalk -- incorrect binding interactions between transcription factors and binding sites that lead to erroneous regulatory states -- and understand the constraints this places on the design of regulatory systems. I will then develop a generic theoretical framework to investigate the coevolution of multiple transcription factors and multiple binding sites, in the context of a gene regulatory network that performs a certain function. As a particular tractable version of this problem, I will consider the evolution of two transcription factors when they transmit upstream signals to downstream target genes. Specifically, I will describe the evolutionary steady states and the evolutionary pathways involved, along with their timescales, of a system that initially undergoes a transcription factor duplication event. To connect this important theoretical model to the prominent biological event of transcription factor duplication giving rise to paralogous families, I will then describe a bioinformatics analysis of C2H2 Zn-finger transcription factors, a major family in humans, and focus on the patterns of evolution that paralogs have undergone in their various protein domains in the recent past.
AU - Prizak, Roshan
ID - 6071
SN - 2663-337X
TI - Coevolution of transcription factors and their binding sites in sequence space
ER -
TY - JOUR
AB - We consider large random matrices with a general slowly decaying correlation among its entries. We prove universality of the local eigenvalue statistics and optimal local laws for the resolvent away from the spectral edges, generalizing the recent result of Ajanki et al. [‘Stability of the matrix Dyson equation and random matrices with correlations’, Probab. Theory Related Fields 173(1–2) (2019), 293–373] to allow slow correlation decay and arbitrary expectation. The main novel tool is
a systematic diagrammatic control of a multivariate cumulant expansion.
AU - Erdös, László
AU - Krüger, Torben H
AU - Schröder, Dominik J
ID - 6182
JF - Forum of Mathematics, Sigma
TI - Random matrices with slow correlation decay
VL - 7
ER -
TY - JOUR
AB - We prove that the local eigenvalue statistics of real symmetric Wigner-type
matrices near the cusp points of the eigenvalue density are universal. Together
with the companion paper [arXiv:1809.03971], which proves the same result for
the complex Hermitian symmetry class, this completes the last remaining case of
the Wigner-Dyson-Mehta universality conjecture after bulk and edge
universalities have been established in the last years. We extend the recent
Dyson Brownian motion analysis at the edge [arXiv:1712.03881] to the cusp
regime using the optimal local law from [arXiv:1809.03971] and the accurate
local shape analysis of the density from [arXiv:1506.05095, arXiv:1804.07752].
We also present a PDE-based method to improve the estimate on eigenvalue
rigidity via the maximum principle of the heat flow related to the Dyson
Brownian motion.
AU - Cipolloni, Giorgio
AU - Erdös, László
AU - Krüger, Torben H
AU - Schröder, Dominik J
ID - 6186
IS - 4
JF - Pure and Applied Analysis
SN - 2578-5893
TI - Cusp universality for random matrices, II: The real symmetric case
VL - 1
ER -
TY - JOUR
AB - Across diverse biological systems—ranging from neural networks to intracellular signaling and genetic regulatory networks—the information about changes in the environment is frequently encoded in the full temporal dynamics of the network nodes. A pressing data-analysis challenge has thus been to efficiently estimate the amount of information that these dynamics convey from experimental data. Here we develop and evaluate decoding-based estimation methods to lower bound the mutual information about a finite set of inputs, encoded in single-cell high-dimensional time series data. For biological reaction networks governed by the chemical Master equation, we derive model-based information approximations and analytical upper bounds, against which we benchmark our proposed model-free decoding estimators. In contrast to the frequently-used k-nearest-neighbor estimator, decoding-based estimators robustly extract a large fraction of the available information from high-dimensional trajectories with a realistic number of data samples. We apply these estimators to previously published data on Erk and Ca2+ signaling in mammalian cells and to yeast stress-response, and find that substantial amount of information about environmental state can be encoded by non-trivial response statistics even in stationary signals. We argue that these single-cell, decoding-based information estimates, rather than the commonly-used tests for significant differences between selected population response statistics, provide a proper and unbiased measure for the performance of biological signaling networks.
AU - Cepeda Humerez, Sarah A
AU - Ruess, Jakob
AU - Tkačik, Gašper
ID - 6900
IS - 9
JF - PLoS computational biology
TI - Estimating information in time-varying signals
VL - 15
ER -
TY - THES
AB - Tissue morphogenesis in developmental or physiological processes is regulated by molecular
and mechanical signals. While the molecular signaling cascades are increasingly well
described, the mechanical signals affecting tissue shape changes have only recently been
studied in greater detail. To gain more insight into the mechanochemical and biophysical
basis of an epithelial spreading process (epiboly) in early zebrafish development, we studied
cell-cell junction formation and actomyosin network dynamics at the boundary between
surface layer epithelial cells (EVL) and the yolk syncytial layer (YSL). During zebrafish epiboly,
the cell mass sitting on top of the yolk cell spreads to engulf the yolk cell by the end of
gastrulation. It has been previously shown that an actomyosin ring residing within the YSL
pulls on the EVL tissue through a cable-constriction and a flow-friction motor, thereby
dragging the tissue vegetal wards. Pulling forces are likely transmitted from the YSL
actomyosin ring to EVL cells; however, the nature and formation of the junctional structure
mediating this process has not been well described so far. Therefore, our main aim was to
determine the nature, dynamics and potential function of the EVL-YSL junction during this
epithelial tissue spreading. Specifically, we show that the EVL-YSL junction is a
mechanosensitive structure, predominantly made of tight junction (TJ) proteins. The process
of TJ mechanosensation depends on the retrograde flow of non-junctional, phase-separated
Zonula Occludens-1 (ZO-1) protein clusters towards the EVL-YSL boundary. Interestingly, we
could demonstrate that ZO-1 is present in a non-junctional pool on the surface of the yolk
cell, and ZO-1 undergoes a phase separation process that likely renders the protein
responsive to flows. These flows are directed towards the junction and mediate proper
tension-dependent recruitment of ZO-1. Upon reaching the EVL-YSL junction ZO-1 gets
incorporated into the junctional pool mediated through its direct actin-binding domain.
When the non-junctional pool and/or ZO-1 direct actin binding is absent, TJs fail in their
proper mechanosensitive responses resulting in slower tissue spreading. We could further
demonstrate that depletion of ZO proteins within the YSL results in diminished actomyosin
ring formation. This suggests that a mechanochemical feedback loop is at work during
zebrafish epiboly: ZO proteins help in proper actomyosin ring formation and actomyosin
contractility and flows positively influence ZO-1 junctional recruitment. Finally, such a
mesoscale polarization process mediated through the flow of phase-separated protein
clusters might have implications for other processes such as immunological synapse
formation, C. elegans zygote polarization and wound healing.
AU - Schwayer, Cornelia
ID - 7186
SN - 2663-337X
TI - Mechanosensation of tight junctions depends on ZO-1 phase separation and flow
ER -
TY - THES
AB - The first part of the thesis considers the computational aspects of the homotopy groups πd(X) of a topological space X. It is well known that there is no algorithm to decide whether the fundamental group π1(X) of a given finite simplicial complex X is trivial. On the other hand, there are several algorithms that, given a finite simplicial complex X that is simply connected (i.e., with π1(X) trivial), compute the higher homotopy group πd(X) for any given d ≥ 2.
However, these algorithms come with a caveat: They compute the isomorphism type of πd(X), d ≥ 2 as an abstract finitely generated abelian group given by generators and relations, but they work with very implicit representations of the elements of πd(X). We present an algorithm that, given a simply connected space X, computes πd(X) and represents its elements as simplicial maps from suitable triangulations of the d-sphere Sd to X. For fixed d, the algorithm runs in time exponential in size(X), the number of simplices of X. Moreover, we prove that this is optimal: For every fixed d ≥ 2,
we construct a family of simply connected spaces X such that for any simplicial map representing a generator of πd(X), the size of the triangulation of S d on which the map is defined, is exponential in size(X).
In the second part of the thesis, we prove that the following question is algorithmically undecidable for d < ⌊3(k+1)/2⌋, k ≥ 5 and (k, d) ̸= (5, 7), which covers essentially everything outside the meta-stable range: Given a finite simplicial complex K of dimension k, decide whether there exists a piecewise-linear (i.e., linear on an arbitrarily fine subdivision of K) embedding f : K ↪→ Rd of K into a d-dimensional Euclidean space.
AU - Zhechev, Stephan Y
ID - 6681
SN - 2663-337X
TI - Algorithmic aspects of homotopy theory and embeddability
ER -
TY - GEN
AB - Suppose that $n\neq p^k$ and $n\neq 2p^k$ for all $k$ and all primes $p$. We prove that for any Hausdorff compactum $X$ with a free action of the symmetric group $\mathfrak S_n$ there exists an $\mathfrak S_n$-equivariant map $X \to
{\mathbb R}^n$ whose image avoids the diagonal $\{(x,x\dots,x)\in {\mathbb R}^n|x\in {\mathbb R}\}$.
Previously, the special cases of this statement for certain $X$ were usually proved using the equivartiant obstruction theory. Such calculations are difficult and may become infeasible past the first (primary) obstruction. We
take a different approach which allows us to prove the vanishing of all obstructions simultaneously. The essential step in the proof is classifying the possible degrees of $\mathfrak S_n$-equivariant maps from the boundary
$\partial\Delta^{n-1}$ of $(n-1)$-simplex to itself. Existence of equivariant maps between spaces is important for many questions arising from discrete mathematics and geometry, such as Kneser's conjecture, the Square Peg conjecture, the Splitting Necklace problem, and the Topological Tverberg conjecture, etc. We demonstrate the utility of our result applying it to one such question, a specific instance of envy-free division problem.
AU - Avvakumov, Sergey
AU - Kudrya, Sergey
ID - 8182
T2 - arXiv
TI - Vanishing of all equivariant obstructions and the mapping degree
ER -
TY - GEN
AB - In this paper we study envy-free division problems. The classical approach to some of such problems, used by David Gale, reduces to considering continuous maps of a simplex to itself and finding sufficient conditions when this map hits the center of the simplex. The mere continuity is not sufficient for such a conclusion, the usual assumption (for example, in the Knaster--Kuratowski--Mazurkiewicz and the Gale theorem) is a certain boundary condition.
We follow Erel Segal-Halevi, Fr\'ed\'eric Meunier, and Shira Zerbib, and replace the boundary condition by another assumption, which has the economic meaning of possibility for a player to prefer an empty part in the segment
partition problem. We solve the problem positively when $n$, the number of players that divide the segment, is a prime power, and we provide counterexamples for every $n$ which is not a prime power. We also provide counterexamples relevant to a wider class of fair or envy-free partition problems when $n$ is odd and not a prime power.
AU - Avvakumov, Sergey
AU - Karasev, Roman
ID - 8185
T2 - arXiv
TI - Envy-free division using mapping degree
ER -
TY - GEN
AB - We prove a lower bound for the free energy (per unit volume) of the two-dimensional Bose gas in the thermodynamic limit. We show that the free energy at density $\rho$ and inverse temperature $\beta$ differs from the one of the non-interacting system by the correction term $4 \pi \rho^2 |\ln a^2 \rho|^{-1} (2 - [1 - \beta_{\mathrm{c}}/\beta]_+^2)$. Here $a$ is the scattering length of the interaction potential, $[\cdot]_+ = \max\{ 0, \cdot \}$ and $\beta_{\mathrm{c}}$ is the inverse Berezinskii--Kosterlitz--Thouless critical temperature for superfluidity. The result is valid in the dilute limit
$a^2\rho \ll 1$ and if $\beta \rho \gtrsim 1$.
AU - Deuchert, Andreas
AU - Mayer, Simon
AU - Seiringer, Robert
ID - 7524
T2 - arXiv:1910.03372
TI - The free energy of the two-dimensional dilute Bose gas. I. Lower bound
ER -
TY - JOUR
AB - We use the canonical bases produced by the tri-partition algorithm in (Edelsbrunner and Ölsböck, 2018) to open and close holes in a polyhedral complex, K. In a concrete application, we consider the Delaunay mosaic of a finite set, we let K be an Alpha complex, and we use the persistence diagram of the distance function to guide the hole opening and closing operations. The dependences between the holes define a partial order on the cells in K that characterizes what can and what cannot be constructed using the operations. The relations in this partial order reveal structural information about the underlying filtration of complexes beyond what is expressed by the persistence diagram.
AU - Edelsbrunner, Herbert
AU - Ölsböck, Katharina
ID - 6608
JF - Computer Aided Geometric Design
TI - Holes and dependences in an ordered complex
VL - 73
ER -
TY - CONF
AB - The Fiat-Shamir heuristic transforms a public-coin interactive proof into a non-interactive argument, by replacing the verifier with a cryptographic hash function that is applied to the protocol’s transcript. Constructing hash functions for which this transformation is sound is a central and long-standing open question in cryptography.
We show that solving the END−OF−METERED−LINE problem is no easier than breaking the soundness of the Fiat-Shamir transformation when applied to the sumcheck protocol. In particular, if the transformed protocol is sound, then any hard problem in #P gives rise to a hard distribution in the class CLS, which is contained in PPAD. Our result opens up the possibility of sampling moderately-sized games for which it is hard to find a Nash equilibrium, by reducing the inversion of appropriately chosen one-way functions to #SAT.
Our main technical contribution is a stateful incrementally verifiable procedure that, given a SAT instance over n variables, counts the number of satisfying assignments. This is accomplished via an exponential sequence of small steps, each computable in time poly(n). Incremental verifiability means that each intermediate state includes a sumcheck-based proof of its correctness, and the proof can be updated and verified in time poly(n).
AU - Choudhuri, Arka Rai
AU - Hubáček, Pavel
AU - Kamath Hosdurg, Chethan
AU - Pietrzak, Krzysztof Z
AU - Rosen, Alon
AU - Rothblum, Guy N.
ID - 6677
SN - 9781450367059
T2 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019
TI - Finding a Nash equilibrium is no easier than breaking Fiat-Shamir
ER -
TY - JOUR
AB - Given a triangulation of a point set in the plane, a flip deletes an edge e whose removal leaves a convex quadrilateral, and replaces e by the opposite diagonal of the quadrilateral. It is well known that any triangulation of a point set can be reconfigured to any other triangulation by some sequence of flips. We explore this question in the setting where each edge of a triangulation has a label, and a flip transfers the label of the removed edge to the new edge. It is not true that every labelled triangulation of a point set can be reconfigured to every other labelled triangulation via a sequence of flips, but we characterize when this is possible. There is an obvious necessary condition: for each label l, if edge e has label l in the first triangulation and edge f has label l in the second triangulation, then there must be some sequence of flips that moves label l from e to f, ignoring all other labels. Bose, Lubiw, Pathak and Verdonschot formulated the Orbit Conjecture, which states that this necessary condition is also sufficient, i.e. that all labels can be simultaneously mapped to their destination if and only if each label individually can be mapped to its destination. We prove this conjecture. Furthermore, we give a polynomial-time algorithm (with 𝑂(𝑛8) being a crude bound on the run-time) to find a sequence of flips to reconfigure one labelled triangulation to another, if such a sequence exists, and we prove an upper bound of 𝑂(𝑛7) on the length of the flip sequence. Our proof uses the topological result that the sets of pairwise non-crossing edges on a planar point set form a simplicial complex that is homeomorphic to a high-dimensional ball (this follows from a result of Orden and Santos; we give a different proof based on a shelling argument). The dual cell complex of this simplicial ball, called the flip complex, has the usual flip graph as its 1-skeleton. We use properties of the 2-skeleton of the flip complex to prove the Orbit Conjecture.
AU - Lubiw, Anna
AU - Masárová, Zuzana
AU - Wagner, Uli
ID - 5986
IS - 4
JF - Discrete & Computational Geometry
SN - 0179-5376
TI - A proof of the orbit conjecture for flipping edge-labelled triangulations
VL - 61
ER -
TY - JOUR
AB - Problems involving quantum impurities, in which one or a few particles are interacting with a macroscopic environment, represent a pervasive paradigm, spanning across atomic, molecular, and condensed-matter physics. In this paper we introduce new variational approaches to quantum impurities and apply them to the Fröhlich polaron–a quasiparticle formed out of an electron (or other point-like impurity) in a polar medium, and to the angulon–a quasiparticle formed out of a rotating molecule in a bosonic bath. We benchmark these approaches against established theories, evaluating their accuracy as a function of the impurity-bath coupling.
AU - Li, Xiang
AU - Bighin, Giacomo
AU - Yakaboylu, Enderalp
AU - Lemeshko, Mikhail
ID - 5886
JF - Molecular Physics
SN - 00268976
TI - Variational approaches to quantum impurities: from the Fröhlich polaron to the angulon
ER -
TY - GEN
AB - The input to the token swapping problem is a graph with vertices v1, v2, . . . , vn, and n tokens with labels 1,2, . . . , n, one on each vertex. The goal is to get token i to vertex vi for all i= 1, . . . , n using a minimum number of swaps, where a swap exchanges the tokens on the endpoints of an edge.Token swapping on a tree, also known as “sorting with a transposition tree,” is not known to be in P nor NP-complete. We present some partial results:
1. An optimum swap sequence may need to perform a swap on a leaf vertex that has the correct token (a “happy leaf”), disproving a conjecture of Vaughan.
2. Any algorithm that fixes happy leaves—as all known approximation algorithms for the problem do—has approximation factor at least 4/3. Furthermore, the two best-known 2-approximation algorithms have approximation factor exactly 2.
3. A generalized problem—weighted coloured token swapping—is NP-complete on trees, but solvable in polynomial time on paths and stars. In this version, tokens and vertices have colours, and colours have weights. The goal is to get every token to a vertex of the same colour, and the cost of a swap is the sum of the weights of the two tokens involved.
AU - Biniaz, Ahmad
AU - Jain, Kshitij
AU - Lubiw, Anna
AU - Masárová, Zuzana
AU - Miltzow, Tillmann
AU - Mondal, Debajyoti
AU - Naredla, Anurag Murty
AU - Tkadlec, Josef
AU - Turcotte, Alexi
ID - 7950
T2 - arXiv
TI - Token swapping on trees
ER -
TY - CONF
AB - Motivated by fixed-parameter tractable (FPT) problems in computational topology, we consider the treewidth tw(M) of a compact, connected 3-manifold M, defined to be the minimum treewidth of the face pairing graph of any triangulation T of M. In this setting the relationship between the topology of a 3-manifold and its treewidth is of particular interest. First, as a corollary of work of Jaco and Rubinstein, we prove that for any closed, orientable 3-manifold M the treewidth tw(M) is at most 4g(M)-2, where g(M) denotes Heegaard genus of M. In combination with our earlier work with Wagner, this yields that for non-Haken manifolds the Heegaard genus and the treewidth are within a constant factor. Second, we characterize all 3-manifolds of treewidth one: These are precisely the lens spaces and a single other Seifert fibered space. Furthermore, we show that all remaining orientable Seifert fibered spaces over the 2-sphere or a non-orientable surface have treewidth two. In particular, for every spherical 3-manifold we exhibit a triangulation of treewidth at most two. Our results further validate the parameter of treewidth (and other related parameters such as cutwidth or congestion) to be useful for topological computing, and also shed more light on the scope of existing FPT-algorithms in the field.
AU - Huszár, Kristóf
AU - Spreer, Jonathan
ID - 6556
KW - computational 3-manifold topology
KW - fixed-parameter tractability
KW - layered triangulations
KW - structural graph theory
KW - treewidth
KW - cutwidth
KW - Heegaard genus
SN - 1868-8969
T2 - 35th International Symposium on Computational Geometry
TI - 3-manifold triangulations with small treewidth
VL - 129
ER -
TY - JOUR
AB - In graph theory, as well as in 3-manifold topology, there exist several width-type parameters to describe how "simple" or "thin" a given graph or 3-manifold is. These parameters, such as pathwidth or treewidth for graphs, or the concept of thin position for 3-manifolds, play an important role when studying algorithmic problems; in particular, there is a variety of problems in computational 3-manifold topology - some of them known to be computationally hard in general - that become solvable in polynomial time as soon as the dual graph of the input triangulation has bounded treewidth.
In view of these algorithmic results, it is natural to ask whether every 3-manifold admits a triangulation of bounded treewidth. We show that this is not the case, i.e., that there exists an infinite family of closed 3-manifolds not admitting triangulations of bounded pathwidth or treewidth (the latter implies the former, but we present two separate proofs).
We derive these results from work of Agol, of Scharlemann and Thompson, and of Scharlemann, Schultens and Saito by exhibiting explicit connections between the topology of a 3-manifold M on the one hand and width-type parameters of the dual graphs of triangulations of M on the other hand, answering a question that had been raised repeatedly by researchers in computational 3-manifold topology. In particular, we show that if a closed, orientable, irreducible, non-Haken 3-manifold M has a triangulation of treewidth (resp. pathwidth) k then the Heegaard genus of M is at most 18(k+1) (resp. 4(3k+1)).
AU - Huszár, Kristóf
AU - Spreer, Jonathan
AU - Wagner, Uli
ID - 7093
IS - 2
JF - Journal of Computational Geometry
SN - 1920-180X
TI - On the treewidth of triangulated 3-manifolds
VL - 10
ER -
TY - JOUR
AB - During bacterial cell division, the tubulin-homolog FtsZ forms a ring-like structure at the center of the cell. This Z-ring not only organizes the division machinery, but treadmilling of FtsZ filaments was also found to play a key role in distributing proteins at the division site. What regulates the architecture, dynamics and stability of the Z-ring is currently unknown, but FtsZ-associated proteins are known to play an important role. Here, using an in vitro reconstitution approach, we studied how the well-conserved protein ZapA affects FtsZ treadmilling and filament organization into large-scale patterns. Using high-resolution fluorescence microscopy and quantitative image analysis, we found that ZapA cooperatively increases the spatial order of the filament network, but binds only transiently to FtsZ filaments and has no effect on filament length and treadmilling velocity. Together, our data provides a model for how FtsZ-associated proteins can increase the precision and stability of the bacterial cell division machinery in a switch-like manner.
AU - Dos Santos Caldas, Paulo R
AU - Lopez Pelegrin, Maria D
AU - Pearce, Daniel J. G.
AU - Budanur, Nazmi B
AU - Brugués, Jan
AU - Loose, Martin
ID - 7197
JF - Nature Communications
SN - 2041-1723
TI - Cooperative ordering of treadmilling filaments in cytoskeletal networks of FtsZ and its crosslinker ZapA
VL - 10
ER -
TY - JOUR
AB - The rate of biological evolution depends on the fixation probability and on the fixation time of new mutants. Intensive research has focused on identifying population structures that augment the fixation probability of advantageous mutants. But these amplifiers of natural selection typically increase fixation time. Here we study population structures that achieve a tradeoff between fixation probability and time. First, we show that no amplifiers can have an asymptotically lower absorption time than the well-mixed population. Then we design population structures that substantially augment the fixation probability with just a minor increase in fixation time. Finally, we show that those structures enable higher effective rate of evolution than the well-mixed population provided that the rate of generating advantageous mutants is relatively low. Our work sheds light on how population structure affects the rate of evolution. Moreover, our structures could be useful for lab-based, medical, or industrial applications of evolutionary optimization.
AU - Tkadlec, Josef
AU - Pavlogiannis, Andreas
AU - Chatterjee, Krishnendu
AU - Nowak, Martin A.
ID - 7210
JF - Communications Biology
SN - 2399-3642
TI - Population structure determines the tradeoff between fixation probability and fixation time
VL - 2
ER -
TY - CONF
AB - The verification of concurrent programs remains an open challenge, as thread interaction has to be accounted for, which leads to state-space explosion. Stateless model checking battles this problem by exploring traces rather than states of the program. As there are exponentially many traces, dynamic partial-order reduction (DPOR) techniques are used to partition the trace space into equivalence classes, and explore a few representatives from each class. The standard equivalence that underlies most DPOR techniques is the happens-before equivalence, however recent works have spawned a vivid interest towards coarser equivalences. The efficiency of such approaches is a product of two parameters: (i) the size of the partitioning induced by the equivalence, and (ii) the time spent by the exploration algorithm in each class of the partitioning. In this work, we present a new equivalence, called value-happens-before and show that it has two appealing features. First, value-happens-before is always at least as coarse as the happens-before equivalence, and can be even exponentially coarser. Second, the value-happens-before partitioning is efficiently explorable when the number of threads is bounded. We present an algorithm called value-centric DPOR (VCDPOR), which explores the underlying partitioning using polynomial time per class. Finally, we perform an experimental evaluation of VCDPOR on various benchmarks, and compare it against other state-of-the-art approaches. Our results show that value-happens-before typically induces a significant reduction in the size of the underlying partitioning, which leads to a considerable reduction in the running time for exploring the whole partitioning.
AU - Chatterjee, Krishnendu
AU - Pavlogiannis, Andreas
AU - Toman, Viktor
ID - 10190
KW - safety
KW - risk
KW - reliability and quality
KW - software
T2 - Proceedings of the 34th ACM International Conference on Object-Oriented Programming, Systems, Languages, and Applications
TI - Value-centric dynamic partial order reduction
VL - 3
ER -
TY - CONF
AB - Several classic problems in graph processing and computational geometry are solved via incremental algorithms, which split computation into a series of small tasks acting on shared state, which gets updated progressively. While the sequential variant of such algorithms usually specifies a fixed (but sometimes random) order in which the tasks should be performed, a standard approach to parallelizing such algorithms is to relax this constraint to allow for out-of-order parallel execution. This is the case for parallel implementations of Dijkstra's single-source shortest-paths (SSSP) algorithm, and for parallel Delaunay mesh triangulation. While many software frameworks parallelize incremental computation in this way, it is still not well understood whether this relaxed ordering approach can still provide any complexity guarantees. In this paper, we address this problem, and analyze the efficiency guarantees provided by a range of incremental algorithms when parallelized via relaxed schedulers. We show that, for algorithms such as Delaunay mesh triangulation and sorting by insertion, schedulers with a maximum relaxation factor of k in terms of the maximum priority inversion allowed will introduce a maximum amount of wasted work of O(łog n poly(k)), where n is the number of tasks to be executed. For SSSP, we show that the additional work is O(poly(k), dmax / wmin), where dmax is the maximum distance between two nodes, and wmin is the minimum such distance. In practical settings where n >> k, this suggests that the overheads of relaxation will be outweighed by the improved scalability of the relaxed scheduler. On the negative side, we provide lower bounds showing that certain algorithms will inherently incur a non-trivial amount of wasted work due to scheduler relaxation, even for relatively benign relaxed schedulers.
AU - Alistarh, Dan-Adrian
AU - Nadiradze, Giorgi
AU - Koval, Nikita
ID - 6673
SN - 9781450361842
T2 - 31st ACM Symposium on Parallelism in Algorithms and Architectures
TI - Efficiency guarantees for parallel incremental algorithms under relaxed schedulers
ER -
TY - CONF
AB - Modern machine learning methods often require more data for training than a single expert can provide. Therefore, it has become a standard procedure to collect data from external sources, e.g. via crowdsourcing. Unfortunately, the quality of these sources is not always guaranteed. As additional complications, the data might be stored in a distributed way, or might even have to remain private. In this work, we address the question of how to learn robustly in such scenarios. Studying the problem through the lens of statistical learning theory, we derive a procedure that allows for learning from all available sources, yet automatically suppresses irrelevant or corrupted data. We show by extensive experiments that our method provides significant improvements over alternative approaches from robust statistics and distributed optimization.
AU - Konstantinov, Nikola H
AU - Lampert, Christoph
ID - 6590
T2 - Proceedings of the 36th International Conference on Machine Learning
TI - Robust learning from untrusted sources
VL - 97
ER -
TY - JOUR
AB - The angular momentum of molecules, or, equivalently, their rotation in three-dimensional space, is ideally suited for quantum control. Molecular angular momentum is naturally quantized, time evolution is governed by a well-known Hamiltonian with only a few accurately known parameters, and transitions between rotational levels can be driven by external fields from various parts of the electromagnetic spectrum. Control over the rotational motion can be exerted in one-, two-, and many-body scenarios, thereby allowing one to probe Anderson localization, target stereoselectivity of bimolecular reactions, or encode quantum information to name just a few examples. The corresponding approaches to quantum control are pursued within separate, and typically disjoint, subfields of physics, including ultrafast science, cold collisions, ultracold gases, quantum information science, and condensed-matter physics. It is the purpose of this review to present the various control phenomena, which all rely on the same underlying physics, within a unified framework. To this end, recall the Hamiltonian for free rotations, assuming the rigid rotor approximation to be valid, and summarize the different ways for a rotor to interact with external electromagnetic fields. These interactions can be exploited for control—from achieving alignment, orientation, or laser cooling in a one-body framework, steering bimolecular collisions, or realizing a quantum computer or quantum simulator in the many-body setting.
AU - Koch, Christiane P.
AU - Lemeshko, Mikhail
AU - Sugny, Dominique
ID - 7396
IS - 3
JF - Reviews of Modern Physics
SN - 0034-6861
TI - Quantum control of molecular rotation
VL - 91
ER -
TY - JOUR
AB - Long non-coding (lnc) RNAs are numerous and found throughout the mammalian genome, and many are thought to be involved in the regulation of gene expression. However, the majority remain relatively uncharacterised and of uncertain function making the use of model systems to uncover their mode of action valuable. Imprinted lncRNAs target and recruit epigenetic silencing factors to a cluster of imprinted genes on the same chromosome, making them one of the best characterized lncRNAs for silencing distant genes in cis. In this study we examined silencing of the distant imprinted gene Slc22a3 by the lncRNA Airn in the Igf2r imprinted cluster in mouse. Previously we proposed that imprinted lncRNAs may silence distant imprinted genes by disrupting promoter-enhancer interactions by being transcribed through the enhancer, which we called the enhancer interference hypothesis. Here we tested this hypothesis by first using allele-specific chromosome conformation capture (3C) to detect interactions between the Slc22a3 promoter and the locus of the Airn lncRNA that silences it on the paternal chromosome. In agreement with the model, we found interactions enriched on the maternal allele across the entire Airn gene consistent with multiple enhancer-promoter interactions. Therefore, to test the enhancer interference hypothesis we devised an approach to delete the entire Airn gene. However, the deletion showed that there are no essential enhancers for Slc22a2, Pde10a and Slc22a3 within the Airn gene, strongly indicating that the Airn RNA rather than its transcription is responsible for silencing distant imprinted genes. Furthermore, we found that silent imprinted genes were covered with large blocks of H3K27me3 on the repressed paternal allele. Therefore we propose an alternative hypothesis whereby the chromosome interactions may initially guide the lncRNA to target imprinted promoters and recruit repressive chromatin, and that these interactions are lost once silencing is established.
AU - Andergassen, Daniel
AU - Muckenhuber, Markus
AU - Bammer, Philipp C.
AU - Kulinski, Tomasz M.
AU - Theussl, Hans-Christian
AU - Shimizu, Takahiko
AU - Penninger, Josef M.
AU - Pauler, Florian
AU - Hudson, Quanah J.
ID - 7399
IS - 7
JF - PLOS Genetics
SN - 1553-7404
TI - The Airn lncRNA does not require any DNA elements within its locus to silence distant imprinted genes
VL - 15
ER -
TY - JOUR
AB - Transporters of the solute carrier 6 (SLC6) family translocate their cognate substrate together with Na+ and Cl−. Detailed kinetic models exist for the transporters of GABA (GAT1/SLC6A1) and the monoamines dopamine (DAT/SLC6A3) and serotonin (SERT/SLC6A4). Here, we posited that the transport cycle of individual SLC6 transporters reflects the physiological requirements they operate under. We tested this hypothesis by analyzing the transport cycle of glycine transporter 1 (GlyT1/SLC6A9) and glycine transporter 2 (GlyT2/SLC6A5). GlyT2 is the only SLC6 family member known to translocate glycine, Na+, and Cl− in a 1:3:1 stoichiometry. We analyzed partial reactions in real time by electrophysiological recordings. Contrary to monoamine transporters, both GlyTs were found to have a high transport capacity driven by rapid return of the empty transporter after release of Cl− on the intracellular side. Rapid cycling of both GlyTs was further supported by highly cooperative binding of cosubstrate ions and substrate such that their forward transport mode was maintained even under conditions of elevated intracellular Na+ or Cl−. The most important differences in the transport cycle of GlyT1 and GlyT2 arose from the kinetics of charge movement and the resulting voltage-dependent rate-limiting reactions: the kinetics of GlyT1 were governed by transition of the substrate-bound transporter from outward- to inward-facing conformations, whereas the kinetics of GlyT2 were governed by Na+ binding (or a related conformational change). Kinetic modeling showed that the kinetics of GlyT1 are ideally suited for supplying the extracellular glycine levels required for NMDA receptor activation.
AU - Erdem, Fatma Asli
AU - Ilic, Marija
AU - Koppensteiner, Peter
AU - Gołacki, Jakub
AU - Lubec, Gert
AU - Freissmuth, Michael
AU - Sandtner, Walter
ID - 7398
IS - 8
JF - The Journal of General Physiology
SN - 0022-1295
TI - A comparison of the transport kinetics of glycine transporter 1 and glycine transporter 2
VL - 151
ER -
TY - JOUR
AB - The mitochondrial electron transport chain complexes are organized into supercomplexes (SCs) of defined stoichiometry, which have been proposed to regulate electron flux via substrate channeling. We demonstrate that CoQ trapping in the isolated SC I+III2 limits complex (C)I turnover, arguing against channeling. The SC structure, resolved at up to 3.8 Å in four distinct states, suggests that CoQ oxidation may be rate limiting because of unequal access of CoQ to the active sites of CIII2. CI shows a transition between “closed” and “open” conformations, accompanied by the striking rotation of a key transmembrane helix. Furthermore, the state of CI affects the conformational flexibility within CIII2, demonstrating crosstalk between the enzymes. CoQ was identified at only three of the four binding sites in CIII2, suggesting that interaction with CI disrupts CIII2 symmetry in a functionally relevant manner. Together, these observations indicate a more nuanced functional role for the SCs.
AU - Letts, James A
AU - Fiedorczuk, Karol
AU - Degliesposti, Gianluca
AU - Skehel, Mark
AU - Sazanov, Leonid A
ID - 7395
IS - 6
JF - Molecular Cell
SN - 1097-2765
TI - Structures of respiratory supercomplex I+III2 reveal functional and conformational crosstalk
VL - 75
ER -
TY - JOUR
AB - Biophysical modeling of neuronal networks helps to integrate and interpret rapidly growing and disparate experimental datasets at multiple scales. The NetPyNE tool (www.netpyne.org) provides both programmatic and graphical interfaces to develop data-driven multiscale network models in NEURON. NetPyNE clearly separates model parameters from implementation code. Users provide specifications at a high level via a standardized declarative language, for example connectivity rules, to create millions of cell-to-cell connections. NetPyNE then enables users to generate the NEURON network, run efficiently parallelized simulations, optimize and explore network parameters through automated batch runs, and use built-in functions for visualization and analysis – connectivity matrices, voltage traces, spike raster plots, local field potentials, and information theoretic measures. NetPyNE also facilitates model sharing by exporting and importing standardized formats (NeuroML and SONATA). NetPyNE is already being used to teach computational neuroscience students and by modelers to investigate brain regions and phenomena.
AU - Dura-Bernal, Salvador
AU - Suter, Benjamin
AU - Gleeson, Padraig
AU - Cantarelli, Matteo
AU - Quintana, Adrian
AU - Rodriguez, Facundo
AU - Kedziora, David J
AU - Chadderdon, George L
AU - Kerr, Cliff C
AU - Neymotin, Samuel A
AU - McDougal, Robert A
AU - Hines, Michael
AU - Shepherd, Gordon MG
AU - Lytton, William W
ID - 7405
JF - eLife
SN - 2050-084X
TI - NetPyNE, a tool for data-driven multiscale modeling of brain circuits
VL - 8
ER -
TY - JOUR
AB - Suppressed recombination allows divergence between homologous sex chromosomes and the functionality of their genes. Here, we reveal patterns of the earliest stages of sex-chromosome evolution in the diploid dioecious herb Mercurialis annua on the basis of cytological analysis, de novo genome assembly and annotation, genetic mapping, exome resequencing of natural populations, and transcriptome analysis. The genome assembly contained 34,105 expressed genes, of which 10,076 were assigned to linkage groups. Genetic mapping and exome resequencing of individuals across the species range both identified the largest linkage group, LG1, as the sex chromosome. Although the sex chromosomes of M. annua are karyotypically homomorphic, we estimate that about one-third of the Y chromosome, containing 568 transcripts and spanning 22.3 cM in the corresponding female map, has ceased recombining. Nevertheless, we found limited evidence for Y-chromosome degeneration in terms of gene loss and pseudogenization, and most X- and Y-linked genes appear to have diverged in the period subsequent to speciation between M. annua and its sister species M. huetii, which shares the same sex-determining region. Taken together, our results suggest that the M. annua Y chromosome has at least two evolutionary strata: a small old stratum shared with M. huetii, and a more recent larger stratum that is probably unique to M. annua and that stopped recombining ∼1 MYA. Patterns of gene expression within the nonrecombining region are consistent with the idea that sexually antagonistic selection may have played a role in favoring suppressed recombination.
AU - Veltsos, Paris
AU - Ridout, Kate E.
AU - Toups, Melissa A
AU - González-Martínez, Santiago C.
AU - Muyle, Aline
AU - Emery, Olivier
AU - Rastas, Pasi
AU - Hudzieczek, Vojtech
AU - Hobza, Roman
AU - Vyskot, Boris
AU - Marais, Gabriel A. B.
AU - Filatov, Dmitry A.
AU - Pannell, John R.
ID - 7400
IS - 3
JF - Genetics
SN - 0016-6731
TI - Early sex-chromosome evolution in the diploid dioecious plant Mercurialis annua
VL - 212
ER -
TY - JOUR
AB - The formation of neuronal dendrite branches is fundamental for the wiring and function of the nervous system. Indeed, dendrite branching enhances the coverage of the neuron's receptive field and modulates the initial processing of incoming stimuli. Complex dendrite patterns are achieved in vivo through a dynamic process of de novo branch formation, branch extension and retraction. The first step towards branch formation is the generation of a dynamic filopodium-like branchlet. The mechanisms underlying the initiation of dendrite branchlets are therefore crucial to the shaping of dendrites. Through in vivo time-lapse imaging of the subcellular localization of actin during the process of branching of Drosophila larva sensory neurons, combined with genetic analysis and electron tomography, we have identified the Actin-related protein (Arp) 2/3 complex as the major actin nucleator involved in the initiation of dendrite branchlet formation, under the control of the activator WAVE and of the small GTPase Rac1. Transient recruitment of an Arp2/3 component marks the site of branchlet initiation in vivo. These data position the activation of Arp2/3 as an early hub for the initiation of branchlet formation.
AU - Stürner, Tomke
AU - Tatarnikova, Anastasia
AU - Müller, Jan
AU - Schaffran, Barbara
AU - Cuntz, Hermann
AU - Zhang, Yun
AU - Nemethova, Maria
AU - Bogdan, Sven
AU - Small, Vic
AU - Tavosanis, Gaia
ID - 7404
IS - 7
JF - Development
SN - 0950-1991
TI - Transient localization of the Arp2/3 complex initiates neuronal dendrite branching in vivo
VL - 146
ER -
TY - CONF
AB - Graph planning gives rise to fundamental algorithmic questions such as shortest path, traveling salesman problem, etc. A classical problem in discrete planning is to consider a weighted graph and construct a path that maximizes the sum of weights for a given time horizon T. However, in many scenarios, the time horizon is not fixed, but the stopping time is chosen according to some distribution such that the expected stopping time is T. If the stopping time distribution is not known, then to ensure robustness, the distribution is chosen by an adversary, to represent the worst-case scenario. A stationary plan for every vertex always chooses the same outgoing edge. For fixed horizon or fixed stopping-time distribution, stationary plans are not sufficient for optimality. Quite surprisingly we show that when an adversary chooses the stopping-time distribution with expected stopping time T, then stationary plans are sufficient. While computing optimal stationary plans for fixed horizon is NP-complete, we show that computing optimal stationary plans under adversarial stopping-time distribution can be achieved in polynomial time. Consequently, our polynomial-time algorithm for adversarial stopping time also computes an optimal plan among all possible plans.
AU - Chatterjee, Krishnendu
AU - Doyen, Laurent
ID - 7402
SN - 9781728136080
T2 - 34th Annual ACM/IEEE Symposium on Logic in Computer Science
TI - Graph planning with expected finite horizon
ER -
TY - JOUR
AB - We prove that the observable telegraph signal accompanying the bistability in the photon-blockade-breakdown regime of the driven and lossy Jaynes–Cummings model is the finite-size precursor of what in the thermodynamic limit is a genuine first-order phase transition. We construct a finite-size scaling of the system parameters to a well-defined thermodynamic limit, in which the system remains the same microscopic system, but the telegraph signal becomes macroscopic both in its timescale and intensity. The existence of such a finite-size scaling completes and justifies the classification of the photon-blockade-breakdown effect as a first-order dissipative quantum phase transition.
AU - Vukics, A.
AU - Dombi, A.
AU - Fink, Johannes M
AU - Domokos, P.
ID - 7451
JF - Quantum
SN - 2521-327X
TI - Finite-size scaling of the photon-blockade breakdown dissipative quantum phase transition
VL - 3
ER -
TY - CONF
AB - We present a new proximal bundle method for Maximum-A-Posteriori (MAP) inference in structured energy minimization problems. The method optimizes a Lagrangean relaxation of the original energy minimization problem using a multi plane block-coordinate Frank-Wolfe method that takes advantage of the specific structure of the Lagrangean decomposition. We show empirically that our method outperforms state-of-the-art Lagrangean decomposition based algorithms on some challenging Markov Random Field, multi-label discrete tomography and graph matching problems.
AU - Swoboda, Paul
AU - Kolmogorov, Vladimir
ID - 7468
SN - 10636919
T2 - Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition
TI - Map inference via block-coordinate Frank-Wolfe algorithm
VL - 2019-June
ER -
TY - CONF
AB - Multi-exit architectures, in which a stack of processing layers is interleaved with early output layers, allow the processing of a test example to stop early and thus save computation time and/or energy. In this work, we propose a new training procedure for multi-exit architectures based on the principle of knowledge distillation. The method encourage searly exits to mimic later, more accurate exits, by matching their output probabilities.
Experiments on CIFAR100 and ImageNet show that distillation-based training significantly improves the accuracy of early exits while maintaining state-of-the-art accuracy for late ones. The method is particularly beneficial when training data is limited and it allows a straightforward extension to semi-supervised learning,i.e. making use of unlabeled data at training time. Moreover, it takes only afew lines to implement and incurs almost no computational overhead at training time, and none at all at test time.
AU - Bui Thi Mai, Phuong
AU - Lampert, Christoph
ID - 7479
SN - 15505499
T2 - IEEE International Conference on Computer Vision
TI - Distillation-based training for multi-exit architectures
VL - 2019-October
ER -
TY - CONF
AB - We present a novel class of convolutional neural networks (CNNs) for set functions,i.e., data indexed with the powerset of a finite set. The convolutions are derivedas linear, shift-equivariant functions for various notions of shifts on set functions.The framework is fundamentally different from graph convolutions based on theLaplacian, as it provides not one but several basic shifts, one for each element inthe ground set. Prototypical experiments with several set function classificationtasks on synthetic datasets and on datasets derived from real-world hypergraphsdemonstrate the potential of our new powerset CNNs.
AU - Wendler, Chris
AU - Alistarh, Dan-Adrian
AU - Püschel, Markus
ID - 7542
SN - 1049-5258
TI - Powerset convolutional neural networks
VL - 32
ER -
TY - CONF
AB - We propose a new model for detecting visual relationships, such as "person riding motorcycle" or "bottle on table". This task is an important step towards comprehensive structured mage understanding, going beyond detecting individual objects. Our main novelty is a Box Attention mechanism that allows to model pairwise interactions between objects using standard object detection pipelines. The resulting model is conceptually clean, expressive and relies on well-justified training and prediction procedures. Moreover, unlike previously proposed approaches, our model does not introduce any additional complex components or hyperparameters on top of those already required by the underlying detection model. We conduct an experimental evaluation on two datasets, V-COCO and Open Images, demonstrating strong quantitative and qualitative results.
AU - Kolesnikov, Alexander
AU - Kuznetsova, Alina
AU - Lampert, Christoph
AU - Ferrari, Vittorio
ID - 7640
SN - 9781728150239
T2 - Proceedings of the 2019 International Conference on Computer Vision Workshop
TI - Detecting visual relationships using box attention
ER -
TY - CONF
AB - We derive a tight lower bound on equivocation (conditional entropy), or equivalently a tight upper bound on mutual information between a signal variable and channel outputs. The bound is in terms of the joint distribution of the signals and maximum a posteriori decodes (most probable signals given channel output). As part of our derivation, we describe the key properties of the distribution of signals, channel outputs and decodes, that minimizes equivocation and maximizes mutual information. This work addresses a problem in data analysis, where mutual information between signals and decodes is sometimes used to lower bound the mutual information between signals and channel outputs. Our result provides a corresponding upper bound.
AU - Hledik, Michal
AU - Sokolowski, Thomas R
AU - Tkačik, Gašper
ID - 7606
SN - 9781538669006
T2 - IEEE Information Theory Workshop, ITW 2019
TI - A tight upper bound on mutual information
ER -
TY - GEN
AB - Denote by ∆N the N-dimensional simplex. A map f : ∆N → Rd is an almost r-embedding if fσ1∩. . .∩fσr = ∅ whenever σ1, . . . , σr are pairwise disjoint faces. A counterexample to the topological Tverberg conjecture asserts that if r is not a prime power and d ≥ 2r + 1, then there is an almost r-embedding ∆(d+1)(r−1) → Rd. This was improved by Blagojevi´c–Frick–Ziegler using a simple construction of higher-dimensional counterexamples by taking k-fold join power of lower-dimensional ones. We improve this further (for d large compared to r): If r is not a prime power and N := (d+ 1)r−r l
d + 2 r + 1 m−2, then there is an almost r-embedding ∆N → Rd. For the r-fold van Kampen–Flores conjecture we also produce counterexamples which are stronger than previously known. Our proof is based on generalizations of the Mabillard–Wagner theorem on construction of almost r-embeddings from equivariant maps, and of the Ozaydin theorem on existence of equivariant maps.
AU - Avvakumov, Sergey
AU - Karasev, R.
AU - Skopenkov, A.
ID - 8184
T2 - arXiv
TI - Stronger counterexamples to the topological Tverberg conjecture
ER -
TY - CONF
AB - A proxy re-encryption (PRE) scheme is a public-key encryption scheme that allows the holder of a key pk to derive a re-encryption key for any other key 𝑝𝑘′. This re-encryption key lets anyone transform ciphertexts under pk into ciphertexts under 𝑝𝑘′ without having to know the underlying message, while transformations from 𝑝𝑘′ to pk should not be possible (unidirectional). Security is defined in a multi-user setting against an adversary that gets the users’ public keys and can ask for re-encryption keys and can corrupt users by requesting their secret keys. Any ciphertext that the adversary cannot trivially decrypt given the obtained secret and re-encryption keys should be secure.
All existing security proofs for PRE only show selective security, where the adversary must first declare the users it wants to corrupt. This can be lifted to more meaningful adaptive security by guessing the set of corrupted users among the n users, which loses a factor exponential in Open image in new window , rendering the result meaningless already for moderate Open image in new window .
Jafargholi et al. (CRYPTO’17) proposed a framework that in some cases allows to give adaptive security proofs for schemes which were previously only known to be selectively secure, while avoiding the exponential loss that results from guessing the adaptive choices made by an adversary. We apply their framework to PREs that satisfy some natural additional properties. Concretely, we give a more fine-grained reduction for several unidirectional PREs, proving adaptive security at a much smaller loss. The loss depends on the graph of users whose edges represent the re-encryption keys queried by the adversary. For trees and chains the loss is quasi-polynomial in the size and for general graphs it is exponential in their depth and indegree (instead of their size as for previous reductions). Fortunately, trees and low-depth graphs cover many, if not most, interesting applications.
Our results apply e.g. to the bilinear-map based PRE schemes by Ateniese et al. (NDSS’05 and CT-RSA’09), Gentry’s FHE-based scheme (STOC’09) and the LWE-based scheme by Chandran et al. (PKC’14).
AU - Fuchsbauer, Georg
AU - Kamath Hosdurg, Chethan
AU - Klein, Karen
AU - Pietrzak, Krzysztof Z
ID - 6430
SN - 03029743
TI - Adaptively secure proxy re-encryption
VL - 11443
ER -
TY - JOUR
AB - Electron transport in two-dimensional conducting materials such as graphene, with dominant electron–electron interaction, exhibits unusual vortex flow that leads to a nonlocal current-field relation (negative resistance), distinct from the classical Ohm’s law. The transport behavior of these materials is best described by low Reynolds number hydrodynamics, where the constitutive pressure–speed relation is Stoke’s law. Here we report evidence of such vortices observed in a viscous flow of Newtonian fluid in a microfluidic device consisting of a rectangular cavity—analogous to the electronic system. We extend our experimental observations to elliptic cavities of different eccentricities, and validate them by numerically solving bi-harmonic equation obtained for the viscous flow with no-slip boundary conditions. We verify the existence of a predicted threshold at which vortices appear. Strikingly, we find that a two-dimensional theoretical model captures the essential features of three-dimensional Stokes flow in experiments.
AU - Mayzel, Jonathan
AU - Steinberg, Victor
AU - Varshney, Atul
ID - 6069
JF - Nature Communications
SN - 2041-1723
TI - Stokes flow analogous to viscous electron current in graphene
VL - 10
ER -
TY - JOUR
AB - Speed of sound waves in gases and liquids are governed by the compressibility of the medium. There exists another type of non-dispersive wave where the wave speed depends on stress instead of elasticity of the medium. A well-known example is the Alfven wave, which propagates through plasma permeated by a magnetic field with the speed determined by magnetic tension. An elastic analogue of Alfven waves has been predicted in a flow of dilute polymer solution where the elastic stress of the stretching polymers determines the elastic wave speed. Here we present quantitative evidence of elastic Alfven waves in elastic turbulence of a viscoelastic creeping flow between two obstacles in channel flow. The key finding in the experimental proof is a nonlinear dependence of the elastic wave speed cel on the Weissenberg number Wi, which deviates from predictions based on a model of linear polymer elasticity.
AU - Varshney, Atul
AU - Steinberg, Victor
ID - 6014
JF - Nature Communications
SN - 2041-1723
TI - Elastic alfven waves in elastic turbulence
VL - 10
ER -
TY - JOUR
AB - Epidermal growth factor receptor (EGFR) signaling controls skin development and homeostasis inmice and humans, and its deficiency causes severe skin inflammation, which might affect epidermalstem cell behavior. Here, we describe the inflammation-independent effects of EGFR deficiency dur-ing skin morphogenesis and in adult hair follicle stem cells. Expression and alternative splicing analysisof RNA sequencing data from interfollicular epidermis and outer root sheath indicate that EGFR con-trols genes involved in epidermal differentiation and also in centrosome function, DNA damage, cellcycle, and apoptosis. Genetic experiments employingp53deletion in EGFR-deficient epidermis revealthat EGFR signaling exhibitsp53-dependent functions in proliferative epidermal compartments, aswell asp53-independent functions in differentiated hair shaft keratinocytes. Loss of EGFR leads toabsence of LEF1 protein specifically in the innermost epithelial hair layers, resulting in disorganizationof medulla cells. Thus, our results uncover important spatial and temporal features of cell-autonomousEGFR functions in the epidermis.
AU - Amberg, Nicole
AU - Sotiropoulou, Panagiota A.
AU - Heller, Gerwin
AU - Lichtenberger, Beate M.
AU - Holcmann, Martin
AU - Camurdanoglu, Bahar
AU - Baykuscheva-Gentscheva, Temenuschka
AU - Blanpain, Cedric
AU - Sibilia, Maria
ID - 6451
JF - iScience
SN - 2589-0042
TI - EGFR controls hair shaft differentiation in a p53-independent manner
VL - 15
ER -
TY - JOUR
AB - We study effects of a bounded and compactly supported perturbation on multidimensional continuum random Schrödinger operators in the region of complete localisation. Our main emphasis is on Anderson orthogonality for random Schrödinger operators. Among others, we prove that Anderson orthogonality does occur for Fermi energies in the region of complete localisation with a non-zero probability. This partially confirms recent non-rigorous findings [V. Khemani et al., Nature Phys. 11 (2015), 560–565]. The spectral shift function plays an important role in our analysis of Anderson orthogonality. We identify it with the index of the corresponding pair of spectral projections and explore the consequences thereof. All our results rely on the main technical estimate of this paper which guarantees separate exponential decay of the disorder-averaged Schatten p-norm of χa(f(H)−f(Hτ))χb in a and b. Here, Hτ is a perturbation of the random Schrödinger operator H, χa is the multiplication operator corresponding to the indicator function of a unit cube centred about a∈Rd, and f is in a suitable class of functions of bounded variation with distributional derivative supported in the region of complete localisation for H.
AU - Dietlein, Adrian M
AU - Gebert, Martin
AU - Müller, Peter
ID - 10879
IS - 3
JF - Journal of Spectral Theory
KW - Random Schrödinger operators
KW - spectral shift function
KW - Anderson orthogonality
SN - 1664-039X
TI - Perturbations of continuum random Schrödinger operators with applications to Anderson orthogonality and the spectral shift function
VL - 9
ER -
TY - JOUR
AB - Starting from a microscopic model for a system of neurons evolving in time which individually follow a stochastic integrate-and-fire type model, we study a mean-field limit of the system. Our model is described by a system of SDEs with discontinuous coefficients for the action potential of each neuron and takes into account the (random) spatial configuration of neurons allowing the interaction to depend on it. In the limit as the number of particles tends to infinity, we obtain a nonlinear Fokker-Planck type PDE in two variables, with derivatives only with respect to one variable and discontinuous coefficients. We also study strong well-posedness of the system of SDEs and prove the existence and uniqueness of a weak measure-valued solution to the PDE, obtained as the limit of the laws of the empirical measures for the system of particles.
AU - Flandoli, Franco
AU - Priola, Enrico
AU - Zanco, Giovanni A
ID - 10878
IS - 6
JF - Discrete and Continuous Dynamical Systems
KW - Applied Mathematics
KW - Discrete Mathematics and Combinatorics
KW - Analysis
SN - 1553-5231
TI - A mean-field model with discontinuous coefficients for neurons with spatial interaction
VL - 39
ER -
TY - CONF
AB - This paper investigates the power of preprocessing in the CONGEST model. Schmid and Suomela (ACM HotSDN 2013) introduced the SUPPORTED CONGEST model to study the application of distributed algorithms in Software-Defined Networks (SDNs). In this paper, we show that a large class of lower bounds in the CONGEST model still hold in the SUPPORTED model, highlighting the robustness of these bounds. This also raises the question how much does
preprocessing help in the CONGEST model.
AU - Foerster, Klaus-Tycho
AU - Korhonen, Janne
AU - Rybicki, Joel
AU - Schmid, Stefan
ID - 6935
SN - 9781450362177
T2 - Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing
TI - Does preprocessing help under congestion?
ER -
TY - JOUR
AB - Autoregulation is the direct modulation of gene expression by the product of the corresponding gene. Autoregulation of bacterial gene expression has been mostly studied at the transcriptional level, when a protein acts as the cognate transcriptional repressor. A recent study investigating dynamics of the bacterial toxin–antitoxin MazEF system has shown how autoregulation at both the transcriptional and post-transcriptional levels affects the heterogeneity of Escherichia coli populations. Toxin–antitoxin systems hold a crucial but still elusive part in bacterial response to stress. This perspective highlights how these modules can also serve as a great model system for investigating basic concepts in gene regulation. However, as the genomic background and environmental conditions substantially influence toxin activation, it is important to study (auto)regulation of toxin–antitoxin systems in well-defined setups as well as in conditions that resemble the environmental niche.
AU - Nikolic, Nela
ID - 138
IS - 1
JF - Current Genetics
TI - Autoregulation of bacterial gene expression: lessons from the MazEF toxin–antitoxin system
VL - 65
ER -
TY - JOUR
AB - We construct planar bi-Sobolev mappings whose local volume distortion is bounded from below by a given function f∈Lp with p>1. More precisely, for any 1<q<(p+1)/2 we construct W1,q-bi-Sobolev maps with identity boundary conditions; for f∈L∞, we provide bi-Lipschitz maps. The basic building block of our construction are bi-Lipschitz maps which stretch a given compact subset of the unit square by a given factor while preserving the boundary. The construction of these stretching maps relies on a slight strengthening of the celebrated covering result of Alberti, Csörnyei, and Preiss for measurable planar sets in the case of compact sets. We apply our result to a model functional in nonlinear elasticity, the integrand of which features fast blowup as the Jacobian determinant of the deformation becomes small. For such functionals, the derivation of the equilibrium equations for minimizers requires an additional regularization of test functions, which our maps provide.
AU - Fischer, Julian L
AU - Kneuss, Olivier
ID - 151
IS - 1
JF - Journal of Differential Equations
TI - Bi-Sobolev solutions to the prescribed Jacobian inequality in the plane with L p data and applications to nonlinear elasticity
VL - 266
ER -
TY - JOUR
AB - The cerebral cortex is composed of a large variety of distinct cell-types including projection neurons, interneurons and glial cells which emerge from distinct neural stem cell (NSC) lineages. The vast majority of cortical projection neurons and certain classes of glial cells are generated by radial glial progenitor cells (RGPs) in a highly orchestrated manner. Recent studies employing single cell analysis and clonal lineage tracing suggest that NSC and RGP lineage progression are regulated in a profound deterministic manner. In this review we focus on recent advances based mainly on correlative phenotypic data emerging from functional genetic studies in mice. We establish hypotheses to test in future research and outline a conceptual framework how epigenetic cues modulate the generation of cell-type diversity during cortical development. This article is protected by copyright. All rights reserved.
AU - Amberg, Nicole
AU - Laukoter, Susanne
AU - Hippenmeyer, Simon
ID - 27
IS - 1
JF - Journal of Neurochemistry
TI - Epigenetic cues modulating the generation of cell type diversity in the cerebral cortex
VL - 149
ER -
TY - JOUR
AB - Tissue morphogenesis is driven by mechanical forces that elicit changes in cell size, shape and motion. The extent by which forces deform tissues critically depends on the rheological properties of the recipient tissue. Yet, whether and how dynamic changes in tissue rheology affect tissue morphogenesis and how they are regulated within the developing organism remain unclear. Here, we show that blastoderm spreading at the onset of zebrafish morphogenesis relies on a rapid, pronounced and spatially patterned tissue fluidization. Blastoderm fluidization is temporally controlled by mitotic cell rounding-dependent cell–cell contact disassembly during the last rounds of cell cleavages. Moreover, fluidization is spatially restricted to the central blastoderm by local activation of non-canonical Wnt signalling within the blastoderm margin, increasing cell cohesion and thereby counteracting the effect of mitotic rounding on contact disassembly. Overall, our results identify a fluidity transition mediated by loss of cell cohesion as a critical regulator of embryo morphogenesis.
AU - Petridou, Nicoletta
AU - Grigolon, Silvia
AU - Salbreux, Guillaume
AU - Hannezo, Edouard B
AU - Heisenberg, Carl-Philipp J
ID - 5789
JF - Nature Cell Biology
SN - 14657392
TI - Fluidization-mediated tissue spreading by mitotic cell rounding and non-canonical Wnt signalling
VL - 21
ER -
TY - JOUR
AB - The abelian sandpile serves as a model to study self-organized criticality, a phenomenon occurring in biological, physical and social processes. The identity of the abelian group is a fractal composed of self-similar patches, and its limit is subject of extensive collaborative research. Here, we analyze the evolution of the sandpile identity under harmonic fields of different orders. We show that this evolution corresponds to periodic cycles through the abelian group characterized by the smooth transformation and apparent conservation of the patches constituting the identity. The dynamics induced by second and third order harmonics resemble smooth stretchings, respectively translations, of the identity, while the ones induced by fourth order harmonics resemble magnifications and rotations. Starting with order three, the dynamics pass through extended regions of seemingly random configurations which spontaneously reassemble into accentuated patterns. We show that the space of harmonic functions projects to the extended analogue of the sandpile group, thus providing a set of universal coordinates identifying configurations between different domains. Since the original sandpile group is a subgroup of the extended one, this directly implies that it admits a natural renormalization. Furthermore, we show that the harmonic fields can be induced by simple Markov processes, and that the corresponding stochastic dynamics show remarkable robustness over hundreds of periods. Finally, we encode information into seemingly random configurations, and decode this information with an algorithm requiring minimal prior knowledge. Our results suggest that harmonic fields might split the sandpile group into sub-sets showing different critical coefficients, and that it might be possible to extend the fractal structure of the identity beyond the boundaries of its domain.
AU - Lang, Moritz
AU - Shkolnikov, Mikhail
ID - 196
IS - 8
JF - Proceedings of the National Academy of Sciences
TI - Harmonic dynamics of the Abelian sandpile
VL - 116
ER -
TY - DATA
AB - This dataset contains the supplementary data for the research paper "Haploinsufficiency of the intellectual disability gene SETD5 disturbs developmental gene expression and cognition".
The contained files have the following content:
'Supplementary Figures.pdf'
Additional figures (as referenced in the paper).
'Supplementary Table 1. Statistics.xlsx'
Details on statistical tests performed in the paper.
'Supplementary Table 2. Differentially expressed gene analysis.xlsx'
Results for the differential gene expression analysis for embryonic (E9.5; analysis with edgeR) and in vitro (ESCs, EBs, NPCs; analysis with DESeq2) samples.
'Supplementary Table 3. Gene Ontology (GO) term enrichment analysis.xlsx'
Results for the GO term enrichment analysis for differentially expressed genes in embryonic (GO E9.5) and in vitro (GO ESC, GO EBs, GO NPCs) samples. Differentially expressed genes for in vitro samples were split into upregulated and downregulated genes (up/down) and the analysis was performed on each subset (e.g. GO ESC up / GO ESC down).
'Supplementary Table 4. Differentially expressed gene analysis for CFC samples.xlsx'
Results for the differential gene expression analysis for samples from adult mice before (HC - Homecage) and 1h and 3h after contextual fear conditioning (1h and 3h, respectively). Each sheet shows the results for a different comparison. Sheets 1-3 show results for comparisons between timepoints for wild type (WT) samples only and sheets 4-6 for the same comparisons in mutant (Het) samples. Sheets 7-9 show results for comparisons between genotypes at each time point and sheet 10 contains the results for the analysis of differential expression trajectories between wild type and mutant.
'Supplementary Table 5. Cluster identification.xlsx'
Results for k-means clustering of genes by expression. Sheet 1 shows clustering of just the genes with significantly different expression trajectories between genotypes. Sheet 2 shows clustering of all genes that are significantly differentially expressed in any of the comparisons (includes also genes with same trajectories).
'Supplementary Table 6. GO term cluster analysis.xlsx'
Results for the GO term enrichment analysis and EWCE analysis for enrichment of cell type specific genes for each cluster identified by clustering genes with different expression trajectories (see Table S5, sheet 1).
'Supplementary Table 7. Setd5 mass spectrometry results.xlsx'
Results showing proteins interacting with Setd5 as identified by mass spectrometry. Sheet 1 shows protein protein interaction data generated from these results (combined with data from the STRING database. Sheet 2 shows the results of the statistical analysis with limma.
'Supplementary Table 8. PolII ChIP-seq analysis.xlsx'
Results for the Chip-Seq analysis for binding of RNA polymerase II (PolII). Sheet 1 shows results for differential binding of PolII at the transcription start site (TSS) between genotypes and sheets 2+3 show the corresponding GO enrichment analysis for these differentially bound genes. Sheet 4 shows RNAseq counts for genes with increased binding of PolII at the TSS.
AU - Dotter, Christoph
AU - Novarino, Gaia
ID - 6074
TI - Supplementary data for the research paper "Haploinsufficiency of the intellectual disability gene SETD5 disturbs developmental gene expression and cognition"
ER -
TY - CONF
AB - Learning disentangled representations is considered a cornerstone problem in
representation learning. Recently, Locatello et al. (2019) demonstrated that
unsupervised disentanglement learning without inductive biases is theoretically
impossible and that existing inductive biases and unsupervised methods do not
allow to consistently learn disentangled representations. However, in many
practical settings, one might have access to a limited amount of supervision,
for example through manual labeling of (some) factors of variation in a few
training examples. In this paper, we investigate the impact of such supervision
on state-of-the-art disentanglement methods and perform a large scale study,
training over 52000 models under well-defined and reproducible experimental
conditions. We observe that a small number of labeled examples (0.01--0.5\% of
the data set), with potentially imprecise and incomplete labels, is sufficient
to perform model selection on state-of-the-art unsupervised models. Further, we
investigate the benefit of incorporating supervision into the training process.
Overall, we empirically validate that with little and imprecise supervision it
is possible to reliably learn disentangled representations.
AU - Locatello, Francesco
AU - Tschannen, Michael
AU - Bauer, Stefan
AU - Rätsch, Gunnar
AU - Schölkopf, Bernhard
AU - Bachem, Olivier
ID - 14184
T2 - 8th International Conference on Learning Representations
TI - Disentangling factors of variation using few labels
ER -
TY - CONF
AB - We consider the problem of recovering a common latent source with independent
components from multiple views. This applies to settings in which a variable is
measured with multiple experimental modalities, and where the goal is to
synthesize the disparate measurements into a single unified representation. We
consider the case that the observed views are a nonlinear mixing of
component-wise corruptions of the sources. When the views are considered
separately, this reduces to nonlinear Independent Component Analysis (ICA) for
which it is provably impossible to undo the mixing. We present novel
identifiability proofs that this is possible when the multiple views are
considered jointly, showing that the mixing can theoretically be undone using
function approximators such as deep neural networks. In contrast to known
identifiability results for nonlinear ICA, we prove that independent latent
sources with arbitrary mixing can be recovered as long as multiple,
sufficiently different noisy views are available.
AU - Gresele, Luigi
AU - Rubenstein, Paul K.
AU - Mehrjou, Arash
AU - Locatello, Francesco
AU - Schölkopf, Bernhard
ID - 14189
T2 - Proceedings of the 35th Conference on Uncertainty in Artificial Intelligence
TI - The incomplete Rosetta Stone problem: Identifiability results for multi-view nonlinear ICA
VL - 115
ER -
TY - CONF
AB - Recently there has been a significant interest in learning disentangled
representations, as they promise increased interpretability, generalization to
unseen scenarios and faster learning on downstream tasks. In this paper, we
investigate the usefulness of different notions of disentanglement for
improving the fairness of downstream prediction tasks based on representations.
We consider the setting where the goal is to predict a target variable based on
the learned representation of high-dimensional observations (such as images)
that depend on both the target variable and an \emph{unobserved} sensitive
variable. We show that in this setting both the optimal and empirical
predictions can be unfair, even if the target variable and the sensitive
variable are independent. Analyzing the representations of more than
\num{12600} trained state-of-the-art disentangled models, we observe that
several disentanglement scores are consistently correlated with increased
fairness, suggesting that disentanglement may be a useful property to encourage
fairness when sensitive variables are not observed.
AU - Locatello, Francesco
AU - Abbati, Gabriele
AU - Rainforth, Tom
AU - Bauer, Stefan
AU - Schölkopf, Bernhard
AU - Bachem, Olivier
ID - 14197
SN - 9781713807933
T2 - Advances in Neural Information Processing Systems
TI - On the fairness of disentangled representations
VL - 32
ER -
TY - CONF
AB - A broad class of convex optimization problems can be formulated as a semidefinite program (SDP), minimization of a convex function over the positive-semidefinite cone subject to some affine constraints. The majority of classical SDP solvers are designed for the deterministic setting where problem data is readily available. In this setting, generalized conditional gradient methods (aka Frank-Wolfe-type methods) provide scalable solutions by leveraging the so-called linear minimization oracle instead of the projection onto the semidefinite cone. Most problems in machine learning and modern engineering applications, however, contain some degree of stochasticity. In this work, we propose the first conditional-gradient-type method for solving stochastic optimization problems under affine constraints. Our method guarantees O(k−1/3) convergence rate in expectation on the objective residual and O(k−5/12) on the feasibility gap.
AU - Locatello, Francesco
AU - Yurtsever, Alp
AU - Fercoq, Olivier
AU - Cevher, Volkan
ID - 14191
SN - 9781713807933
T2 - Advances in Neural Information Processing Systems
TI - Stochastic Frank-Wolfe for composite convex minimization
VL - 32
ER -
TY - CONF
AB - A disentangled representation encodes information about the salient factors
of variation in the data independently. Although it is often argued that this
representational format is useful in learning to solve many real-world
down-stream tasks, there is little empirical evidence that supports this claim.
In this paper, we conduct a large-scale study that investigates whether
disentangled representations are more suitable for abstract reasoning tasks.
Using two new tasks similar to Raven's Progressive Matrices, we evaluate the
usefulness of the representations learned by 360 state-of-the-art unsupervised
disentanglement models. Based on these representations, we train 3600 abstract
reasoning models and observe that disentangled representations do in fact lead
to better down-stream performance. In particular, they enable quicker learning
using fewer samples.
AU - Steenkiste, Sjoerd van
AU - Locatello, Francesco
AU - Schmidhuber, Jürgen
AU - Bachem, Olivier
ID - 14193
SN - 9781713807933
T2 - Advances in Neural Information Processing Systems
TI - Are disentangled representations helpful for abstract visual reasoning?
VL - 32
ER -
TY - CONF
AB - The key idea behind the unsupervised learning of disentangled representations
is that real-world data is generated by a few explanatory factors of variation
which can be recovered by unsupervised learning algorithms. In this paper, we
provide a sober look at recent progress in the field and challenge some common
assumptions. We first theoretically show that the unsupervised learning of
disentangled representations is fundamentally impossible without inductive
biases on both the models and the data. Then, we train more than 12000 models
covering most prominent methods and evaluation metrics in a reproducible
large-scale experimental study on seven different data sets. We observe that
while the different methods successfully enforce properties ``encouraged'' by
the corresponding losses, well-disentangled models seemingly cannot be
identified without supervision. Furthermore, increased disentanglement does not
seem to lead to a decreased sample complexity of learning for downstream tasks.
Our results suggest that future work on disentanglement learning should be
explicit about the role of inductive biases and (implicit) supervision,
investigate concrete benefits of enforcing disentanglement of the learned
representations, and consider a reproducible experimental setup covering
several data sets.
AU - Locatello, Francesco
AU - Bauer, Stefan
AU - Lucic, Mario
AU - Rätsch, Gunnar
AU - Gelly, Sylvain
AU - Schölkopf, Bernhard
AU - Bachem, Olivier
ID - 14200
T2 - Proceedings of the 36th International Conference on Machine Learning
TI - Challenging common assumptions in the unsupervised learning of disentangled representations
VL - 97
ER -
TY - JOUR
AB - We theoretically study the shapes of lipid vesicles confined to a spherical cavity, elaborating a framework based on the so-called limiting shapes constructed from geometrically simple structural elements such as double-membrane walls and edges. Partly inspired by numerical results, the proposed non-compartmentalized and compartmentalized limiting shapes are arranged in the bilayer-couple phase diagram which is then compared to its free-vesicle counterpart. We also compute the area-difference-elasticity phase diagram of the limiting shapes and we use it to interpret shape transitions experimentally observed in vesicles confined within another vesicle. The limiting-shape framework may be generalized to theoretically investigate the structure of certain cell organelles such as the mitochondrion.
AU - Kavcic, Bor
AU - Sakashita, A.
AU - Noguchi, H.
AU - Ziherl, P.
ID - 5817
IS - 4
JF - Soft Matter
SN - 1744-683X
TI - Limiting shapes of confined lipid vesicles
VL - 15
ER -
TY - JOUR
AB - We consider the space of probability measures on a discrete set X, endowed with a dynamical optimal transport metric. Given two probability measures supported in a subset Y⊆X, it is natural to ask whether they can be connected by a constant speed geodesic with support in Y at all times. Our main result answers this question affirmatively, under a suitable geometric condition on Y introduced in this paper. The proof relies on an extension result for subsolutions to discrete Hamilton-Jacobi equations, which is of independent interest.
AU - Erbar, Matthias
AU - Maas, Jan
AU - Wirth, Melchior
ID - 73
IS - 1
JF - Calculus of Variations and Partial Differential Equations
SN - 09442669
TI - On the geometry of geodesics in discrete optimal transport
VL - 58
ER -
TY - CONF
AB - Learning meaningful and compact representations with disentangled semantic
aspects is considered to be of key importance in representation learning. Since
real-world data is notoriously costly to collect, many recent state-of-the-art
disentanglement models have heavily relied on synthetic toy data-sets. In this
paper, we propose a novel data-set which consists of over one million images of
physical 3D objects with seven factors of variation, such as object color,
shape, size and position. In order to be able to control all the factors of
variation precisely, we built an experimental platform where the objects are
being moved by a robotic arm. In addition, we provide two more datasets which
consist of simulations of the experimental setup. These datasets provide for
the first time the possibility to systematically investigate how well different
disentanglement methods perform on real data in comparison to simulation, and
how simulated data can be leveraged to build better representations of the real
world. We provide a first experimental study of these questions and our results
indicate that learned models transfer poorly, but that model and hyperparameter
selection is an effective means of transferring information to the real world.
AU - Gondal, Muhammad Waleed
AU - Wüthrich, Manuel
AU - Miladinović, Đorđe
AU - Locatello, Francesco
AU - Breidt, Martin
AU - Volchkov, Valentin
AU - Akpo, Joel
AU - Bachem, Olivier
AU - Schölkopf, Bernhard
AU - Bauer, Stefan
ID - 14190
SN - 9781713807933
T2 - Advances in Neural Information Processing Systems
TI - On the transfer of inductive bias from simulation to the real world: a new disentanglement dataset
VL - 32
ER -
TY - JOUR
AB - We present an efficient algorithm for a problem in the interface between clustering and graph embeddings. An embedding ϕ : G → M of a graph G into a 2-manifold M maps the vertices in V(G) to distinct points and the edges in E(G) to interior-disjoint Jordan arcs between the corresponding vertices. In applications in clustering, cartography, and visualization, nearby vertices and edges are often bundled to the same point or overlapping arcs due to data compression or low resolution. This raises the computational problem of deciding whether a given map ϕ : G → M comes from an embedding. A map ϕ : G → M is a weak embedding if it can be perturbed into an embedding ψ ϵ : G → M with ‖ ϕ − ψ ϵ ‖ < ϵ for every ϵ > 0, where ‖.‖ is the unform norm.
A polynomial-time algorithm for recognizing weak embeddings has recently been found by Fulek and Kynčl. It reduces the problem to solving a system of linear equations over Z2. It runs in O(n2ω)≤ O(n4.75) time, where ω ∈ [2,2.373) is the matrix multiplication exponent and n is the number of vertices and edges of G. We improve the running time to O(n log n). Our algorithm is also conceptually simpler: We perform a sequence of local operations that gradually “untangles” the image ϕ(G) into an embedding ψ(G) or reports that ϕ is not a weak embedding. It combines local constraints on the orientation of subgraphs directly, thereby eliminating the need for solving large systems of linear equations.
AU - Akitaya, Hugo
AU - Fulek, Radoslav
AU - Tóth, Csaba
ID - 6982
IS - 4
JF - ACM Transactions on Algorithms
TI - Recognizing weak embeddings of graphs
VL - 15
ER -
TY - THES
AB - Hybrid automata combine finite automata and dynamical systems, and model the interaction of digital with physical systems. Formal analysis that can guarantee the safety of all behaviors or rigorously witness failures, while unsolvable in general, has been tackled algorithmically using, e.g., abstraction, bounded model-checking, assisted theorem proving.
Nevertheless, very few methods have addressed the time-unbounded reachability analysis of hybrid automata and, for current sound and automatic tools, scalability remains critical. We develop methods for the polyhedral abstraction of hybrid automata, which construct coarse overapproximations and tightens them incrementally, in a CEGAR fashion. We use template polyhedra, i.e., polyhedra whose facets are normal to a given set of directions.
While, previously, directions were given by the user, we introduce (1) the first method
for computing template directions from spurious counterexamples, so as to generalize and
eliminate them. The method applies naturally to convex hybrid automata, i.e., hybrid
automata with (possibly non-linear) convex constraints on derivatives only, while for linear
ODE requires further abstraction. Specifically, we introduce (2) the conic abstractions,
which, partitioning the state space into appropriate (possibly non-uniform) cones, divide
curvy trajectories into relatively straight sections, suitable for polyhedral abstractions.
Finally, we introduce (3) space-time interpolation, which, combining interval arithmetic
and template refinement, computes appropriate (possibly non-uniform) time partitioning
and template directions along spurious trajectories, so as to eliminate them.
We obtain sound and automatic methods for the reachability analysis over dense
and unbounded time of convex hybrid automata and hybrid automata with linear ODE.
We build prototype tools and compare—favorably—our methods against the respective
state-of-the-art tools, on several benchmarks.
AU - Giacobbe, Mirco
ID - 6894
TI - Automatic time-unbounded reachability analysis of hybrid systems
ER -
TY - GEN
AB - The spread of adaptive alleles is fundamental to evolution, and in theory, this process is well‐understood. However, only rarely can we follow this process—whether it originates from the spread of a new mutation, or by introgression from another population. In this issue of Molecular Ecology, Hanemaaijer et al. (2018) report on a 25‐year long study of the mosquitoes Anopheles gambiae (Figure 1) and Anopheles coluzzi in Mali, based on genotypes at 15 single‐nucleotide polymorphism (SNP). The species are usually reproductively isolated from each other, but in 2002 and 2006, bursts of hybridization were observed, when F1 hybrids became abundant. Alleles backcrossed from A. gambiae into A. coluzzi, but after the first event, these declined over the following years. In contrast, after 2006, an insecticide resistance allele that had established in A. gambiae spread into A. coluzzi, and rose to high frequency there, over 6 years (~75 generations). Whole genome sequences of 74 individuals showed that A. gambiae SNP from across the genome had become common in the A. coluzzi population, but that most of these were clustered in 34 genes around the resistance locus. A new set of SNP from 25 of these genes were assayed over time; over the 4 years since near‐fixation of the resistance allele; some remained common, whereas others declined. What do these patterns tell us about this introgression event?
AU - Barton, Nicholas H
ID - 9805
TI - Data from: The consequences of an introgression event
ER -
TY - JOUR
AB - Despite their different origins, Drosophila glia and hemocytes are related cell populations that provide an immune function. Drosophila hemocytes patrol the body cavity and act as macrophages outside the nervous system whereas glia originate from the neuroepithelium and provide the scavenger population of the nervous system. Drosophila glia are hence the functional orthologs of vertebrate microglia, even though the latter are cells of immune origin that subsequently move into the brain during development. Interestingly, the Drosophila immune cells within (glia) and outside the nervous system (hemocytes) require the same transcription factor Glide/Gcm for their development. This raises the issue of how do glia specifically differentiate in the nervous system and hemocytes in the procephalic mesoderm. The Repo homeodomain transcription factor and pan-glial direct target of Glide/Gcm is known to ensure glial terminal differentiation. Here we show that Repo also takes center stage in the process that discriminates between glia and hemocytes. First, Repo expression is repressed in the hemocyte anlagen by mesoderm-specific factors. Second, Repo ectopic activation in the procephalic mesoderm is sufficient to repress the expression of hemocyte-specific genes. Third, the lack of Repo triggers the expression of hemocyte markers in glia. Thus, a complex network of tissue-specific cues biases the potential of Glide/Gcm. These data allow us to revise the concept of fate determinants and help us understand the bases of cell specification. Both sexes were analyzed.SIGNIFICANCE STATEMENTDistinct cell types often require the same pioneer transcription factor, raising the issue of how does one factor trigger different fates. In Drosophila, glia and hemocytes provide a scavenger activity within and outside the nervous system, respectively. While they both require the Glide/Gcm transcription factor, glia originate from the ectoderm, hemocytes from the mesoderm. Here we show that tissue-specific factors inhibit the gliogenic potential of Glide/Gcm in the mesoderm by repressing the expression of the homeodomain protein Repo, a major glial-specific target of Glide/Gcm. Repo expression in turn inhibits the expression of hemocyte-specific genes in the nervous system. These cell-specific networks secure the establishment of the glial fate only in the nervous system and allow cell diversification.
AU - Trébuchet, Guillaume
AU - Cattenoz, Pierre B
AU - Zsámboki, János
AU - Mazaud, David
AU - Siekhaus, Daria E
AU - Fanto, Manolis
AU - Giangrande, Angela
ID - 8
IS - 2
JF - Journal of Neuroscience
TI - The Repo homeodomain transcription factor suppresses hematopoiesis in Drosophila and preserves the glial fate
VL - 39
ER -
TY - JOUR
AB - In this paper, we introduce a quantum version of the wonderful compactification of a group as a certain noncommutative projective scheme. Our approach stems from the fact that the wonderful compactification encodes the asymptotics of matrix coefficients, and from its realization as a GIT quotient of the Vinberg semigroup. In order to define the wonderful compactification for a quantum group, we adopt a generalized formalism of Proj categories in the spirit of Artin and Zhang. Key to our construction is a quantum version of the Vinberg semigroup, which we define as a q-deformation of a certain Rees algebra, compatible with a standard Poisson structure. Furthermore, we discuss quantum analogues of the stratification of the wonderful compactification by orbits for a certain group action, and provide explicit computations in the case of SL2.
AU - Ganev, Iordan V
ID - 5
IS - 3
JF - Journal of the London Mathematical Society
TI - The wonderful compactification for quantum groups
VL - 99
ER -
TY - THES
AB - The development and growth of Arabidopsis thaliana is regulated by a combination of genetic programing and also by the environmental influences. An important role in these processes play the phytohormones and among them, auxin is crucial as it controls many important functions. It is transported through the whole plant body by creating local and temporal concentration maxima and minima, which have an impact on the cell status, tissue and organ identity. Auxin has the property to undergo a directional and finely regulated cell-to-cell transport, which is enabled by the transport proteins, localized on the plasma membrane. An important role in this process have the PIN auxin efflux proteins, which have an asymmetric/polar subcellular localization and determine the directionality of the auxin transport. During the last years, there were significant advances in understanding how the trafficking molecular machineries function, including studies on molecular interactions, function, subcellular localization and intracellular distribution. However, there is still a lack of detailed characterization on the steps of endocytosis, exocytosis, endocytic recycling and degradation. Due to this fact, I focused on the identification of novel trafficking factors and better characterization of the intracellular trafficking pathways. My PhD thesis consists of an introductory chapter, three experimental chapters, a chapter containing general discussion, conclusions and perspectives and also an appendix chapter with published collaborative papers.
The first chapter is separated in two different parts: I start by a general introduction to auxin biology and then I introduce the trafficking pathways in the model plant Arabidopsis thaliana. Then, I explain also the phosphorylation-signals for polar targeting and also the roles of the phytohormone strigolactone.
The second chapter includes the characterization of bar1/sacsin mutant, which was identified in a forward genetic screen for novel trafficking components in Arabidopsis thaliana, where by the implementation of an EMS-treated pPIN1::PIN1-GFP marker line and by using the established inhibitor of ARF-GEFs, Brefeldin A (BFA) as a tool to study trafficking processes, we identified a novel factor, which is mediating the adaptation of the plant cell to ARF-GEF inhibition. The mutation is in a previously uncharacterized gene, encoding a very big protein that we, based on its homologies, called SACSIN with domains suggesting roles as a molecular chaperon or as a component of the ubiquitin-proteasome system. Our physiology and imaging studies revealed that SACSIN is a crucial plant cell component of the adaptation to the ARF-GEF inhibition.
The third chapter includes six subchapters, where I focus on the role of the phytohormone strigolactone, which interferes with auxin feedback on PIN internalization. Strigolactone moderates the polar auxin transport by increasing the internalization of the PIN auxin efflux carriers, which reduces the canalization related growth responses. In addition, I also studied the role of phosphorylation in the strigolactone regulation of auxin feedback on PIN internalization. In this chapter I also present my results on the MAX2-dependence of strigolactone-mediated root growth inhibition and I also share my results on the auxin metabolomics profiling after application of GR24.
In the fourth chapter I studied the effect of two small molecules ES-9 and ES9-17, which were identified from a collection of small molecules with the property to impair the clathrin-mediated endocytosis.
In the fifth chapter, I discuss all my observations and experimental findings and suggest alternative hypothesis to interpret my results.
In the appendix there are three collaborative published projects. In the first, I participated in the characterization of the role of ES9 as a small molecule, which is inhibitor of clathrin- mediated endocytosis in different model organisms. In the second paper, I contributed to the characterization of another small molecule ES9-17, which is a non-protonophoric analog of ES9 and also impairs the clathrin-mediated endocytosis not only in plant cells, but also in mammalian HeLa cells. Last but not least, I also attach another paper, where I tried to establish the grafting method as a technique in our lab to study canalization related processes.
AU - Vasileva, Mina K
ID - 7172
TI - Molecular mechanisms of endomembrane trafficking in Arabidopsis thaliana
ER -
TY - JOUR
AB - Blebs are cellular protrusions observed in migrating cells and in cells undergoing spreading, cytokinesis, and apoptosis. Here we investigate the flow of cytoplasm during bleb formation and the concurrent changes in cell volume using zebrafish primordial germ cells (PGCs) as an in vivo model. We show that bleb inflation occurs concomitantly with cytoplasmic inflow into it and that during this process the total cell volume does not change. We thus show that bleb formation in primordial germ cells results primarily from redistribution of material within the cell rather than being driven by flow of water from an external source.
AU - Goudarzi, Mohammad
AU - Boquet-Pujadas, Aleix
AU - Olivo-Marin, Jean Christophe
AU - Raz, Erez
ID - 6093
IS - 2
JF - PLOS ONE
TI - Fluid dynamics during bleb formation in migrating cells in vivo
VL - 14
ER -
TY - THES
AB - In the first part of this thesis we consider large random matrices with arbitrary expectation and a general slowly decaying correlation among its entries. We prove universality of the local eigenvalue statistics and optimal local laws for the resolvent in the bulk and edge regime. The main novel tool is a systematic diagrammatic control of a multivariate cumulant expansion.
In the second part we consider Wigner-type matrices and show that at any cusp singularity of the limiting eigenvalue distribution the local eigenvalue statistics are uni- versal and form a Pearcey process. Since the density of states typically exhibits only square root or cubic root cusp singularities, our work complements previous results on the bulk and edge universality and it thus completes the resolution of the Wigner- Dyson-Mehta universality conjecture for the last remaining universality type. Our analysis holds not only for exact cusps, but approximate cusps as well, where an ex- tended Pearcey process emerges. As a main technical ingredient we prove an optimal local law at the cusp, and extend the fast relaxation to equilibrium of the Dyson Brow- nian motion to the cusp regime.
In the third and final part we explore the entrywise linear statistics of Wigner ma- trices and identify the fluctuations for a large class of test functions with little regularity. This enables us to study the rectangular Young diagram obtained from the interlacing eigenvalues of the random matrix and its minor, and we find that, despite having the same limit, the fluctuations differ from those of the algebraic Young tableaux equipped with the Plancharel measure.
AU - Schröder, Dominik J
ID - 6179
SN - 2663-337X
TI - From Dyson to Pearcey: Universal statistics in random matrix theory
ER -
TY - THES
AB - Single cells are constantly interacting with their environment and each other, more importantly, the accurate perception of environmental cues is crucial for growth, survival, and reproduction. This communication between cells and their environment can be formalized in mathematical terms and be quantified as the information flow between them, as prescribed by information theory.
The recent availability of real–time dynamical patterns of signaling molecules in single cells has allowed us to identify encoding about the identity of the environment in the time–series. However, efficient estimation of the information transmitted by these signals has been a data–analysis challenge due to the high dimensionality of the trajectories and the limited number of samples. In the first part of this thesis, we develop and evaluate decoding–based estimation methods to lower bound the mutual information and derive model–based precise information estimates for biological reaction networks governed by the chemical master equation. This is followed by applying the decoding-based methods to study the intracellular representation of extracellular changes in budding yeast, by observing the transient dynamics of nuclear translocation of 10 transcription factors in response to 3 stress conditions. Additionally, we apply these estimators to previously published data on ERK and Ca2+ signaling and yeast stress response. We argue that this single cell decoding-based measure of information provides an unbiased, quantitative and interpretable measure for the fidelity of biological signaling processes.
Finally, in the last section, we deal with gene regulation which is primarily controlled by transcription factors (TFs) that bind to the DNA to activate gene expression. The possibility that non-cognate TFs activate transcription diminishes the accuracy of regulation with potentially disastrous effects for the cell. This ’crosstalk’ acts as a previously unexplored source of noise in biochemical networks and puts a strong constraint on their performance. To mitigate erroneous initiation we propose an out of equilibrium scheme that implements kinetic proofreading. We show that such architectures are favored over their equilibrium counterparts for complex organisms despite introducing noise in gene expression.
AU - Cepeda Humerez, Sarah A
ID - 6473
KW - Information estimation
KW - Time-series
KW - data analysis
SN - 2663-337X
TI - Estimating information flow in single cells
ER -