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 -