TY - GEN AB - The infiltration of immune cells into tissues underlies the establishment of tissue resident macrophages, and responses to infections and tumors. Yet the mechanisms immune cells utilize to negotiate tissue barriers in living organisms are not well understood, and a role for cortical actin has not been examined. Here we find that the tissue invasion of Drosophila macrophages, also known as plasmatocytes or hemocytes, utilizes enhanced cortical F-actin levels stimulated by the Drosophila member of the fos proto oncogene transcription factor family (Dfos, Kayak). RNA sequencing analysis and live imaging show that Dfos enhances F-actin levels around the entire macrophage surface by increasing mRNA levels of the membrane spanning molecular scaffold tetraspanin TM4SF, and the actin cross-linking filamin Cheerio which are themselves required for invasion. Cortical F-actin levels are critical as expressing a dominant active form of Diaphanous, a actin polymerizing Formin, can rescue the Dfos Dominant Negative macrophage invasion defect. In vivo imaging shows that Dfos is required to enhance the efficiency of the initial phases of macrophage tissue entry. Genetic evidence argues that this Dfos-induced program in macrophages counteracts the constraint produced by the tension of surrounding tissues and buffers the mechanical properties of the macrophage nucleus from affecting tissue entry. We thus identify tuning the cortical actin cytoskeleton through Dfos as a key process allowing efficient forward movement of an immune cell into surrounding tissues. AU - Belyaeva, Vera AU - Wachner, Stephanie AU - Gridchyn, Igor AU - Linder, Markus AU - Emtenani, Shamsi AU - György, Attila AU - Sibilia, Maria AU - Siekhaus, Daria E ID - 8557 T2 - bioRxiv TI - Cortical actin properties controlled by Drosophila Fos aid macrophage infiltration against surrounding tissue resistance ER - TY - GEN AB - Holes in planar Ge have high mobilities, strong spin-orbit interaction and electrically tunable g-factors, and are therefore emerging as a promising candidate for hybrid superconductorsemiconductor devices. This is further motivated by the observation of supercurrent transport in planar Ge Josephson Field effect transistors (JoFETs). A key challenge towards hybrid germanium quantum technology is the design of high quality interfaces and superconducting contacts that are robust against magnetic fields. By combining the assets of Al, which has a long superconducting coherence, and Nb, which has a significant superconducting gap, we form low-disordered JoFETs with large ICRN products that are capable of withstanding high magnetic fields. We furthermore demonstrate the ability of phase-biasing individual JoFETs opening up an avenue to explore topological superconductivity in planar Ge. The persistence of superconductivity in the reported hybrid devices beyond 1.8 T paves the way towards integrating spin qubits and proximity-induced superconductivity on the same chip. AU - Aggarwal, Kushagra AU - Hofmann, Andrea C AU - Jirovec, Daniel AU - Prieto Gonzalez, Ivan AU - Sammak, Amir AU - Botifoll, Marc AU - Marti-Sanchez, Sara AU - Veldhorst, Menno AU - Arbiol, Jordi AU - Scappucci, Giordano AU - Katsaros, Georgios ID - 8831 T2 - arXiv TI - Enhancement of proximity induced superconductivity in planar Germanium ER - TY - JOUR AB - The molecular anatomy of synapses defines their characteristics in transmission and plasticity. Precise measurements of the number and distribution of synaptic proteins are important for our understanding of synapse heterogeneity within and between brain regions. Freeze–fracture replica immunogold electron microscopy enables us to analyze them quantitatively on a two-dimensional membrane surface. Here, we introduce Darea software, which utilizes deep learning for analysis of replica images and demonstrate its usefulness for quick measurements of the pre- and postsynaptic areas, density and distribution of gold particles at synapses in a reproducible manner. We used Darea for comparing glutamate receptor and calcium channel distributions between hippocampal CA3-CA1 spine synapses on apical and basal dendrites, which differ in signaling pathways involved in synaptic plasticity. We found that apical synapses express a higher density of α-amino-3-hydroxy-5-methyl-4-isoxazolepropionic acid (AMPA) receptors and a stronger increase of AMPA receptors with synaptic size, while basal synapses show a larger increase in N-methyl-D-aspartate (NMDA) receptors with size. Interestingly, AMPA and NMDA receptors are segregated within postsynaptic sites and negatively correlated in density among both apical and basal synapses. In the presynaptic sites, Cav2.1 voltage-gated calcium channels show similar densities in apical and basal synapses with distributions consistent with an exclusion zone model of calcium channel-release site topography. AU - Kleindienst, David AU - Montanaro-Punzengruber, Jacqueline-Claire AU - Bhandari, Pradeep AU - Case, Matthew J AU - Fukazawa, Yugo AU - Shigemoto, Ryuichi ID - 8532 IS - 18 JF - International Journal of Molecular Sciences SN - 16616596 TI - Deep learning-assisted high-throughput analysis of freeze-fracture replica images applied to glutamate receptors and calcium channels at hippocampal synapses VL - 21 ER - TY - CONF AB - Interprocedural data-flow analyses form an expressive and useful paradigm of numerous static analysis applications, such as live variables analysis, alias analysis and null pointers analysis. The most widely-used framework for interprocedural data-flow analysis is IFDS, which encompasses distributive data-flow functions over a finite domain. On-demand data-flow analyses restrict the focus of the analysis on specific program locations and data facts. This setting provides a natural split between (i) an offline (or preprocessing) phase, where the program is partially analyzed and analysis summaries are created, and (ii) an online (or query) phase, where analysis queries arrive on demand and the summaries are used to speed up answering queries. In this work, we consider on-demand IFDS analyses where the queries concern program locations of the same procedure (aka same-context queries). We exploit the fact that flow graphs of programs have low treewidth to develop faster algorithms that are space and time optimal for many common data-flow analyses, in both the preprocessing and the query phase. We also use treewidth to develop query solutions that are embarrassingly parallelizable, i.e. the total work for answering each query is split to a number of threads such that each thread performs only a constant amount of work. Finally, we implement a static analyzer based on our algorithms, and perform a series of on-demand analysis experiments on standard benchmarks. Our experimental results show a drastic speed-up of the queries after only a lightweight preprocessing phase, which significantly outperforms existing techniques. AU - Chatterjee, Krishnendu AU - Goharshady, Amir Kafshdar AU - Ibsen-Jensen, Rasmus AU - Pavlogiannis, Andreas ID - 7810 SN - 03029743 T2 - European Symposium on Programming TI - Optimal and perfectly parallel algorithms for on-demand data-flow analysis VL - 12075 ER - TY - CONF AB - Discrete-time Markov Chains (MCs) and Markov Decision Processes (MDPs) are two standard formalisms in system analysis. Their main associated quantitative objectives are hitting probabilities, discounted sum, and mean payoff. Although there are many techniques for computing these objectives in general MCs/MDPs, they have not been thoroughly studied in terms of parameterized algorithms, particularly when treewidth is used as the parameter. This is in sharp contrast to qualitative objectives for MCs, MDPs and graph games, for which treewidth-based algorithms yield significant complexity improvements. In this work, we show that treewidth can also be used to obtain faster algorithms for the quantitative problems. For an MC with n states and m transitions, we show that each of the classical quantitative objectives can be computed in O((n+m)⋅t2) time, given a tree decomposition of the MC with width t. Our results also imply a bound of O(κ⋅(n+m)⋅t2) for each objective on MDPs, where κ is the number of strategy-iteration refinements required for the given input and objective. Finally, we make an experimental evaluation of our new algorithms on low-treewidth MCs and MDPs obtained from the DaCapo benchmark suite. Our experiments show that on low-treewidth MCs and MDPs, our algorithms outperform existing well-established methods by one or more orders of magnitude. AU - Asadi, Ali AU - Chatterjee, Krishnendu AU - Goharshady, Amir Kafshdar AU - Mohammadi, Kiarash AU - Pavlogiannis, Andreas ID - 8728 SN - 0302-9743 T2 - Automated Technology for Verification and Analysis TI - Faster algorithms for quantitative analysis of MCs and MDPs with small treewidth VL - 12302 ER - TY - CONF AB - We consider the classical problem of invariant generation for programs with polynomial assignments and focus on synthesizing invariants that are a conjunction of strict polynomial inequalities. We present a sound and semi-complete method based on positivstellensaetze, i.e. theorems in semi-algebraic geometry that characterize positive polynomials over a semi-algebraic set. On the theoretical side, the worst-case complexity of our approach is subexponential, whereas the worst-case complexity of the previous complete method (Kapur, ACA 2004) is doubly-exponential. Even when restricted to linear invariants, the best previous complexity for complete invariant generation is exponential (Colon et al, CAV 2003). On the practical side, we reduce the invariant generation problem to quadratic programming (QCLP), which is a classical optimization problem with many industrial solvers. We demonstrate the applicability of our approach by providing experimental results on several academic benchmarks. To the best of our knowledge, the only previous invariant generation method that provides completeness guarantees for invariants consisting of polynomial inequalities is (Kapur, ACA 2004), which relies on quantifier elimination and cannot even handle toy programs such as our running example. AU - Chatterjee, Krishnendu AU - Fu, Hongfei AU - Goharshady, Amir Kafshdar AU - Goharshady, Ehsan Kafshdar ID - 8089 SN - 9781450376136 T2 - Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation TI - Polynomial invariant generation for non-deterministic recursive programs ER - TY - JOUR AB - We consider the classic problem of Network Reliability. A network is given together with a source vertex, one or more target vertices, and probabilities assigned to each of the edges. Each edge of the network is operable with its associated probability and the problem is to determine the probability of having at least one source-to-target path that is entirely composed of operable edges. This problem is known to be NP-hard. We provide a novel scalable algorithm to solve the Network Reliability problem when the treewidth of the underlying network is small. We also show our algorithm’s applicability for real-world transit networks that have small treewidth, including the metro networks of major cities, such as London and Tokyo. Our algorithm leverages tree decompositions to shrink the original graph into much smaller graphs, for which reliability can be efficiently and exactly computed using a brute force method. To the best of our knowledge, this is the first exact algorithm for Network Reliability that can scale to handle real-world instances of the problem. AU - Goharshady, Amir Kafshdar AU - Mohammadi, Fatemeh ID - 6918 JF - Reliability Engineering and System Safety SN - 09518320 TI - An efficient algorithm for computing network reliability in small treewidth VL - 193 ER - TY - JOUR AB - In this paper, we introduce an inertial projection-type method with different updating strategies for solving quasi-variational inequalities with strongly monotone and Lipschitz continuous operators in real Hilbert spaces. Under standard assumptions, we establish different strong convergence results for the proposed algorithm. Primary numerical experiments demonstrate the potential applicability of our scheme compared with some related methods in the literature. AU - Shehu, Yekini AU - Gibali, Aviv AU - Sagratella, Simone ID - 7161 JF - Journal of Optimization Theory and Applications SN - 0022-3239 TI - Inertial projection-type methods for solving quasi-variational inequalities in real Hilbert spaces VL - 184 ER - TY - JOUR AB - Organisms cope with change by taking advantage of transcriptional regulators. However, when faced with rare environments, the evolution of transcriptional regulators and their promoters may be too slow. Here, we investigate whether the intrinsic instability of gene duplication and amplification provides a generic alternative to canonical gene regulation. Using real-time monitoring of gene-copy-number mutations in Escherichia coli, we show that gene duplications and amplifications enable adaptation to fluctuating environments by rapidly generating copy-number and, therefore, expression-level polymorphisms. This amplification-mediated gene expression tuning (AMGET) occurs on timescales that are similar to canonical gene regulation and can respond to rapid environmental changes. Mathematical modelling shows that amplifications also tune gene expression in stochastic environments in which transcription-factor-based schemes are hard to evolve or maintain. The fleeting nature of gene amplifications gives rise to a generic population-level mechanism that relies on genetic heterogeneity to rapidly tune the expression of any gene, without leaving any genomic signature. AU - Tomanek, Isabella AU - Grah, Rok AU - Lagator, M. AU - Andersson, A. M. C. AU - Bollback, Jonathan P AU - Tkačik, Gašper AU - Guet, Calin C ID - 7652 IS - 4 JF - Nature Ecology & Evolution SN - 2397-334X TI - Gene amplification as a form of population-level gene expression regulation VL - 4 ER - TY - THES AB - Many flows encountered in nature and applications are characterized by a chaotic motion known as turbulence. Turbulent flows generate intense friction with pipe walls and are responsible for considerable amounts of energy losses at world scale. The nature of turbulent friction and techniques aimed at reducing it have been subject of extensive research over the last century, but no definite answer has been found yet. In this thesis we show that in pipes at moderate turbulent Reynolds numbers friction is better described by the power law first introduced by Blasius and not by the Prandtl–von Kármán formula. At higher Reynolds numbers, large scale motions gradually become more important in the flow and can be related to the change in scaling of friction. Next, we present a series of new techniques that can relaminarize turbulence by suppressing a key mechanism that regenerates it at walls, the lift–up effect. In addition, we investigate the process of turbulence decay in several experiments and discuss the drag reduction potential. Finally, we examine the behavior of friction under pulsating conditions inspired by the human heart cycle and we show that under such circumstances turbulent friction can be reduced to produce energy savings. AU - Scarselli, Davide ID - 7258 SN - 2663-337X TI - New approaches to reduce friction in turbulent pipe flow ER - TY - THES AB - Mutations are the raw material of evolution and come in many different flavors. Point mutations change a single letter in the DNA sequence, while copy number mutations like duplications or deletions add or remove many letters of the DNA sequence simultaneously. Each type of mutation exhibits specific properties like its rate of formation and reversal. Gene expression is a fundamental phenotype that can be altered by both, point and copy number mutations. The following thesis is concerned with the dynamics of gene expression evolution and how it is affected by the properties exhibited by point and copy number mutations. Specifically, we are considering i) copy number mutations during adaptation to fluctuating environments and ii) the interaction of copy number and point mutations during adaptation to constant environments.   AU - Tomanek, Isabella ID - 8653 KW - duplication KW - amplification KW - promoter KW - CNV KW - AMGET KW - experimental evolution KW - Escherichia coli SN - 2663-337X TI - The evolution of gene expression by copy number and point mutations ER - TY - JOUR AB - Plants, like other multicellular organisms, survive through a delicate balance between growth and defense against pathogens. Salicylic acid (SA) is a major defense signal in plants, and the perception mechanism as well as downstream signaling activating the immune response are known. Here, we identify a parallel SA signaling that mediates growth attenuation. SA directly binds to A subunits of protein phosphatase 2A (PP2A), inhibiting activity of this complex. Among PP2A targets, the PIN2 auxin transporter is hyperphosphorylated in response to SA, leading to changed activity of this important growth regulator. Accordingly, auxin transport and auxin-mediated root development, including growth, gravitropic response, and lateral root organogenesis, are inhibited. This study reveals how SA, besides activating immunity, concomitantly attenuates growth through crosstalk with the auxin distribution network. Further analysis of this dual role of SA and characterization of additional SA-regulated PP2A targets will provide further insights into mechanisms maintaining a balance between growth and defense. AU - Tan, Shutang AU - Abas, Melinda F AU - Verstraeten, Inge AU - Glanc, Matous AU - Molnar, Gergely AU - Hajny, Jakub AU - Lasák, Pavel AU - Petřík, Ivan AU - Russinova, Eugenia AU - Petrášek, Jan AU - Novák, Ondřej AU - Pospíšil, Jiří AU - Friml, Jiří ID - 7427 IS - 3 JF - Current Biology SN - 09609822 TI - Salicylic acid targets protein phosphatase 2A to attenuate growth in plants VL - 30 ER - TY - JOUR AB - Plant survival depends on vascular tissues, which originate in a self‐organizing manner as strands of cells co‐directionally transporting the plant hormone auxin. The latter phenomenon (also known as auxin canalization) is classically hypothesized to be regulated by auxin itself via the effect of this hormone on the polarity of its own intercellular transport. Correlative observations supported this concept, but molecular insights remain limited. In the current study, we established an experimental system based on the model Arabidopsis thaliana, which exhibits auxin transport channels and formation of vasculature strands in response to local auxin application. Our methodology permits the genetic analysis of auxin canalization under controllable experimental conditions. By utilizing this opportunity, we confirmed the dependence of auxin canalization on a PIN‐dependent auxin transport and nuclear, TIR1/AFB‐mediated auxin signaling. We also show that leaf venation and auxin‐mediated PIN repolarization in the root require TIR1/AFB signaling. Further studies based on this experimental system are likely to yield better understanding of the mechanisms underlying auxin transport polarization in other developmental contexts. AU - Mazur, E AU - Kulik, Ivan AU - Hajny, Jakub AU - Friml, Jiří ID - 7500 IS - 5 JF - New Phytologist SN - 0028-646x TI - Auxin canalization and vascular tissue formation by TIR1/AFB-mediated auxin signaling in arabidopsis VL - 226 ER - TY - THES AB - Self-organization is a hallmark of plant development manifested e.g. by intricate leaf vein patterns, flexible formation of vasculature during organogenesis or its regeneration following wounding. Spontaneously arising channels transporting the phytohormone auxin, created by coordinated polar localizations of PIN-FORMED 1 (PIN1) auxin exporter, provide positional cues for these as well as other plant patterning processes. To find regulators acting downstream of auxin and the TIR1/AFB auxin signaling pathway essential for PIN1 coordinated polarization during auxin canalization, we performed microarray experiments. Besides the known components of general PIN polarity maintenance, such as PID and PIP5K kinases, we identified and characterized a new regulator of auxin canalization, the transcription factor WRKY DNA-BINDING PROTEIN 23 (WRKY23). Next, we designed a subsequent microarray experiment to further uncover other molecular players, downstream of auxin-TIR1/AFB-WRKY23 involved in the regulation of auxin-mediated PIN repolarization. We identified a novel and crucial part of the molecular machinery underlying auxin canalization. The auxin-regulated malectin-type receptor-like kinase CAMEL and the associated leucine-rich repeat receptor-like kinase CANAR target and directly phosphorylate PIN auxin transporters. camel and canar mutants are impaired in PIN1 subcellular trafficking and auxin-mediated repolarization leading to defects in auxin transport, ultimately to leaf venation and vasculature regeneration defects. Our results describe the CAMEL-CANAR receptor complex, which is required for auxin feed-back on its own transport and thus for coordinated tissue polarization during auxin canalization. AU - Hajny, Jakub ID - 8822 SN - 2663-337X TI - Identification and characterization of the molecular machinery of auxin-dependent canalization during vasculature formation and regeneration ER - TY - THES AB - Cytoplasm is a gel-like crowded environment composed of tens of thousands of macromolecules, organelles, cytoskeletal networks and cytosol. The structure of the cytoplasm is thought to be highly organized and heterogeneous due to the crowding of its constituents and their effective compartmentalization. In such an environment, the diffusive dynamics of the molecules is very restricted, an effect that is further amplified by clustering and anchoring of molecules. Despite the jammed nature of the cytoplasm at the microscopic scale, large-scale reorganization of cytoplasm is essential for important cellular functions, such as nuclear positioning and cell division. How such mesoscale reorganization of the cytoplasm is achieved, especially for very large cells such as oocytes or syncytial tissues that can span hundreds of micrometers in size, has only begun to be understood. In this thesis, I focus on the recent advances in elucidating the molecular, cellular and biophysical principles underlying cytoplasmic organization across different scales, structures and species. First, I outline which of these principles have been identified by reductionist approaches, such as in vitro reconstitution assays, where boundary conditions and components can be modulated at ease. I then describe how the theoretical and experimental framework established in these reduced systems have been applied to their more complex in vivo counterparts, in particular oocytes and embryonic syncytial structures, and discuss how such complex biological systems can initiate symmetry breaking and establish patterning. Specifically, I examine an example of large-scale reorganizations taking place in zebrafish embryos, where extensive cytoplasmic streaming leads to the segregation of cytoplasm from yolk granules along the animal-vegetal axis of the embryo. Using biophysical experimentation and theory, I investigate the forces underlying this process, to show that this process does not rely on cortical actin reorganization, as previously thought, but instead on a cell-cycle-dependent bulk actin polymerization wave traveling from the animal to the vegetal pole of the embryo. This wave functions in segregation by both pulling cytoplasm animally and pushing yolk granules vegetally. Cytoplasm pulling is mediated by bulk actin network flows exerting friction forces on the cytoplasm, while yolk granule pushing is achieved by a mechanism closely resembling actin comet formation on yolk granules. This study defines a novel role of bulk actin polymerization waves in embryo polarization via cytoplasmic segregation. Lastly, I describe the cytoplasmic reorganizations taking place during zebrafish oocyte maturation, where the initial segregation of the cytoplasm and yolk granules occurs. Here, I demonstrate a previously uncharacterized wave of microtubule aster formation, traveling the oocyte along the animal-vegetal axis. Further research is required to determine the role of such microtubule structures in cytoplasmic reorganizations therein. Collectively, these studies provide further evidence for the coupling between cell cytoskeleton and cell cycle machinery, which can underlie a core self-organizing mechanism for orchestrating large-scale reorganizations in a cell-cycle-tunable manner, where the modulations of the force-generating machinery and cytoplasmic mechanics can be harbored to fulfill cellular functions. AU - Shamipour, Shayan ID - 8350 SN - 2663-337X TI - Bulk actin dynamics drive phase segregation in zebrafish oocytes ER - TY - JOUR AB - Concerted radial migration of newly born cortical projection neurons, from their birthplace to their final target lamina, is a key step in the assembly of the cerebral cortex. The cellular and molecular mechanisms regulating the specific sequential steps of radial neuronal migration in vivo are however still unclear, let alone the effects and interactions with the extracellular environment. In any in vivo context, cells will always be exposed to a complex extracellular environment consisting of (1) secreted factors acting as potential signaling cues, (2) the extracellular matrix, and (3) other cells providing cell–cell interaction through receptors and/or direct physical stimuli. Most studies so far have described and focused mainly on intrinsic cell-autonomous gene functions in neuronal migration but there is accumulating evidence that non-cell-autonomous-, local-, systemic-, and/or whole tissue-wide effects substantially contribute to the regulation of radial neuronal migration. These non-cell-autonomous effects may differentially affect cortical neuron migration in distinct cellular environments. However, the cellular and molecular natures of such non-cell-autonomous mechanisms are mostly unknown. Furthermore, physical forces due to collective migration and/or community effects (i.e., interactions with surrounding cells) may play important roles in neocortical projection neuron migration. In this concise review, we first outline distinct models of non-cell-autonomous interactions of cortical projection neurons along their radial migration trajectory during development. We then summarize experimental assays and platforms that can be utilized to visualize and potentially probe non-cell-autonomous mechanisms. Lastly, we define key questions to address in the future. AU - Hansen, Andi H AU - Hippenmeyer, Simon ID - 8569 IS - 9 JF - Frontiers in Cell and Developmental Biology SN - 2296-634X TI - Non-cell-autonomous mechanisms in radial projection neuron migration in the developing cerebral cortex VL - 8 ER - TY - JOUR AB - Beginning from a limited pool of progenitors, the mammalian cerebral cortex forms highly organized functional neural circuits. However, the underlying cellular and molecular mechanisms regulating lineage transitions of neural stem cells (NSCs) and eventual production of neurons and glia in the developing neuroepithelium remains unclear. Methods to trace NSC division patterns and map the lineage of clonally related cells have advanced dramatically. However, many contemporary lineage tracing techniques suffer from the lack of cellular resolution of progeny cell fate, which is essential for deciphering progenitor cell division patterns. Presented is a protocol using mosaic analysis with double markers (MADM) to perform in vivo clonal analysis. MADM concomitantly manipulates individual progenitor cells and visualizes precise division patterns and lineage progression at unprecedented single cell resolution. MADM-based interchromosomal recombination events during the G2-X phase of mitosis, together with temporally inducible CreERT2, provide exact information on the birth dates of clones and their division patterns. Thus, MADM lineage tracing provides unprecedented qualitative and quantitative optical readouts of the proliferation mode of stem cell progenitors at the single cell level. MADM also allows for examination of the mechanisms and functional requirements of candidate genes in NSC lineage progression. This method is unique in that comparative analysis of control and mutant subclones can be performed in the same tissue environment in vivo. Here, the protocol is described in detail, and experimental paradigms to employ MADM for clonal analysis and lineage tracing in the developing cerebral cortex are demonstrated. Importantly, this protocol can be adapted to perform MADM clonal analysis in any murine stem cell niche, as long as the CreERT2 driver is present. AU - Beattie, Robert J AU - Streicher, Carmen AU - Amberg, Nicole AU - Cheung, Giselle T AU - Contreras, Ximena AU - Hansen, Andi H AU - Hippenmeyer, Simon ID - 7815 IS - 159 JF - Journal of Visual Experiments SN - 1940-087X TI - Lineage tracing and clonal analysis in developing cerebral cortex using mosaic analysis with double markers (MADM) ER - TY - THES AB - Mosaic genetic analysis has been widely used in different model organisms such as the fruit fly to study gene-function in a cell-autonomous or tissue-specific fashion. More recently, and less easily conducted, mosaic genetic analysis in mice has also been enabled with the ambition to shed light on human gene function and disease. These genetic tools are of particular interest, but not restricted to, the study of the brain. Notably, the MADM technology offers a genetic approach in mice to visualize and concomitantly manipulate small subsets of genetically defined cells at a clonal level and single cell resolution. MADM-based analysis has already advanced the study of genetic mechanisms regulating brain development and is expected that further MADM-based analysis of genetic alterations will continue to reveal important insights on the fundamental principles of development and disease to potentially assist in the development of new therapies or treatments. In summary, this work completed and characterized the necessary genome-wide genetic tools to perform MADM-based analysis at single cell level of the vast majority of mouse genes in virtually any cell type and provided a protocol to perform lineage tracing using the novel MADM resource. Importantly, this work also explored and revealed novel aspects of biologically relevant events in an in vivo context, such as the chromosome-specific bias of chromatid sister segregation pattern, the generation of cell-type diversity in the cerebral cortex and in the cerebellum and finally, the relevance of the interplay between the cell-autonomous gene function and cell-non-autonomous (community) effects in radial glial progenitor lineage progression. This work provides a foundation and opens the door to further elucidating the molecular mechanisms underlying neuronal diversity and astrocyte generation. AU - Contreras, Ximena ID - 7902 SN - 2663-337X TI - Genetic dissection of neural development in health and disease at single cell resolution ER - TY - JOUR AU - Sixt, Michael K AU - Huttenlocher, Anna ID - 8190 IS - 8 JF - The Journal of Cell Biology TI - Zena Werb (1945-2020): Cell biology in context VL - 219 ER - TY - JOUR AB - Flowering plants display the highest diversity among plant species and have notably shaped terrestrial landscapes. Nonetheless, the evolutionary origin of their unprecedented morphological complexity remains largely an enigma. Here, we show that the coevolution of cis-regulatory and coding regions of PIN-FORMED (PIN) auxin transporters confined their expression to certain cell types and directed their subcellular localization to particular cell sides, which together enabled dynamic auxin gradients across tissues critical to the complex architecture of flowering plants. Extensive intraspecies and interspecies genetic complementation experiments with PINs from green alga up to flowering plant lineages showed that PIN genes underwent three subsequent, critical evolutionary innovations and thus acquired a triple function to regulate the development of three essential components of the flowering plant Arabidopsis: shoot/root, inflorescence, and floral organ. Our work highlights the critical role of functional innovations within the PIN gene family as essential prerequisites for the origin of flowering plants. AU - Zhang, Yuzhou AU - Rodriguez Solovey, Lesia AU - Li, Lanxin AU - Zhang, Xixi AU - Friml, Jiří ID - 8986 IS - 50 JF - Science Advances TI - Functional innovations of PIN auxin transporters mark crucial evolutionary transitions during rise of flowering plants VL - 6 ER - TY - JOUR AB - Drought and salt stress are the main environmental cues affecting the survival, development, distribution, and yield of crops worldwide. MYB transcription factors play a crucial role in plants’ biological processes, but the function of pineapple MYB genes is still obscure. In this study, one of the pineapple MYB transcription factors, AcoMYB4, was isolated and characterized. The results showed that AcoMYB4 is localized in the cell nucleus, and its expression is induced by low temperature, drought, salt stress, and hormonal stimulation, especially by abscisic acid (ABA). Overexpression of AcoMYB4 in rice and Arabidopsis enhanced plant sensitivity to osmotic stress; it led to an increase in the number stomata on leaf surfaces and lower germination rate under salt and drought stress. Furthermore, in AcoMYB4 OE lines, the membrane oxidation index, free proline, and soluble sugar contents were decreased. In contrast, electrolyte leakage and malondialdehyde (MDA) content increased significantly due to membrane injury, indicating higher sensitivity to drought and salinity stresses. Besides the above, both the expression level and activities of several antioxidant enzymes were decreased, indicating lower antioxidant activity in AcoMYB4 transgenic plants. Moreover, under osmotic stress, overexpression of AcoMYB4 inhibited ABA biosynthesis through a decrease in the transcription of genes responsible for ABA synthesis (ABA1 and ABA2) and ABA signal transduction factor ABI5. These results suggest that AcoMYB4 negatively regulates osmotic stress by attenuating cellular ABA biosynthesis and signal transduction pathways. AU - Chen, Huihuang AU - Lai, Linyi AU - Li, Lanxin AU - Liu, Liping AU - Jakada, Bello Hassan AU - Huang, Youmei AU - He, Qing AU - Chai, Mengnan AU - Niu, Xiaoping AU - Qin, Yuan ID - 8283 IS - 16 JF - International Journal of Molecular Sciences SN - 16616596 TI - AcoMYB4, an Ananas comosus L. MYB transcription factor, functions in osmotic stress through negative regulation of ABA signaling VL - 21 ER - TY - JOUR AB - Clathrin-mediated endocytosis (CME) is a crucial cellular process implicated in many aspects of plant growth, development, intra- and inter-cellular signaling, nutrient uptake and pathogen defense. Despite these significant roles, little is known about the precise molecular details of how it functions in planta. In order to facilitate the direct quantitative study of plant CME, here we review current routinely used methods and present refined, standardized quantitative imaging protocols which allow the detailed characterization of CME at multiple scales in plant tissues. These include: (i) an efficient electron microscopy protocol for the imaging of Arabidopsis CME vesicles in situ, thus providing a method for the detailed characterization of the ultra-structure of clathrin-coated vesicles; (ii) a detailed protocol and analysis for quantitative live-cell fluorescence microscopy to precisely examine the temporal interplay of endocytosis components during single CME events; (iii) a semi-automated analysis to allow the quantitative characterization of global internalization of cargos in whole plant tissues; and (iv) an overview and validation of useful genetic and pharmacological tools to interrogate the molecular mechanisms and function of CME in intact plant samples. AU - Johnson, Alexander J AU - Gnyliukh, Nataliia AU - Kaufmann, Walter AU - Narasimhan, Madhumitha AU - Vert, G AU - Bednarek, SY AU - Friml, Jiří ID - 8139 IS - 15 JF - Journal of Cell Science SN - 0021-9533 TI - Experimental toolbox for quantitative evaluation of clathrin-mediated endocytosis in the plant model Arabidopsis VL - 133 ER - TY - JOUR AB - Auxin is a key hormonal regulator, that governs plant growth and development in concert with other hormonal pathways. The unique feature of auxin is its polar, cell-to-cell transport that leads to the formation of local auxin maxima and gradients, which coordinate initiation and patterning of plant organs. The molecular machinery mediating polar auxin transport is one of the important points of interaction with other hormones. Multiple hormonal pathways converge at the regulation of auxin transport and form a regulatory network that integrates various developmental and environmental inputs to steer plant development. In this review, we discuss recent advances in understanding the mechanisms that underlie regulation of polar auxin transport by multiple hormonal pathways. Specifically, we focus on the post-translational mechanisms that contribute to fine-tuning of the abundance and polarity of auxin transporters at the plasma membrane and thereby enable rapid modification of the auxin flow to coordinate plant growth and development. AU - Semeradova, Hana AU - Montesinos López, Juan C AU - Benková, Eva ID - 9160 IS - 3 JF - Plant Communications SN - 2590-3462 TI - All roads lead to auxin: Post-translational regulation of auxin transport by multiple hormonal pathways VL - 1 ER - TY - CONF AB - This report presents the results of a friendly competition for formal verification of continuous and hybrid systems with piecewise constant dynamics. The friendly competition took place as part of the workshop Applied Verification for Continuous and Hybrid Systems (ARCH) in 2019. In this third edition, six tools have been applied to solve five different benchmark problems in the category for piecewise constant dynamics: BACH, Lyse, Hy- COMP, PHAVer/SX, PHAVerLite, and VeriSiMPL. Compared to last year, a new tool has participated (HyCOMP) and PHAVerLite has replaced PHAVer-lite. The result is a snap- shot of the current landscape of tools and the types of benchmarks they are particularly suited for. Due to the diversity of problems, we are not ranking tools, yet the presented results probably provide the most complete assessment of tools for the safety verification of continuous and hybrid systems with piecewise constant dynamics up to this date. AU - Frehse, Goran AU - Abate, Alessandro AU - Adzkiya, Dieky AU - Becchi, Anna AU - Bu, Lei AU - Cimatti, Alessandro AU - Giacobbe, Mirco AU - Griggio, Alberto AU - Mover, Sergio AU - Mufid, Muhammad Syifa'ul AU - Riouak, Idriss AU - Tonetta, Stefano AU - Zaffanella, Enea ED - Frehse, Goran ED - Althoff, Matthias ID - 10877 SN - 2398-7340 T2 - ARCH19. 6th International Workshop on Applied Verification of Continuous and Hybrid Systems TI - ARCH-COMP19 Category Report: Hybrid systems with piecewise constant dynamics VL - 61 ER - TY - JOUR AU - Kalinin, Nikita AU - Shkolnikov, Mikhail ID - 441 IS - 3 JF - European Journal of Mathematics SN - 2199-675X TI - Tropical formulae for summation over a part of SL(2,Z) VL - 5 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 - 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 give non-degeneracy criteria for Riemannian simplices based on simplices in spaces of constant sectional curvature. It extends previous work on Riemannian simplices, where we developed Riemannian simplices with respect to Euclidean reference simplices. The criteria we give in this article are in terms of quality measures for spaces of constant curvature that we develop here. We see that simplices in spaces that have nearly constant curvature, are already non-degenerate under very weak quality demands. This is of importance because it allows for sampling of Riemannian manifolds based on anisotropy of the manifold and not (absolute) curvature. AU - Dyer, Ramsay AU - Vegter, Gert AU - Wintraecken, Mathijs ID - 6515 IS - 1 JF - Journal of Computational Geometry SN - 1920-180X TI - Simplices modelled on spaces of constant curvature VL - 10 ER - TY - CONF AB - We construct a verifiable delay function (VDF) by showing how the Rivest-Shamir-Wagner time-lock puzzle can be made publicly verifiable. Concretely, we give a statistically sound public-coin protocol to prove that a tuple (N,x,T,y) satisfies y=x2T (mod N) where the prover doesn’t know the factorization of N and its running time is dominated by solving the puzzle, that is, compute x2T, which is conjectured to require T sequential squarings. To get a VDF we make this protocol non-interactive using the Fiat-Shamir heuristic.The motivation for this work comes from the Chia blockchain design, which uses a VDF as akey ingredient. For typical parameters (T≤2 40, N= 2048), our proofs are of size around 10K B, verification cost around three RSA exponentiations and computing the proof is 8000 times faster than solving the puzzle even without any parallelism. AU - Pietrzak, Krzysztof Z ID - 6528 SN - 1868-8969 T2 - 10th Innovations in Theoretical Computer Science Conference TI - Simple verifiable delay functions VL - 124 ER - TY - CONF AB - In this paper, we address the problem of synthesizing periodic switching controllers for stabilizing a family of linear systems. Our broad approach consists of constructing a finite game graph based on the family of linear systems such that every winning strategy on the game graph corresponds to a stabilizing switching controller for the family of linear systems. The construction of a (finite) game graph, the synthesis of a winning strategy and the extraction of a stabilizing controller are all computationally feasible. We illustrate our method on an example. AU - Kundu, Atreyee AU - Garcia Soto, Miriam AU - Prabhakar, Pavithra ID - 6565 SN - 978-153866246-5 T2 - 5th Indian Control Conference Proceedings TI - Formal synthesis of stabilizing controllers for periodically controlled linear switched systems ER - TY - CONF AB - Fejes Tóth [5] and Schneider [9] studied approximations of smooth convex hypersurfaces in Euclidean space by piecewise flat triangular meshes with a given number of vertices on the hypersurface that are optimal with respect to Hausdorff distance. They proved that this Hausdorff distance decreases inversely proportional with m 2/(d−1), where m is the number of vertices and d is the dimension of Euclidean space. Moreover the pro-portionality constant can be expressed in terms of the Gaussian curvature, an intrinsic quantity. In this short note, we prove the extrinsic nature of this constant for manifolds of sufficiently high codimension. We do so by constructing an family of isometric embeddings of the flat torus in Euclidean space. AU - Vegter, Gert AU - Wintraecken, Mathijs ID - 6628 T2 - The 31st Canadian Conference in Computational Geometry TI - The extrinsic nature of the Hausdorff distance of optimal triangulations of manifolds ER - TY - CONF AB - Various kinds of data are routinely represented as discrete probability distributions. Examples include text documents summarized by histograms of word occurrences and images represented as histograms of oriented gradients. Viewing a discrete probability distribution as a point in the standard simplex of the appropriate dimension, we can understand collections of such objects in geometric and topological terms. Importantly, instead of using the standard Euclidean distance, we look into dissimilarity measures with information-theoretic justification, and we develop the theory needed for applying topological data analysis in this setting. In doing so, we emphasize constructions that enable the usage of existing computational topology software in this context. AU - Edelsbrunner, Herbert AU - Virk, Ziga AU - Wagner, Hubert ID - 6648 SN - 9783959771047 T2 - 35th International Symposium on Computational Geometry TI - Topological data analysis in information space VL - 129 ER - TY - JOUR AB - Chemical labeling of proteins with synthetic molecular probes offers the possibility to probe the functions of proteins of interest in living cells. However, the methods for covalently labeling targeted proteins using complementary peptide tag-probe pairs are still limited, irrespective of the versatility of such pairs in biological research. Herein, we report the new CysHis tag-Ni(II) probe pair for the specific covalent labeling of proteins. A broad-range evaluation of the reactivity profiles of the probe and the CysHis peptide tag afforded a tag-probe pair with an optimized and high labeling selectivity and reactivity. In particular, the labeling specificity of this pair was notably improved compared to the previously reported one. This pair was successfully utilized for the fluorescence imaging of membrane proteins on the surfaces of living cells, demonstrating its potential utility in biological research. AU - Zenmyo, Naoki AU - Tokumaru, Hiroki AU - Uchinomiya, Shohei AU - Fuchida, Hirokazu AU - Tabata, Shigekazu AU - Hamachi, Itaru AU - Shigemoto, Ryuichi AU - Ojida, Akio ID - 6659 IS - 5 JF - Bulletin of the Chemical Society of Japan SN - 00092673 TI - Optimized reaction pair of the CysHis tag and Ni(II)-NTA probe for highly selective chemical labeling of membrane proteins VL - 92 ER - TY - CONF AB - A Valued Constraint Satisfaction Problem (VCSP) provides a common framework that can express a wide range of discrete optimization problems. A VCSP instance is given by a finite set of variables, a finite domain of labels, and an objective function to be minimized. This function is represented as a sum of terms where each term depends on a subset of the variables. To obtain different classes of optimization problems, one can restrict all terms to come from a fixed set Γ of cost functions, called a language. Recent breakthrough results have established a complete complexity classification of such classes with respect to language Γ: if all cost functions in Γ satisfy a certain algebraic condition then all Γ-instances can be solved in polynomial time, otherwise the problem is NP-hard. Unfortunately, testing this condition for a given language Γ is known to be NP-hard. We thus study exponential algorithms for this meta-problem. We show that the tractability condition of a finite-valued language Γ can be tested in O(3‾√3|D|⋅poly(size(Γ))) time, where D is the domain of Γ and poly(⋅) is some fixed polynomial. We also obtain a matching lower bound under the Strong Exponential Time Hypothesis (SETH). More precisely, we prove that for any constant δ<1 there is no O(3‾√3δ|D|) algorithm, assuming that SETH holds. AU - Kolmogorov, Vladimir ID - 6725 SN - 1868-8969 T2 - 46th International Colloquium on Automata, Languages and Programming TI - Testing the complexity of a valued CSP language VL - 132 ER - TY - CHAP AB - Randomness is an essential part of any secure cryptosystem, but many constructions rely on distributions that are not uniform. This is particularly true for lattice based cryptosystems, which more often than not make use of discrete Gaussian distributions over the integers. For practical purposes it is crucial to evaluate the impact that approximation errors have on the security of a scheme to provide the best possible trade-off between security and performance. Recent years have seen surprising results allowing to use relatively low precision while maintaining high levels of security. A key insight in these results is that sampling a distribution with low relative error can provide very strong security guarantees. Since floating point numbers provide guarantees on the relative approximation error, they seem a suitable tool in this setting, but it is not obvious which sampling algorithms can actually profit from them. While previous works have shown that inversion sampling can be adapted to provide a low relative error (Pöppelmann et al., CHES 2014; Prest, ASIACRYPT 2017), other works have called into question if this is possible for other sampling techniques (Zheng et al., Eprint report 2018/309). In this work, we consider all sampling algorithms that are popular in the cryptographic setting and analyze the relationship of floating point precision and the resulting relative error. We show that all of the algorithms either natively achieve a low relative error or can be adapted to do so. AU - Walter, Michael ED - Buchmann, J ED - Nitaj, A ED - Rachidi, T ID - 6726 SN - 0302-9743 T2 - Progress in Cryptology – AFRICACRYPT 2019 TI - Sampling the integers with low relative error VL - 11627 ER - TY - JOUR AB - Polar codes have gained extensive attention during the past few years and recently they have been selected for the next generation of wireless communications standards (5G). Successive-cancellation-based (SC-based) decoders, such as SC list (SCL) and SC flip (SCF), provide a reasonable error performance for polar codes at the cost of low decoding speed. Fast SC-based decoders, such as Fast-SSC, Fast-SSCL, and Fast-SSCF, identify the special constituent codes in a polar code graph off-line, produce a list of operations, store the list in memory, and feed the list to the decoder to decode the constituent codes in order efficiently, thus increasing the decoding speed. However, the list of operations is dependent on the code rate and as the rate changes, a new list is produced, making fast SC-based decoders not rate-flexible. In this paper, we propose a completely rate-flexible fast SC-based decoder by creating the list of operations directly in hardware, with low implementation complexity. We further propose a hardware architecture implementing the proposed method and show that the area occupation of the rate-flexible fast SC-based decoder in this paper is only 38% of the total area of the memory-based base-line decoder when 5G code rates are supported. AU - Hashemi, Seyyed Ali AU - Condo, Carlo AU - Mondelli, Marco AU - Gross, Warren J ID - 6750 IS - 22 JF - IEEE Transactions on Signal Processing SN - 1053587X TI - Rate-flexible fast polar decoders VL - 67 ER - TY - JOUR AB - We consider the graph class Grounded-L corresponding to graphs that admit an intersection representation by L-shaped curves, where additionally the topmost points of each curve are assumed to belong to a common horizontal line. We prove that Grounded-L graphs admit an equivalent characterisation in terms of vertex ordering with forbidden patterns. We also compare this class to related intersection classes, such as the grounded segment graphs, the monotone L-graphs (a.k.a. max point-tolerance graphs), or the outer-1-string graphs. We give constructions showing that these classes are all distinct and satisfy only trivial or previously known inclusions. AU - Jelínek, Vít AU - Töpfer, Martin ID - 6759 IS - 3 JF - Electronic Journal of Combinatorics TI - On grounded L-graphs and their relatives VL - 26 ER - TY - CONF AB - In two-player games on graphs, the players move a token through a graph to produce an infinite path, which determines the qualitative winner or quantitative payoff of the game. In bidding games, in each turn, we hold an auction between the two players to determine which player moves the token. Bidding games have largely been studied with concrete bidding mechanisms that are variants of a first-price auction: in each turn both players simultaneously submit bids, the higher bidder moves the token, and pays his bid to the lower bidder in Richman bidding, to the bank in poorman bidding, and in taxman bidding, the bid is split between the other player and the bank according to a predefined constant factor. Bidding games are deterministic games. They have an intriguing connection with a fragment of stochastic games called randomturn games. We study, for the first time, a combination of bidding games with probabilistic behavior; namely, we study bidding games that are played on Markov decision processes, where the players bid for the right to choose the next action, which determines the probability distribution according to which the next vertex is chosen. We study parity and meanpayoff bidding games on MDPs and extend results from the deterministic bidding setting to the probabilistic one. AU - Avni, Guy AU - Henzinger, Thomas A AU - Ibsen-Jensen, Rasmus AU - Novotny, Petr ID - 6822 SN - 0302-9743 T2 - Proceedings of the 13th International Conference of Reachability Problems TI - Bidding games on Markov decision processes VL - 11674 ER - TY - CONF AB - The fundamental model-checking problem, given as input a model and a specification, asks for the algorithmic verification of whether the model satisfies the specification. Two classical models for reactive systems are graphs and Markov decision processes (MDPs). A basic specification formalism in the verification of reactive systems is the strong fairness (aka Streett) objective, where given different types of requests and corresponding grants, the requirement is that for each type, if the request event happens infinitely often, then the corresponding grant event must also happen infinitely often. All omega-regular objectives can be expressed as Streett objectives and hence they are canonical in verification. Consider graphs/MDPs with n vertices, m edges, and a Streett objectives with k pairs, and let b denote the size of the description of the Streett objective for the sets of requests and grants. The current best-known algorithm for the problem requires time O(min(n^2, m sqrt{m log n}) + b log n). In this work we present randomized near-linear time algorithms, with expected running time O~(m + b), where the O~ notation hides poly-log factors. Our randomized algorithms are near-linear in the size of the input, and hence optimal up to poly-log factors. AU - Chatterjee, Krishnendu AU - Dvorák, Wolfgang AU - Henzinger, Monika H AU - Svozil, Alexander ID - 6887 T2 - Leibniz International Proceedings in Informatics TI - Near-linear time algorithms for Streett objectives in graphs and MDPs VL - 140 ER - TY - CONF AB - In this paper, we design novel liquid time-constant recurrent neural networks for robotic control, inspired by the brain of the nematode, C. elegans. In the worm's nervous system, neurons communicate through nonlinear time-varying synaptic links established amongst them by their particular wiring structure. This property enables neurons to express liquid time-constants dynamics and therefore allows the network to originate complex behaviors with a small number of neurons. We identify neuron-pair communication motifs as design operators and use them to configure compact neuronal network structures to govern sequential robotic tasks. The networks are systematically designed to map the environmental observations to motor actions, by their hierarchical topology from sensory neurons, through recurrently-wired interneurons, to motor neurons. The networks are then parametrized in a supervised-learning scheme by a search-based algorithm. We demonstrate that obtained networks realize interpretable dynamics. We evaluate their performance in controlling mobile and arm robots, and compare their attributes to other artificial neural network-based control agents. Finally, we experimentally show their superior resilience to environmental noise, compared to the existing machine learning-based methods. AU - Lechner, Mathias AU - Hasani, Ramin AU - Zimmer, Manuel AU - Henzinger, Thomas A AU - Grosu, Radu ID - 6888 SN - 9781538660270 T2 - Proceedings - IEEE International Conference on Robotics and Automation TI - Designing worm-inspired neural networks for interpretable robotic control VL - 2019-May ER - TY - CONF AB - In two-player games on graphs, the players move a token through a graph to produce an infinite path, which determines the winner of the game. Such games are central in formal methods since they model the interaction between a non-terminating system and its environment. In bidding games the players bid for the right to move the token: in each round, the players simultaneously submit bids, and the higher bidder moves the token and pays the other player. Bidding games are known to have a clean and elegant mathematical structure that relies on the ability of the players to submit arbitrarily small bids. Many applications, however, require a fixed granularity for the bids, which can represent, for example, the monetary value expressed in cents. We study, for the first time, the combination of discrete-bidding and infinite-duration games. Our most important result proves that these games form a large determined subclass of concurrent games, where determinacy is the strong property that there always exists exactly one player who can guarantee winning the game. In particular, we show that, in contrast to non-discrete bidding games, the mechanism with which tied bids are resolved plays an important role in discrete-bidding games. We study several natural tie-breaking mechanisms and show that, while some do not admit determinacy, most natural mechanisms imply determinacy for every pair of initial budgets. AU - Aghajohari, Milad AU - Avni, Guy AU - Henzinger, Thomas A ID - 6886 TI - Determinacy in discrete-bidding infinite-duration games VL - 140 ER - TY - CONF AB - A vector addition system with states (VASS) consists of a finite set of states and counters. A configuration is a state and a value for each counter; a transition changes the state and each counter is incremented, decremented, or left unchanged. While qualitative properties such as state and configuration reachability have been studied for VASS, we consider the long-run average cost of infinite computations of VASS. The cost of a configuration is for each state, a linear combination of the counter values. In the special case of uniform cost functions, the linear combination is the same for all states. The (regular) long-run emptiness problem is, given a VASS, a cost function, and a threshold value, if there is a (lasso-shaped) computation such that the long-run average value of the cost function does not exceed the threshold. For uniform cost functions, we show that the regular long-run emptiness problem is (a) decidable in polynomial time for integer-valued VASS, and (b) decidable but nonelementarily hard for natural-valued VASS (i.e., nonnegative counters). For general cost functions, we show that the problem is (c) NP-complete for integer-valued VASS, and (d) undecidable for natural-valued VASS. Our most interesting result is for (c) integer-valued VASS with general cost functions, where we establish a connection between the regular long-run emptiness problem and quadratic Diophantine inequalities. The general (nonregular) long-run emptiness problem is equally hard as the regular problem in all cases except (c), where it remains open. AU - Chatterjee, Krishnendu AU - Henzinger, Thomas A AU - Otop, Jan ID - 6885 TI - Long-run average behavior of vector addition systems with states VL - 140 ER - TY - CONF AB - We study Markov decision processes and turn-based stochastic games with parity conditions. There are three qualitative winning criteria, namely, sure winning, which requires all paths to satisfy the condition, almost-sure winning, which requires the condition to be satisfied with probability 1, and limit-sure winning, which requires the condition to be satisfied with probability arbitrarily close to 1. We study the combination of two of these criteria for parity conditions, e.g., there are two parity conditions one of which must be won surely, and the other almost-surely. The problem has been studied recently by Berthon et al. for MDPs with combination of sure and almost-sure winning, under infinite-memory strategies, and the problem has been established to be in NP cap co-NP. Even in MDPs there is a difference between finite-memory and infinite-memory strategies. Our main results for combination of sure and almost-sure winning are as follows: (a) we show that for MDPs with finite-memory strategies the problem is in NP cap co-NP; (b) we show that for turn-based stochastic games the problem is co-NP-complete, both for finite-memory and infinite-memory strategies; and (c) we present algorithmic results for the finite-memory case, both for MDPs and turn-based stochastic games, by reduction to non-stochastic parity games. In addition we show that all the above complexity results also carry over to combination of sure and limit-sure winning, and results for all other combinations can be derived from existing results in the literature. Thus we present a complete picture for the study of combinations of two qualitative winning criteria for parity conditions in MDPs and turn-based stochastic games. AU - Chatterjee, Krishnendu AU - Piterman, Nir ID - 6889 TI - Combinations of Qualitative Winning for Stochastic Parity Games VL - 140 ER - TY - CONF AB - Consider a distributed system with n processors out of which f can be Byzantine faulty. In the approximate agreement task, each processor i receives an input value xi and has to decide on an output value yi such that 1. the output values are in the convex hull of the non-faulty processors’ input values, 2. the output values are within distance d of each other. Classically, the values are assumed to be from an m-dimensional Euclidean space, where m ≥ 1. In this work, we study the task in a discrete setting, where input values with some structure expressible as a graph. Namely, the input values are vertices of a finite graph G and the goal is to output vertices that are within distance d of each other in G, but still remain in the graph-induced convex hull of the input values. For d = 0, the task reduces to consensus and cannot be solved with a deterministic algorithm in an asynchronous system even with a single crash fault. For any d ≥ 1, we show that the task is solvable in asynchronous systems when G is chordal and n > (ω + 1)f, where ω is the clique number of G. In addition, we give the first Byzantine-tolerant algorithm for a variant of lattice agreement. For synchronous systems, we show tight resilience bounds for the exact variants of these and related tasks over a large class of combinatorial structures. AU - Nowak, Thomas AU - Rybicki, Joel ID - 6931 KW - consensus KW - approximate agreement KW - Byzantine faults KW - chordal graphs KW - lattice agreement T2 - 33rd International Symposium on Distributed Computing TI - Byzantine approximate agreement on graphs VL - 146 ER - TY - CONF AB - In this paper, we introduce a novel method to interpret recurrent neural networks (RNNs), particularly long short-term memory networks (LSTMs) at the cellular level. We propose a systematic pipeline for interpreting individual hidden state dynamics within the network using response characterization methods. The ranked contribution of individual cells to the network's output is computed by analyzing a set of interpretable metrics of their decoupled step and sinusoidal responses. As a result, our method is able to uniquely identify neurons with insightful dynamics, quantify relationships between dynamical properties and test accuracy through ablation analysis, and interpret the impact of network capacity on a network's dynamical distribution. Finally, we demonstrate the generalizability and scalability of our method by evaluating a series of different benchmark sequential datasets. AU - Hasani, Ramin AU - Amini, Alexander AU - Lechner, Mathias AU - Naser, Felix AU - Grosu, Radu AU - Rus, Daniela ID - 6985 SN - 9781728119854 T2 - Proceedings of the International Joint Conference on Neural Networks TI - Response characterization for auditing cell dynamics in long short-term memory networks ER - TY - JOUR AB - We consider the primitive relay channel, where the source sends a message to the relay and to the destination, and the relay helps the communication by transmitting an additional message to the destination via a separate channel. Two well-known coding techniques have been introduced for this setting: decode-and-forward and compress-and-forward. In decode-and-forward, the relay completely decodes the message and sends some information to the destination; in compress-and-forward, the relay does not decode, and it sends a compressed version of the received signal to the destination using Wyner–Ziv coding. In this paper, we present a novel coding paradigm that provides an improved achievable rate for the primitive relay channel. The idea is to combine compress-and-forward and decode-and-forward via a chaining construction. We transmit over pairs of blocks: in the first block, we use compress-and-forward; and, in the second block, we use decode-and-forward. More specifically, in the first block, the relay does not decode, it compresses the received signal via Wyner–Ziv, and it sends only part of the compression to the destination. In the second block, the relay completely decodes the message, it sends some information to the destination, and it also sends the remaining part of the compression coming from the first block. By doing so, we are able to strictly outperform both compress-and-forward and decode-and-forward. Note that the proposed coding scheme can be implemented with polar codes. As such, it has the typical attractive properties of polar coding schemes, namely, quasi-linear encoding and decoding complexity, and error probability that decays at super-polynomial speed. As a running example, we take into account the special case of the erasure relay channel, and we provide a comparison between the rates achievable by our proposed scheme and the existing upper and lower bounds. AU - Mondelli, Marco AU - Hassani, S. Hamed AU - Urbanke, Rüdiger ID - 7007 IS - 10 JF - Algorithms SN - 1999-4893 TI - A new coding paradigm for the primitive relay channel VL - 12 ER - TY - CONF AB - The aim of this short note is to expound one particular issue that was discussed during the talk [10] given at the symposium ”Researches on isometries as preserver problems and related topics” at Kyoto RIMS. That is, the role of Dirac masses by describing the isometry group of various metric spaces of probability measures. This article is of survey character, and it does not contain any essentially new results.From an isometric point of view, in some cases, metric spaces of measures are similar to C(K)-type function spaces. Similarity means here that their isometries are driven by some nice transformations of the underlying space. Of course, it depends on the particular choice of the metric how nice these transformations should be. Sometimes, as we will see, being a homeomorphism is enough to generate an isometry. But sometimes we need more: the transformation must preserve the underlying distance as well. Statements claiming that isometries in questions are necessarily induced by homeomorphisms are called Banach-Stone-type results, while results asserting that the underlying transformation is necessarily an isometry are termed as isometric rigidity results.As Dirac masses can be considered as building bricks of the set of all Borel measures, a natural question arises:Is it enough to understand how an isometry acts on the set of Dirac masses? Does this action extend uniquely to all measures?In what follows, we will thoroughly investigate this question. AU - Geher, Gyorgy Pal AU - Titkos, Tamas AU - Virosztek, Daniel ID - 7035 T2 - Kyoto RIMS Kôkyûroku TI - Dirac masses and isometric rigidity VL - 2125 ER - TY - BOOK AB - Wissen Sie, was sich hinter künstlicher Intelligenz und maschinellem Lernen verbirgt? Dieses Sachbuch erklärt Ihnen leicht verständlich und ohne komplizierte Formeln die grundlegenden Methoden und Vorgehensweisen des maschinellen Lernens. Mathematisches Vorwissen ist dafür nicht nötig. Kurzweilig und informativ illustriert Lisa, die Protagonistin des Buches, diese anhand von Alltagssituationen. Ein Buch für alle, die in Diskussionen über Chancen und Risiken der aktuellen Entwicklung der künstlichen Intelligenz und des maschinellen Lernens mit Faktenwissen punkten möchten. Auch für Schülerinnen und Schüler geeignet! ED - Kersting, Kristian ED - Lampert, Christoph ED - Rothkopf, Constantin ID - 7171 SN - 978-3-658-26762-9 TI - Wie Maschinen Lernen: Künstliche Intelligenz Verständlich Erklärt ER - TY - CONF AB - The genus g(G) of a graph G is the minimum g such that G has an embedding on the orientable surface M_g of genus g. A drawing of a graph on a surface is independently even if every pair of nonadjacent edges in the drawing crosses an even number of times. The Z_2-genus of a graph G, denoted by g_0(G), is the minimum g such that G has an independently even drawing on M_g. By a result of Battle, Harary, Kodama and Youngs from 1962, the graph genus is additive over 2-connected blocks. In 2013, Schaefer and Stefankovic proved that the Z_2-genus of a graph is additive over 2-connected blocks as well, and asked whether this result can be extended to so-called 2-amalgamations, as an analogue of results by Decker, Glover, Huneke, and Stahl for the genus. We give the following partial answer. If G=G_1 cup G_2, G_1 and G_2 intersect in two vertices u and v, and G-u-v has k connected components (among which we count the edge uv if present), then |g_0(G)-(g_0(G_1)+g_0(G_2))|<=k+1. For complete bipartite graphs K_{m,n}, with n >= m >= 3, we prove that g_0(K_{m,n})/g(K_{m,n})=1-O(1/n). Similar results are proved also for the Euler Z_2-genus. We express the Z_2-genus of a graph using the minimum rank of partial symmetric matrices over Z_2; a problem that might be of independent interest. AU - Fulek, Radoslav AU - Kyncl, Jan ID - 7401 SN - 1868-8969 T2 - 35th International Symposium on Computational Geometry (SoCG 2019) TI - Z_2-Genus of graphs and minimum rank of partial symmetric matrices VL - 129 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 - 1611-3349 T2 - Computing and Software Science TI - Continuous-time models for system design and analysis VL - 10000 ER - TY - JOUR 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, Ulisse ID - 7550 IS - 2 JF - Advances in Mathematical Sciences and Applications SN - 1343-4373 TI - Penalization via global functionals of optimal-control problems for dissipative evolution VL - 28 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 study edge asymptotics of poissonized Plancherel-type measures on skew Young diagrams (integer partitions). These measures can be seen as generalizations of those studied by Baik--Deift--Johansson and Baik--Rains in resolving Ulam's problem on longest increasing subsequences of random permutations and the last passage percolation (corner growth) discrete versions thereof. Moreover they interpolate between said measures and the uniform measure on partitions. In the new KPZ-like 1/3 exponent edge scaling limit with logarithmic corrections, we find new probability distributions generalizing the classical Tracy--Widom GUE, GOE and GSE distributions from the theory of random matrices. AU - Betea, Dan AU - Bouttier, Jérémie AU - Nejjar, Peter AU - Vuletíc, Mirjana ID - 8175 T2 - Proceedings on the 31st International Conference on Formal Power Series and Algebraic Combinatorics TI - New edge asymptotics of skew Young diagrams via free boundaries ER - TY - CONF AB - This report presents the results of a friendly competition for formal verification of continuous and hybrid systems with linear continuous dynamics. The friendly competition took place as part of the workshop Applied Verification for Continuous and Hybrid Systems (ARCH) in 2019. In its third edition, seven tools have been applied to solve six different benchmark problems in the category for linear continuous dynamics (in alphabetical order): CORA, CORA/SX, HyDRA, Hylaa, JuliaReach, SpaceEx, and XSpeed. This report is a snapshot of the current landscape of tools and the types of benchmarks they are particularly suited for. Due to the diversity of problems, we are not ranking tools, yet the presented results provide one of the most complete assessments of tools for the safety verification of continuous and hybrid systems with linear continuous dynamics up to this date. AU - Althoff, Matthias AU - Bak, Stanley AU - Forets, Marcelo AU - Frehse, Goran AU - Kochdumper, Niklas AU - Ray, Rajarshi AU - Schilling, Christian AU - Schupp, Stefan ID - 8570 T2 - EPiC Series in Computing TI - ARCH-COMP19 Category Report: Continuous and hybrid systems with linear continuous dynamics VL - 61 ER - TY - JOUR AB - Epigenetic reprogramming is required for proper regulation of gene expression in eukaryotic organisms. In Arabidopsis, active DNA demethylation is crucial for seed viability, pollen function, and successful reproduction. The DEMETER (DME) DNA glycosylase initiates localized DNA demethylation in vegetative and central cells, so-called companion cells that are adjacent to sperm and egg gametes, respectively. In rice, the central cell genome displays local DNA hypomethylation, suggesting that active DNA demethylation also occurs in rice; however, the enzyme responsible for this process is unknown. One candidate is the rice REPRESSOR OF SILENCING 1a (ROS1a) gene, which is related to DME and is essential for rice seed viability and pollen function. Here, we report genome-wide analyses of DNA methylation in wild-type and ros1a mutant sperm and vegetative cells. We find that the rice vegetative cell genome is locally hypomethylated compared with sperm by a process that requires ROS1a activity. We show that many ROS1a target sequences in the vegetative cell are hypomethylated in the rice central cell, suggesting that ROS1a also demethylates the central cell genome. Similar to Arabidopsis, we show that sperm non-CG methylation is indirectly promoted by DNA demethylation in the vegetative cell. These results reveal that DNA glycosylase-mediated DNA demethylation processes are conserved in Arabidopsis and rice, plant species that diverged 150 million years ago. Finally, although global non-CG methylation levels of sperm and egg differ, the maternal and paternal embryo genomes show similar non-CG methylation levels, suggesting that rice gamete genomes undergo dynamic DNA methylation reprogramming after cell fusion. AU - Kim, M. Yvonne AU - Ono, Akemi AU - Scholten, Stefan AU - Kinoshita, Tetsu AU - Zilberman, Daniel AU - Okamoto, Takashi AU - Fischer, Robert L. ID - 9460 IS - 19 JF - Proceedings of the National Academy of Sciences KW - Multidisciplinary SN - 0027-8424 TI - DNA demethylation by ROS1a in rice vegetative cells promotes methylation in sperm VL - 116 ER - TY - JOUR AB - Glyphosate (N-phosphonomethyl glycine) and its commercial herbicide formulations have been shown to exert toxicity via various mechanisms. It has been asserted that glyphosate substitutes for glycine in polypeptide chains leading to protein misfolding and toxicity. However, as no direct evidence exists for glycine to glyphosate substitution in proteins, including in mammalian organisms, we tested this claim by conducting a proteomics analysis of MDA-MB-231 human breast cancer cells grown in the presence of 100 mg/L glyphosate for 6 days. Protein extracts from three treated and three untreated cell cultures were analysed as one TMT-6plex labelled sample, to highlight a specific pattern (+/+/+/−/−/−) of reporter intensities for peptides bearing true glyphosate treatment induced-post translational modifications as well as allowing an investigation of the total proteome. AU - Antoniou, Michael N. AU - Nicolas, Armel AU - Mesnage, Robin AU - Biserni, Martina AU - Rao, Francesco V. AU - Martin, Cristina Vazquez ID - 6819 JF - BMC Research Notes TI - Glyphosate does not substitute for glycine in proteins of actively dividing mammalian cells VL - 12 ER - TY - GEN AB - Additional file 1: Table S1. Kinetics of MDA-MB-231 cell growth in either the presence or absence of 100Â mg/L glyphosate. Cell counts are given at day-1 of seeding flasks and following 6-days of continuous culture. Note: no differences in cell numbers were observed between negative control and glyphosate treated cultures. AU - Antoniou, Michael N. AU - Nicolas, Armel AU - Mesnage, Robin AU - Biserni, Martina AU - Rao, Francesco V. AU - Martin, Cristina Vazquez ID - 9784 TI - MOESM1 of Glyphosate does not substitute for glycine in proteins of actively dividing mammalian cells ER - TY - GEN AB - More than 100 years after Grigg’s influential analysis of species’ borders, the causes of limits to species’ ranges still represent a puzzle that has never been understood with clarity. The topic has become especially important recently as many scientists have become interested in the potential for species’ ranges to shift in response to climate change—and yet nearly all of those studies fail to recognise or incorporate evolutionary genetics in a way that relates to theoretical developments. I show that range margins can be understood based on just two measurable parameters: (i) the fitness cost of dispersal—a measure of environmental heterogeneity—and (ii) the strength of genetic drift, which reduces genetic diversity. Together, these two parameters define an ‘expansion threshold’: adaptation fails when genetic drift reduces genetic diversity below that required for adaptation to a heterogeneous environment. When the key parameters drop below this expansion threshold locally, a sharp range margin forms. When they drop below this threshold throughout the species’ range, adaptation collapses everywhere, resulting in either extinction or formation of a fragmented metapopulation. Because the effects of dispersal differ fundamentally with dimension, the second parameter—the strength of genetic drift—is qualitatively different compared to a linear habitat. In two-dimensional habitats, genetic drift becomes effectively independent of selection. It decreases with ‘neighbourhood size’—the number of individuals accessible by dispersal within one generation. Moreover, in contrast to earlier predictions, which neglected evolution of genetic variance and/or stochasticity in two dimensions, dispersal into small marginal populations aids adaptation. This is because the reduction of both genetic and demographic stochasticity has a stronger effect than the cost of dispersal through increased maladaptation. The expansion threshold thus provides a novel, theoretically justified, and testable prediction for formation of the range margin and collapse of the species’ range. AU - Polechova, Jitka ID - 9839 TI - Data from: Is the sky the limit? On the expansion threshold of a species' range ER - TY - JOUR AB - Background DNA methylation of active genes, also known as gene body methylation, is found in many animal and plant genomes. Despite this, the transcriptional and developmental role of such methylation remains poorly understood. Here, we explore the dynamic range of DNA methylation in honey bee, a model organism for gene body methylation. Results Our data show that CG methylation in gene bodies globally fluctuates during honey bee development. However, these changes cause no gene expression alterations. Intriguingly, despite the global alterations, tissue-specific CG methylation patterns of complete genes or exons are rare, implying robust maintenance of genic methylation during development. Additionally, we show that CG methylation maintenance fluctuates in somatic cells, while reaching maximum fidelity in sperm cells. Finally, unlike universally present CG methylation, we discovered non-CG methylation specifically in bee heads that resembles such methylation in mammalian brain tissue. Conclusions Based on these results, we propose that gene body CG methylation can oscillate during development if it is kept to a level adequate to preserve function. Additionally, our data suggest that heightened non-CG methylation is a conserved regulator of animal nervous systems. AU - Harris, Keith D. AU - Lloyd, James P. B. AU - Domb, Katherine AU - Zilberman, Daniel AU - Zemach, Assaf ID - 9530 JF - Epigenetics and Chromatin TI - DNA methylation is maintained with high fidelity in the honey bee germline and exhibits global non-functional fluctuations during somatic development VL - 12 ER - TY - JOUR AB - Transposable elements (TEs), the movement of which can damage the genome, are epigenetically silenced in eukaryotes. Intriguingly, TEs are activated in the sperm companion cell – vegetative cell (VC) – of the flowering plant Arabidopsis thaliana. However, the extent and mechanism of this activation are unknown. Here we show that about 100 heterochromatic TEs are activated in VCs, mostly by DEMETER-catalyzed DNA demethylation. We further demonstrate that DEMETER access to some of these TEs is permitted by the natural depletion of linker histone H1 in VCs. Ectopically expressed H1 suppresses TEs in VCs by reducing DNA demethylation and via a methylation-independent mechanism. We demonstrate that H1 is required for heterochromatin condensation in plant cells and show that H1 overexpression creates heterochromatic foci in the VC progenitor cell. Taken together, our results demonstrate that the natural depletion of H1 during male gametogenesis facilitates DEMETER-directed DNA demethylation, heterochromatin relaxation, and TE activation. AU - He, Shengbo AU - Vickers, Martin AU - Zhang, Jingyi AU - Feng, Xiaoqi ID - 12192 JF - eLife KW - General Immunology and Microbiology KW - General Biochemistry KW - Genetics and Molecular Biology KW - General Medicine KW - General Neuroscience SN - 2050-084X TI - Natural depletion of histone H1 in sex cells causes DNA demethylation, heterochromatin decondensation and transposon activation VL - 8 ER - TY - JOUR AB - Meiotic crossover frequency varies within genomes, which influences genetic diversity and adaptation. In turn, genetic variation within populations can act to modify crossover frequency in cis and trans. To identify genetic variation that controls meiotic crossover frequency, we screened Arabidopsis accessions using fluorescent recombination reporters. We mapped a genetic modifier of crossover frequency in Col × Bur populations of Arabidopsis to a premature stop codon within TBP-ASSOCIATED FACTOR 4b (TAF4b), which encodes a subunit of the RNA polymerase II general transcription factor TFIID. The Arabidopsis taf4b mutation is a rare variant found in the British Isles, originating in South-West Ireland. Using genetics, genomics, and immunocytology, we demonstrate a genome-wide decrease in taf4b crossovers, with strongest reduction in the sub-telomeric regions. Using RNA sequencing (RNA-seq) from purified meiocytes, we show that TAF4b expression is meiocyte enriched, whereas its paralog TAF4 is broadly expressed. Consistent with the role of TFIID in promoting gene expression, RNA-seq of wild-type and taf4b meiocytes identified widespread transcriptional changes, including in genes that regulate the meiotic cell cycle and recombination. Therefore, TAF4b duplication is associated with acquisition of meiocyte-specific expression and promotion of germline transcription, which act directly or indirectly to elevate crossovers. This identifies a novel mode of meiotic recombination control via a general transcription factor. AU - Lawrence, Emma J. AU - Gao, Hongbo AU - Tock, Andrew J. AU - Lambing, Christophe AU - Blackwell, Alexander R. AU - Feng, Xiaoqi AU - Henderson, Ian R. ID - 12190 IS - 16 JF - Current Biology KW - General Agricultural and Biological Sciences KW - General Biochemistry KW - Genetics and Molecular Biology SN - 0960-9822 TI - Natural variation in TBP-ASSOCIATED FACTOR 4b controls meiotic crossover and germline transcription in Arabidopsis VL - 29 ER - TY - GEN AU - Schlögl, Alois AU - Kiss, Janos AU - Elefante, Stefano ID - 12901 T2 - AHPC19 - Austrian HPC Meeting 2019 TI - Is Debian suitable for running an HPC Cluster? ER - TY - CONF AB - When can a polyomino piece of paper be folded into a unit cube? Prior work studied tree-like polyominoes, but polyominoes with holes remain an intriguing open problem. We present sufficient conditions for a polyomino with hole(s) to fold into a cube, and conditions under which cube folding is impossible. In particular, we show that all but five special simple holes guarantee foldability. AU - Aichholzer, Oswin AU - Akitaya, Hugo A AU - Cheung, Kenneth C AU - Demaine, Erik D AU - Demaine, Martin L AU - Fekete, Sandor P AU - Kleist, Linda AU - Kostitsyna, Irina AU - Löffler, Maarten AU - Masárová, Zuzana AU - Mundilova, Klara AU - Schmidt, Christiane ID - 6989 T2 - Proceedings of the 31st Canadian Conference on Computational Geometry TI - Folding polyominoes with holes into a cube ER - TY - CONF AB - In two-player games on graphs, the players move a token through a graph to produce a finite or infinite path, which determines the qualitative winner or quantitative payoff of the game. We study bidding games in which the players bid for the right to move the token. Several bidding rules were studied previously. In Richman bidding, in each round, the players simultaneously submit bids, and the higher bidder moves the token and pays the other player. Poorman bidding is similar except that the winner of the bidding pays the "bank" rather than the other player. Taxman bidding spans the spectrum between Richman and poorman bidding. They are parameterized by a constant tau in [0,1]: portion tau of the winning bid is paid to the other player, and portion 1-tau to the bank. While finite-duration (reachability) taxman games have been studied before, we present, for the first time, results on infinite-duration taxman games. It was previously shown that both Richman and poorman infinite-duration games with qualitative objectives reduce to reachability games, and we show a similar result here. Our most interesting results concern quantitative taxman games, namely mean-payoff games, where poorman and Richman bidding differ significantly. A central quantity in these games is the ratio between the two players' initial budgets. While in poorman mean-payoff games, the optimal payoff of a player depends on the initial ratio, in Richman bidding, the payoff depends only on the structure of the game. In both games the optimal payoffs can be found using (different) probabilistic connections with random-turn games in which in each turn, instead of bidding, a coin is tossed to determine which player moves. While the value with Richman bidding equals the value of a random-turn game with an un-biased coin, with poorman bidding, the bias in the coin is the initial ratio of the budgets. We give a complete classification of mean-payoff taxman games that is based on a probabilistic connection: the value of a taxman bidding game with parameter tau and initial ratio r, equals the value of a random-turn game that uses a coin with bias F(tau, r) = (r+tau * (1-r))/(1+tau). Thus, we show that Richman bidding is the exception; namely, for every tau <1, the value of the game depends on the initial ratio. Our proof technique simplifies and unifies the previous proof techniques for both Richman and poorman bidding. AU - Avni, Guy AU - Henzinger, Thomas A AU - Zikelic, Dorde ID - 6884 TI - Bidding mechanisms in graph games VL - 138 ER - TY - GEN AB - A detailed description of the two stochastic models, table of parameters, supplementary data for Figures 4 and 5, parameter dependence of the results, and an analysis on motors with different force–velocity functions (PDF) AU - Ucar, Mehmet C AU - Lipowsky, Reinhard ID - 9726 TI - Supplementary information - Collective force generation by molecular motors is determined by strain-induced unbinding ER - TY - JOUR AB - In this paper we discuss three results. The first two concern general sets of positive reach: we first characterize the reach of a closed set by means of a bound on the metric distortion between the distance measured in the ambient Euclidean space and the shortest path distance measured in the set. Secondly, we prove that the intersection of a ball with radius less than the reach with the set is geodesically convex, meaning that the shortest path between any two points in the intersection lies itself in the intersection. For our third result we focus on manifolds with positive reach and give a bound on the angle between tangent spaces at two different points in terms of the reach and the distance between the two points. AU - Boissonnat, Jean-Daniel AU - Lieutier, André AU - Wintraecken, Mathijs ID - 6671 IS - 1-2 JF - Journal of Applied and Computational Topology SN - 2367-1726 TI - The reach, metric distortion, geodesic convexity and the variation of tangent spaces VL - 3 ER - TY - JOUR AB - A representation formula for solutions of stochastic partial differential equations with Dirichlet boundary conditions is proved. The scope of our setting is wide enough to cover the general situation when the backward characteristics that appear in the usual formulation are not even defined in the Itô sense. AU - Gerencser, Mate AU - Gyöngy, István ID - 301 IS - 3 JF - Stochastic Processes and their Applications TI - A Feynman–Kac formula for stochastic Dirichlet problems VL - 129 ER - TY - JOUR AB - We consider an interacting, dilute Bose gas trapped in a harmonic potential at a positive temperature. The system is analyzed in a combination of a thermodynamic and a Gross–Pitaevskii (GP) limit where the trap frequency ω, the temperature T, and the particle number N are related by N∼ (T/ ω) 3→ ∞ while the scattering length is so small that the interaction energy per particle around the center of the trap is of the same order of magnitude as the spectral gap in the trap. We prove that the difference between the canonical free energy of the interacting gas and the one of the noninteracting system can be obtained by minimizing the GP energy functional. We also prove Bose–Einstein condensation in the following sense: The one-particle density matrix of any approximate minimizer of the canonical free energy functional is to leading order given by that of the noninteracting gas but with the free condensate wavefunction replaced by the GP minimizer. AU - Deuchert, Andreas AU - Seiringer, Robert AU - Yngvason, Jakob ID - 80 IS - 2 JF - Communications in Mathematical Physics TI - Bose–Einstein condensation in a dilute, trapped gas at positive temperature VL - 368 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 - We count points over a finite field on wild character varieties,of Riemann surfaces for singularities with regular semisimple leading term. The new feature in our counting formulas is the appearance of characters of Yokonuma–Hecke algebras. Our result leads to the conjecture that the mixed Hodge polynomials of these character varieties agree with previously conjectured perverse Hodge polynomials of certain twisted parabolic Higgs moduli spaces, indicating the possibility of a P = W conjecture for a suitable wild Hitchin system. AU - Hausel, Tamas AU - Mereb, Martin AU - Wong, Michael ID - 439 IS - 10 JF - Journal of the European Mathematical Society TI - Arithmetic and representation theory of wild character varieties VL - 21 ER - TY - JOUR AB - Clinical Utility Gene Card. 1. Name of Disease (Synonyms): Pontocerebellar hypoplasia type 9 (PCH9) and spastic paraplegia-63 (SPG63). 2. OMIM# of the Disease: 615809 and 615686. 3. Name of the Analysed Genes or DNA/Chromosome Segments: AMPD2 at 1p13.3. 4. OMIM# of the Gene(s): 102771. AU - Marsh, Ashley AU - Novarino, Gaia AU - Lockhart, Paul AU - Leventer, Richard ID - 105 JF - European Journal of Human Genetics TI - CUGC for pontocerebellar hypoplasia type 9 and spastic paraplegia-63 VL - 27 ER - TY - JOUR AB - We provide an entropy formulation for porous medium-type equations with a stochastic, non-linear, spatially inhomogeneous forcing. Well-posedness and L1-contraction is obtained in the class of entropy solutions. Our scope allows for porous medium operators Δ(|u|m−1u) for all m∈(1,∞), and Hölder continuous diffusion nonlinearity with exponent 1/2. AU - Dareiotis, Konstantinos AU - Gerencser, Mate AU - Gess, Benjamin ID - 65 IS - 6 JF - Journal of Differential Equations TI - Entropy solutions for stochastic porous media equations VL - 266 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 - 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 - 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 - JOUR AB - We investigate the quantum Jensen divergences from the viewpoint of joint convexity. It turns out that the set of the functions which generate jointly convex quantum Jensen divergences on positive matrices coincides with the Matrix Entropy Class which has been introduced by Chen and Tropp quite recently. AU - Virosztek, Daniel ID - 405 JF - Linear Algebra and Its Applications TI - Jointly convex quantum Jensen divergences VL - 576 ER - TY - JOUR AB - An upper bound sieve for rational points on suitable varieties isdeveloped, together with applications tocounting rational points in thin sets,to local solubility in families, and to the notion of “friable” rational pointswith respect to divisors. In the special case of quadrics, sharper estimates areobtained by developing a version of the Selberg sieve for rational points. AU - Browning, Timothy D AU - Loughran, Daniel ID - 175 IS - 8 JF - Transactions of the American Mathematical Society SN - 00029947 TI - Sieving rational points on varieties VL - 371 ER - TY - JOUR AB - We study spaces of modelled distributions with singular behaviour near the boundary of a domain that, in the context of the theory of regularity structures, allow one to give robust solution theories for singular stochastic PDEs with boundary conditions. The calculus of modelled distributions established in Hairer (Invent Math 198(2):269–504, 2014. https://doi.org/10.1007/s00222-014-0505-4) is extended to this setting. We formulate and solve fixed point problems in these spaces with a class of kernels that is sufficiently large to cover in particular the Dirichlet and Neumann heat kernels. These results are then used to provide solution theories for the KPZ equation with Dirichlet and Neumann boundary conditions and for the 2D generalised parabolic Anderson model with Dirichlet boundary conditions. In the case of the KPZ equation with Neumann boundary conditions, we show that, depending on the class of mollifiers one considers, a “boundary renormalisation” takes place. In other words, there are situations in which a certain boundary condition is applied to an approximation to the KPZ equation, but the limiting process is the Hopf–Cole solution to the KPZ equation with a different boundary condition. AU - Gerencser, Mate AU - Hairer, Martin ID - 319 IS - 3-4 JF - Probability Theory and Related Fields SN - 01788051 TI - Singular SPDEs in domains with boundaries VL - 173 ER - TY - JOUR AB - We consider real symmetric or complex hermitian random matrices with correlated entries. We prove local laws for the resolvent and universality of the local eigenvalue statistics in the bulk of the spectrum. The correlations have fast decay but are otherwise of general form. The key novelty is the detailed stability analysis of the corresponding matrix valued Dyson equation whose solution is the deterministic limit of the resolvent. AU - Ajanki, Oskari H AU - Erdös, László AU - Krüger, Torben H ID - 429 IS - 1-2 JF - Probability Theory and Related Fields SN - 01788051 TI - Stability of the matrix Dyson equation and random matrices with correlations VL - 173 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 - 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 - 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 - Protein micropatterning has become an important tool for many biomedical applications as well as in academic research. Current techniques that allow to reduce the feature size of patterns below 1 μm are, however, often costly and require sophisticated equipment. We present here a straightforward and convenient method to generate highly condensed nanopatterns of proteins without the need for clean room facilities or expensive equipment. Our approach is based on nanocontact printing and allows for the fabrication of protein patterns with feature sizes of 80 nm and periodicities down to 140 nm. This was made possible by the use of the material X-poly(dimethylsiloxane) (X-PDMS) in a two-layer stamp layout for protein printing. In a proof of principle, different proteins at various scales were printed and the pattern quality was evaluated by atomic force microscopy (AFM) and super-resolution fluorescence microscopy. AU - Lindner, Marco AU - Tresztenyak, Aliz AU - Fülöp, Gergö AU - Jahr, Wiebke AU - Prinz, Adrian AU - Prinz, Iris AU - Danzl, Johann G AU - Schütz, Gerhard J. AU - Sevcsik, Eva ID - 6029 JF - Frontiers in Chemistry TI - A fast and simple contact printing approach to generate 2D protein nanopatterns VL - 6 ER - TY - JOUR AB - We give a construction allowing us to build local renormalized solutions to general quasilinear stochastic PDEs within the theory of regularity structures, thus greatly generalizing the recent results of [1, 5, 11]. Loosely speaking, our construction covers quasilinear variants of all classes of equations for which the general construction of [3, 4, 7] applies, including in particular one‐dimensional systems with KPZ‐type nonlinearities driven by space‐time white noise. In a less singular and more specific case, we furthermore show that the counterterms introduced by the renormalization procedure are given by local functionals of the solution. The main feature of our construction is that it allows exploitation of a number of existing results developed for the semilinear case, so that the number of additional arguments it requires is relatively small. AU - Gerencser, Mate AU - Hairer, Martin ID - 6028 IS - 9 JF - Communications on Pure and Applied Mathematics TI - A solution theory for quasilinear singular SPDEs VL - 72 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 - 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 - 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 - CONF AB - Static program analyzers are increasingly effective in checking correctness properties of programs and reporting any errors found, often in the form of error traces. However, developers still spend a significant amount of time on debugging. This involves processing long error traces in an effort to localize a bug to a relatively small part of the program and to identify its cause. In this paper, we present a technique for automated fault localization that, given a program and an error trace, efficiently narrows down the cause of the error to a few statements. These statements are then ranked in terms of their suspiciousness. Our technique relies only on the semantics of the given program and does not require any test cases or user guidance. In experiments on a set of C benchmarks, we show that our technique is effective in quickly isolating the cause of error while out-performing other state-of-the-art fault-localization techniques. AU - Christakis, Maria AU - Heizmann, Matthias AU - Mansur, Muhammad Numair AU - Schilling, Christian AU - Wüstholz, Valentin ID - 6042 T2 - 25th International Conference on Tools and Algorithms for the Construction and Analysis of Systems TI - Semantic fault localization and suspiciousness ranking VL - 11427 ER - TY - CONF AB - We present JuliaReach, a toolbox for set-based reachability analysis of dynamical systems. JuliaReach consists of two main packages: Reachability, containing implementations of reachability algorithms for continuous and hybrid systems, and LazySets, a standalone library that implements state-of-the-art algorithms for calculus with convex sets. The library offers both concrete and lazy set representations, where the latter stands for the ability to delay set computations until they are needed. The choice of the programming language Julia and the accompanying documentation of our toolbox allow researchers to easily translate set-based algorithms from mathematics to software in a platform-independent way, while achieving runtime performance that is comparable to statically compiled languages. Combining lazy operations in high dimensions and explicit computations in low dimensions, JuliaReach can be applied to solve complex, large-scale problems. AU - Bogomolov, Sergiy AU - Forets, Marcelo AU - Frehse, Goran AU - Potomkin, Kostiantyn AU - Schilling, Christian ID - 6035 KW - reachability analysis KW - hybrid systems KW - lazy computation SN - 9781450362825 T2 - Proceedings of the 22nd International Conference on Hybrid Systems: Computation and Control TI - JuliaReach: A toolbox for set-based reachability VL - 22 ER - TY - JOUR AB - Expansion microscopy is a relatively new approach to super-resolution imaging that uses expandable hydrogels to isotropically increase the physical distance between fluorophores in biological samples such as cell cultures or tissue slices. The classic gel recipe results in an expansion factor of ~4×, with a resolution of 60–80 nm. We have recently developed X10 microscopy, which uses a gel that achieves an expansion factor of ~10×, with a resolution of ~25 nm. Here, we provide a step-by-step protocol for X10 expansion microscopy. A typical experiment consists of seven sequential stages: (i) immunostaining, (ii) anchoring, (iii) polymerization, (iv) homogenization, (v) expansion, (vi) imaging, and (vii) validation. The protocol presented here includes recommendations for optimization, pitfalls and their solutions, and detailed guidelines that should increase reproducibility. Although our protocol focuses on X10 expansion microscopy, we detail which of these suggestions are also applicable to classic fourfold expansion microscopy. We exemplify our protocol using primary hippocampal neurons from rats, but our approach can be used with other primary cells or cultured cell lines of interest. This protocol will enable any researcher with basic experience in immunostainings and access to an epifluorescence microscope to perform super-resolution microscopy with X10. The procedure takes 3 d and requires ~5 h of actively handling the sample for labeling and expansion, and another ~3 h for imaging and analysis. AU - Truckenbrodt, Sven M AU - Sommer, Christoph M AU - Rizzoli, Silvio O AU - Danzl, Johann G ID - 6052 IS - 3 JF - Nature Protocols TI - A practical guide to optimization in X10 expansion microscopy VL - 14 ER - TY - JOUR AB - Non-canonical Wnt signaling plays a central role for coordinated cell polarization and directed migration in metazoan development. While spatiotemporally restricted activation of non-canonical Wnt-signaling drives cell polarization in epithelial tissues, it remains unclear whether such instructive activity is also critical for directed mesenchymal cell migration. Here, we developed a light-activated version of the non-canonical Wnt receptor Frizzled 7 (Fz7) to analyze how restricted activation of non-canonical Wnt signaling affects directed anterior axial mesendoderm (prechordal plate, ppl) cell migration within the zebrafish gastrula. We found that Fz7 signaling is required for ppl cell protrusion formation and migration and that spatiotemporally restricted ectopic activation is capable of redirecting their migration. Finally, we show that uniform activation of Fz7 signaling in ppl cells fully rescues defective directed cell migration in fz7 mutant embryos. Together, our findings reveal that in contrast to the situation in epithelial cells, non-canonical Wnt signaling functions permissively rather than instructively in directed mesenchymal cell migration during gastrulation. AU - Capek, Daniel AU - Smutny, Michael AU - Tichy, Alexandra Madelaine AU - Morri, Maurizio AU - Janovjak, Harald L AU - Heisenberg, Carl-Philipp J ID - 6025 JF - eLife TI - Light-activated Frizzled7 reveals a permissive role of non-canonical wnt signaling in mesendoderm cell migration VL - 8 ER - TY - JOUR AB - The evolution of new species is made easier when traits under divergent ecological selection are also mating cues. Such ecological mating cues are now considered more common than previously thought, but we still know little about the genetic changes underlying their evolution or more generally about the genetic basis for assortative mating behaviors. Both tight physical linkage and the existence of large-effect preference loci will strengthen genetic associations between behavioral and ecological barriers, promoting the evolution of assortative mating. The warning patterns of Heliconius melpomene and H. cydno are under disruptive selection due to increased predation of nonmimetic hybrids and are used during mate recognition. We carried out a genome-wide quantitative trait locus (QTL) analysis of preference behaviors between these species and showed that divergent male preference has a simple genetic basis. We identify three QTLs that together explain a large proportion (approximately 60%) of the difference in preference behavior observed between the parental species. One of these QTLs is just 1.2 (0-4.8) centiMorgans (cM) from the major color pattern gene optix, and, individually, all three have a large effect on the preference phenotype. Genomic divergence between H. cydno and H. melpomene is high but broadly heterogenous, and admixture is reduced at the preference-optix color pattern locus but not the other preference QTLs. The simple genetic architecture we reveal will facilitate the evolution and maintenance of new species despite ongoing gene flow by coupling behavioral and ecological aspects of reproductive isolation. AU - Merrill, Richard M. AU - Rastas, Pasi AU - Martin, Simon H. AU - Melo Hurtado, Maria C AU - Barker, Sarah AU - Davey, John AU - Mcmillan, W. Owen AU - Jiggins, Chris D. ID - 6022 IS - 2 JF - PLoS Biology TI - Genetic dissection of assortative mating behavior VL - 17 ER - TY - JOUR AB - Multicellular development requires coordinated cell polarization relative to body axes, and translation to oriented cell division 1–3 . In plants, it is unknown how cell polarities are connected to organismal axes and translated to division. Here, we identify Arabidopsis SOSEKI proteins that integrate apical–basal and radial organismal axes to localize to polar cell edges. Localization does not depend on tissue context, requires cell wall integrity and is defined by a transferrable, protein-specific motif. A Domain of Unknown Function in SOSEKI proteins resembles the DIX oligomerization domain in the animal Dishevelled polarity regulator. The DIX-like domain self-interacts and is required for edge localization and for influencing division orientation, together with a second domain that defines the polar membrane domain. Our work shows that SOSEKI proteins locally interpret global polarity cues and can influence cell division orientation. Furthermore, this work reveals that, despite fundamental differences, cell polarity mechanisms in plants and animals converge on a similar protein domain. AU - Yoshida, Saiko AU - Van Der Schuren, Alja AU - Van Dop, Maritza AU - Van Galen, Luc AU - Saiga, Shunsuke AU - Adibi, Milad AU - Möller, Barbara AU - Ten Hove, Colette A. AU - Marhavy, Peter AU - Smith, Richard AU - Friml, Jiří AU - Weijers, Dolf ID - 6023 IS - 2 JF - Nature Plants TI - A SOSEKI-based coordinate system interprets global polarity cues in arabidopsis VL - 5 ER - TY - JOUR AB - Recent technical developments in the fields of quantum electromechanics and optomechanics have spawned nanoscale mechanical transducers with the sensitivity to measure mechanical displacements at the femtometre scale and the ability to convert electromagnetic signals at the single photon level. A key challenge in this field is obtaining strong coupling between motion and electromagnetic fields without adding additional decoherence. Here we present an electromechanical transducer that integrates a high-frequency (0.42 GHz) hypersonic phononic crystal with a superconducting microwave circuit. The use of a phononic bandgap crystal enables quantum-level transduction of hypersonic mechanical motion and concurrently eliminates decoherence caused by acoustic radiation. Devices with hypersonic mechanical frequencies provide a natural pathway for integration with Josephson junction quantum circuits, a leading quantum computing technology, and nanophotonic systems capable of optical networking and distributing quantum information. AU - Kalaee, Mahmoud AU - Mirhosseini, Mohammad AU - Dieterle, Paul B. AU - Peruzzo, Matilda AU - Fink, Johannes M AU - Painter, Oskar ID - 6053 IS - 4 JF - Nature Nanotechnology SN - 1748-3387 TI - Quantum electromechanics of a hypersonic crystal VL - 14 ER - TY - JOUR AB - We answer a question of David Hilbert: given two circles it is not possible in general to construct their centers using only a straightedge. On the other hand, we give infinitely many families of pairs of circles for which such construction is possible. AU - Akopyan, Arseniy AU - Fedorov, Roman ID - 6050 JF - Proceedings of the American Mathematical Society TI - Two circles and only a straightedge VL - 147 ER - TY - GEN AU - Merrill, Richard M. AU - Rastas, Pasi AU - Martin, Simon H. AU - Melo Hurtado, Maria C AU - Barker, Sarah AU - Davey, John AU - Mcmillan, W. Owen AU - Jiggins, Chris D. ID - 9801 TI - Raw behavioral data ER - TY - JOUR AB - Both classical and recent studies suggest that chromosomal inversion polymorphisms are important in adaptation and speciation. However, biases in discovery and reporting of inversions make it difficult to assess their prevalence and biological importance. Here, we use an approach based on linkage disequilibrium among markers genotyped for samples collected across a transect between contrasting habitats to detect chromosomal rearrangements de novo. We report 17 polymorphic rearrangements in a single locality for the coastal marine snail, Littorina saxatilis. Patterns of diversity in the field and of recombination in controlled crosses provide strong evidence that at least the majority of these rearrangements are inversions. Most show clinal changes in frequency between habitats, suggestive of divergent selection, but only one appears to be fixed for different arrangements in the two habitats. Consistent with widespread evidence for balancing selection on inversion polymorphisms, we argue that a combination of heterosis and divergent selection can explain the observed patterns and should be considered in other systems spanning environmental gradients. AU - Faria, Rui AU - Chaube, Pragya AU - Morales, Hernán E. AU - Larsson, Tomas AU - Lemmon, Alan R. AU - Lemmon, Emily M. AU - Rafajlović, Marina AU - Panova, Marina AU - Ravinet, Mark AU - Johannesson, Kerstin AU - Westram, Anja M AU - Butlin, Roger K. ID - 6095 IS - 6 JF - Molecular Ecology SN - 0962-1083 TI - Multiple chromosomal rearrangements in a hybrid zone between Littorina saxatilis ecotypes VL - 28 ER - TY - JOUR AB - In this article it is shown that large systems with many interacting units endowing multiple phases display self-oscillations in the presence of linear feedback between the control and order parameters, where an Andronov–Hopf bifurcation takes over the phase transition. This is simply illustrated through the mean field Landau theory whose feedback dynamics turn out to be described by the Van der Pol equation and it is then validated for the fully connected Ising model following heat bath dynamics. Despite its simplicity, this theory accounts potentially for a rich range of phenomena: here it is applied to describe in a stylized way (i) excess demand-price cycles due to strong herding in a simple agent-based market model; (ii) congestion waves in queuing networks triggered by user feedback to delays in overloaded conditions; and (iii) metabolic network oscillations resulting from cell growth control in a bistable phenotypic landscape. AU - De Martino, Daniele ID - 6049 IS - 4 JF - Journal of Physics A: Mathematical and Theoretical TI - Feedback-induced self-oscillations in large interacting systems subjected to phase transitions VL - 52 ER -