TY - THES AB - Decades of studies have revealed the mechanisms of gene regulation in molecular detail. We make use of such well-described regulatory systems to explore how the molecular mechanisms of protein-protein and protein-DNA interactions shape the dynamics and evolution of gene regulation. i) We uncover how the biophysics of protein-DNA binding determines the potential of regulatory networks to evolve and adapt, which can be captured using a simple mathematical model. ii) The evolution of regulatory connections can lead to a significant amount of crosstalk between binding proteins. We explore the effect of crosstalk on gene expression from a target promoter, which seems to be modulated through binding competition at non-specific DNA sites. iii) We investigate how the very same biophysical characteristics as in i) can generate significant fitness costs for cells through global crosstalk, meaning non-specific DNA binding across the genomic background. iv) Binding competition between proteins at a target promoter is a prevailing regulatory feature due to the prevalence of co-regulation at bacterial promoters. However, the dynamics of these systems are not always straightforward to determine even if the molecular mechanisms of regulation are known. A detailed model of the biophysical interactions reveals that interference between the regulatory proteins can constitute a new, generic form of system memory that records the history of the input signals at the promoter. We demonstrate how the biophysics of protein-DNA binding can be harnessed to investigate the principles that shape and ultimately limit cellular gene regulation. These results provide a basis for studies of higher-level functionality, which arises from the underlying regulation. AU - Igler, Claudia ID - 6371 KW - gene regulation KW - biophysics KW - transcription factor binding KW - bacteria SN - 2663-337X TI - On the nature of gene regulatory design - The biophysics of transcription factor binding shapes gene regulation ER - TY - JOUR AB - In this paper, we evaluate clock signals generated in ring oscillators and self-timed rings and the way their jitter can be transformed into random numbers. We show that counting the periods of the jittery clock signal produces random numbers of significantly better quality than the methods in which the jittery signal is simply sampled (the case in almost all current methods). Moreover, we use the counter values to characterize and continuously monitor the source of randomness. However, instead of using the widely used statistical variance, we propose to use Allan variance to do so. There are two main advantages: Allan variance is insensitive to low frequency noises such as flicker noise that are known to be autocorrelated and significantly less circuitry is required for its computation than that used to compute commonly used variance. We also show that it is essential to use a differential principle of randomness extraction from the jitter based on the use of two identical oscillators to avoid autocorrelations originating from external and internal global jitter sources and that this fact is valid for both kinds of rings. Last but not least, we propose a method of statistical testing based on high order Markov model to show the reduced dependencies when the proposed randomness extraction is applied. AU - Allini, Elie Noumon AU - Skórski, Maciej AU - Petura, Oto AU - Bernard, Florent AU - Laban, Marek AU - Fischer, Viktor ID - 10286 IS - 3 JF - IACR Transactions on Cryptographic Hardware and Embedded Systems TI - Evaluation and monitoring of free running oscillators serving as source of randomness VL - 2018 ER - TY - CONF AB - Solving parity games, which are equivalent to modal μ-calculus model checking, is a central algorithmic problem in formal methods, with applications in reactive synthesis, program repair, verification of branching-time properties, etc. Besides the standard compu- tation model with the explicit representation of games, another important theoretical model of computation is that of set-based symbolic algorithms. Set-based symbolic algorithms use basic set operations and one-step predecessor operations on the implicit description of games, rather than the explicit representation. The significance of symbolic algorithms is that they provide scalable algorithms for large finite-state systems, as well as for infinite-state systems with finite quotient. Consider parity games on graphs with n vertices and parity conditions with d priorities. While there is a rich literature of explicit algorithms for parity games, the main results for set-based symbolic algorithms are as follows: (a) the basic algorithm that requires O(nd) symbolic operations and O(d) symbolic space; and (b) an improved algorithm that requires O(nd/3+1) symbolic operations and O(n) symbolic space. In this work, our contributions are as follows: (1) We present a black-box set-based symbolic algorithm based on the explicit progress measure algorithm. Two important consequences of our algorithm are as follows: (a) a set-based symbolic algorithm for parity games that requires quasi-polynomially many symbolic operations and O(n) symbolic space; and (b) any future improvement in progress measure based explicit algorithms immediately imply an efficiency improvement in our set-based symbolic algorithm for parity games. (2) We present a set-based symbolic algorithm that requires quasi-polynomially many symbolic operations and O(d · log n) symbolic space. Moreover, for the important special case of d ≤ log n, our algorithm requires only polynomially many symbolic operations and poly-logarithmic symbolic space. AU - Chatterjee, Krishnendu AU - Dvořák, Wolfgang AU - Henzinger, Monika H AU - Svozil, Alexander ID - 10883 SN - 2398-7340 T2 - 22nd International Conference on Logic for Programming, Artificial Intelligence and Reasoning TI - Quasipolynomial set-based symbolic algorithms for parity games VL - 57 ER - TY - CONF AB - We report on a novel strategy to derive mean-field limits of quantum mechanical systems in which a large number of particles weakly couple to a second-quantized radiation field. The technique combines the method of counting and the coherent state approach to study the growth of the correlations among the particles and in the radiation field. As an instructional example, we derive the Schrödinger–Klein–Gordon system of equations from the Nelson model with ultraviolet cutoff and possibly massless scalar field. In particular, we prove the convergence of the reduced density matrices (of the nonrelativistic particles and the field bosons) associated with the exact time evolution to the projectors onto the solutions of the Schrödinger–Klein–Gordon equations in trace norm. Furthermore, we derive explicit bounds on the rate of convergence of the one-particle reduced density matrix of the nonrelativistic particles in Sobolev norm. AU - Leopold, Nikolai K AU - Pickl, Peter ID - 11 TI - Mean-field limits of particles in interaction with quantised radiation fields VL - 270 ER - TY - JOUR AB - Two generalizations of Itô formula to infinite-dimensional spaces are given. The first one, in Hilbert spaces, extends the classical one by taking advantage of cancellations when they occur in examples and it is applied to the case of a group generator. The second one, based on the previous one and a limit procedure, is an Itô formula in a special class of Banach spaces having a product structure with the noise in a Hilbert component; again the key point is the extension due to a cancellation. This extension to Banach spaces and in particular the specific cancellation are motivated by path-dependent Itô calculus. AU - Flandoli, Franco AU - Russo, Francesco AU - Zanco, Giovanni A ID - 1215 IS - 2 JF - Journal of Theoretical Probability TI - Infinite-dimensional calculus under weak spatial regularity of the processes VL - 31 ER - TY - CONF AB - We resolve in the affirmative conjectures of A. Skopenkov and Repovš (1998), and M. Skopenkov (2003) generalizing the classical Hanani-Tutte theorem to the setting of approximating maps of graphs on 2-dimensional surfaces by embeddings. Our proof of this result is constructive and almost immediately implies an efficient algorithm for testing whether a given piecewise linear map of a graph in a surface is approximable by an embedding. More precisely, an instance of this problem consists of (i) a graph G whose vertices are partitioned into clusters and whose inter-cluster edges are partitioned into bundles, and (ii) a region R of a 2-dimensional compact surface M given as the union of a set of pairwise disjoint discs corresponding to the clusters and a set of pairwise disjoint "pipes" corresponding to the bundles, connecting certain pairs of these discs. We are to decide whether G can be embedded inside M so that the vertices in every cluster are drawn in the corresponding disc, the edges in every bundle pass only through its corresponding pipe, and every edge crosses the boundary of each disc at most once. AU - Fulek, Radoslav AU - Kynčl, Jan ID - 185 SN - 978-3-95977-066-8 TI - Hanani-Tutte for approximating maps of graphs VL - 99 ER - TY - CONF AB - Smallest enclosing spheres of finite point sets are central to methods in topological data analysis. Focusing on Bregman divergences to measure dissimilarity, we prove bounds on the location of the center of a smallest enclosing sphere. These bounds depend on the range of radii for which Bregman balls are convex. AU - Edelsbrunner, Herbert AU - Virk, Ziga AU - Wagner, Hubert ID - 188 TI - Smallest enclosing spheres and Chernoff points in Bregman geometry VL - 99 ER - TY - JOUR AB - A cornerstone of statistical inference, the maximum entropy framework is being increasingly applied to construct descriptive and predictive models of biological systems, especially complex biological networks, from large experimental data sets. Both its broad applicability and the success it obtained in different contexts hinge upon its conceptual simplicity and mathematical soundness. Here we try to concisely review the basic elements of the maximum entropy principle, starting from the notion of ‘entropy’, and describe its usefulness for the analysis of biological systems. As examples, we focus specifically on the problem of reconstructing gene interaction networks from expression data and on recent work attempting to expand our system-level understanding of bacterial metabolism. Finally, we highlight some extensions and potential limitations of the maximum entropy approach, and point to more recent developments that are likely to play a key role in the upcoming challenges of extracting structures and information from increasingly rich, high-throughput biological data. AU - De Martino, Andrea AU - De Martino, Daniele ID - 306 IS - 4 JF - Heliyon TI - An introduction to the maximum entropy approach and its application to inference problems in biology VL - 4 ER - TY - BOOK AB - This book first explores the origins of this idea, grounded in theoretical work on temporal logic and automata. The editors and authors are among the world's leading researchers in this domain, and they contributed 32 chapters representing a thorough view of the development and application of the technique. Topics covered include binary decision diagrams, symbolic model checking, satisfiability modulo theories, partial-order reduction, abstraction, interpolation, concurrency, security protocols, games, probabilistic model checking, and process algebra, and chapters on the transfer of theory to industrial practice, property specification languages for hardware, and verification of real-time systems and hybrid systems. The book will be valuable for researchers and graduate students engaged with the development of formal methods and verification tools. AU - Clarke, Edmund M. AU - Henzinger, Thomas A AU - Veith, Helmut AU - Bloem, Roderick ID - 3300 SN - 978-3-319-10574-1 TI - Handbook of Model Checking ER - TY - CHAP AB - Developmental processes are inherently dynamic and understanding them requires quantitative measurements of gene and protein expression levels in space and time. While live imaging is a powerful approach for obtaining such data, it is still a challenge to apply it over long periods of time to large tissues, such as the embryonic spinal cord in mouse and chick. Nevertheless, dynamics of gene expression and signaling activity patterns in this organ can be studied by collecting tissue sections at different developmental stages. In combination with immunohistochemistry, this allows for measuring the levels of multiple developmental regulators in a quantitative manner with high spatiotemporal resolution. The mean protein expression levels over time, as well as embryo-to-embryo variability can be analyzed. A key aspect of the approach is the ability to compare protein levels across different samples. This requires a number of considerations in sample preparation, imaging and data analysis. Here we present a protocol for obtaining time course data of dorsoventral expression patterns from mouse and chick neural tube in the first 3 days of neural tube development. The described workflow starts from embryo dissection and ends with a processed dataset. Software scripts for data analysis are included. The protocol is adaptable and instructions that allow the user to modify different steps are provided. Thus, the procedure can be altered for analysis of time-lapse images and applied to systems other than the neural tube. AU - Zagórski, Marcin P AU - Kicheva, Anna ID - 37 SN - 1064-3745 T2 - Morphogen Gradients TI - Measuring dorsoventral pattern and morphogen signaling profiles in the growing neural tube VL - 1863 ER - TY - JOUR AB - The hanging-drop network (HDN) is a technology platform based on a completely open microfluidic network at the bottom of an inverted, surface-patterned substrate. The platform is predominantly used for the formation, culturing, and interaction of self-assembled spherical microtissues (spheroids) under precisely controlled flow conditions. Here, we describe design, fabrication, and operation of microfluidic hanging-drop networks. AU - Misun, Patrick AU - Birchler, Axel AU - Lang, Moritz AU - Hierlemann, Andreas AU - Frey, Olivier ID - 305 JF - Methods in Molecular Biology TI - Fabrication and operation of microfluidic hanging drop networks VL - 1771 ER - TY - CONF AB - Probabilistic programs extend classical imperative programs with real-valued random variables and random branching. The most basic liveness property for such programs is the termination property. The qualitative (aka almost-sure) termination problem asks whether a given program program terminates with probability 1. While ranking functions provide a sound and complete method for non-probabilistic programs, the extension of them to probabilistic programs is achieved via ranking supermartingales (RSMs). Although deep theoretical results have been established about RSMs, their application to probabilistic programs with nondeterminism has been limited only to programs of restricted control-flow structure. For non-probabilistic programs, lexicographic ranking functions provide a compositional and practical approach for termination analysis of real-world programs. In this work we introduce lexicographic RSMs and show that they present a sound method for almost-sure termination of probabilistic programs with nondeterminism. We show that lexicographic RSMs provide a tool for compositional reasoning about almost-sure termination, and for probabilistic programs with linear arithmetic they can be synthesized efficiently (in polynomial time). We also show that with additional restrictions even asymptotic bounds on expected termination time can be obtained through lexicographic RSMs. Finally, we present experimental results on benchmarks adapted from previous work to demonstrate the effectiveness of our approach. AU - Agrawal, Sheshansh AU - Chatterjee, Krishnendu AU - Novotny, Petr ID - 325 IS - POPL TI - Lexicographic ranking supermartingales: an efficient approach to termination of probabilistic programs VL - 2 ER - TY - CHAP AB - Adventitious roots (AR) are de novo formed roots that emerge from any part of the plant or from callus in tissue culture, except root tissue. The plant tissue origin and the method by which they are induced determine the physiological properties of emerged ARs. Hence, a standard method encompassing all types of AR does not exist. Here we describe a method for the induction and analysis of AR that emerge from the etiolated hypocotyl of dicot plants. The hypocotyl is formed during embryogenesis and shows a determined developmental pattern which usually does not involve AR formation. However, the hypocotyl shows propensity to form de novo roots under specific circumstances such as removal of the root system, high humidity or flooding, or during de-etiolation. The hypocotyl AR emerge from a pericycle-like cell layer surrounding the vascular tissue of the central cylinder, which is reminiscent to the developmental program of lateral roots. Here we propose an easy protocol for in vitro hypocotyl AR induction from etiolated Arabidopsis seedlings. AU - Trinh, Hoang AU - Verstraeten, Inge AU - Geelen, Danny ID - 408 SN - 1064-3745 T2 - Root Development TI - In vitro assay for induction of adventitious rooting on intact arabidopsis hypocotyls VL - 1761 ER - TY - CHAP AB - Immunolocalization is a valuable tool for cell biology research that allows to rapidly determine the localization and expression levels of endogenous proteins. In plants, whole-mount in situ immunolocalization remains a challenging method, especially in tissues protected by waxy layers and complex cell wall carbohydrates. Here, we present a robust method for whole-mount in situ immunolocalization in primary root meristems and lateral root primordia in Arabidopsis thaliana. For good epitope preservation, fixation is done in an alkaline paraformaldehyde/glutaraldehyde mixture. This fixative is suitable for detecting a wide range of proteins, including integral transmembrane proteins and proteins peripherally attached to the plasma membrane. From initiation until emergence from the primary root, lateral root primordia are surrounded by several layers of differentiated tissues with a complex cell wall composition that interferes with the efficient penetration of all buffers. Therefore, immunolocalization in early lateral root primordia requires a modified method, including a strong solvent treatment for removal of hydrophobic barriers and a specific cocktail of cell wall-degrading enzymes. The presented method allows for easy, reliable, and high-quality in situ detection of the subcellular localization of endogenous proteins in primary and lateral root meristems without the need of time-consuming crosses or making translational fusions to fluorescent proteins. AU - Karampelias, Michael AU - Tejos, Ricardo AU - Friml, Jirí AU - Vanneste, Steffen ED - Ristova, Daniela ED - Barbez, Elke ID - 411 T2 - Root Development. Methods and Protocols TI - Optimized whole mount in situ immunolocalization for Arabidopsis thaliana root meristems and lateral root primordia VL - 1761 ER - TY - JOUR AB - Inhibition of the endoplasmic reticulum stress pathway may hold the key to Zika virus-associated microcephaly treatment. AU - Novarino, Gaia ID - 456 IS - 423 JF - Science Translational Medicine TI - Zika-associated microcephaly: Reduce the stress and race for the treatment VL - 10 ER - TY - JOUR AB - In 2013, a publication repository was implemented at IST Austria and 2015 after a thorough preparation phase a data repository was implemented - both based on the Open Source Software EPrints. In this text, designed as field report, we will reflect on our experiences with Open Source Software in general and specifically with EPrints regarding technical aspects but also regarding their characteristics of the user community. The second part is a pleading for including the end users in the process of implementation, adaption and evaluation. AU - Petritsch, Barbara AU - Porsche, Jana ID - 53 IS - 1 JF - VÖB Mitteilungen TI - IST PubRep and IST DataRep: the institutional repositories at IST Austria VL - 71 ER - TY - JOUR AB - We consider the problem of consensus in the challenging classic model. In this model, the adversary is adaptive; it can choose which processors crash at any point during the course of the algorithm. Further, communication is via asynchronous message passing: there is no known upper bound on the time to send a message from one processor to another, and all messages and coin flips are seen by the adversary. We describe a new randomized consensus protocol with expected message complexity O(n2log2n) when fewer than n / 2 processes may fail by crashing. This is an almost-linear improvement over the best previously known protocol, and within logarithmic factors of a known Ω(n2) message lower bound. The protocol further ensures that no process sends more than O(nlog3n) messages in expectation, which is again within logarithmic factors of optimal. We also present a generalization of the algorithm to an arbitrary number of failures t, which uses expected O(nt+t2log2t) total messages. Our approach is to build a message-efficient, resilient mechanism for aggregating individual processor votes, implementing the message-passing equivalent of a weak shared coin. Roughly, in our protocol, a processor first announces its votes to small groups, then propagates them to increasingly larger groups as it generates more and more votes. To bound the number of messages that an individual process might have to send or receive, the protocol progressively increases the weight of generated votes. The main technical challenge is bounding the impact of votes that are still “in flight” (generated, but not fully propagated) on the final outcome of the shared coin, especially since such votes might have different weights. We achieve this by leveraging the structure of the algorithm, and a technical argument based on martingale concentration bounds. Overall, we show that it is possible to build an efficient message-passing implementation of a shared coin, and in the process (almost-optimally) solve the classic consensus problem in the asynchronous message-passing model. AU - Alistarh, Dan-Adrian AU - Aspnes, James AU - King, Valerie AU - Saia, Jared ID - 536 IS - 6 JF - Distributed Computing SN - 01782770 TI - Communication-efficient randomized consensus VL - 31 ER - TY - JOUR AB - We analyse the canonical Bogoliubov free energy functional in three dimensions at low temperatures in the dilute limit. We prove existence of a first-order phase transition and, in the limit (Formula presented.), we determine the critical temperature to be (Formula presented.) to leading order. Here, (Formula presented.) is the critical temperature of the free Bose gas, ρ is the density of the gas and a is the scattering length of the pair-interaction potential V. We also prove asymptotic expansions for the free energy. In particular, we recover the Lee–Huang–Yang formula in the limit (Formula presented.). AU - Napiórkowski, Marcin M AU - Reuvers, Robin AU - Solovej, Jan ID - 554 IS - 1 JF - Communications in Mathematical Physics SN - 00103616 TI - The Bogoliubov free energy functional II: The dilute Limit VL - 360 ER - TY - CHAP AB - Primary neuronal cell culture preparations are widely used to investigate synaptic functions. This chapter describes a detailed protocol for the preparation of a neuronal cell culture in which giant calyx-type synaptic terminals are formed. This chapter also presents detailed protocols for utilizing the main technical advantages provided by such a preparation, namely, labeling and imaging of synaptic organelles and electrophysiological recordings directly from presynaptic terminals. AU - Dimitrov, Dimitar AU - Guillaud, Laurent AU - Eguchi, Kohgaku AU - Takahashi, Tomoyuki ED - Skaper, Stephen D. ID - 562 T2 - Neurotrophic Factors TI - Culture of mouse giant central nervous system synapses and application for imaging and electrophysiological analyses VL - 1727 ER - TY - CHAP AB - Graph-based games are an important tool in computer science. They have applications in synthesis, verification, refinement, and far beyond. We review graphbased games with objectives on infinite plays. We give definitions and algorithms to solve the games and to give a winning strategy. The objectives we consider are mostly Boolean, but we also look at quantitative graph-based games and their objectives. Synthesis aims to turn temporal logic specifications into correct reactive systems. We explain the reduction of synthesis to graph-based games (or equivalently tree automata) using synthesis of LTL specifications as an example. We treat the classical approach that uses determinization of parity automata and more modern approaches. AU - Bloem, Roderick AU - Chatterjee, Krishnendu AU - Jobstmann, Barbara ED - Henzinger, Thomas A ED - Clarke, Edmund M. ED - Veith, Helmut ED - Bloem, Roderick ID - 59 SN - 978-3-319-10574-1 T2 - Handbook of Model Checking TI - Graph games and reactive synthesis ER -