TY - CONF AB - High-dimensional time series are common in many domains. Since human cognition is not optimized to work well in high-dimensional spaces, these areas could benefit from interpretable low-dimensional representations. However, most representation learning algorithms for time series data are difficult to interpret. This is due to non-intuitive mappings from data features to salient properties of the representation and non-smoothness over time. To address this problem, we propose a new representation learning framework building on ideas from interpretable discrete dimensionality reduction and deep generative modeling. This framework allows us to learn discrete representations of time series, which give rise to smooth and interpretable embeddings with superior clustering performance. We introduce a new way to overcome the non-differentiability in discrete representation learning and present a gradient-based version of the traditional self-organizing map algorithm that is more performant than the original. Furthermore, to allow for a probabilistic interpretation of our method, we integrate a Markov model in the representation space. This model uncovers the temporal transition structure, improves clustering performance even further and provides additional explanatory insights as well as a natural representation of uncertainty. We evaluate our model in terms of clustering performance and interpretability on static (Fashion-)MNIST data, a time series of linearly interpolated (Fashion-)MNIST images, a chaotic Lorenz attractor system with two macro states, as well as on a challenging real world medical time series application on the eICU data set. Our learned representations compare favorably with competitor methods and facilitate downstream tasks on the real world data. AU - Fortuin, Vincent AU - Hüser, Matthias AU - Locatello, Francesco AU - Strathmann, Heiko AU - Rätsch, Gunnar ID - 14198 T2 - International Conference on Learning Representations TI - SOM-VAE: Interpretable discrete representation learning on time series ER - TY - CONF AB - We propose a conditional gradient framework for a composite convex minimization template with broad applications. Our approach combines smoothing and homotopy techniques under the CGM framework, and provably achieves the optimal O(1/k−−√) convergence rate. We demonstrate that the same rate holds if the linear subproblems are solved approximately with additive or multiplicative error. In contrast with the relevant work, we are able to characterize the convergence when the non-smooth term is an indicator function. Specific applications of our framework include the non-smooth minimization, semidefinite programming, and minimization with linear inclusion constraints over a compact domain. Numerical evidence demonstrates the benefits of our framework. AU - Yurtsever, Alp AU - Fercoq, Olivier AU - Locatello, Francesco AU - Cevher, Volkan ID - 14203 T2 - Proceedings of the 35th International Conference on Machine Learning TI - A conditional gradient framework for composite convex minimization with applications to semidefinite programming VL - 80 ER - TY - JOUR AB - Adaptive introgression is common in nature and can be driven by selection acting on multiple, linked genes. We explore the effects of polygenic selection on introgression under the infinitesimal model with linkage. This model assumes that the introgressing block has an effectively infinite number of genes, each with an infinitesimal effect on the trait under selection. The block is assumed to introgress under directional selection within a native population that is genetically homogeneous. We use individual-based simulations and a branching process approximation to compute various statistics of the introgressing block, and explore how these depend on parameters such as the map length and initial trait value associated with the introgressing block, the genetic variability along the block, and the strength of selection. Our results show that the introgression dynamics of a block under infinitesimal selection is qualitatively different from the dynamics of neutral introgression. We also find that in the long run, surviving descendant blocks are likely to have intermediate lengths, and clarify how the length is shaped by the interplay between linkage and infinitesimal selection. Our results suggest that it may be difficult to distinguish introgression of single loci from that of genomic blocks with multiple, tightly linked and weakly selected loci. AU - Sachdeva, Himani AU - Barton, Nicholas H ID - 282 IS - 4 JF - Genetics TI - Introgression of a block of genome under infinitesimal selection VL - 209 ER - TY - CONF AB - Universal hashing found a lot of applications in computer science. In cryptography the most important fact about universal families is the so called Leftover Hash Lemma, proved by Impagliazzo, Levin and Luby. In the language of modern cryptography it states that almost universal families are good extractors. In this work we provide a somewhat surprising characterization in the opposite direction. Namely, every extractor with sufficiently good parameters yields a universal family on a noticeable fraction of its inputs. Our proof technique is based on tools from extremal graph theory applied to the \'collision graph\' induced by the extractor, and may be of independent interest. We discuss possible applications to the theory of randomness extractors and non-malleable codes. AU - Obremski, Marciej AU - Skorski, Maciej ID - 108 TI - Inverted leftover hash lemma VL - 2018 ER - TY - CONF AB - Two popular examples of first-order optimization methods over linear spaces are coordinate descent and matching pursuit algorithms, with their randomized variants. While the former targets the optimization by moving along coordinates, the latter considers a generalized notion of directions. Exploiting the connection between the two algorithms, we present a unified analysis of both, providing affine invariant sublinear O(1/t) rates on smooth objectives and linear convergence on strongly convex objectives. As a byproduct of our affine invariant analysis of matching pursuit, our rates for steepest coordinate descent are the tightest known. Furthermore, we show the first accelerated convergence rate O(1/t2) for matching pursuit and steepest coordinate descent on convex objectives. AU - Locatello, Francesco AU - Raj, Anant AU - Karimireddy, Sai Praneeth AU - Rätsch, Gunnar AU - Schölkopf, Bernhard AU - Stich, Sebastian U. AU - Jaggi, Martin ID - 14204 T2 - Proceedings of the 35th International Conference on Machine Learning TI - On matching pursuit and coordinate descent VL - 80 ER - TY - CONF AB - We present layered concurrent programs, a compact and expressive notation for specifying refinement proofs of concurrent programs. A layered concurrent program specifies a sequence of connected concurrent programs, from most concrete to most abstract, such that common parts of different programs are written exactly once. These programs are expressed in the ordinary syntax of imperative concurrent programs using gated atomic actions, sequencing, choice, and (recursive) procedure calls. Each concurrent program is automatically extracted from the layered program. We reduce refinement to the safety of a sequence of concurrent checker programs, one each to justify the connection between every two consecutive concurrent programs. These checker programs are also automatically extracted from the layered program. Layered concurrent programs have been implemented in the CIVL verifier which has been successfully used for the verification of several complex concurrent programs. AU - Kragl, Bernhard AU - Qadeer, Shaz ID - 160 TI - Layered Concurrent Programs VL - 10981 ER - TY - JOUR AB - Flowers have a species-specific functional life span that determines the time window in which pollination, fertilization and seed set can occur. The stigma tissue plays a key role in flower receptivity by intercepting pollen and initiating pollen tube growth toward the ovary. In this article, we show that a developmentally controlled cell death programme terminates the functional life span of stigma cells in Arabidopsis. We identified the leaf senescence regulator ORESARA1 (also known as ANAC092) and the previously uncharacterized KIRA1 (also known as ANAC074) as partially redundant transcription factors that modulate stigma longevity by controlling the expression of programmed cell death-associated genes. KIRA1 expression is sufficient to induce cell death and terminate floral receptivity, whereas lack of both KIRA1 and ORESARA1 substantially increases stigma life span. Surprisingly, the extension of stigma longevity is accompanied by only a moderate extension of flower receptivity, suggesting that additional processes participate in the control of the flower's receptive life span. AU - Gao, Zhen AU - Daneva, Anna AU - Salanenka, Yuliya AU - Van Durme, Matthias AU - Huysmans, Marlies AU - Lin, Zongcheng AU - De Winter, Freya AU - Vanneste, Steffen AU - Karimi, Mansour AU - Van De Velde, Jan AU - Vandepoele, Klaas AU - Van De Walle, Davy AU - Dewettinck, Koen AU - Lambrecht, Bart AU - Nowack, Moritz ID - 280 IS - 6 JF - Nature Plants TI - KIRA1 and ORESARA1 terminate flower receptivity by promoting cell death in the stigma of Arabidopsis VL - 4 ER - TY - JOUR AB - Buffers are essential for diluting bacterial cultures for flow cytometry analysis in order to study bacterial physiology and gene expression parameters based on fluorescence signals. Using a variety of constitutively expressed fluorescent proteins in Escherichia coli K-12 strain MG1655, we found strong artifactual changes in fluorescence levels after dilution into the commonly used flow cytometry buffer phosphate-buffered saline (PBS) and two other buffer solutions, Tris-HCl and M9 salts. These changes appeared very rapidly after dilution, and were linked to increased membrane permeability and loss in cell viability. We observed buffer-related effects in several different E. coli strains, K-12, C and W, but not E. coli B, which can be partially explained by differences in lipopolysaccharide (LPS) and outer membrane composition. Supplementing the buffers with divalent cations responsible for outer membrane stability, Mg2+ and Ca2+, preserved fluorescence signals, membrane integrity and viability of E. coli. Thus, stabilizing the bacterial outer membrane is essential for precise and unbiased measurements of fluorescence parameters using flow cytometry. AU - Tomasek, Kathrin AU - Bergmiller, Tobias AU - Guet, Calin C ID - 503 JF - Journal of Biotechnology TI - Lack of cations in flow cytometry buffers affect fluorescence signals by reducing membrane stability and viability of Escherichia coli strains VL - 268 ER - TY - JOUR AB - In experimental cultures, when bacteria are mixed with lytic (virulent) bacteriophage, bacterial cells resistant to the phage commonly emerge and become the dominant population of bacteria. Following the ascent of resistant mutants, the densities of bacteria in these simple communities become limited by resources rather than the phage. Despite the evolution of resistant hosts, upon which the phage cannot replicate, the lytic phage population is most commonly maintained in an apparently stable state with the resistant bacteria. Several mechanisms have been put forward to account for this result. Here we report the results of population dynamic/evolution experiments with a virulent mutant of phage Lambda, λVIR, and Escherichia coli in serial transfer cultures. We show that, following the ascent of λVIR-resistant bacteria, λVIRis maintained in the majority of cases in maltose-limited minimal media and in all cases in nutrient-rich broth. Using mathematical models and experiments, we show that the dominant mechanism responsible for maintenance of λVIRin these resource-limited populations dominated by resistant E. coli is a high rate of either phenotypic or genetic transition from resistance to susceptibility—a hitherto undemonstrated mechanism we term "leaky resistance." We discuss the implications of leaky resistance to our understanding of the conditions for the maintenance of phage in populations of bacteria—their “existence conditions.”. AU - Chaudhry, Waqas AU - Pleska, Maros AU - Shah, Nilang AU - Weiss, Howard AU - Mccall, Ingrid AU - Meyer, Justin AU - Gupta, Animesh AU - Guet, Calin C AU - Levin, Bruce ID - 82 IS - 8 JF - PLoS Biology TI - Leaky resistance and the conditions for the existence of lytic bacteriophage VL - 16 ER - TY - JOUR AB - We present a data-driven technique to instantly predict how fluid flows around various three-dimensional objects. Such simulation is useful for computational fabrication and engineering, but is usually computationally expensive since it requires solving the Navier-Stokes equation for many time steps. To accelerate the process, we propose a machine learning framework which predicts aerodynamic forces and velocity and pressure fields given a threedimensional shape input. Handling detailed free-form three-dimensional shapes in a data-driven framework is challenging because machine learning approaches usually require a consistent parametrization of input and output. We present a novel PolyCube maps-based parametrization that can be computed for three-dimensional shapes at interactive rates. This allows us to efficiently learn the nonlinear response of the flow using a Gaussian process regression. We demonstrate the effectiveness of our approach for the interactive design and optimization of a car body. AU - Umetani, Nobuyuki AU - Bickel, Bernd ID - 4 IS - 4 JF - ACM Trans. Graph. TI - Learning three-dimensional flow for interactive aerodynamic design VL - 37 ER - TY - CONF AB - Fault-localization is considered to be a very tedious and time-consuming activity in the design of complex Cyber-Physical Systems (CPS). This laborious task essentially requires expert knowledge of the system in order to discover the cause of the fault. In this context, we propose a new procedure that AIDS designers in debugging Simulink/Stateflow hybrid system models, guided by Signal Temporal Logic (STL) specifications. The proposed method relies on three main ingredients: (1) a monitoring and a trace diagnostics procedure that checks whether a tested behavior satisfies or violates an STL specification, localizes time segments and interfaces variables contributing to the property violations; (2) a slicing procedure that maps these observable behavior segments to the internal states and transitions of the Simulink model; and (3) a spectrum-based fault-localization method that combines the previous analysis from multiple tests to identify the internal states and/or transitions that are the most likely to explain the fault. We demonstrate the applicability of our approach on two Simulink models from the automotive and the avionics domain. AU - Bartocci, Ezio AU - Ferrere, Thomas AU - Manjunath, Niveditha AU - Nickovic, Dejan ID - 183 TI - Localizing faults in simulink/stateflow models with STL ER - TY - JOUR AB - We consider large random matrices X with centered, independent entries which have comparable but not necessarily identical variances. Girko's circular law asserts that the spectrum is supported in a disk and in case of identical variances, the limiting density is uniform. In this special case, the local circular law by Bourgade et. al. [11,12] shows that the empirical density converges even locally on scales slightly above the typical eigenvalue spacing. In the general case, the limiting density is typically inhomogeneous and it is obtained via solving a system of deterministic equations. Our main result is the local inhomogeneous circular law in the bulk spectrum on the optimal scale for a general variance profile of the entries of X. AU - Alt, Johannes AU - Erdös, László AU - Krüger, Torben H ID - 566 IS - 1 JF - Annals Applied Probability TI - Local inhomogeneous circular law VL - 28 ER - TY - JOUR AB - The goal of this article is to introduce the reader to the theory of intrinsic geometry of convex surfaces. We illustrate the power of the tools by proving a theorem on convex surfaces containing an arbitrarily long closed simple geodesic. Let us remind ourselves that a curve in a surface is called geodesic if every sufficiently short arc of the curve is length minimizing; if, in addition, it has no self-intersections, we call it simple geodesic. A tetrahedron with equal opposite edges is called isosceles. The axiomatic method of Alexandrov geometry allows us to work with the metrics of convex surfaces directly, without approximating it first by a smooth or polyhedral metric. Such approximations destroy the closed geodesics on the surface; therefore it is difficult (if at all possible) to apply approximations in the proof of our theorem. On the other hand, a proof in the smooth or polyhedral case usually admits a translation into Alexandrov’s language; such translation makes the result more general. In fact, our proof resembles a translation of the proof given by Protasov. Note that the main theorem implies in particular that a smooth convex surface does not have arbitrarily long simple closed geodesics. However we do not know a proof of this corollary that is essentially simpler than the one presented below. AU - Akopyan, Arseniy AU - Petrunin, Anton ID - 106 IS - 3 JF - Mathematical Intelligencer TI - Long geodesics on convex surfaces VL - 40 ER - TY - GEN AU - Chaudhry, Waqas AU - Pleska, Maros AU - Shah, Nilang AU - Weiss, Howard AU - Mccall, Ingrid AU - Meyer, Justin AU - Gupta, Animesh AU - Guet, Calin C AU - Levin, Bruce ID - 9810 TI - Numerical data used in figures ER - TY - JOUR AB - Lymphatic endothelial cells (LECs) release extracellular chemokines to guide the migration of dendritic cells. In this study, we report that LECs also release basolateral exosome-rich endothelial vesicles (EEVs) that are secreted in greater numbers in the presence of inflammatory cytokines and accumulate in the perivascular stroma of small lymphatic vessels in human chronic inflammatory diseases. Proteomic analyses of EEV fractions identified > 1,700 cargo proteins and revealed a dominant motility-promoting protein signature. In vitro and ex vivo EEV fractions augmented cellular protrusion formation in a CX3CL1/fractalkine-dependent fashion and enhanced the directional migratory response of human dendritic cells along guidance cues. We conclude that perilymphatic LEC exosomes enhance exploratory behavior and thus promote directional migration of CX3CR1-expressing cells in complex tissue environments. AU - Brown, Markus AU - Johnson, Louise AU - Leone, Dario AU - Májek, Peter AU - Vaahtomeri, Kari AU - Senfter, Daniel AU - Bukosza, Nora AU - Schachner, Helga AU - Asfour, Gabriele AU - Langer, Brigitte AU - Hauschild, Robert AU - Parapatics, Katja AU - Hong, Young AU - Bennett, Keiryn AU - Kain, Renate AU - Detmar, Michael AU - Sixt, Michael K AU - Jackson, David AU - Kerjaschki, Dontscho ID - 275 IS - 6 JF - Journal of Cell Biology TI - Lymphatic exosomes promote dendritic cell migration along guidance cues VL - 217 ER - TY - JOUR AB - The angiosperm seed is composed of three genetically distinct tissues: the diploid embryo that originates from the fertilized egg cell, the triploid endosperm that is produced from the fertilized central cell, and the maternal sporophytic integuments that develop into the seed coat1. At the onset of embryo development in Arabidopsis thaliana, the zygote divides asymmetrically, producing a small apical embryonic cell and a larger basal cell that connects the embryo to the maternal tissue2. The coordinated and synchronous development of the embryo and the surrounding integuments, and the alignment of their growth axes, suggest communication between maternal tissues and the embryo. In contrast to animals, however, where a network of maternal factors that direct embryo patterning have been identified3,4, only a few maternal mutations have been described to affect embryo development in plants5–7. Early embryo patterning in Arabidopsis requires accumulation of the phytohormone auxin in the apical cell by directed transport from the suspensor8–10. However, the origin of this auxin has remained obscure. Here we investigate the source of auxin for early embryogenesis and provide evidence that the mother plant coordinates seed development by supplying auxin to the early embryo from the integuments of the ovule. We show that auxin response increases in ovules after fertilization, due to upregulated auxin biosynthesis in the integuments, and this maternally produced auxin is required for correct embryo development. AU - Robert, Hélène AU - Park, Chulmin AU - Gutièrrez, Carla AU - Wójcikowska, Barbara AU - Pěnčík, Aleš AU - Novák, Ondřej AU - Chen, Junyi AU - Grunewald, Wim AU - Dresselhaus, Thomas AU - Friml, Jirí AU - Laux, Thomas ID - 158 IS - 8 JF - Nature Plants TI - Maternal auxin supply contributes to early embryo patterning in Arabidopsis VL - 4 ER - TY - JOUR AB - Complex I has an essential role in ATP production by coupling electron transfer from NADH to quinone with translocation of protons across the inner mitochondrial membrane. Isolated complex I deficiency is a frequent cause of mitochondrial inherited diseases. Complex I has also been implicated in cancer, ageing, and neurodegenerative conditions. Until recently, the understanding of complex I deficiency on the molecular level was limited due to the lack of high-resolution structures of the enzyme. However, due to developments in single particle cryo-electron microscopy (cryo-EM), recent studies have reported nearly atomic resolution maps and models of mitochondrial complex I. These structures significantly add to our understanding of complex I mechanism and assembly. The disease-causing mutations are discussed here in their structural context. AU - Fiedorczuk, Karol AU - Sazanov, Leonid A ID - 152 IS - 10 JF - Trends in Cell Biology TI - Mammalian mitochondrial complex I structure and disease causing mutations VL - 28 ER - TY - CONF AB - A model of computation that is widely used in the formal analysis of reactive systems is symbolic algorithms. In this model the access to the input graph is restricted to consist of symbolic operations, which are expensive in comparison to the standard RAM operations. We give lower bounds on the number of symbolic operations for basic graph problems such as the computation of the strongly connected components and of the approximate diameter as well as for fundamental problems in model checking such as safety, liveness, and coliveness. Our lower bounds are linear in the number of vertices of the graph, even for constant-diameter graphs. For none of these problems lower bounds on the number of symbolic operations were known before. The lower bounds show an interesting separation of these problems from the reachability problem, which can be solved with O(D) symbolic operations, where D is the diameter of the graph. Additionally we present an approximation algorithm for the graph diameter which requires Õ(n/D) symbolic steps to achieve a (1 +ϵ)-approximation for any constant > 0. This compares to O(n/D) symbolic steps for the (naive) exact algorithm and O(D) symbolic steps for a 2-approximation. Finally we also give a refined analysis of the strongly connected components algorithms of [15], showing that it uses an optimal number of symbolic steps that is proportional to the sum of the diameters of the strongly connected components. AU - Chatterjee, Krishnendu AU - Dvorák, Wolfgang AU - Henzinger, Monika H AU - Loitzenbauer, Veronika ID - 310 TI - Lower bounds for symbolic computation on graphs: Strongly connected components, liveness, safety, and diameter ER - TY - JOUR AB - There has been significant interest recently in using complex quantum systems to create effective nonreciprocal dynamics. Proposals have been put forward for the realization of artificial magnetic fields for photons and phonons; experimental progress is fast making these proposals a reality. Much work has concentrated on the use of such systems for controlling the flow of signals, e.g., to create isolators or directional amplifiers for optical signals. In this Letter, we build on this work but move in a different direction. We develop the theory of and discuss a potential realization for the controllable flow of thermal noise in quantum systems. We demonstrate theoretically that the unidirectional flow of thermal noise is possible within quantum cascaded systems. Viewing an optomechanical platform as a cascaded system we show here that one can ultimately control the direction of the flow of thermal noise. By appropriately engineering the mechanical resonator, which acts as an artificial reservoir, the flow of thermal noise can be constrained to a desired direction, yielding a thermal rectifier. The proposed quantum thermal noise rectifier could potentially be used to develop devices such as a thermal modulator, a thermal router, and a thermal amplifier for nanoelectronic devices and superconducting circuits. AU - Barzanjeh, Shabir AU - Aquilina, Matteo AU - Xuereb, André ID - 436 IS - 6 JF - Physical Review Letters TI - Manipulating the flow of thermal noise in quantum devices VL - 120 ER - TY - JOUR AB - Spatial patterns are ubiquitous on the subcellular, cellular and tissue level, and can be studied using imaging techniques such as light and fluorescence microscopy. Imaging data provide quantitative information about biological systems; however, mechanisms causing spatial patterning often remain elusive. In recent years, spatio-temporal mathematical modelling has helped to overcome this problem. Yet, outliers and structured noise limit modelling of whole imaging data, and models often consider spatial summary statistics. Here, we introduce an integrated data-driven modelling approach that can cope with measurement artefacts and whole imaging data. Our approach combines mechanistic models of the biological processes with robust statistical models of the measurement process. The parameters of the integrated model are calibrated using a maximum-likelihood approach. We used this integrated modelling approach to study in vivo gradients of the chemokine (C-C motif) ligand 21 (CCL21). CCL21 gradients guide dendritic cells and are important in the adaptive immune response. Using artificial data, we verified that the integrated modelling approach provides reliable parameter estimates in the presence of measurement noise and that bias and variance of these estimates are reduced compared to conventional approaches. The application to experimental data allowed the parametrization and subsequent refinement of the model using additional mechanisms. Among other results, model-based hypothesis testing predicted lymphatic vessel-dependent concentration of heparan sulfate, the binding partner of CCL21. The selected model provided an accurate description of the experimental data and was partially validated using published data. Our findings demonstrate that integrated statistical modelling of whole imaging data is computationally feasible and can provide novel biological insights. AU - Hross, Sabrina AU - Theis, Fabian J. AU - Sixt, Michael K AU - Hasenauer, Jan ID - 5858 IS - 149 JF - Journal of the Royal Society Interface SN - 17425689 TI - Mechanistic description of spatial processes using integrative modelling of noise-corrupted imaging data VL - 15 ER -