TY - JOUR
AB - X and Y chromosomes can diverge when rearrangements block recombination between them. Here we present the first genomic view of a reciprocal translocation that causes two physically unconnected pairs of chromosomes to be coinherited as sex chromosomes. In a population of the common frog (Rana temporaria), both pairs of X and Y chromosomes show extensive sequence differentiation, but not degeneration of the Y chromosomes. A new method based on gene trees shows both chromosomes are sex‐linked. Furthermore, the gene trees from the two Y chromosomes have identical topologies, showing they have been coinherited since the reciprocal translocation occurred. Reciprocal translocations can thus reshape sex linkage on a much greater scale compared with inversions, the type of rearrangement that is much better known in sex chromosome evolution, and they can greatly amplify the power of sexually antagonistic selection to drive genomic rearrangement. Two more populations show evidence of other rearrangements, suggesting that this species has unprecedented structural polymorphism in its sex chromosomes.
AU - Toups, Melissa A
AU - Rodrigues, Nicolas
AU - Perrin, Nicolas
AU - Kirkpatrick, Mark
ID - 7421
IS - 8
JF - Molecular Ecology
SN - 0962-1083
TI - A reciprocal translocation radically reshapes sex‐linked inheritance in the common frog
VL - 28
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 - 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 - 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 - 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 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 - CHAP
AB - We illustrate the ingredients of the state-of-the-art of model-based approach for the formal design and verification of cyber-physical systems. To capture the interaction between a discrete controller and its continuously evolving environment, we use the formal models of timed and hybrid automata. We explain the steps of modeling and verification in the tools Uppaal and SpaceEx using a case study based on a dual-chamber implantable pacemaker monitoring a human heart. We show how to design a model as a composition of components, how to construct models at varying levels of detail, how to establish that one model is an abstraction of another, how to specify correctness requirements using temporal logic, and how to verify that a model satisfies a logical requirement.
AU - Alur, Rajeev
AU - Giacobbe, Mirco
AU - Henzinger, Thomas A
AU - Larsen, Kim G.
AU - Mikučionis, Marius
ED - Steffen, Bernhard
ED - Woeginger, Gerhard
ID - 7453
SN - 0302-9743
T2 - Computing and Software Science
TI - Continuous-time models for system design and analysis
VL - 10000
ER -
TY - JOUR
AB - We report the fabrication of BaTiO3-Ni magnetoelectric nanocomposites comprising of BaTiO3 nanotubes surrounded by Ni matrix. BaTiO3 nanotubes obtained from the hydrothermal transformation of TiO2 have both inner and outer surfaces, which facilitates greater magnetoelectric coupling with the surrounding Ni matrix. The magnetoelectric coupling was studied by measuring the piezoelectric behavior in the presence of an in-plane direct magnetic field. A higher magnetoelectric voltage coefficient of 110 mV/cm·Oe was obtained, because of better coupling between Ni and BaTiO3 through the walls of the nanotubes. Such nanocomposite developed directly on Ti substrate may lead to efficient fabrication of magnetoelectric devices.
AU - Vadla, Samba Siva
AU - Costanzo, Tommaso
AU - John, Subish
AU - Caruntu, Gabriel
AU - Roy, Somnath C.
ID - 7459
JF - Scripta Materialia
SN - 1359-6462
TI - Local probing of magnetoelectric coupling in BaTiO3-Ni 1–3 composites
VL - 159
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 - JOUR
AB - The sebaceous gland (SG) is an essential component of the skin, and SG dysfunction is debilitating1,2. Yet, the cellular bases for its origin, development and subsequent maintenance remain poorly understood. Here, we apply large-scale quantitative fate mapping to define the patterns of cell fate behaviour during SG development and maintenance. We show that the SG develops from a defined number of lineage-restricted progenitors that undergo a programme of independent and stochastic cell fate decisions. Following an expansion phase, equipotent progenitors transition into a phase of homeostatic turnover, which is correlated with changes in the mechanical properties of the stroma and spatial restrictions on gland size. Expression of the oncogene KrasG12D results in a release from these constraints and unbridled gland expansion. Quantitative clonal fate analysis reveals that, during this phase, the primary effect of the Kras oncogene is to drive a constant fate bias with little effect on cell division rates. These findings provide insight into the developmental programme of the SG, as well as the mechanisms that drive tumour progression and gland dysfunction.
AU - Andersen, Marianne Stemann
AU - Hannezo, Edouard B
AU - Ulyanchenko, Svetlana
AU - Estrach, Soline
AU - Antoku, Yasuko
AU - Pisano, Sabrina
AU - Boonekamp, Kim E.
AU - Sendrup, Sarah
AU - Maimets, Martti
AU - Pedersen, Marianne Terndrup
AU - Johansen, Jens V.
AU - Clement, Ditte L.
AU - Feral, Chloe C.
AU - Simons, Benjamin D.
AU - Jensen, Kim B.
ID - 7476
IS - 8
JF - Nature Cell Biology
SN - 1465-7392
TI - Tracing the cellular dynamics of sebaceous gland development in normal and perturbed states
VL - 21
ER -
TY - CHAP
AB - Social insects (i.e., ants, termites and the social bees and wasps) protect their colonies from disease using a combination of individual immunity and collectively performed defenses, termed social immunity. The first line of social immune defense is sanitary care, which is performed by colony members to protect their pathogen-exposed nestmates from developing an infection. If sanitary care fails and an infection becomes established, a second line of social immune defense is deployed to stop disease transmission within the colony and to protect the valuable queens, which together with the males are the reproductive individuals of the colony. Insect colonies are separated into these reproductive individuals and the sterile worker force, forming a superorganismal reproductive unit reminiscent of the differentiated germline and soma in a multicellular organism. Ultimately, the social immune response preserves the germline of the superorganism insect colony and increases overall fitness of the colony in case of disease.
AU - Cremer, Sylvia
AU - Kutzer, Megan
ED - Choe, Jae
ID - 7513
SN - 9780128132517
T2 - Encyclopedia of Animal Behavior
TI - Social immunity
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 - 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
TI - Powerset convolutional neural networks
VL - 32
ER -
TY - JOUR
AB - The BH3-only family of proteins is key for initiating apoptosis in a variety of contexts, and may also contribute to non-apoptotic cellular processes. Historically, the nematode Caenorhabditis elegans has provided a powerful system for studying and identifying conserved regulators of BH3-only proteins. In C. elegans, the BH3-only protein egl-1 is expressed during development to cell-autonomously trigger most developmental cell deaths. Here we provide evidence that egl-1 is also transcribed after development in the sensory neuron pair URX without inducing apoptosis. We used genetic screening and epistasis analysis to determine that its transcription is regulated in URX by neuronal activity and/or in parallel by orthologs of Protein Kinase G and the Salt-Inducible Kinase family. Because several BH3-only family proteins are also expressed in the adult nervous system of mammals, we suggest that studying egl-1 expression in URX may shed light on mechanisms that regulate conserved family members in higher organisms.
AU - Cohn, Jesse
AU - Dwivedi, Vivek
AU - Valperga, Giulio
AU - Zarate, Nicole
AU - de Bono, Mario
AU - Horvitz, H. Robert
AU - Pierce, Jonathan T.
ID - 7547
IS - 11
JF - G3: Genes, Genomes, Genetics
SN - 2160-1836
TI - Activity-dependent regulation of the proapoptotic BH3-only gene egl-1 in a living neuron pair in Caenorhabditis elegans
VL - 9
ER -
TY - JOUR
AB - Although the aggregation of the amyloid-β peptide (Aβ) into amyloid fibrils is a well-established hallmark of Alzheimer’s disease, the complex mechanisms linking this process to neurodegeneration are still incompletely understood. The nematode worm C. elegans is a valuable model organism through which to study these mechanisms because of its simple nervous system and its relatively short lifespan. Standard Aβ-based C. elegans models of Alzheimer’s disease are designed to study the toxic effects of the overexpression of Aβ in the muscle or nervous systems. However, the wide variety of effects associated with the tissue-level overexpression of Aβ makes it difficult to single out and study specific cellular mechanisms related to the onset of Alzheimer’s disease. Here, to better understand how to investigate the early events affecting neuronal signalling, we created a C. elegans model expressing Aβ42, the 42-residue form of Aβ, from a single-copy gene insertion in just one pair of glutamatergic sensory neurons, the BAG neurons. In behavioural assays, we found that the Aβ42-expressing animals displayed a subtle modulation of the response to CO2, compared to controls. Ca2+ imaging revealed that the BAG neurons in young Aβ42-expressing nematodes were activated more strongly than in control animals, and that neuronal activation remained intact until old age. Taken together, our results suggest that Aβ42-expression in this very subtle model of AD is sufficient to modulate the behavioural response but not strong enough to generate significant neurotoxicity, suggesting that slightly more aggressive perturbations will enable effectively studies of the links between the modulation of a physiological response and its associated neurotoxicity.
AU - Sinnige, Tessa
AU - Ciryam, Prashanth
AU - Casford, Samuel
AU - Dobson, Christopher M.
AU - de Bono, Mario
AU - Vendruscolo, Michele
ID - 7548
IS - 5
JF - PLOS ONE
SN - 1932-6203
TI - Expression of the amyloid-β peptide in a single pair of C. elegans sensory neurons modulates the associated behavioural response
VL - 14
ER -
TY - GEN
AB - We consider an optimal control problem for an abstract nonlinear dissipative evolution equation. The differential constraint is penalized by augmenting the target functional by a nonnegative global-in-time functional which is null-minimized in the evolution equation is satisfied. Different variational settings are presented, leading to the convergence of the penalization method for gradient flows, noncyclic and semimonotone flows, doubly nonlinear evolutions, and GENERIC systems.
AU - Portinale, Lorenzo
AU - Stefanelli, U
ID - 7550
TI - Penalization via global functionals of optimal-control problems for dissipative evolution
ER -
TY - GEN
AB - There is increasing evidence that protein binding to specific sites along DNA can activate the reading out of genetic information without coming into direct physical contact with the gene. There also is evidence that these distant but interacting sites are embedded in a liquid droplet of proteins which condenses out of the surrounding solution. We argue that droplet-mediated interactions can account for crucial features of gene regulation only if the droplet is poised at a non-generic point in its phase diagram. We explore a minimal model that embodies this idea, show that this model has a natural mechanism for self-tuning, and suggest direct experimental tests.
AU - Bialek, William
AU - Gregor, Thomas
AU - Tkačik, Gašper
ID - 7552
T2 - arXiv:1912.08579
TI - Action at a distance in transcriptional regulation
ER -
TY - CONF
AB - We present the results of a friendly competition for formal verification of continuous and hybrid systems with nonlinear continuous dynamics. The friendly competition took place as part of the workshop Applied Verification for Continuous and Hybrid Systems (ARCH) in 2019. In this year, 6 tools Ariadne, CORA, DynIbex, Flow*, Isabelle/HOL, and JuliaReach (in alphabetic order) participated. They are applied to solve reachability analysis problems on four benchmark problems, one of them with hybrid dynamics. We do not rank the tools based on the results, but show the current status and discover the potential advantages of different tools.
AU - Immler, Fabian
AU - Althoff, Matthias
AU - Benet, Luis
AU - Chapoutot, Alexandre
AU - Chen, Xin
AU - Forets, Marcelo
AU - Geretti, Luca
AU - Kochdumper, Niklas
AU - Sanders, David P.
AU - Schilling, Christian
ID - 7576
T2 - EPiC Series in Computing
TI - ARCH-COMP19 Category Report: Continuous and hybrid systems with nonlinear dynamics
VL - 61
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 - Electrodepositing insulating and insoluble Li2O2 is the key process during discharge of aprotic Li-O2 batteries and determines rate, capacity, and reversibility. Current understanding states that the partition between surface adsorbed and solvated LiO2 governs whether Li2O2 grows as surface film, leading to low capacity even at low rates, or in solution, leading to particles and high capacities. Here we show that Li2O2 forms to the widest extent as particles via solution mediated LiO2 disproportionation. We describe a unified Li2O2 growth model that conclusively explains capacity limitations across the whole range of electrolytes. Deciding for particle morphology, achievable rate and capacities are species mobilities, electrode specific surface area (determining true areal rate) and the concentration distribution of associated LiO2 in solution. Provided that species mobilities and surface are high, high, capacities are possible even with low-donor-number electrolytes, previously considered prototypical for low capacity via surface growth. The tools for these insights are microscopy, hydrodynamic voltammetry, a numerical reaction model, and in situ small/wide angle X-ray scattering (SAXS/WAXS). Combined with sophisticated data analysis, SAXS allows retrieving rich quantitative information from complex multi-phase systems. On a wider perspective, this SAXS method is a powerful in situ metrology with atomic to sub-micron resolution to study mechanisms in complex electrochemical systems and beyond.
AU - Prehal, Christian
AU - Samojlov, Aleksej
AU - Nachtnebel, Manfred
AU - Kriechbaum, Manfred
AU - Amenitsch, Heinz
AU - Freunberger, Stefan Alexander
ID - 7627
TI - A revised O2 reduction model in Li-O2 batteries as revealed by in situ small angle X-ray scattering
ER -
TY - CONF
AB - Deep neural networks (DNNs) have become increasingly important due to their excellent empirical performance on a wide range of problems. However, regularization is generally achieved by indirect means, largely due to the complex set of functions defined by a network and the difficulty in measuring function complexity. There exists no method in the literature for additive regularization based on a norm of the function, as is classically considered in statistical learning theory. In this work, we study the tractability of function norms for deep neural networks with ReLU activations. We provide, to the best of our knowledge, the first proof in the literature of the NP-hardness of computing function norms of DNNs of 3 or more layers. We also highlight a fundamental difference between shallow and deep networks. In the light on these results, we propose a new regularization strategy based on approximate function norms, and show its efficiency on a segmentation task with a DNN.
AU - Rannen-Triki, Amal
AU - Berman, Maxim
AU - Kolmogorov, Vladimir
AU - Blaschko, Matthew B.
ID - 7639
SN - 9781728150239
T2 - Proceedings of the 2019 International Conference on Computer Vision Workshop
TI - Function norms for neural networks
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 - JOUR
AB - The number of human genomes being genotyped or sequenced increases exponentially and efficient haplotype estimation methods able to handle this amount of data are now required. Here we present a method, SHAPEIT4, which substantially improves upon other methods to process large genotype and high coverage sequencing datasets. It notably exhibits sub-linear running times with sample size, provides highly accurate haplotypes and allows integrating external phasing information such as large reference panels of haplotypes, collections of pre-phased variants and long sequencing reads. We provide SHAPEIT4 in an open source format and demonstrate its performance in terms of accuracy and running times on two gold standard datasets: the UK Biobank data and the Genome In A Bottle.
AU - Delaneau, Olivier
AU - Zagury, Jean-François
AU - Robinson, Matthew Richard
AU - Marchini, Jonathan L.
AU - Dermitzakis, Emmanouil T.
ID - 7710
JF - Nature Communications
SN - 2041-1723
TI - Accurate, scalable and integrative haplotype estimation
VL - 10
ER -
TY - JOUR
AB - The nature and extent of mitochondrial DNA variation in a population and how it affects traits is poorly understood. Here we resequence the mitochondrial genomes of 169 Drosophila Genetic Reference Panel lines, identifying 231 variants that stratify along 12 mitochondrial haplotypes. We identify 1,845 cases of mitonuclear allelic imbalances, thus implying that mitochondrial haplotypes are reflected in the nuclear genome. However, no major fitness effects are associated with mitonuclear imbalance, suggesting that such imbalances reflect population structure at the mitochondrial level rather than genomic incompatibilities. Although mitochondrial haplotypes have no direct impact on mitochondrial respiration, some haplotypes are associated with stress- and metabolism-related phenotypes, including food intake in males. Finally, through reciprocal swapping of mitochondrial genomes, we demonstrate that a mitochondrial haplotype associated with high food intake can rescue a low food intake phenotype. Together, our findings provide new insight into population structure at the mitochondrial level and point to the importance of incorporating mitochondrial haplotypes in genotype–phenotype relationship studies.
AU - Bevers, Roel P. J.
AU - Litovchenko, Maria
AU - Kapopoulou, Adamandia
AU - Braman, Virginie S.
AU - Robinson, Matthew Richard
AU - Auwerx, Johan
AU - Hollis, Brian
AU - Deplancke, Bart
ID - 7711
IS - 12
JF - Nature Metabolism
SN - 2522-5812
TI - Mitochondrial haplotypes affect metabolic phenotypes in the Drosophila Genetic Reference Panel
VL - 1
ER -
TY - GEN
AB - As genome-wide association studies (GWAS) increased in size, numerous gene-environment interactions (GxE) have been discovered, many of which however explore only one environment at a time and may suffer from statistical artefacts leading to biased interaction estimates. Here we propose a maximum likelihood method to estimate the contribution of GxE to complex traits taking into account all interacting environmental variables at the same time, without the need to measure any. This is possible because GxE induces fluctuations in the conditional trait variance, the extent of which depends on the strength of GxE. The approach can be applied to continuous outcomes and for single SNPs or genetic risk scores (GRS). Extensive simulations demonstrated that our method yields unbiased interaction estimates and excellent confidence interval coverage. We also offer a strategy to distinguish specific GxE from general heteroscedasticity (scale effects). Applying our method to 32 complex traits in the UK Biobank reveals that for body mass index (BMI) the GRSxE explains an additional 1.9% variance on top of the 5.2% GRS contribution. However, this interaction is not specific to the GRS and holds for any variable similarly correlated with BMI. On the contrary, the GRSxE interaction effect for leg impedance Embedded Image is significantly (P < 10−56) larger than it would be expected for a similarly correlated variable Embedded Image. We showed that our method could robustly detect the global contribution of GxE to complex traits, which turned out to be substantial for certain obesity measures.
AU - Sulc, Jonathan
AU - Mounier, Ninon
AU - Günther, Felix
AU - Winkler, Thomas
AU - Wood, Andrew R.
AU - Frayling, Timothy M.
AU - Heid, Iris M.
AU - Robinson, Matthew Richard
AU - Kutalik, Zoltán
ID - 7782
T2 - bioRxiv
TI - Maximum likelihood method quantifies the overall contribution of gene-environment interaction to continuous traits: An application to complex traits in the UK Biobank
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 - 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 - 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 - Pollinators display a remarkable diversity of foraging strategies with flowering plants, from primarily mutualistic interactions to cheating through nectar robbery. Despite numerous studies on the effect of nectar robbing on components of plant fitness, its contribution to reproductive isolation is unclear. We experimentally tested the impact of different pollinator strategies in a natural hybrid zone between two subspecies of Antirrhinum majus with alternate flower colour guides. On either side of a steep cline in flower colour between Antirrhinum majus pseudomajus (magenta) and A. m. striatum (yellow), we quantified the behaviour of all floral visitors at different time points during the flowering season. Using long-run camera surveys, we quantify the impact of nectar robbing on the number of flowers visited per inflorescence and the flower probing time. We further experimentally tested the effect of nectar robbing on female reproductive success by manipulating the intensity of robbing. While robbing increased over time the number of legitimate visitors tended to decrease concomitantly. We found that the number of flowers pollinated on a focal inflorescence decreased with the number of prior robbing events. However, in the manipulative experiment, fruit set and fruit volume did not vary significantly between low robbing and control treatments. Our findings challenge the idea that robbers have a negative impact on plant fitness through female function. This study also adds to our understanding of the components of pollinator-mediated reproductive isolation and the maintenance of Antirrhinum hybrid zones.
AU - Andalo, Christophe
AU - Burrus, Monique
AU - Paute, Sandrine
AU - Lauzeral, Christine
AU - Field, David
ID - 5680
IS - 1
JF - Botany Letters
SN - 23818107
TI - Prevalence of legitimate pollinators and nectar robbers and the consequences for fruit set in an Antirrhinum majus hybrid zone
VL - 166
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 partial representation extension problem is a recently introduced generalization of the recognition problem. A circle graph is an intersection graph of chords of a circle. We study the partial representation extension problem for circle graphs, where the input consists of a graph G and a partial representation R′ giving some predrawn chords that represent an induced subgraph of G. The question is whether one can extend R′ to a representation R of the entire graph G, that is, whether one can draw the remaining chords into a partially predrawn representation to obtain a representation of G. Our main result is an O(n3) time algorithm for partial representation extension of circle graphs, where n is the number of vertices. To show this, we describe the structure of all representations of a circle graph using split decomposition. This can be of independent interest.
AU - Chaplick, Steven
AU - Fulek, Radoslav
AU - Klavík, Pavel
ID - 5790
IS - 4
JF - Journal of Graph Theory
SN - 03649024
TI - Extending partial representations of circle graphs
VL - 91
ER -
TY - CHAP
AB - The transcription coactivator, Yes-associated protein (YAP), which is a nuclear effector of the Hippo signaling pathway, has been shown to be a mechano-transducer. By using mutant fish and human 3D spheroids, we have recently demonstrated that YAP is also a mechano-effector. YAP functions in three-dimensional (3D) morphogenesis of organ and global body shape by controlling actomyosin-mediated tissue tension. In this chapter, we present a platform that links the findings in fish embryos with human cells. The protocols for analyzing tissue tension-mediated global body shape/organ morphogenesis in vivo and ex vivo using medaka fish embryos and in vitro using human cell spheroids represent useful tools for unraveling the molecular mechanisms by which YAP functions in regulating global body/organ morphogenesis.
AU - Asaoka, Yoichi
AU - Morita, Hitoshi
AU - Furumoto, Hiroko
AU - Heisenberg, Carl-Philipp J
AU - Furutani-Seiki, Makoto
ED - Hergovich, Alexander
ID - 5793
SN - 978-1-4939-8909-6
T2 - The hippo pathway
TI - Studying YAP-mediated 3D morphogenesis using fish embryos and human spheroids
VL - 1893
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 - 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 - A thrackle is a graph drawn in the plane so that every pair of its edges meet exactly once: either at a common end vertex or in a proper crossing. We prove that any thrackle of n vertices has at most 1.3984n edges. Quasi-thrackles are defined similarly, except that every pair of edges that do not share a vertex are allowed to cross an odd number of times. It is also shown that the maximum number of edges of a quasi-thrackle on n vertices is [Formula presented](n−1), and that this bound is best possible for infinitely many values of n.
AU - Fulek, Radoslav
AU - Pach, János
ID - 5857
IS - 4
JF - Discrete Applied Mathematics
SN - 0166218X
TI - Thrackles: An improved upper bound
VL - 259
ER -
TY - JOUR
AB - We consider the motion of a droplet bouncing on a vibrating bath of the same fluid in the presence of a central potential. We formulate a rotation symmetry-reduced description of this system, which allows for the straightforward application of dynamical systems theory tools. As an illustration of the utility of the symmetry reduction, we apply it to a model of the pilot-wave system with a central harmonic force. We begin our analysis by identifying local bifurcations and the onset of chaos. We then describe the emergence of chaotic regions and their merging bifurcations, which lead to the formation of a global attractor. In this final regime, the droplet’s angular momentum spontaneously changes its sign as observed in the experiments of Perrard et al.
AU - Budanur, Nazmi B
AU - Fleury, Marc
ID - 5878
IS - 1
JF - Chaos: An Interdisciplinary Journal of Nonlinear Science
SN - 1054-1500
TI - State space geometry of the chaotic pilot-wave hydrodynamics
VL - 29
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 - JOUR
AB - Cryptographic security is usually defined as a guarantee that holds except when a bad event with negligible probability occurs, and nothing is guaranteed in that bad case. However, in settings where such failure can happen with substantial probability, one needs to provide guarantees even for the bad case. A typical example is where a (possibly weak) password is used instead of a secure cryptographic key to protect a session, the bad event being that the adversary correctly guesses the password. In a situation with multiple such sessions, a per-session guarantee is desired: any session for which the password has not been guessed remains secure, independently of whether other sessions have been compromised. A new formalism for stating such gracefully degrading security guarantees is introduced and applied to analyze the examples of password-based message authentication and password-based encryption. While a natural per-message guarantee is achieved for authentication, the situation of password-based encryption is more delicate: a per-session confidentiality guarantee only holds against attackers for which the distribution of password-guessing effort over the sessions is known in advance. In contrast, for more general attackers without such a restriction, a strong, composable notion of security cannot be achieved.
AU - Demay, Gregory
AU - Gazi, Peter
AU - Maurer, Ueli
AU - Tackmann, Bjorn
ID - 5887
IS - 1
JF - Journal of Computer Security
SN - 0926227X
TI - Per-session security: Password-based cryptography revisited
VL - 27
ER -
TY - JOUR
AB - We introduce a simple, exactly solvable strong-randomness renormalization group (RG) model for the many-body localization (MBL) transition in one dimension. Our approach relies on a family of RG flows parametrized by the asymmetry between thermal and localized phases. We identify the physical MBL transition in the limit of maximal asymmetry, reflecting the instability of MBL against rare thermal inclusions. We find a critical point that is localized with power-law distributed thermal inclusions. The typical size of critical inclusions remains finite at the transition, while the average size is logarithmically diverging. We propose a two-parameter scaling theory for the many-body localization transition that falls into the Kosterlitz-Thouless universality class, with the MBL phase corresponding to a stable line of fixed points with multifractal behavior.
AU - Goremykina, Anna
AU - Vasseur, Romain
AU - Serbyn, Maksym
ID - 5906
IS - 4
JF - Physical Review Letters
SN - 0031-9007
TI - Analytically solvable renormalization group for the many-body localization transition
VL - 122
ER -
TY - JOUR
AB - Microalgae of the genus Chlorella vulgaris are candidates for the production of lipids for biofuel production. Besides that, Chlorella vulgaris is marketed as protein and vitamin rich food additive. Its potential as a novel expression system for recombinant proteins inspired us to study its asparagine-linked oligosaccharides (N-glycans) by mass spectrometry, chromatography and gas chromatography. Oligomannosidic N-glycans with up to nine mannoses were the structures found in culture collection strains as well as several commercial products. These glycans co-eluted with plant N-glycans in the highly shape selective porous graphitic carbon chromatography. Thus, Chlorella vulgaris generates oligomannosidic N-glycans of the structural type known from land plants and animals. In fact, Man5 (Man5GlcNAc2) served as substrate for GlcNAc-transferase I and a trace of an endogenous structure with terminal GlcNAc was seen. The unusual more linear Man5 structure recently found on glycoproteins of Chlamydomonas reinhardtii occurred - if at all - in traces only. Notably, a majority of the oligomannosidic glycans was multiply O-methylated with 3-O-methyl and 3,6-di-O-methyl mannoses at the non-reducing termini. This modification has so far been neither found on plant nor vertebrate N-glycans. It’s possible immunogenicity raises concerns as to the use of C. vulgaris for production of pharmaceutical glycoproteins.
AU - Mócsai, Réka
AU - Figl, Rudolf
AU - Troschl, Clemens
AU - Strasser, Richard
AU - Svehla, Elisabeth
AU - Windwarder, Markus
AU - Thader, Andreas
AU - Altmann, Friedrich
ID - 5907
IS - 1
JF - Scientific Reports
TI - N-glycans of the microalga Chlorella vulgaris are of the oligomannosidic type but highly methylated
VL - 9
ER -
TY - JOUR
AB - The interorganelle communication mediated by membrane contact sites (MCSs) is an evolutionary hallmark of eukaryotic cells. MCS connections enable the nonvesicular exchange of information between organelles and allow them to coordinate responses to changing cellular environments. In plants, the importance of MCS components in the responses to environmental stress has been widely established, but the molecular mechanisms regulating interorganelle connectivity during stress still remain opaque. In this report, we use the model plant Arabidopsis thaliana to show that ionic stress increases endoplasmic reticulum (ER)–plasma membrane (PM) connectivity by promoting the cortical expansion of synaptotagmin 1 (SYT1)-enriched ER–PM contact sites (S-EPCSs). We define differential roles for the cortical cytoskeleton in the regulation of S-EPCS dynamics and ER–PM connectivity, and we identify the accumulation of phosphatidylinositol 4,5-bisphosphate [PI(4,5)P2] at the PM as a molecular signal associated with the ER–PM connectivity changes. Our study highlights the functional conservation of EPCS components and PM phosphoinositides as modulators of ER–PM connectivity in eukaryotes, and uncovers unique aspects of the spatiotemporal regulation of ER–PM connectivity in plants.
AU - Lee, Eunkyoung
AU - Vanneste, Steffen
AU - Pérez-Sancho, Jessica
AU - Benitez-Fuente, Francisco
AU - Strelau, Matthew
AU - Macho, Alberto P.
AU - Botella, Miguel A.
AU - Friml, Jiří
AU - Rosado, Abel
ID - 5908
IS - 4
JF - Proceedings of the National Academy of Sciences of the United States of America
TI - Ionic stress enhances ER–PM connectivity via phosphoinositide-associated SYT1 contact site expansion in Arabidopsis
VL - 116
ER -
TY - JOUR
AB - Empirical data suggest that inversions in many species contain genes important for intraspecific divergence and speciation, yet mechanisms of evolution remain unclear. While genes inside an inversion are tightly linked, inversions are not static but evolve separately from the rest of the genome by new mutations, recombination within arrangements, and gene flux between arrangements. Inversion polymorphisms are maintained by different processes, for example, divergent or balancing selection, or a mix of multiple processes. Moreover, the relative roles of selection, drift, mutation, and recombination will change over the lifetime of an inversion and within its area of distribution. We believe inversions are central to the evolution of many species, but we need many more data and new models to understand the complex mechanisms involved.
AU - Faria, Rui
AU - Johannesson, Kerstin
AU - Butlin, Roger K.
AU - Westram, Anja M
ID - 5911
IS - 3
JF - Trends in Ecology and Evolution
SN - 01695347
TI - Evolving inversions
VL - 34
ER -
TY - JOUR
AB - The hairpin instability of a jet in a crossflow (JICF) for a low jet-to-crossflow velocity ratio is investigated experimentally for a velocity ratio range of R ∈ (0.14, 0.75) and crossflow Reynolds numbers ReD ∈ (260, 640). From spectral analysis we characterize the Strouhal number and amplitude of the hairpin instability as a function of R and ReD. We demonstrate that the dynamics of the hairpins is well described by the Landau model, and, hence, that the instability occurs through Hopf bifurcation, similarly to other hydrodynamical oscillators such as wake behind different bluff bodies. Using the Landau model, we determine the precise threshold values of hairpin shedding. We also study the spatial dependence of this hydrodynamical instability, which shows a global behaviour.
AU - Klotz, Lukasz
AU - Gumowski, Konrad
AU - Wesfreid, José Eduardo
ID - 5943
JF - Journal of Fluid Mechanics
TI - Experiments on a jet in a crossflow in the low-velocity-ratio regime
VL - 863
ER -
TY - JOUR
AB - Understanding the thermodynamics of the duplication process is a fundamental step towards a comprehensive physical theory of biological systems. However, the immense complexity of real cells obscures the fundamental tensions between energy gradients and entropic contributions that underlie duplication. The study of synthetic, feasible systems reproducing part of the key ingredients of living entities but overcoming major sources of biological complexity is of great relevance to deepen the comprehension of the fundamental thermodynamic processes underlying life and its prevalence. In this paper an abstract—yet realistic—synthetic system made of small synthetic protocell aggregates is studied in detail. A fundamental relation between free energy and entropic gradients is derived for a general, non-equilibrium scenario, setting the thermodynamic conditions for the occurrence and prevalence of duplication phenomena. This relation sets explicitly how the energy gradients invested in creating and maintaining structural—and eventually, functional—elements of the system must always compensate the entropic gradients, whose contributions come from changes in the translational, configurational, and macrostate entropies, as well as from dissipation due to irreversible transitions. Work/energy relations are also derived, defining lower bounds on the energy required for the duplication event to take place. A specific example including real ternary emulsions is provided in order to grasp the orders of magnitude involved in the problem. It is found that the minimal work invested over the system to trigger a duplication event is around ~ 10−13J , which results, in the case of duplication of all the vesicles contained in a liter of emulsion, in an amount of energy around ~ 1kJ . Without aiming to describe a truly biological process of duplication, this theoretical contribution seeks to explicitly define and identify the key actors that participate in it.
AU - Corominas-Murtra, Bernat
ID - 5944
IS - 1
JF - Life
TI - Thermodynamics of duplication thresholds in synthetic protocell systems
VL - 9
ER -
TY - JOUR
AB - In developing organisms, spatially prescribed cell identities are thought to be determined by the expression levels of multiple genes. Quantitative tests of this idea, however, require a theoretical framework capable of exposing the rules and precision of cell specification over developmental time. We use the gap gene network in the early fly embryo as an example to show how expression levels of the four gap genes can be jointly decoded into an optimal specification of position with 1% accuracy. The decoder correctly predicts, with no free parameters, the dynamics of pair-rule expression patterns at different developmental time points and in various mutant backgrounds. Precise cellular identities are thus available at the earliest stages of development, contrasting the prevailing view of positional information being slowly refined across successive layers of the patterning network. Our results suggest that developmental enhancers closely approximate a mathematically optimal decoding strategy.
AU - Petkova, Mariela D.
AU - Tkacik, Gasper
AU - Bialek, William
AU - Wieschaus, Eric F.
AU - Gregor, Thomas
ID - 5945
IS - 4
JF - Cell
TI - Optimal decoding of cellular identities in a genetic network
VL - 176
ER -
TY - CONF
AB - Graph algorithms applied in many applications, including social networks, communication networks, VLSI design, graphics, and several others, require dynamic modifications - addition and removal of vertices and/or edges - in the graph. This paper presents a novel concurrent non-blocking algorithm to implement a dynamic unbounded directed graph in a shared-memory machine. The addition and removal operations of vertices and edges are lock-free. For a finite sized graph, the lookup operations are wait-free. Most significant component of the presented algorithm is the reachability query in a concurrent graph. The reachability queries in our algorithm are obstruction-free and thus impose minimal additional synchronization cost over other operations. We prove that each of the data structure operations are linearizable. We extensively evaluate a sample C/C++ implementation of the algorithm through a number of micro-benchmarks. The experimental results show that the proposed algorithm scales well with the number of threads and on an average provides 5 to 7x performance improvement over a concurrent graph implementation using coarse-grained locking.
AU - Chatterjee, Bapi
AU - Peri, Sathya
AU - Sa, Muktikanta
AU - Singhal, Nandini
ID - 5947
SN - 978-1-4503-6094-4
T2 - ACM International Conference Proceeding Series
TI - A simple and practical concurrent non-blocking unbounded graph with linearizable reachability queries
ER -
TY - CONF
AB - We study the termination problem for nondeterministic probabilistic programs. We consider the bounded termination problem that asks whether the supremum of the expected termination time over all schedulers is bounded. First, we show that ranking supermartingales (RSMs) are both sound and complete for proving bounded termination over nondeterministic probabilistic programs. For nondeterministic probabilistic programs a previous result claimed that RSMs are not complete for bounded termination, whereas our result corrects the previous flaw and establishes completeness with a rigorous proof. Second, we present the first sound approach to establish lower bounds on expected termination time through RSMs.
AU - Fu, Hongfei
AU - Chatterjee, Krishnendu
ID - 5948
T2 - International Conference on Verification, Model Checking, and Abstract Interpretation
TI - Termination of nondeterministic probabilistic programs
VL - 11388
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 - 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 -