TY - JOUR
AB - Actin filaments polymerizing against membranes power endocytosis, vesicular traffic, and cell motility. In vitro reconstitution studies suggest that the structure and the dynamics of actin networks respond to mechanical forces. We demonstrate that lamellipodial actin of migrating cells responds to mechanical load when membrane tension is modulated. In a steady state, migrating cell filaments assume the canonical dendritic geometry, defined by Arp2/3-generated 70° branch points. Increased tension triggers a dense network with a broadened range of angles, whereas decreased tension causes a shift to a sparse configuration dominated by filaments growing perpendicularly to the plasma membrane. We show that these responses emerge from the geometry of branched actin: when load per filament decreases, elongation speed increases and perpendicular filaments gradually outcompete others because they polymerize the shortest distance to the membrane, where they are protected from capping. This network-intrinsic geometrical adaptation mechanism tunes protrusive force in response to mechanical load.
AU - Mueller, Jan
AU - Szep, Gregory
AU - Nemethova, Maria
AU - De Vries, Ingrid
AU - Lieber, Arnon
AU - Winkler, Christoph
AU - Kruse, Karsten
AU - Small, John
AU - Schmeiser, Christian
AU - Keren, Kinneret
AU - Hauschild, Robert
AU - Sixt, Michael K
ID - 727
IS - 1
JF - Cell
SN - 00928674
TI - Load adaptation of lamellipodial actin networks
VL - 171
ER -
TY - JOUR
AB - During animal development, cell-fate-specific changes in gene expression can modify the material properties of a tissue and drive tissue morphogenesis. While mechanistic insights into the genetic control of tissue-shaping events are beginning to emerge, how tissue morphogenesis and mechanics can reciprocally impact cell-fate specification remains relatively unexplored. Here we review recent findings reporting how multicellular morphogenetic events and their underlying mechanical forces can feed back into gene regulatory pathways to specify cell fate. We further discuss emerging techniques that allow for the direct measurement and manipulation of mechanical signals in vivo, offering unprecedented access to study mechanotransduction during development. Examination of the mechanical control of cell fate during tissue morphogenesis will pave the way to an integrated understanding of the design principles that underlie robust tissue patterning in embryonic development.
AU - Chan, Chii
AU - Heisenberg, Carl-Philipp J
AU - Hiiragi, Takashi
ID - 728
IS - 18
JF - Current Biology
SN - 09609822
TI - Coordination of morphogenesis and cell fate specification in development
VL - 27
ER -
TY - JOUR
AB - The cellular mechanisms allowing tissues to efficiently regenerate are not fully understood. In this issue of Developmental Cell, Cao et al. (2017)) discover that during zebrafish heart regeneration, epicardial cells at the leading edge of regenerating tissue undergo endoreplication, possibly due to increased tissue tension, thereby boosting their regenerative capacity.
AU - Spiro, Zoltan P
AU - Heisenberg, Carl-Philipp J
ID - 729
IS - 6
JF - Developmental Cell
SN - 15345807
TI - Regeneration tensed up polyploidy takes the lead
VL - 42
ER -
TY - JOUR
AB - Neural responses are highly structured, with population activity restricted to a small subset of the astronomical range of possible activity patterns. Characterizing these statistical regularities is important for understanding circuit computation, but challenging in practice. Here we review recent approaches based on the maximum entropy principle used for quantifying collective behavior in neural activity. We highlight recent models that capture population-level statistics of neural data, yielding insights into the organization of the neural code and its biological substrate. Furthermore, the MaxEnt framework provides a general recipe for constructing surrogate ensembles that preserve aspects of the data, but are otherwise maximally unstructured. This idea can be used to generate a hierarchy of controls against which rigorous statistical tests are possible.
AU - Savin, Cristina
AU - Tkacik, Gasper
ID - 730
JF - Current Opinion in Neurobiology
SN - 09594388
TI - Maximum entropy models as a tool for building precise neural controls
VL - 46
ER -
TY - JOUR
AB - Genetic variations in the oxytocin receptor gene affect patients with ASD and ADHD differently.
AU - Novarino, Gaia
ID - 731
IS - 411
JF - Science Translational Medicine
SN - 19466234
TI - The science of love in ASD and ADHD
VL - 9
ER -
TY - JOUR
AB - Let A and B be two N by N deterministic Hermitian matrices and let U be an N by N Haar distributed unitary matrix. It is well known that the spectral distribution of the sum H = A + UBU∗ converges weakly to the free additive convolution of the spectral distributions of A and B, as N tends to infinity. We establish the optimal convergence rate in the bulk of the spectrum.
AU - Bao, Zhigang
AU - Erdös, László
AU - Schnelli, Kevin
ID - 733
JF - Advances in Mathematics
TI - Convergence rate for spectral distribution of addition of random matrices
VL - 319
ER -
TY - JOUR
AB - Inflammation, which is a highly regulated host response against danger signals, may be harmful if it is excessive and deregulated. Ideally, anti-inflammatory therapy should autonomously commence as soon as possible after the onset of inflammation, should be controllable by a physician, and should not systemically block beneficial immune response in the long term. We describe a genetically encoded anti-inflammatory mammalian cell device based on a modular engineered genetic circuit comprising a sensor, an amplifier, a “thresholder” to restrict activation of a positive-feedback loop, a combination of advanced clinically used biopharmaceutical proteins, and orthogonal regulatory elements that linked modules into the functional device. This genetic circuit was autonomously activated by inflammatory signals, including endogenous cecal ligation and puncture (CLP)-induced inflammation in mice and serum from a systemic juvenile idiopathic arthritis (sIJA) patient, and could be reset externally by a chemical signal. The microencapsulated anti-inflammatory device significantly reduced the pathology in dextran sodium sulfate (DSS)-induced acute murine colitis, demonstrating a synthetic immunological approach for autonomous anti-inflammatory therapy.
AU - Smole, Anže
AU - Lainšček, Duško
AU - Bezeljak, Urban
AU - Horvat, Simon
AU - Jerala, Roman
ID - 7360
IS - 1
JF - Molecular Therapy
SN - 1525-0016
TI - A synthetic mammalian therapeutic gene circuit for sensing and suppressing inflammation
VL - 25
ER -
TY - CONF
AB - Modern communication technologies allow first responders to contact thousands of potential volunteers simultaneously for support during a crisis or disaster event. However, such volunteer efforts must be well coordinated and monitored, in order to offer an effective relief to the professionals. In this paper we extend earlier work on optimally assigning volunteers to selected landmark locations. In particular, we emphasize the aspect that obtaining good assignments requires not only advanced computational tools, but also a realistic measure of distance between volunteers and landmarks. Specifically, we propose the use of the Open Street Map (OSM) driving distance instead of he previously used flight distance. We find the OSM driving distance to be better aligned with the interests of volunteers and first responders. Furthermore, we show that relying on the flying distance leads to a substantial underestimation of the number of required volunteers, causing negative side effects in case of an actual crisis situation.
AU - Pielorz, Jasmin
AU - Prandtstetter, Matthias
AU - Straub, Markus
AU - Lampert, Christoph
ID - 750
SN - 978-153862714-3
T2 - 2017 IEEE International Conference on Big Data
TI - Optimal geospatial volunteer allocation needs realistic distances
ER -
TY - JOUR
AB - We introduce a common generalization of the strong Hanani–Tutte theorem and the weak Hanani–Tutte theorem: if a graph G has a drawing D in the plane where every pair of independent edges crosses an even number of times, then G has a planar drawing preserving the rotation of each vertex whose incident edges cross each other evenly in D. The theorem is implicit in the proof of the strong Hanani–Tutte theorem by Pelsmajer, Schaefer and Štefankovič. We give a new, somewhat simpler proof.
AU - Fulek, Radoslav
AU - Kynčl, Jan
AU - Pálvölgyi, Dömötör
ID - 795
IS - 3
JF - Electronic Journal of Combinatorics
SN - 10778926
TI - Unified Hanani Tutte theorem
VL - 24
ER -
TY - JOUR
AB - Phasenübergänge helfen beim Verständnis von Vielteilchensystemen in der Festkörperphysik und Fluiddynamik bis hin zur Teilchenphysik. Unserer internationalen Kollaboration ist es gelungen, einen neuartigen Phasenübergang in einem Quantensystem zu beobachten [1]. In einem Mikrowellenresonator konnte erstmals die spontane Zustandsänderung von undurchsichtig zu transparent nachgewiesen werden.
AU - Fink, Johannes M
ID - 797
IS - 3
JF - Physik in unserer Zeit
TI - Photonenblockade aufgelöst
VL - 48
ER -
TY - JOUR
AB - On January the 1st, 2016 a new agreement between 32 Austrian scientific libraries and the publisher Springer took its effect: this deal covers accessing the licensed content on the one hand, and publishing open access on the other hand. More than 1000 papers by Austrian authors were published open access at Springer in the first year alone. The working group "Springer Compact Evaluierung" made the data for these articles available via the platform OpenAPC and would like to use this opportunity to give a short account of what this publishing agreement actually entails and the working group intends to do.
AU - Andrae, Magdalena
AU - Villányi, Márton
ID - 807
IS - 2
JF - Mitteilungen der Vereinigung Österreichischer Bibliothekarinnen und Bibliothekare
SN - 10222588
TI - Der Springer Compact-Deal – Ein erster Einblick in die Evaluierung einer Offsetting-Vereinbarung
VL - 70
ER -
TY - JOUR
AB - What data is needed about data? Describing the process to answer this question for the institutional data repository IST DataRep.
AU - Petritsch, Barbara
ID - 825
IS - 2
JF - Mitteilungen der Vereinigung Österreichischer Bibliothekarinnen & Bibliothekare
SN - 10222588
TI - Metadata for research data in practice
VL - 70
ER -
TY - CHAP
AB - The advent of high-throughput technologies and the concurrent advances in information sciences have led to a data revolution in biology. This revolution is most significant in molecular biology, with an increase in the number and scale of the “omics” projects over the last decade. Genomics projects, for example, have produced impressive advances in our knowledge of the information concealed into genomes, from the many genes that encode for the proteins that are responsible for most if not all cellular functions, to the noncoding regions that are now known to provide regulatory functions. Proteomics initiatives help to decipher the role of post-translation modifications on the protein structures and provide maps of protein-protein interactions, while functional genomics is the field that attempts to make use of the data produced by these projects to understand protein functions. The biggest challenge today is to assimilate the wealth of information provided by these initiatives into a conceptual framework that will help us decipher life. For example, the current views of the relationship between protein structure and function remain fragmented. We know of their sequences, more and more about their structures, we have information on their biological activities, but we have difficulties connecting this dotted line into an informed whole. We lack the experimental and computational tools for directly studying protein structure, function, and dynamics at the molecular and supra-molecular levels. In this chapter, we review some of the current developments in building the computational tools that are needed, focusing on the role that geometry and topology play in these efforts. One of our goals is to raise the general awareness about the importance of geometric methods in elucidating the mysterious foundations of our very existence. Another goal is the broadening of what we consider a geometric algorithm. There is plenty of valuable no-man’s-land between combinatorial and numerical algorithms, and it seems opportune to explore this land with a computational-geometric frame of mind.
AU - Edelsbrunner, Herbert
AU - Koehl, Patrice
ED - Toth, Csaba
ED - O'Rourke, Joseph
ED - Goodman, Jacob
ID - 84
T2 - Handbook of Discrete and Computational Geometry, Third Edition
TI - Computational topology for structural molecular biology
ER -
TY - JOUR
AB - Cytosine methylation regulates essential genome functions across eukaryotes, but the fundamental question of whether nucleosomal or naked DNA is the preferred substrate of plant and animal methyltransferases remains unresolved. Here, we show that genetic inactivation of a single DDM1/Lsh family nucleosome remodeler biases methylation toward inter-nucleosomal linker DNA in Arabidopsis thaliana and mouse. We find that DDM1 enables methylation of DNA bound to the nucleosome, suggesting that nucleosome-free DNA is the preferred substrate of eukaryotic methyltransferases in vivo. Furthermore, we show that simultaneous mutation of DDM1 and linker histone H1 in Arabidopsis reproduces the strong linker-specific methylation patterns of species that diverged from flowering plants and animals over a billion years ago. Our results indicate that in the absence of remodeling, nucleosomes are strong barriers to DNA methyltransferases. Linker-specific methylation can evolve simply by breaking the connection between nucleosome remodeling and DNA methylation.
AU - Lyons, David B
AU - Zilberman, Daniel
ID - 9445
JF - eLife
TI - DDM1 and Lsh remodelers allow methylation of DNA wrapped in nucleosomes
VL - 6
ER -
TY - CHAP
AB - Small molecule biosensors based on Forster resonance energy transfer (FRET) enable small molecule signaling to be monitored with high spatial and temporal resolution in complex cellular environments. FRET sensors can be constructed by fusing a pair of fluorescent proteins to a suitable recognition domain, such as a member of the solute-binding protein (SBP) superfamily. However, naturally occurring SBPs may be unsuitable for incorporation into FRET sensors due to their low thermostability, which may preclude imaging under physiological conditions, or because the positions of their N- and C-termini may be suboptimal for fusion of fluorescent proteins, which may limit the dynamic range of the resulting sensors. Here, we show how these problems can be overcome using ancestral protein reconstruction and circular permutation. Ancestral protein reconstruction, used as a protein engineering strategy, leverages phylogenetic information to improve the thermostability of proteins, while circular permutation enables the termini of an SBP to be repositioned to maximize the dynamic range of the resulting FRET sensor. We also provide a protocol for cloning the engineered SBPs into FRET sensor constructs using Golden Gate assembly and discuss considerations for in situ characterization of the FRET sensors.
AU - Clifton, Ben
AU - Whitfield, Jason
AU - Sanchez Romero, Inmaculada
AU - Herde, Michel
AU - Henneberger, Christian
AU - Janovjak, Harald L
AU - Jackson, Colin
ED - Stein, Viktor
ID - 957
SN - 10643745
T2 - Synthetic Protein Switches
TI - Ancestral protein reconstruction and circular permutation for improving the stability and dynamic range of FRET sensors
VL - 1596
ER -
TY - CONF
AB - Network games are widely used as a model for selfish resource-allocation problems. In the classical model, each player selects a path connecting her source and target vertex. The cost of traversing an edge depends on the number of players that traverse it. Thus, it abstracts the fact that different users may use a resource at different times and for different durations, which plays an important role in defining the costs of the users in reality. For example, when transmitting packets in a communication network, routing traffic in a road network, or processing a task in a production system, the traversal of the network involves an inherent delay, and so sharing and congestion of resources crucially depends on time. We study timed network games , which add a time component to network games. Each vertex v in the network is associated with a cost function, mapping the load on v to the price that a player pays for staying in v for one time unit with this load. In addition, each edge has a guard, describing time intervals in which the edge can be traversed, forcing the players to spend time on vertices. Unlike earlier work that add a time component to network games, the time in our model is continuous and cannot be discretized. In particular, players have uncountably many strategies, and a game may have uncountably many pure Nash equilibria. We study properties of timed network games with cost-sharing or congestion cost functions: their stability, equilibrium inefficiency, and complexity. In particular, we show that the answer to the question whether we can restrict attention to boundary strategies, namely ones in which edges are traversed only at the boundaries of guards, is mixed.
AU - Avni, Guy
AU - Guha, Shibashis
AU - Kupferman, Orna
ID - 963
SN - 18688969
TI - Timed network games with clocks
VL - 83
ER -
TY - GEN
AB - Across the nervous system, certain population spiking patterns are observed far more frequently than others. A hypothesis about this structure is that these collective activity patterns function as population codewords–collective modes–carrying information distinct from that of any single cell. We investigate this phenomenon in recordings of ∼150 retinal ganglion cells, the retina’s output. We develop a novel statistical model that decomposes the population response into modes; it predicts the distribution of spiking activity in the ganglion cell population with high accuracy. We found that the modes represent localized features of the visual stimulus that are distinct from the features represented by single neurons. Modes form clusters of activity states that are readily discriminated from one another. When we repeated the same visual stimulus, we found that the same mode was robustly elicited. These results suggest that retinal ganglion cells’ collective signaling is endowed with a form of error-correcting code–a principle that may hold in brain areas beyond retina.
AU - Prentice, Jason
AU - Marre, Olivier
AU - Ioffe, Mark
AU - Loback, Adrianna
AU - Tkačik, Gašper
AU - Berry, Michael
ID - 9709
TI - Data from: Error-robust modes of the retinal population code
ER -
TY - JOUR
AB - While we have good understanding of bacterial metabolism at the population level, we know little about the metabolic behavior of individual cells: do single cells in clonal populations sometimes specialize on different metabolic pathways? Such metabolic specialization could be driven by stochastic gene expression and could provide individual cells with growth benefits of specialization. We measured the degree of phenotypic specialization in two parallel metabolic pathways, the assimilation of glucose and arabinose. We grew Escherichia coli in chemostats, and used isotope-labeled sugars in combination with nanometer-scale secondary ion mass spectrometry and mathematical modeling to quantify sugar assimilation at the single-cell level. We found large variation in metabolic activities between single cells, both in absolute assimilation and in the degree to which individual cells specialize in the assimilation of different sugars. Analysis of transcriptional reporters indicated that this variation was at least partially based on cell-to-cell variation in gene expression. Metabolic differences between cells in clonal populations could potentially reduce metabolic incompatibilities between different pathways, and increase the rate at which parallel reactions can be performed.
AU - Nikolic, Nela
AU - Schreiber, Frank
AU - Dal Co, Alma
AU - Kiviet, Daniel
AU - Bergmiller, Tobias
AU - Littmann, Sten
AU - Kuypers, Marcel
AU - Ackermann, Martin
ID - 541
IS - 12
JF - PLoS Genetics
SN - 15537390
TI - Cell-to-cell variation and specialization in sugar metabolism in clonal bacterial populations
VL - 13
ER -
TY - GEN
AB - information on culture conditions, phage mutagenesis, verification and lysate preparation; Raw data
AU - Pleska, Maros
AU - Guet, Calin C
ID - 9847
TI - Supplementary materials and methods; Full data set from effects of mutations in phage restriction sites during escape from restriction–modification
ER -
TY - GEN
AB - Estimates of 13 C-arabinose and 2 H-glucose uptake from the fractions of heavy isotopes measured in single cells
AU - Nikolic, Nela
AU - Schreiber, Frank
AU - Dal Co, Alma
AU - Kiviet, Daniel
AU - Bergmiller, Tobias
AU - Littmann, Sten
AU - Kuypers, Marcel
AU - Ackermann, Martin
ID - 9845
TI - Mathematical model
ER -
TY - GEN
AB - This text provides additional information about the model, a derivation of the analytic results in Eq (4), and details about simulations of an additional parameter set.
AU - Lukacisinova, Marta
AU - Novak, Sebastian
AU - Paixao, Tiago
ID - 9849
TI - Modelling and simulation details
ER -
TY - GEN
AB - In this text, we discuss how a cost of resistance and the possibility of lethal mutations impact our model.
AU - Lukacisinova, Marta
AU - Novak, Sebastian
AU - Paixao, Tiago
ID - 9850
TI - Extensions of the model
ER -
TY - GEN
AU - Nikolic, Nela
AU - Schreiber, Frank
AU - Dal Co, Alma
AU - Kiviet, Daniel
AU - Bergmiller, Tobias
AU - Littmann, Sten
AU - Kuypers, Marcel
AU - Ackermann, Martin
ID - 9846
TI - Supplementary methods
ER -
TY - JOUR
AB - In order to respond reliably to specific features of their environment, sensory neurons need to integrate multiple incoming noisy signals. Crucially, they also need to compete for the interpretation of those signals with other neurons representing similar features. The form that this competition should take depends critically on the noise corrupting these signals. In this study we show that for the type of noise commonly observed in sensory systems, whose variance scales with the mean signal, sensory neurons should selectively divide their input signals by their predictions, suppressing ambiguous cues while amplifying others. Any change in the stimulus context alters which inputs are suppressed, leading to a deep dynamic reshaping of neural receptive fields going far beyond simple surround suppression. Paradoxically, these highly variable receptive fields go alongside and are in fact required for an invariant representation of external sensory features. In addition to offering a normative account of context-dependent changes in sensory responses, perceptual inference in the presence of signal-dependent noise accounts for ubiquitous features of sensory neurons such as divisive normalization, gain control and contrast dependent temporal dynamics.
AU - Chalk, Matthew J
AU - Masset, Paul
AU - Gutkin, Boris
AU - Denève, Sophie
ID - 680
IS - 6
JF - PLoS Computational Biology
SN - 1553734X
TI - Sensory noise predicts divisive reshaping of receptive fields
VL - 13
ER -
TY - GEN
AB - Based on the intuitive derivation of the dynamics of SIM allele frequency pM in the main text, we present a heuristic prediction for the long-term SIM allele frequencies with χ > 1 stresses and compare it to numerical simulations.
AU - Lukacisinova, Marta
AU - Novak, Sebastian
AU - Paixao, Tiago
ID - 9851
TI - Heuristic prediction for multiple stresses
ER -
TY - GEN
AB - We show how different combination strategies affect the fraction of individuals that are multi-resistant.
AU - Lukacisinova, Marta
AU - Novak, Sebastian
AU - Paixao, Tiago
ID - 9852
TI - Resistance frequencies for different combination strategies
ER -
TY - GEN
AB - Includes derivation of optimal estimation algorithm, generalisation to non-poisson noise statistics, correlated input noise, and implementation of in a multi-layer neural network.
AU - Chalk, Matthew J
AU - Masset, Paul
AU - Gutkin, Boris
AU - Denève, Sophie
ID - 9855
TI - Supplementary appendix
ER -
TY - CONF
AB - Recently there has been a proliferation of automated program repair (APR) techniques, targeting various programming languages. Such techniques can be generally classified into two families: syntactic- and semantics-based. Semantics-based APR, on which we focus, typically uses symbolic execution to infer semantic constraints and then program synthesis to construct repairs conforming to them. While syntactic-based APR techniques have been shown successful on bugs in real-world programs written in both C and Java, semantics-based APR techniques mostly target C programs. This leaves empirical comparisons of the APR families not fully explored, and developers without a Java-based semantics APR technique. We present JFix, a semantics-based APR framework that targets Java, and an associated Eclipse plugin. JFix is implemented atop Symbolic PathFinder, a well-known symbolic execution engine for Java programs. It extends one particular APR technique (Angelix), and is designed to be sufficiently generic to support a variety of such techniques. We demonstrate that semantics-based APR can indeed efficiently and effectively repair a variety of classes of bugs in large real-world Java programs. This supports our claim that the framework can both support developers seeking semantics-based repair of bugs in Java programs, as well as enable larger scale empirical studies comparing syntactic- and semantics-based APR targeting Java. The demonstration of our tool is available via the project website at: https://xuanbachle.github.io/semanticsrepair/
AU - Le, Xuan
AU - Chu, Duc Hiep
AU - Lo, David
AU - Le Goues, Claire
AU - Visser, Willem
ID - 941
T2 - Proceedings of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis
TI - JFIX: Semantics-based repair of Java programs via symbolic PathFinder
ER -
TY - JOUR
AB - Methylation in the bodies of active genes is common in animals and vascular plants. Evolutionary patterns indicate homeostatic functions for this type of methylation.
AU - Zilberman, Daniel
ID - 9506
IS - 1
JF - Genome Biology
SN - 1474-760X
TI - An evolutionary case for functional gene body methylation in plants and animals
VL - 18
ER -
TY - CHAP
AB - Biosensors that exploit Forster resonance energy transfer (FRET) can be used to visualize biological and physiological processes and are capable of providing detailed information in both spatial and temporal dimensions. In a FRET-based biosensor, substrate binding is associated with a change in the relative positions of two fluorophores, leading to a change in FRET efficiency that may be observed in the fluorescence spectrum. As a result, their design requires a ligand-binding protein that exhibits a conformational change upon binding. However, not all ligand-binding proteins produce responsive sensors upon conjugation to fluorescent proteins or dyes, and identifying the optimum locations for the fluorophores often involves labor-intensive iterative design or high-throughput screening. Combining the genetic fusion of a fluorescent protein to the ligand-binding protein with site-specific covalent attachment of a fluorescent dye can allow fine control over the positions of the two fluorophores, allowing the construction of very sensitive sensors. This relies upon the accurate prediction of the locations of the two fluorophores in bound and unbound states. In this chapter, we describe a method for computational identification of dye-attachment sites that allows the use of cysteine modification to attach synthetic dyes that can be paired with a fluorescent protein for the purposes of creating FRET sensors.
AU - Mitchell, Joshua
AU - Zhang, William
AU - Herde, Michel
AU - Henneberger, Christian
AU - Janovjak, Harald L
AU - O'Mara, Megan
AU - Jackson, Colin
ED - Stein, Viktor
ID - 958
SN - 10643745
T2 - Synthetic Protein Switches
TI - Method for developing optical sensors using a synthetic dye fluorescent protein FRET pair and computational modeling and assessment
VL - 1596
ER -
TY - GEN
AB - Branching morphogenesis of the epithelial ureteric bud forms the renal collecting duct system and is critical for normal nephron number, while low nephron number is implicated in hypertension and renal disease. Ureteric bud growth and branching requires GDNF signaling from the surrounding mesenchyme to cells at the ureteric bud tips, via the Ret receptor tyrosine kinase and coreceptor Gfrα1; Ret signaling up-regulates transcription factors Etv4 and Etv5, which are also critical for branching. Despite extensive knowledge of the genetic control of these events, it is not understood, at the cellular level, how renal branching morphogenesis is achieved or how Ret signaling influences epithelial cell behaviors to promote this process. Analysis of chimeric embryos previously suggested a role for Ret signaling in promoting cell rearrangements in the nephric duct, but this method was unsuited to study individual cell behaviors during ureteric bud branching. Here, we use Mosaic Analysis with Double Markers (MADM), combined with organ culture and time-lapse imaging, to trace the movements and divisions of individual ureteric bud tip cells. We first examine wild-type clones and then Ret or Etv4 mutant/wild-type clones in which the mutant and wild-type sister cells are differentially and heritably marked by green and red fluorescent proteins. We find that, in normal kidneys, most individual tip cells behave as self-renewing progenitors, some of whose progeny remain at the tips while others populate the growing UB trunks. In Ret or Etv4 MADM clones, the wild-type cells generated at a UB tip are much more likely to remain at, or move to, the new tips during branching and elongation, while their Ret−/− or Etv4−/− sister cells tend to lag behind and contribute only to the trunks. By tracking successive mitoses in a cell lineage, we find that Ret signaling has little effect on proliferation, in contrast to its effects on cell movement. Our results show that Ret/Etv4 signaling promotes directed cell movements in the ureteric bud tips, and suggest a model in which these cell movements mediate branching morphogenesis.
AU - Riccio, Paul
AU - Cebrián, Christina
AU - Zong, Hui
AU - Hippenmeyer, Simon
AU - Costantini, Frank
ID - 9707
TI - Data from: Ret and Etv4 promote directed movements of progenitor cells during renal branching morphogenesis
ER -
TY - GEN
AU - Nikolic, Nela
AU - Schreiber, Frank
AU - Dal Co, Alma
AU - Kiviet, Daniel
AU - Bergmiller, Tobias
AU - Littmann, Sten
AU - Kuypers, Marcel
AU - Ackermann, Martin
ID - 9844
TI - Source data for figures and tables
ER -
TY - GEN
AU - Schlögl, Alois
AU - Kiss, Janos
ID - 12905
T2 - AHPC17 – Austrian HPC Meeting 2017
TI - Scientific Computing at IST Austria
ER -
TY - CONF
AB - Transforming deterministic ω
-automata into deterministic parity automata is traditionally done using variants of appearance records. We present a more efficient variant of this approach, tailored to Rabin automata, and several optimizations applicable to all appearance records. We compare the methods experimentally and find out that our method produces smaller automata than previous approaches. Moreover, the experiments demonstrate the potential of our method for LTL synthesis, using LTL-to-Rabin translators. It leads to significantly smaller parity automata when compared to state-of-the-art approaches on complex formulae.
AU - Kretinsky, Jan
AU - Meggendorfer, Tobias
AU - Waldmann, Clara
AU - Weininger, Maximilian
ID - 13160
SN - 0302-9743
T2 - Tools and Algorithms for the Construction and Analysis of Systems
TI - Index appearance record for transforming Rabin automata into parity automata
VL - 10205
ER -
TY - CONF
AB - Two-player games on graphs are widely studied in formal methods as they model the interaction between a system and its environment. The game is played by moving a token throughout a graph to produce an infinite path. There are several common modes to determine how the players move the token through the graph; e.g., in turn-based games the players alternate turns in moving the token. We study the bidding mode of moving the token, which, to the best of our knowledge, has never been studied in infinite-duration games. Both players have separate budgets, which sum up to $1$. In each turn, a bidding takes place. Both players submit bids simultaneously, and a bid is legal if it does not exceed the available budget. The winner of the bidding pays his bid to the other player and moves the token. For reachability objectives, repeated bidding games have been studied and are called Richman games. There, a central question is the existence and computation of threshold budgets; namely, a value t\in [0,1] such that if\PO's budget exceeds $t$, he can win the game, and if\PT's budget exceeds 1-t, he can win the game. We focus on parity games and mean-payoff games. We show the existence of threshold budgets in these games, and reduce the problem of finding them to Richman games. We also determine the strategy-complexity of an optimal strategy. Our most interesting result shows that memoryless strategies suffice for mean-payoff bidding games.
AU - Avni, Guy
AU - Henzinger, Thomas A
AU - Chonev, Ventsislav K
ID - 950
SN - 1868-8969
TI - Infinite-duration bidding games
VL - 85
ER -
TY - CONF
AB - Given a triangulation of a point set in the plane, a flip deletes an edge e whose removal leaves a convex quadrilateral, and replaces e by the opposite diagonal of the quadrilateral. It is well known that any triangulation of a point set can be reconfigured to any other triangulation by some sequence of flips. We explore this question in the setting where each edge of a triangulation has a label, and a flip transfers the label of the removed edge to the new edge. It is not true that every labelled triangulation of a point set can be reconfigured to every other labelled triangulation via a sequence of flips, but we characterize when this is possible. There is an obvious necessary condition: for each label l, if edge e has label l in the first triangulation and edge f has label l in the second triangulation, then there must be some sequence of flips that moves label l from e to f, ignoring all other labels. Bose, Lubiw, Pathak and Verdonschot formulated the Orbit Conjecture, which states that this necessary condition is also sufficient, i.e. that all labels can be simultaneously mapped to their destination if and only if each label individually can be mapped to its destination. We prove this conjecture. Furthermore, we give a polynomial-time algorithm to find a sequence of flips to reconfigure one labelled triangulation to another, if such a sequence exists, and we prove an upper bound of O(n7) on the length of the flip sequence. Our proof uses the topological result that the sets of pairwise non-crossing edges on a planar point set form a simplicial complex that is homeomorphic to a high-dimensional ball (this follows from a result of Orden and Santos; we give a different proof based on a shelling argument). The dual cell complex of this simplicial ball, called the flip complex, has the usual flip graph as its 1-skeleton. We use properties of the 2-skeleton of the flip complex to prove the Orbit Conjecture.
AU - Lubiw, Anna
AU - Masárová, Zuzana
AU - Wagner, Uli
ID - 683
TI - A proof of the orbit conjecture for flipping edge labelled triangulations
VL - 77
ER -
TY - JOUR
AB - DNA methylation regulates eukaryotic gene expression and is extensively reprogrammed during animal development. However, whether developmental methylation reprogramming during the sporophytic life cycle of flowering plants regulates genes is presently unknown. Here we report a distinctive gene-targeted RNA-directed DNA methylation (RdDM) activity in the Arabidopsis thaliana male sexual lineage that regulates gene expression in meiocytes. Loss of sexual-lineage-specific RdDM causes mis-splicing of the MPS1 gene (also known as PRD2), thereby disrupting meiosis. Our results establish a regulatory paradigm in which de novo methylation creates a cell-lineage-specific epigenetic signature that controls gene expression and contributes to cellular function in flowering plants.
AU - Walker, James
AU - Gao, Hongbo
AU - Zhang, Jingyi
AU - Aldridge, Billy
AU - Vickers, Martin
AU - Higgins, James D.
AU - Feng, Xiaoqi
ID - 12193
IS - 1
JF - Nature Genetics
KW - Genetics
SN - 1061-4036
TI - Sexual-lineage-specific DNA methylation regulates meiosis in Arabidopsis
VL - 50
ER -
TY - THES
AB - This dissertation concerns the automatic verification of probabilistic systems and programs with arrays by statistical and logical methods. Although statistical and logical methods are different in nature, we show that they can be successfully combined for system analysis. In the first part of the dissertation we present a new statistical algorithm for the verification of probabilistic systems with respect to unbounded properties, including linear temporal logic. Our algorithm often performs faster than the previous approaches, and at the same time requires less information about the system. In addition, our method can be generalized to unbounded quantitative properties such as mean-payoff bounds. In the second part, we introduce two techniques for comparing probabilistic systems. Probabilistic systems are typically compared using the notion of equivalence, which requires the systems to have the equal probability of all behaviors. However, this notion is often too strict, since probabilities are typically only empirically estimated, and any imprecision may break the relation between processes. On the one hand, we propose to replace the Boolean notion of equivalence by a quantitative distance of similarity. For this purpose, we introduce a statistical framework for estimating distances between Markov chains based on their simulation runs, and we investigate which distances can be approximated in our framework. On the other hand, we propose to compare systems with respect to a new qualitative logic, which expresses that behaviors occur with probability one or a positive probability. This qualitative analysis is robust with respect to modeling errors and applicable to many domains. In the last part, we present a new quantifier-free logic for integer arrays, which allows us to express counting. Counting properties are prevalent in array-manipulating programs, however they cannot be expressed in the quantified fragments of the theory of arrays. We present a decision procedure for our logic, and provide several complexity results.
AU - Daca, Przemyslaw
ID - 1155
SN - 2663-337X
TI - Statistical and logical methods for property checking
ER -
TY - THES
AB - Bacteria and their pathogens – phages – are the most abundant living entities on Earth. Throughout their coevolution, bacteria have evolved multiple immune systems to overcome the ubiquitous threat from the phages. Although the molecu- lar details of these immune systems’ functions are relatively well understood, their epidemiological consequences for the phage-bacterial communities have been largely neglected. In this thesis we employed both experimental and theoretical methods to explore whether herd and social immunity may arise in bacterial popu- lations. Using our experimental system consisting of Escherichia coli strains with a CRISPR based immunity to the T7 phage we show that herd immunity arises in phage-bacterial communities and that it is accentuated when the populations are spatially structured. By fitting a mathematical model, we inferred expressions for the herd immunity threshold and the velocity of spread of a phage epidemic in partially resistant bacterial populations, which both depend on the bacterial growth rate, phage burst size and phage latent period. We also investigated the poten- tial for social immunity in Streptococcus thermophilus and its phage 2972 using a bioinformatic analysis of potentially coding short open reading frames with a signalling signature, encoded within the CRISPR associated genes. Subsequently, we tested one identified potentially signalling peptide and found that its addition to a phage-challenged culture increases probability of survival of bacteria two fold, although the results were only marginally significant. Together, these results demonstrate that the ubiquitous arms races between bacteria and phages have further consequences at the level of the population.
AU - Payne, Pavel
ID - 6291
SN - 2663-337X
TI - Bacterial herd and social immunity to phages
ER -
TY - JOUR
AB - Restriction–modification systems are widespread genetic elements that protect bacteria from bacteriophage infections by recognizing and cleaving heterologous DNA at short, well-defined sequences called restriction sites. Bioinformatic evidence shows that restriction sites are significantly underrepresented in bacteriophage genomes, presumably because bacteriophages with fewer restriction sites are more likely to escape cleavage by restriction–modification systems. However, how mutations in restriction sites affect the likelihood of bacteriophage escape is unknown. Using the bacteriophage l and the restriction–modification system EcoRI, we show that while mutation effects at different restriction sites are unequal, they are independent. As a result, the probability of bacteriophage escape increases with each mutated restriction site. Our results experimentally support the role of restriction site avoidance as a response to selection imposed by restriction–modification systems and offer an insight into the events underlying the process of bacteriophage escape.
AU - Pleska, Maros
AU - Guet, Calin C
ID - 561
IS - 12
JF - Biology Letters
SN - 1744-9561
TI - Effects of mutations in phage restriction sites during escape from restriction–modification
VL - 13
ER -
TY - THES
AB - Antibiotics have diverse effects on bacteria, including massive changes in bacterial gene expression. Whereas the gene expression changes under many antibiotics have been measured, the temporal organization of these responses and their dependence on the bacterial growth rate are unclear. As described in Chapter 1, we quantified the temporal gene expression changes in the bacterium Escherichia coli in response to the sudden exposure to antibiotics using a fluorescent reporter library and a robotic system. Our data show temporally structured gene expression responses, with response times for individual genes ranging from tens of minutes to several hours. We observed that many stress response genes were activated in response to antibiotics. As certain stress responses cross-protect bacteria from other stressors, we then asked whether cellular responses to antibiotics have a similar protective role in Chapter 2. Indeed, we found that the trimethoprim-induced acid stress response protects bacteria from subsequent acid stress. We combined microfluidics with time-lapse imaging to monitor survival, intracellular pH, and acid stress response in single cells. This approach revealed that the variable expression of the acid resistance operon gadBC strongly correlates with single-cell survival time. Cells with higher gadBC expression following trimethoprim maintain higher intracellular pH and survive the acid stress longer. Overall, we provide a way to identify single-cell cross-protection between antibiotics and environmental stressors from temporal gene expression data, and show how antibiotics can increase bacterial fitness in changing environments. While gene expression changes to antibiotics show a clear temporal structure at the population-level, it is unclear whether this clear temporal order is followed by every single cell. Using dual-reporter strains described in Chapter 3, we measured gene expression dynamics of promoter pairs in the same cells using microfluidics and microscopy. Chapter 4 shows that the oxidative stress response and the DNA stress response showed little timing variability and a clear temporal order under the antibiotic nitrofurantoin. In contrast, the acid stress response under trimethoprim ran independently from all other activated response programs including the DNA stress response, which showed particularly high timing variability in this stress condition. In summary, this approach provides insight into the temporal organization of gene expression programs at the single-cell level and suggests dependencies between response programs and the underlying variability-introducing mechanisms. Altogether, this work advances our understanding of the diverse effects that antibiotics have on bacteria. These results were obtained by taking into account gene expression dynamics, which allowed us to identify general principles, molecular mechanisms, and dependencies between genes. Our findings may have implications for infectious disease treatments, and microbial communities in the human body and in nature.
AU - Mitosch, Karin
ID - 818
SN - 2663-337X
TI - Timing, variability and cross-protection in bacteria – insights from dynamic gene expression responses to antibiotics
ER -
TY - JOUR
AB - Background: Social insects form densely crowded societies in environments with high pathogen loads, but have evolved collective defences that mitigate the impact of disease. However, colony-founding queens lack this protection and suffer high rates of mortality. The impact of pathogens may be exacerbated in species where queens found colonies together, as healthy individuals may contract pathogens from infectious co-founders. Therefore, we tested whether ant queens avoid founding colonies with pathogen-exposed conspecifics and how they might limit disease transmission from infectious individuals. Results: Using Lasius Niger queens and a naturally infecting fungal pathogen Metarhizium brunneum, we observed that queens were equally likely to found colonies with another pathogen-exposed or sham-treated queen. However, when one queen died, the surviving individual performed biting, burial and removal of the corpse. These undertaking behaviours were performed prophylactically, i.e. targeted equally towards non-infected and infected corpses, as well as carried out before infected corpses became infectious. Biting and burial reduced the risk of the queens contracting and dying from disease from an infectious corpse of a dead co-foundress. Conclusions: We show that co-founding ant queens express undertaking behaviours that, in mature colonies, are performed exclusively by workers. Such infection avoidance behaviours act before the queens can contract the disease and will therefore improve the overall chance of colony founding success in ant queens.
AU - Pull, Christopher
AU - Cremer, Sylvia
ID - 732
IS - 1
JF - BMC Evolutionary Biology
SN - 14712148
TI - Co-founding ant queens prevent disease by performing prophylactic undertaking behaviour
VL - 17
ER -
TY - JOUR
AB - Antibiotics elicit drastic changes in microbial gene expression, including the induction of stress response genes. While certain stress responses are known to “cross-protect” bacteria from other stressors, it is unclear whether cellular responses to antibiotics have a similar protective role. By measuring the genome-wide transcriptional response dynamics of Escherichia coli to four antibiotics, we found that trimethoprim induces a rapid acid stress response that protects bacteria from subsequent exposure to acid. Combining microfluidics with time-lapse imaging to monitor survival and acid stress response in single cells revealed that the noisy expression of the acid resistance operon gadBC correlates with single-cell survival. Cells with higher gadBC expression following trimethoprim maintain higher intracellular pH and survive the acid stress longer. The seemingly random single-cell survival under acid stress can therefore be predicted from gadBC expression and rationalized in terms of GadB/C molecular function. Overall, we provide a roadmap for identifying the molecular mechanisms of single-cell cross-protection between antibiotics and other stressors.
AU - Mitosch, Karin
AU - Rieckh, Georg
AU - Bollenbach, Tobias
ID - 666
IS - 4
JF - Cell Systems
SN - 24054712
TI - Noisy response to antibiotic stress predicts subsequent single cell survival in an acidic environment
VL - 4
ER -
TY - THES
AB - This dissertation focuses on algorithmic aspects of program verification, and presents modeling and complexity advances on several problems related to the
static analysis of programs, the stateless model checking of concurrent programs, and the competitive analysis of real-time scheduling algorithms.
Our contributions can be broadly grouped into five categories.
Our first contribution is a set of new algorithms and data structures for the quantitative and data-flow analysis of programs, based on the graph-theoretic notion of treewidth.
It has been observed that the control-flow graphs of typical programs have special structure, and are characterized as graphs of small treewidth.
We utilize this structural property to provide faster algorithms for the quantitative and data-flow analysis of recursive and concurrent programs.
In most cases we make an algebraic treatment of the considered problem,
where several interesting analyses, such as the reachability, shortest path, and certain kind of data-flow analysis problems follow as special cases.
We exploit the constant-treewidth property to obtain algorithmic improvements for on-demand versions of the problems,
and provide data structures with various tradeoffs between the resources spent in the preprocessing and querying phase.
We also improve on the algorithmic complexity of quantitative problems outside the algebraic path framework,
namely of the minimum mean-payoff, minimum ratio, and minimum initial credit for energy problems.
Our second contribution is a set of algorithms for Dyck reachability with applications to data-dependence analysis and alias analysis.
In particular, we develop an optimal algorithm for Dyck reachability on bidirected graphs, which are ubiquitous in context-insensitive, field-sensitive points-to analysis.
Additionally, we develop an efficient algorithm for context-sensitive data-dependence analysis via Dyck reachability,
where the task is to obtain analysis summaries of library code in the presence of callbacks.
Our algorithm preprocesses libraries in almost linear time, after which the contribution of the library in the complexity of the client analysis is (i)~linear in the number of call sites and (ii)~only logarithmic in the size of the whole library, as opposed to linear in the size of the whole library.
Finally, we prove that Dyck reachability is Boolean Matrix Multiplication-hard in general, and the hardness also holds for graphs of constant treewidth.
This hardness result strongly indicates that there exist no combinatorial algorithms for Dyck reachability with truly subcubic complexity.
Our third contribution is the formalization and algorithmic treatment of the Quantitative Interprocedural Analysis framework.
In this framework, the transitions of a recursive program are annotated as good, bad or neutral, and receive a weight which measures
the magnitude of their respective effect.
The Quantitative Interprocedural Analysis problem asks to determine whether there exists an infinite run of the program where the long-run ratio of the bad weights over the good weights is above a given threshold.
We illustrate how several quantitative problems related to static analysis of recursive programs can be instantiated in this framework,
and present some case studies to this direction.
Our fourth contribution is a new dynamic partial-order reduction for the stateless model checking of concurrent programs. Traditional approaches rely on the standard Mazurkiewicz equivalence between traces, by means of partitioning the trace space into equivalence classes, and attempting to explore a few representatives from each class.
We present a new dynamic partial-order reduction method called the Data-centric Partial Order Reduction (DC-DPOR).
Our algorithm is based on a new equivalence between traces, called the observation equivalence.
DC-DPOR explores a coarser partitioning of the trace space than any exploration method based on the standard Mazurkiewicz equivalence.
Depending on the program, the new partitioning can be even exponentially coarser.
Additionally, DC-DPOR spends only polynomial time in each explored class.
Our fifth contribution is the use of automata and game-theoretic verification techniques in the competitive analysis and synthesis of real-time scheduling algorithms for firm-deadline tasks.
On the analysis side, we leverage automata on infinite words to compute the competitive ratio of real-time schedulers subject to various environmental constraints.
On the synthesis side, we introduce a new instance of two-player mean-payoff partial-information games, and show
how the synthesis of an optimal real-time scheduler can be reduced to computing winning strategies in this new type of games.
AU - Pavlogiannis, Andreas
ID - 821
SN - 2663-337X
TI - Algorithmic advances in program analysis and their applications
ER -
TY - THES
AB - The lac operon is a classic model system for bacterial gene regulation, and has been studied extensively in E. coli, a classic model organism. However, not much is known about E. coli’s ecology and life outside the laboratory, in particular in soil and water environments. The natural diversity of the lac operon outside the laboratory, its role in the ecology of E. coli and the selection pressures it is exposed to, are similarly unknown.
In Chapter Two of this thesis, I explore the genetic diversity, phylogenetic history and signatures of selection of the lac operon across 20 natural isolates of E. coli and divergent clades of Escherichia. I found that complete lac operons were present in all isolates examined, which in all but one case were functional. The lac operon phylogeny conformed to the whole-genome phylogeny of the divergent Escherichia clades, which excludes horizontal gene transfer as an explanation for the presence of functional lac operons in these clades. All lac operon genes showed a signature of purifying selection; this signature was strongest for the lacY gene. Lac operon genes of human and environmental isolates showed similar signatures of selection, except the lacZ gene, which showed a stronger signature of selection in environmental isolates.
In Chapter Three, I try to identify the natural genetic variation relevant for phenotype and fitness in the lac operon, comparing growth rate on lactose and LacZ activity of the lac operons of these wild isolates in a common genetic background. Sequence variation in the lac promoter region, upstream of the -10 and -35 RNA polymerase binding motif, predicted variation in LacZ activity at full induction, using a thermodynamic model of polymerase binding (Tugrul, 2016). However, neither variation in LacZ activity, nor RNA polymerase binding predicted by the model correlated with variation in growth rate. Lac operons of human and environmental isolates did not differ systematically in either growth rate on lactose or LacZ protein activity, suggesting that these lac operons have been exposed to similar selection pressures. We thus have no evidence that the phenotypic variation we measured is relevant for fitness.
To start assessing the effect of genomic background on the growth phenotype conferred by the lac operon, I compared growth on minimal medium with lactose between lac operon constructs and the corresponding original isolates, I found that maximal growth rate was determined by genomic background, with almost all backgrounds conferring higher growth rates than lab strain K12 MG1655. However, I found no evidence that the lactose concentration at which growth was half maximal depended on genomic background.
AU - Jesse, Fabienne
ID - 820
SN - 2663-337X
TI - The lac operon in the wild
ER -
TY - THES
AB - This thesis describes a brittle fracture simulation method for visual effects applications. Building upon a symmetric Galerkin boundary element method, we first compute stress intensity factors following the theory of linear elastic fracture mechanics. We then use these stress intensities to simulate the motion of a propagating crack front at a significantly higher resolution than the overall deformation of the breaking object. Allowing for spatial variations of the material's toughness during crack propagation produces visually realistic, highly-detailed fracture surfaces. Furthermore, we introduce approximations for stress intensities and crack opening displacements, resulting in both practical speed-up and theoretically superior runtime complexity compared to previous methods. While we choose a quasi-static approach to fracture mechanics, ignoring dynamic deformations, we also couple our fracture simulation framework to a standard rigid-body dynamics solver, enabling visual effects artists to simulate both large scale motion, as well as fracturing due to collision forces in a combined system. As fractures inside of an object grow, their geometry must be represented both in the coarse boundary element mesh, as well as at the desired fine output resolution. Using a boundary element method, we avoid complicated volumetric meshing operations. Instead we describe a simple set of surface meshing operations that allow us to progressively add cracks to the mesh of an object and still re-use all previously computed entries of the linear boundary element system matrix. On the high resolution level, we opt for an implicit surface representation. We then describe how to capture fracture surfaces during crack propagation, as well as separate the individual fragments resulting from the fracture process, based on this implicit representation. We show results obtained with our method, either solving the full boundary element system in every time step, or alternatively using our fast approximations. These results demonstrate that both of these methods perform well in basic test cases and produce realistic fracture surfaces. Furthermore we show that our fast approximations substantially out-perform the standard approach in more demanding scenarios. Finally, these two methods naturally combine, using the full solution while the problem size is manageably small and switching to the fast approximations later on. The resulting hybrid method gives the user a direct way to choose between speed and accuracy of the simulation.
AU - Hahn, David
ID - 839
SN - 2663-337X
TI - Brittle fracture simulation with boundary elements for computer graphics
ER -
TY - THES
AB - In this thesis we discuss the exact security of message authentications codes HMAC , NMAC , and PMAC . NMAC is a mode of operation which turns a fixed input-length keyed hash function f into a variable input-length function. A practical single-key variant of NMAC called HMAC is a very popular and widely deployed message authentication code (MAC). PMAC is a block-cipher based mode of operation, which also happens to be the most famous fully parallel MAC. NMAC was introduced by Bellare, Canetti and Krawczyk Crypto’96, who proved it to be a secure pseudorandom function (PRF), and thus also a MAC, under two assumptions. Unfortunately, for many instantiations of HMAC one of them has been found to be wrong. To restore the provable guarantees for NMAC , Bellare [Crypto’06] showed its security without this assumption. PMAC was introduced by Black and Rogaway at Eurocrypt 2002. If instantiated with a pseudorandom permutation over n -bit strings, PMAC constitutes a provably secure variable input-length PRF. For adversaries making q queries, each of length at most ` (in n -bit blocks), and of total length σ ≤ q` , the original paper proves an upper bound on the distinguishing advantage of O ( σ 2 / 2 n ), while the currently best bound is O ( qσ/ 2 n ). In this work we show that this bound is tight by giving an attack with advantage Ω( q 2 `/ 2 n ). In the PMAC construction one initially XORs a mask to every message block, where the mask for the i th block is computed as τ i := γ i · L , where L is a (secret) random value, and γ i is the i -th codeword of the Gray code. Our attack applies more generally to any sequence of γ i ’s which contains a large coset of a subgroup of GF (2 n ). As for NMAC , our first contribution is a simpler and uniform proof: If f is an ε -secure PRF (against q queries) and a δ - non-adaptively secure PRF (against q queries), then NMAC f is an ( ε + `qδ )-secure PRF against q queries of length at most ` blocks each. We also show that this ε + `qδ bound is basically tight by constructing an f for which an attack with advantage `qδ exists. Moreover, we analyze the PRF-security of a modification of NMAC called NI by An and Bellare that avoids the constant rekeying on multi-block messages in NMAC and allows for an information-theoretic analysis. We carry out such an analysis, obtaining a tight `q 2 / 2 c bound for this step, improving over the trivial bound of ` 2 q 2 / 2 c . Finally, we investigate, if the security of PMAC can be further improved by using τ i ’s that are k -wise independent, for k > 1 (the original has k = 1). We observe that the security of PMAC will not increase in general if k = 2, and then prove that the security increases to O ( q 2 / 2 n ), if the k = 4. Due to simple extension attacks, this is the best bound one can hope for, using any distribution on the masks. Whether k = 3 is already sufficient to get this level of security is left as an open problem. Keywords: Message authentication codes, Pseudorandom functions, HMAC, PMAC.
AU - Rybar, Michal
ID - 838
SN - 2663-337X
TI - (The exact security of) Message authentication codes
ER -
TY - JOUR
AB - PMAC is a simple and parallel block-cipher mode of operation, which was introduced by Black and Rogaway at Eurocrypt 2002. If instantiated with a (pseudo)random permutation over n-bit strings, PMAC constitutes a provably secure variable input-length (pseudo)random function. For adversaries making q queries, each of length at most l (in n-bit blocks), and of total length σ ≤ ql, the original paper proves an upper bound on the distinguishing advantage of Ο(σ2/2n), while the currently best bound is Ο (qσ/2n).In this work we show that this bound is tight by giving an attack with advantage Ω (q2l/2n). In the PMAC construction one initially XORs a mask to every message block, where the mask for the ith block is computed as τi := γi·L, where L is a (secret) random value, and γi is the i-th codeword of the Gray code. Our attack applies more generally to any sequence of γi’s which contains a large coset of a subgroup of GF(2n). We then investigate if the security of PMAC can be further improved by using τi’s that are k-wise independent, for k > 1 (the original distribution is only 1-wise independent). We observe that the security of PMAC will not increase in general, even if the masks are chosen from a 2-wise independent distribution, and then prove that the security increases to O(q<2/2n), if the τi are 4-wise independent. Due to simple extension attacks, this is the best bound one can hope for, using any distribution on the masks. Whether 3-wise independence is already sufficient to get this level of security is left as an open problem.
AU - Gazi, Peter
AU - Pietrzak, Krzysztof Z
AU - Rybar, Michal
ID - 6196
IS - 2
JF - IACR Transactions on Symmetric Cryptology
TI - The exact security of PMAC
VL - 2016
ER -
TY - DATA
AB - Includes source codes, test cases, and example data used in the thesis Brittle Fracture Simulation with Boundary Elements for Computer Graphics. Also includes pre-built binaries of the HyENA library, but not sources - please contact the HyENA authors to obtain these sources if required (https://mech.tugraz.at/hyena)
AU - Hahn, David
ID - 5568
KW - Boundary elements
KW - brittle fracture
KW - computer graphics
KW - fracture simulation
TI - Source codes: Brittle fracture simulation with boundary elements for computer graphics
ER -
TY - THES
AB - The hippocampus is a key brain region for memory and notably for spatial memory, and is needed for both spatial working and reference memories. Hippocampal place cells selectively discharge in specific locations of the environment to form mnemonic represen tations of space. Several behavioral protocols have been designed to test spatial memory which requires the experimental subject to utilize working memory and reference memory. However, less is known about how these memory traces are presented in the hippo campus, especially considering tasks that require both spatial working and long -term reference memory demand. The aim of my thesis was to elucidate how spatial working memory, reference memory, and the combination of both are represented in the hippocampus. In this thesis, using a radial eight -arm maze, I examined how the combined demand on these memories influenced place cell assemblies while reference memories were partially updated by changing some of the reward- arms. This was contrasted with task varian ts requiring working or reference memories only. Reference memory update led to gradual place field shifts towards the rewards on the switched arms. Cells developed enhanced firing in passes between newly -rewarded arms as compared to those containing an unchanged reward. The working memory task did not show such gradual changes. Place assemblies on occasions replayed trajectories of the maze; at decision points the next arm choice was preferentially replayed in tasks needing reference memory while in the pure working memory task the previously visited arm was replayed. Hence trajectory replay only reflected the decision of the animal in tasks needing reference memory update. At the reward locations, in all three tasks outbound trajectories of the current arm were preferentially replayed, showing the animals’ next path to the center. At reward locations trajectories were replayed preferentially in reverse temporal order. Moreover, in the center reverse replay was seen in the working memory task but in the other tasks forward replay was seen. Hence, the direction of reactivation was determined by the goal locations so that part of the trajectory which was closer to the goal was reactivated later in an HSE while places further away from the goal were reactivated earlier. Altogether my work demonstrated that reference memory update triggers several levels of reorganization of the hippocampal cognitive map which are not seen in simpler working memory demand s. Moreover, hippocampus is likely to be involved in spatial decisions through reactivating planned trajectories when reference memory recall is required for such a decision.
AU - Xu, Haibing
ID - 837
SN - 2663-337X
TI - Reactivation of the hippocampal cognitive map in goal-directed spatial tasks
ER -
TY - THES
AB - The thesis encompasses several topics of plant cell biology which were studied in the model plant Arabidopsis thaliana. Chapter 1 concerns the plant hormone auxin and its polar transport through cells and tissues. The highly controlled, directional transport of auxin is facilitated by plasma membrane-localized transporters. Transporters from the PIN family direct auxin transport due to their polarized localizations at cell membranes. Substantial effort has been put into research on cellular trafficking of PIN proteins, which is thought to underlie their polar distribution. I participated in a forward genetic screen aimed at identifying novel regulators of PIN polarity. The screen yielded several genes which may be involved in PIN polarity regulation or participate in polar auxin transport by other means. Chapter 2 focuses on the endomembrane system, with particular attention to clathrin-mediated endocytosis. The project started with identification of several proteins that interact with clathrin light chains. Among them, I focused on two putative homologues of auxilin, which in non-plant systems is an endocytotic factor known for uncoating clathrin-coated vesicles in the final step of endocytosis. The body of my work consisted of an in-depth characterization of transgenic A. thaliana lines overexpressing these putative auxilins in an inducible manner. Overexpression of these proteins leads to an inhibition of endocytosis, as documented by imaging of cargoes and clathrin-related endocytic machinery. An extension of this work is an investigation into a concept of homeostatic regulation acting between distinct transport processes in the endomembrane system. With auxilin overexpressing lines, where endocytosis is blocked specifically, I made observations on the mutual relationship between two opposite trafficking processes of secretion and endocytosis. In Chapter 3, I analyze cortical microtubule arrays and their relationship to auxin signaling and polarized growth in elongating cells. In plants, microtubules are organized into arrays just below the plasma membrane, and it is thought that their function is to guide membrane-docked cellulose synthase complexes. These, in turn, influence cell wall structure and cell shape by directed deposition of cellulose fibres. In elongating cells, cortical microtubule arrays are able to reorient in relation to long cell axis, and these reorientations have been linked to cell growth and to signaling of growth-regulating factors such as auxin or light. In this chapter, I am addressing the causal relationship between microtubule array reorientation, growth, and auxin signaling. I arrive at a model where array reorientation is not guided by auxin directly, but instead is only controlled by growth, which, in turn, is regulated by auxin.
AU - Adamowski, Maciek
ID - 938
SN - 2663-337X
TI - Investigations into cell polarity and trafficking in the plant model Arabidopsis thaliana
ER -
TY - THES
AB - An instance of the Constraint Satisfaction Problem (CSP) is given by a finite set of
variables, a finite domain of labels, and a set of constraints, each constraint acting on
a subset of the variables. The goal is to find an assignment of labels to its variables
that satisfies all constraints (or decide whether one exists). If we allow more general
“soft” constraints, which come with (possibly infinite) costs of particular assignments,
we obtain instances from a richer class called Valued Constraint Satisfaction Problem
(VCSP). There the goal is to find an assignment with minimum total cost.
In this thesis, we focus (assuming that P
6
=
NP) on classifying computational com-
plexity of CSPs and VCSPs under certain restricting conditions. Two results are the core
content of the work. In one of them, we consider VCSPs parametrized by a constraint
language, that is the set of “soft” constraints allowed to form the instances, and finish
the complexity classification modulo (missing pieces of) complexity classification for
analogously parametrized CSP. The other result is a generalization of Edmonds’ perfect
matching algorithm. This generalization contributes to complexity classfications in two
ways. First, it gives a new (largest known) polynomial-time solvable class of Boolean
CSPs in which every variable may appear in at most two constraints and second, it
settles full classification of Boolean CSPs with planar drawing (again parametrized by a
constraint language).
AU - Rolinek, Michal
ID - 992
SN - 2663-337X
TI - Complexity of constraint satisfaction
ER -
TY - JOUR
AB - Mapping every simplex in the Delaunay mosaic of a discrete point set to the radius of the smallest empty circumsphere gives a generalized discrete Morse function. Choosing the points from a Poisson point process in ℝ n , we study the expected number of simplices in the Delaunay mosaic as well as the expected number of critical simplices and nonsingular intervals in the corresponding generalized discrete gradient. Observing connections with other probabilistic models, we obtain precise expressions for the expected numbers in low dimensions. In particular, we obtain the expected numbers of simplices in the Poisson–Delaunay mosaic in dimensions n ≤ 4.
AU - Edelsbrunner, Herbert
AU - Nikitenko, Anton
AU - Reitzner, Matthias
ID - 718
IS - 3
JF - Advances in Applied Probability
SN - 00018678
TI - Expected sizes of poisson Delaunay mosaics and their discrete Morse functions
VL - 49
ER -
TY - CONF
AB - Proofs of space (PoS) were suggested as more ecological and economical alternative to proofs of work, which are currently used in blockchain designs like Bitcoin. The existing PoS are based on rather sophisticated graph pebbling lower bounds. Much simpler and in several aspects more efficient schemes based on inverting random functions have been suggested, but they don’t give meaningful security guarantees due to existing time-memory trade-offs. In particular, Hellman showed that any permutation over a domain of size N can be inverted in time T by an algorithm that is given S bits of auxiliary information whenever (Formula presented). For functions Hellman gives a weaker attack with S2· T≈ N2 (e.g., S= T≈ N2/3). To prove lower bounds, one considers an adversary who has access to an oracle f: [ N] → [N] and can make T oracle queries. The best known lower bound is S· T∈ Ω(N) and holds for random functions and permutations. We construct functions that provably require more time and/or space to invert. Specifically, for any constant k we construct a function [N] → [N] that cannot be inverted unless Sk· T∈ Ω(Nk) (in particular, S= T≈ (Formula presented). Our construction does not contradict Hellman’s time-memory trade-off, because it cannot be efficiently evaluated in forward direction. However, its entire function table can be computed in time quasilinear in N, which is sufficient for the PoS application. Our simplest construction is built from a random function oracle g: [N] × [N] → [ N] and a random permutation oracle f: [N] → N] and is defined as h(x) = g(x, x′) where f(x) = π(f(x′)) with π being any involution without a fixed point, e.g. flipping all the bits. For this function we prove that any adversary who gets S bits of auxiliary information, makes at most T oracle queries, and inverts h on an ϵ fraction of outputs must satisfy S2· T∈ Ω(ϵ2N2).
AU - Abusalah, Hamza M
AU - Alwen, Joel F
AU - Cohen, Bram
AU - Khilko, Danylo
AU - Pietrzak, Krzysztof Z
AU - Reyzin, Leonid
ID - 559
SN - 978-331970696-2
TI - Beyond Hellman’s time-memory trade-offs with applications to proofs of space
VL - 10625
ER -
TY - JOUR
AB - For large random matrices X with independent, centered entries but not necessarily identical variances, the eigenvalue density of XX* is well-approximated by a deterministic measure on ℝ. We show that the density of this measure has only square and cubic-root singularities away from zero. We also extend the bulk local law in [5] to the vicinity of these singularities.
AU - Alt, Johannes
ID - 550
JF - Electronic Communications in Probability
SN - 1083589X
TI - Singularities of the density of states of random Gram matrices
VL - 22
ER -
TY - CONF
AB - Despite researchers’ efforts in the last couple of decades, reachability analysis is still a challenging problem even for linear hybrid systems. Among the existing approaches, the most practical ones are mainly based on bounded-time reachable set over-approximations. For the purpose of unbounded-time analysis, one important strategy is to abstract the original system and find an invariant for the abstraction. In this paper, we propose an approach to constructing a new kind of abstraction called conic abstraction for affine hybrid systems, and to computing reachable sets based on this abstraction. The essential feature of a conic abstraction is that it partitions the state space of a system into a set of convex polyhedral cones which is derived from a uniform conic partition of the derivative space. Such a set of polyhedral cones is able to cut all trajectories of the system into almost straight segments so that every segment of a reach pipe in a polyhedral cone tends to be straight as well, and hence can be over-approximated tightly by polyhedra using similar techniques as HyTech or PHAVer. In particular, for diagonalizable affine systems, our approach can guarantee to find an invariant for unbounded reachable sets, which is beyond the capability of bounded-time reachability analysis tools. We implemented the approach in a tool and experiments on benchmarks show that our approach is more powerful than SpaceEx and PHAVer in dealing with diagonalizable systems.
AU - Bogomolov, Sergiy
AU - Giacobbe, Mirco
AU - Henzinger, Thomas A
AU - Kong, Hui
ID - 647
SN - 978-331965764-6
TI - Conic abstractions for hybrid systems
VL - 10419
ER -
TY - CONF
AB - Template polyhedra generalize intervals and octagons to polyhedra whose facets are orthogonal to a given set of arbitrary directions. They have been employed in the abstract interpretation of programs and, with particular success, in the reachability analysis of hybrid automata. While previously, the choice of directions has been left to the user or a heuristic, we present a method for the automatic discovery of directions that generalize and eliminate spurious counterexamples. We show that for the class of convex hybrid automata, i.e., hybrid automata with (possibly nonlinear) convex constraints on derivatives, such directions always exist and can be found using convex optimization. We embed our method inside a CEGAR loop, thus enabling the time-unbounded reachability analysis of an important and richer class of hybrid automata than was previously possible. We evaluate our method on several benchmarks, demonstrating also its superior efficiency for the special case of linear hybrid automata.
AU - Bogomolov, Sergiy
AU - Frehse, Goran
AU - Giacobbe, Mirco
AU - Henzinger, Thomas A
ID - 631
SN - 978-366254576-8
TI - Counterexample guided refinement of template polyhedra
VL - 10205
ER -
TY - JOUR
AB - We show that matrix elements of functions of N × N Wigner matrices fluctuate on a scale of order N−1/2 and we identify the limiting fluctuation. Our result holds for any function f of the matrix that has bounded variation thus considerably relaxing the regularity requirement imposed in [7, 11].
AU - Erdös, László
AU - Schröder, Dominik J
ID - 1144
JF - Electronic Communications in Probability
TI - Fluctuations of functions of Wigner matrices
VL - 21
ER -
TY - JOUR
AB - Color texture reproduction in 3D printing commonly ignores volumetric light transport (cross-talk) between surface points on a 3D print. Such light diffusion leads to significant blur of details and color bleeding, and is particularly severe for highly translucent resin-based print materials. Given their widely varying scattering properties, this cross-talk between surface points strongly depends on the internal structure of the volume surrounding each surface point. Existing scattering-aware methods use simplified models for light diffusion, and often accept the visual blur as an immutable property of the print medium. In contrast, our work counteracts heterogeneous scattering to obtain the impression of a crisp albedo texture on top of the 3D print, by optimizing for a fully volumetric material distribution that preserves the target appearance. Our method employs an efficient numerical optimizer on top of a general Monte-Carlo simulation of heterogeneous scattering, supported by a practical calibration procedure to obtain scattering parameters from a given set of printer materials. Despite the inherent translucency of the medium, we reproduce detailed surface textures on 3D prints. We evaluate our system using a commercial, five-tone 3D print process and compare against the printer’s native color texturing mode, demonstrating that our method preserves high-frequency features well without having to compromise on color gamut.
AU - Elek, Oskar
AU - Sumin, Denis
AU - Zhang, Ran
AU - Weyrich, Tim
AU - Myszkowski, Karol
AU - Bickel, Bernd
AU - Wilkie, Alexander
AU - Krivanek, Jaroslav
ID - 486
IS - 6
JF - ACM Transactions on Graphics
SN - 07300301
TI - Scattering-aware texture reproduction for 3D printing
VL - 36
ER -
TY - CONF
AB - We develop a probabilistic technique for colorizing grayscale natural images. In light of the intrinsic uncertainty of this task, the proposed probabilistic framework has numerous desirable properties. In particular, our model is able to produce multiple plausible and vivid colorizations for a given grayscale image and is one of the first colorization models to provide a proper stochastic sampling scheme. Moreover, our training procedure is supported by a rigorous theoretical framework that does not require any ad hoc heuristics and allows for efficient modeling and learning of the joint pixel color distribution.We demonstrate strong quantitative and qualitative experimental results on the CIFAR-10 dataset and the challenging ILSVRC 2012 dataset.
AU - Royer, Amélie
AU - Kolesnikov, Alexander
AU - Lampert, Christoph
ID - 911
TI - Probabilistic image colorization
ER -
TY - CONF
AB - For many cryptographic primitives, it is relatively easy to achieve selective security (where the adversary commits a-priori to some of the choices to be made later in the attack) but appears difficult to achieve the more natural notion of adaptive security (where the adversary can make all choices on the go as the attack progresses). A series of several recent works shows how to cleverly achieve adaptive security in several such scenarios including generalized selective decryption (Panjwani, TCC ’07 and Fuchsbauer et al., CRYPTO ’15), constrained PRFs (Fuchsbauer et al., ASIACRYPT ’14), and Yao garbled circuits (Jafargholi and Wichs, TCC ’16b). Although the above works expressed vague intuition that they share a common technique, the connection was never made precise. In this work we present a new framework that connects all of these works and allows us to present them in a unified and simplified fashion. Moreover, we use the framework to derive a new result for adaptively secure secret sharing over access structures defined via monotone circuits. We envision that further applications will follow in the future. Underlying our framework is the following simple idea. It is well known that selective security, where the adversary commits to n-bits of information about his future choices, automatically implies adaptive security at the cost of amplifying the adversary’s advantage by a factor of up to 2n. However, in some cases the proof of selective security proceeds via a sequence of hybrids, where each pair of adjacent hybrids locally only requires some smaller partial information consisting of m ≪ n bits. The partial information needed might be completely different between different pairs of hybrids, and if we look across all the hybrids we might rely on the entire n-bit commitment. Nevertheless, the above is sufficient to prove adaptive security, at the cost of amplifying the adversary’s advantage by a factor of only 2m ≪ 2n. In all of our examples using the above framework, the different hybrids are captured by some sort of a graph pebbling game and the amount of information that the adversary needs to commit to in each pair of hybrids is bounded by the maximum number of pebbles in play at any point in time. Therefore, coming up with better strategies for proving adaptive security translates to various pebbling strategies for different types of graphs.
AU - Jafargholi, Zahra
AU - Kamath Hosdurg, Chethan
AU - Klein, Karen
AU - Komargodski, Ilan
AU - Pietrzak, Krzysztof Z
AU - Wichs, Daniel
ED - Katz, Jonathan
ED - Shacham, Hovav
ID - 637
SN - 978-331963687-0
TI - Be adaptive avoid overcommitting
VL - 10401
ER -
TY - GEN
AB - Mathematica notebooks used to generate figures.
AU - Etheridge, Alison
AU - Barton, Nicholas H
ID - 9842
TI - Data for: Establishment in a new habitat by polygenic adaptation
ER -
TY - CONF
AB - Greedy optimization methods such as Matching Pursuit (MP) and Frank-Wolfe (FW) algorithms regained popularity in recent years due to their simplicity, effectiveness and theoretical guarantees. MP and FW address optimization over the linear span and the convex hull of a set of atoms, respectively. In this paper, we consider the intermediate case of optimization over the convex cone, parametrized as the conic hull of a generic atom set, leading to the first principled definitions of non-negative MP algorithms for which we give explicit convergence rates and demonstrate excellent empirical performance. In particular, we derive sublinear (O(1/t)) convergence on general smooth and convex objectives, and linear convergence (O(e−t)) on strongly convex objectives, in both cases for general sets of atoms. Furthermore, we establish a clear correspondence of our algorithms to known algorithms from the MP and FW literature. Our novel algorithms and analyses target general atom sets and general objective functions, and hence are directly applicable to a large variety of learning settings.
AU - Locatello, Francesco
AU - Tschannen, Michael
AU - Rätsch, Gunnar
AU - Jaggi, Martin
ID - 14206
SN - 9781510860964
T2 - Advances in Neural Information Processing Systems
TI - Greedy algorithms for cone constrained optimization with convergence guarantees
ER -
TY - CONF
AB - Two of the most fundamental prototypes of greedy optimization are the matching pursuit and Frank-Wolfe algorithms. In this paper, we take a unified view on both classes of methods, leading to the first explicit convergence rates of matching pursuit methods in an optimization sense, for general sets of atoms. We derive sublinear (1/t) convergence for both classes on general smooth objectives, and linear convergence on strongly convex objectives, as well as a clear correspondence of algorithm variants. Our presented algorithms and rates are affine invariant, and do not need any incoherence or sparsity assumptions.
AU - Locatello, Francesco
AU - Khanna, Rajiv
AU - Tschannen, Michael
AU - Jaggi, Martin
ID - 14205
T2 - Proceedings of the 20th International Conference on Artificial Intelligence and Statistics
TI - A unified optimization view on generalized matching pursuit and Frank-Wolfe
VL - 54
ER -
TY - THES
AB - Restriction-modification (RM) represents the simplest and possibly the most widespread mechanism of self/non-self discrimination in nature. In order to provide bacteria with immunity against bacteriophages and other parasitic genetic elements, RM systems rely on a balance between two enzymes: the restriction enzyme, which cleaves non-self DNA at specific restriction sites, and the modification enzyme, which tags the host’s DNA as self and thus protects it from cleavage. In this thesis, I use population and single-cell level experiments in combination with mathematical modeling to study different aspects of the interplay between RM systems, bacteria and bacteriophages. First, I analyze how mutations in phage restriction sites affect the probability of phage escape – an inherently stochastic process, during which phages accidently get modified instead of restricted. Next, I use single-cell experiments to show that RM systems can, with a low probability, attack the genome of their bacterial host and that this primitive form of autoimmunity leads to a tradeoff between the evolutionary cost and benefit of RM systems. Finally, I investigate the nature of interactions between bacteria, RM systems and temperate bacteriophages to find that, as a consequence of phage escape and its impact on population dynamics, RM systems can promote acquisition of symbiotic bacteriophages, rather than limit it. The results presented here uncover new fundamental biological properties of RM systems and highlight their importance in the ecology and evolution of bacteria, bacteriophages and their interactions.
AU - Pleska, Maros
ID - 202
SN - 2663-337X
TI - Biology of restriction-modification systems at the single-cell and population level
ER -
TY - THES
AB - The main objects considered in the present work are simplicial and CW-complexes with vertices forming a random point cloud. In particular, we consider a Poisson point process in R^n and study Delaunay and Voronoi complexes of the first and higher orders and weighted Delaunay complexes obtained as sections of Delaunay complexes, as well as the Čech complex. Further, we examine theDelaunay complex of a Poisson point process on the sphere S^n, as well as of a uniform point cloud, which is equivalent to the convex hull, providing a connection to the theory of random polytopes. Each of the complexes in question can be endowed with a radius function, which maps its cells to the radii of appropriately chosen circumspheres, called the radius of the cell. Applying and developing discrete Morse theory for these functions, joining it together with probabilistic and sometimes analytic machinery, and developing several integral geometric tools, we aim at getting the distributions of circumradii of typical cells. For all considered complexes, we are able to generalize and obtain up to constants the distribution of radii of typical intervals of all types. In low dimensions the constants can be computed explicitly, thus providing the explicit expressions for the expected numbers of cells. In particular, it allows to find the expected density of simplices of every dimension for a Poisson point process in R^4, whereas the result for R^3 was known already in 1970's.
AU - Nikitenko, Anton
ID - 6287
SN - 2663-337X
TI - Discrete Morse theory for random complexes
ER -
TY - DATA
AB - This folder contains all the data used in each of the main figures of "The genomic characterization of the t-haplotype, a mouse meiotic driver, highlights its complex history and specialized biology" (Kelemen, R., Vicoso, B.), as well as in the supplementary figures.
AU - Vicoso, Beatriz
ID - 5571
TI - Data for "The genomic characterization of the t-haplotype, a mouse meiotic driver, highlights its complex history and specialized biology"
ER -
TY - DATA
AB - Code described in the Supplementary Methods of "The genomic characterization of the t-haplotype, a mouse meiotic driver, highlights its complex history and specialized biology" (Kelemen, R., Vicoso, B.)
AU - Vicoso, Beatriz
ID - 5572
TI - Code for "The genomic characterization of the t-haplotype, a mouse meiotic driver, highlights its complex history and specialized biology"
ER -
TY - THES
AB - Plant hormone auxin and its transport between cells belong to the most important
mechanisms controlling plant development. Auxin itself could change localization of PINs and
thereby control direction of its own flow. We performed an expression profiling experiment
in Arabidopsis roots to identify potential regulators of PIN polarity which are transcriptionally
regulated by auxin signalling. We identified several novel regulators and performed a detailed
characterization of the transcription factor WRKY23 (At2g47260) and its role in auxin
feedback on PIN polarity. Gain-of-function and dominant-negative mutants revealed that
WRKY23 plays a crucial role in mediating the auxin effect on PIN polarity. In concordance,
typical polar auxin transport processes such as gravitropism and leaf vascular pattern
formation were disturbed by interfering with WRKY23 function.
In order to identify direct targets of WRKY23, we performed consequential expression
profiling experiments using a WRKY23 inducible gain-of-function line and dominant-negative
WRKY23 line that is defunct in PIN re-arrangement. Among several genes mostly related to
the groups of cell wall and defense process regulators, we identified LYSINE-HISTIDINE
TRANSPORTER 1 (LHT1; At5g40780), a small amino acid permease gene from the amino
acid/auxin permease family (AAAP), we present its detailed characterisation in auxin feedback
on PIN repolarization, identified its transcriptional regulation, we propose a potential
mechanism of its action. Moreover, we identified also a member of receptor-like protein
kinase LRR-RLK (LEUCINE-RICH REPEAT TRANSMEMBRANE PROTEIN KINASE PROTEIN 1;
LRRK1; At1g05700), which also affects auxin-dependent PIN re-arrangement. We described
its transcriptional behaviour, subcellular localization. Based on global expression data, we
tried to identify ligand responsible for mechanism of signalling and suggest signalling partner
and interactors. Additionally, we described role of novel phytohormone group, strigolactone,
in auxin-dependent PIN re-arrangement, that could be a fundament for future studies in this
field.
Our results provide first insights into an auxin transcriptional network targeting PIN
localization and thus regulating plant development. We highlighted WRKY23 transcriptional
network and characterised its mediatory role in plant development. We identified direct
effectors of this network, LHT1 and LRRK1, and describe their roles in PIN re-arrangement and
PIN-dependent auxin transport processes.
AU - Prat, Tomas
ID - 1127
SN - 2663-337X
TI - Identification of novel regulators of PIN polarity and development of novel auxin sensor
ER -
TY - DATA
AB - Strong amplifiers of natural selection
AU - Pavlogiannis, Andreas
AU - Tkadlec, Josef
AU - Chatterjee, Krishnendu
AU - Nowak , Martin
ID - 5559
KW - natural selection
TI - Strong amplifiers of natural selection
ER -
TY - JOUR
AB - The molecular mechanisms underlying phenotypic variation in isogenic bacterial populations remain poorly understood.We report that AcrAB-TolC, the main multidrug efflux pump of Escherichia coli, exhibits a strong partitioning bias for old cell poles by a segregation mechanism that is mediated by ternary AcrAB-TolC complex formation. Mother cells inheriting old poles are phenotypically distinct and display increased drug efflux activity relative to daughters. Consequently, we find systematic and long-lived growth differences between mother and daughter cells in the presence of subinhibitory drug concentrations. A simple model for biased partitioning predicts a population structure of long-lived and highly heterogeneous phenotypes. This straightforward mechanism of generating sustained growth rate differences at subinhibitory antibiotic concentrations has implications for understanding the emergence of multidrug resistance in bacteria.
AU - Bergmiller, Tobias
AU - Andersson, Anna M
AU - Tomasek, Kathrin
AU - Balleza, Enrique
AU - Kiviet, Daniel
AU - Hauschild, Robert
AU - Tkacik, Gasper
AU - Guet, Calin C
ID - 665
IS - 6335
JF - Science
SN - 00368075
TI - Biased partitioning of the multidrug efflux pump AcrAB TolC underlies long lived phenotypic heterogeneity
VL - 356
ER -
TY - DATA
AB - This repository contains the data collected for the manuscript "Biased partitioning of the multi-drug efflux pump AcrAB-TolC underlies long-lived phenotypic heterogeneity".
The data is compressed into a single archive. Within the archive, different folders correspond to figures of the main text and the SI of the related publication.
Data is saved as plain text, with each folder containing a separate readme file describing the format. Typically, the data is from fluorescence microscopy measurements of single cells growing in a microfluidic "mother machine" device, and consists of relevant values (primarily arbitrary unit or normalized fluorescence measurements, and division times / growth rates) after raw microscopy images have been processed, segmented, and their features extracted, as described in the methods section of the related publication.
AU - Bergmiller, Tobias
AU - Andersson, Anna M
AU - Tomasek, Kathrin
AU - Balleza, Enrique
AU - Kiviet, Daniel
AU - Hauschild, Robert
AU - Tkacik, Gasper
AU - Guet, Calin C
ID - 5560
KW - single cell microscopy
KW - mother machine microfluidic device
KW - AcrAB-TolC pump
KW - multi-drug efflux
KW - Escherichia coli
TI - Biased partitioning of the multi-drug efflux pump AcrAB-TolC underlies long-lived phenotypic heterogeneity
ER -
TY - JOUR
AB - The Ising model is one of the simplest and most famous models of interacting systems. It was originally proposed to model ferromagnetic interactions in statistical physics and is now widely used to model spatial processes in many areas such as ecology, sociology, and genetics, usually without testing its goodness-of-fit. Here, we propose an exact goodness-of-fit test for the finite-lattice Ising model. The theory of Markov bases has been developed in algebraic statistics for exact goodness-of-fit testing using a Monte Carlo approach. However, this beautiful theory has fallen short of its promise for applications, because finding a Markov basis is usually computationally intractable. We develop a Monte Carlo method for exact goodness-of-fit testing for the Ising model which avoids computing a Markov basis and also leads to a better connectivity of the Markov chain and hence to a faster convergence. We show how this method can be applied to analyze the spatial organization of receptors on the cell membrane.
AU - Martin Del Campo Sanchez, Abraham
AU - Cepeda Humerez, Sarah A
AU - Uhler, Caroline
ID - 2016
IS - 2
JF - Scandinavian Journal of Statistics
SN - 03036898
TI - Exact goodness-of-fit testing for the Ising model
VL - 44
ER -
TY - JOUR
AB - We consider N×N Hermitian random matrices H consisting of blocks of size M≥N6/7. The matrix elements are i.i.d. within the blocks, close to a Gaussian in the four moment matching sense, but their distribution varies from block to block to form a block-band structure, with an essential band width M. We show that the entries of the Green’s function G(z)=(H−z)−1 satisfy the local semicircle law with spectral parameter z=E+iη down to the real axis for any η≫N−1, using a combination of the supersymmetry method inspired by Shcherbina (J Stat Phys 155(3): 466–499, 2014) and the Green’s function comparison strategy. Previous estimates were valid only for η≫M−1. The new estimate also implies that the eigenvectors in the middle of the spectrum are fully delocalized.
AU - Bao, Zhigang
AU - Erdös, László
ID - 1528
IS - 3-4
JF - Probability Theory and Related Fields
SN - 01788051
TI - Delocalization for a class of random block band matrices
VL - 167
ER -
TY - JOUR
AB - Phat is an open-source C. ++ library for the computation of persistent homology by matrix reduction, targeted towards developers of software for topological data analysis. We aim for a simple generic design that decouples algorithms from data structures without sacrificing efficiency or user-friendliness. We provide numerous different reduction strategies as well as data types to store and manipulate the boundary matrix. We compare the different combinations through extensive experimental evaluation and identify optimization techniques that work well in practical situations. We also compare our software with various other publicly available libraries for persistent homology.
AU - Bauer, Ulrich
AU - Kerber, Michael
AU - Reininghaus, Jan
AU - Wagner, Hubert
ID - 1433
JF - Journal of Symbolic Computation
SN - 07477171
TI - Phat - Persistent homology algorithms toolbox
VL - 78
ER -
TY - JOUR
AB - We consider the problem of computing the set of initial states of a dynamical system such that there exists a control strategy to ensure that the trajectories satisfy a temporal logic specification with probability 1 (almost-surely). We focus on discrete-time, stochastic linear dynamics and specifications given as formulas of the Generalized Reactivity(1) fragment of Linear Temporal Logic over linear predicates in the states of the system. We propose a solution based on iterative abstraction-refinement, and turn-based 2-player probabilistic games. While the theoretical guarantee of our algorithm after any finite number of iterations is only a partial solution, we show that if our algorithm terminates, then the result is the set of all satisfying initial states. Moreover, for any (partial) solution our algorithm synthesizes witness control strategies to ensure almost-sure satisfaction of the temporal logic specification. While the proposed algorithm guarantees progress and soundness in every iteration, it is computationally demanding. We offer an alternative, more efficient solution for the reachability properties that decomposes the problem into a series of smaller problems of the same type. All algorithms are demonstrated on an illustrative case study.
AU - Svoreňová, Mária
AU - Kretinsky, Jan
AU - Chmelik, Martin
AU - Chatterjee, Krishnendu
AU - Cěrná, Ivana
AU - Belta, Cǎlin
ID - 1407
IS - 2
JF - Nonlinear Analysis: Hybrid Systems
TI - Temporal logic control for stochastic linear systems using abstraction refinement of probabilistic games
VL - 23
ER -
TY - JOUR
AB - One of the major challenges in physically based modelling is making simulations efficient. Adaptive models provide an essential solution to these efficiency goals. These models are able to self-adapt in space and time, attempting to provide the best possible compromise between accuracy and speed. This survey reviews the adaptive solutions proposed so far in computer graphics. Models are classified according to the strategy they use for adaptation, from time-stepping and freezing techniques to geometric adaptivity in the form of structured grids, meshes and particles. Applications range from fluids, through deformable bodies, to articulated solids.
AU - Manteaux, Pierre
AU - Wojtan, Christopher J
AU - Narain, Rahul
AU - Redon, Stéphane
AU - Faure, François
AU - Cani, Marie
ID - 1367
IS - 6
JF - Computer Graphics Forum
SN - 01677055
TI - Adaptive physically based models in computer graphics
VL - 36
ER -
TY - JOUR
AB - We present a computer-aided programming approach to concurrency. The approach allows programmers to program assuming a friendly, non-preemptive scheduler, and our synthesis procedure inserts synchronization to ensure that the final program works even with a preemptive scheduler. The correctness specification is implicit, inferred from the non-preemptive behavior. Let us consider sequences of calls that the program makes to an external interface. The specification requires that any such sequence produced under a preemptive scheduler should be included in the set of sequences produced under a non-preemptive scheduler. We guarantee that our synthesis does not introduce deadlocks and that the synchronization inserted is optimal w.r.t. a given objective function. The solution is based on a finitary abstraction, an algorithm for bounded language inclusion modulo an independence relation, and generation of a set of global constraints over synchronization placements. Each model of the global constraints set corresponds to a correctness-ensuring synchronization placement. The placement that is optimal w.r.t. the given objective function is chosen as the synchronization solution. We apply the approach to device-driver programming, where the driver threads call the software interface of the device and the API provided by the operating system. Our experiments demonstrate that our synthesis method is precise and efficient. The implicit specification helped us find one concurrency bug previously missed when model-checking using an explicit, user-provided specification. We implemented objective functions for coarse-grained and fine-grained locking and observed that different synchronization placements are produced for our experiments, favoring a minimal number of synchronization operations or maximum concurrency, respectively.
AU - Cerny, Pavol
AU - Clarke, Edmund
AU - Henzinger, Thomas A
AU - Radhakrishna, Arjun
AU - Ryzhyk, Leonid
AU - Samanta, Roopsha
AU - Tarrach, Thorsten
ID - 1338
IS - 2-3
JF - Formal Methods in System Design
TI - From non-preemptive to preemptive scheduling using synchronization synthesis
VL - 50
ER -
TY - JOUR
AB - The behaviour of gene regulatory networks (GRNs) is typically analysed using simulation-based statistical testing-like methods. In this paper, we demonstrate that we can replace this approach by a formal verification-like method that gives higher assurance and scalability. We focus on Wagner’s weighted GRN model with varying weights, which is used in evolutionary biology. In the model, weight parameters represent the gene interaction strength that may change due to genetic mutations. For a property of interest, we synthesise the constraints over the parameter space that represent the set of GRNs satisfying the property. We experimentally show that our parameter synthesis procedure computes the mutational robustness of GRNs—an important problem of interest in evolutionary biology—more efficiently than the classical simulation method. We specify the property in linear temporal logic. We employ symbolic bounded model checking and SMT solving to compute the space of GRNs that satisfy the property, which amounts to synthesizing a set of linear constraints on the weights.
AU - Giacobbe, Mirco
AU - Guet, Calin C
AU - Gupta, Ashutosh
AU - Henzinger, Thomas A
AU - Paixao, Tiago
AU - Petrov, Tatjana
ID - 1351
IS - 8
JF - Acta Informatica
SN - 00015903
TI - Model checking the evolution of gene regulatory networks
VL - 54
ER -
TY - JOUR
AB - Evolutionary algorithms (EAs) form a popular optimisation paradigm inspired by natural evolution. In recent years the field of evolutionary computation has developed a rigorous analytical theory to analyse the runtimes of EAs on many illustrative problems. Here we apply this theory to a simple model of natural evolution. In the Strong Selection Weak Mutation (SSWM) evolutionary regime the time between occurrences of new mutations is much longer than the time it takes for a mutated genotype to take over the population. In this situation, the population only contains copies of one genotype and evolution can be modelled as a stochastic process evolving one genotype by means of mutation and selection between the resident and the mutated genotype. The probability of accepting the mutated genotype then depends on the change in fitness. We study this process, SSWM, from an algorithmic perspective, quantifying its expected optimisation time for various parameters and investigating differences to a similar evolutionary algorithm, the well-known (1+1) EA. We show that SSWM can have a moderate advantage over the (1+1) EA at crossing fitness valleys and study an example where SSWM outperforms the (1+1) EA by taking advantage of information on the fitness gradient.
AU - Paixao, Tiago
AU - Pérez Heredia, Jorge
AU - Sudholt, Dirk
AU - Trubenova, Barbora
ID - 1336
IS - 2
JF - Algorithmica
SN - 01784617
TI - Towards a runtime comparison of natural and artificial evolution
VL - 78
ER -
TY - JOUR
AB - We consider the local eigenvalue distribution of large self-adjoint N×N random matrices H=H∗ with centered independent entries. In contrast to previous works the matrix of variances sij=\mathbbmE|hij|2 is not assumed to be stochastic. Hence the density of states is not the Wigner semicircle law. Its possible shapes are described in the companion paper (Ajanki et al. in Quadratic Vector Equations on the Complex Upper Half Plane. arXiv:1506.05095). We show that as N grows, the resolvent, G(z)=(H−z)−1, converges to a diagonal matrix, diag(m(z)), where m(z)=(m1(z),…,mN(z)) solves the vector equation −1/mi(z)=z+∑jsijmj(z) that has been analyzed in Ajanki et al. (Quadratic Vector Equations on the Complex Upper Half Plane. arXiv:1506.05095). We prove a local law down to the smallest spectral resolution scale, and bulk universality for both real symmetric and complex hermitian symmetry classes.
AU - Ajanki, Oskari H
AU - Erdös, László
AU - Krüger, Torben H
ID - 1337
IS - 3-4
JF - Probability Theory and Related Fields
SN - 01788051
TI - Universality for general Wigner-type matrices
VL - 169
ER -
TY - JOUR
AB - We study controller synthesis problems for finite-state Markov decision processes, where the objective is to optimize the expected mean-payoff performance and stability (also known as variability in the literature). We argue that the basic notion of expressing the stability using the statistical variance of the mean payoff is sometimes insufficient, and propose an alternative definition. We show that a strategy ensuring both the expected mean payoff and the variance below given bounds requires randomization and memory, under both the above definitions. We then show that the problem of finding such a strategy can be expressed as a set of constraints.
AU - Brázdil, Tomáš
AU - Chatterjee, Krishnendu
AU - Forejt, Vojtěch
AU - Kučera, Antonín
ID - 1294
JF - Journal of Computer and System Sciences
TI - Trading performance for stability in Markov decision processes
VL - 84
ER -
TY - JOUR
AB - Since 2006, reprogrammed cells have increasingly been used as a biomedical research technique in addition to neuro-psychiatric methods. These rapidly evolving techniques allow for the generation of neuronal sub-populations, and have sparked interest not only in monogenetic neuro-psychiatric diseases, but also in poly-genetic and poly-aetiological disorders such as schizophrenia (SCZ) and bipolar disorder (BPD). This review provides a summary of 19 publications on reprogrammed adult somatic cells derived from patients with SCZ, and five publications using this technique in patients with BPD. As both disorders are complex and heterogeneous, there is a plurality of hypotheses to be tested in vitro. In SCZ, data on alterations of dopaminergic transmission in vitro are sparse, despite the great explanatory power of the so-called DA hypothesis of SCZ. Some findings correspond to perturbations of cell energy metabolism, and observations in reprogrammed cells suggest neuro-developmental alterations. Some studies also report on the efficacy of medicinal compounds to revert alterations observed in cellular models. However, due to the paucity of replication studies, no comprehensive conclusions can be drawn from studies using reprogrammed cells at the present time. In the future, findings from cell culture methods need to be integrated with clinical, epidemiological, pharmacological and imaging data in order to generate a more comprehensive picture of SCZ and BPD.
AU - Sauerzopf, Ulrich
AU - Sacco, Roberto
AU - Novarino, Gaia
AU - Niello, Marco
AU - Weidenauer, Ana
AU - Praschak Rieder, Nicole
AU - Sitte, Harald
AU - Willeit, Matthaeus
ID - 1228
IS - 1
JF - European Journal of Neuroscience
TI - Are reprogrammed cells a useful tool for studying dopamine dysfunction in psychotic disorders? A review of the current evidence
VL - 45
ER -
TY - CHAP
AB - Bacterial cytokinesis is commonly initiated by the Z-ring, a dynamic cytoskeletal structure that assembles at the site of division. Its primary component is FtsZ, a tubulin-like GTPase, that like its eukaryotic relative forms protein filaments in the presence of GTP. Since the discovery of the Z-ring 25 years ago, various models for the role of FtsZ have been suggested. However, important information about the architecture and dynamics of FtsZ filaments during cytokinesis is still missing. One reason for this lack of knowledge has been the small size of bacteria, which has made it difficult to resolve the orientation and dynamics of individual FtsZ filaments in the Z-ring. While superresolution microscopy experiments have helped to gain more information about the organization of the Z-ring in the dividing cell, they were not yet able to elucidate a mechanism of how FtsZ filaments reorganize during assembly and disassembly of the Z-ring. In this chapter, we explain how to use an in vitro reconstitution approach to investigate the self-organization of FtsZ filaments recruited to a biomimetic lipid bilayer by its membrane anchor FtsA. We show how to perform single-molecule experiments to study the behavior of individual FtsZ monomers during the constant reorganization of the FtsZ-FtsA filament network. We describe how to analyze the dynamics of single molecules and explain why this information can help to shed light onto possible mechanism of Z-ring constriction. We believe that similar experimental approaches will be useful to study the mechanism of membrane-based polymerization of other cytoskeletal systems, not only from prokaryotic but also eukaryotic origin.
AU - Baranova, Natalia
AU - Loose, Martin
ED - Echard, Arnaud
ID - 1213
SN - 0091679X
T2 - Cytokinesis
TI - Single-molecule measurements to study polymerization dynamics of FtsZ-FtsA copolymers
VL - 137
ER -
TY - JOUR
AB - We consider a model of fermions interacting via point interactions, defined via a certain weighted Dirichlet form. While for two particles the interaction corresponds to infinite scattering length, the presence of further particles effectively decreases the interaction strength. We show that the model becomes trivial in the thermodynamic limit, in the sense that the free energy density at any given particle density and temperature agrees with the corresponding expression for non-interacting particles.
AU - Moser, Thomas
AU - Seiringer, Robert
ID - 1198
IS - 3
JF - Letters in Mathematical Physics
SN - 03779017
TI - Triviality of a model of particles with point interactions in the thermodynamic limit
VL - 107
ER -
TY - JOUR
AB - The eigenvalue distribution of the sum of two large Hermitian matrices, when one of them is conjugated by a Haar distributed unitary matrix, is asymptotically given by the free convolution of their spectral distributions. We prove that this convergence also holds locally in the bulk of the spectrum, down to the optimal scales larger than the eigenvalue spacing. The corresponding eigenvectors are fully delocalized. Similar results hold for the sum of two real symmetric matrices, when one is conjugated by Haar orthogonal matrix.
AU - Bao, Zhigang
AU - Erdös, László
AU - Schnelli, Kevin
ID - 1207
IS - 3
JF - Communications in Mathematical Physics
SN - 00103616
TI - Local law of addition of random matrices on optimal scale
VL - 349
ER -
TY - JOUR
AB - We define the . model-measuring problem: given a model . M and specification . ϕ, what is the maximal distance . ρ such that all models . M' within distance . ρ from . M satisfy (or violate) . ϕ. The model-measuring problem presupposes a distance function on models. We concentrate on . automatic distance functions, which are defined by weighted automata. The model-measuring problem subsumes several generalizations of the classical model-checking problem, in particular, quantitative model-checking problems that measure the degree of satisfaction of a specification; robustness problems that measure how much a model can be perturbed without violating the specification; and parameter synthesis for hybrid systems. We show that for automatic distance functions, and (a) . ω-regular linear-time, (b) . ω-regular branching-time, and (c) hybrid specifications, the model-measuring problem can be solved.We use automata-theoretic model-checking methods for model measuring, replacing the emptiness question for word, tree, and hybrid automata by the . optimal-value question for the weighted versions of these automata. For automata over words and trees, we consider weighted automata that accumulate weights by maximizing, summing, discounting, and limit averaging. For hybrid automata, we consider monotonic (parametric) hybrid automata, a hybrid counterpart of (discrete) weighted automata.We give several examples of using the model-measuring problem to compute various notions of robustness and quantitative satisfaction for temporal specifications. Further, we propose the modeling framework for model measuring to ease the specification and reduce the likelihood of errors in modeling.Finally, we present a variant of the model-measuring problem, called the . model-repair problem. The model-repair problem applies to models that do not satisfy the specification; it can be used to derive restrictions, under which the model satisfies the specification, i.e., to repair the model.
AU - Henzinger, Thomas A
AU - Otop, Jan
ID - 1196
JF - Nonlinear Analysis: Hybrid Systems
TI - Model measuring for discrete and hybrid systems
VL - 23
ER -
TY - JOUR
AB - Much of quantitative genetics is based on the ‘infinitesimal model’, under which selection has a negligible effect on the genetic variance. This is typically justified by assuming a very large number of loci with additive effects. However, it applies even when genes interact, provided that the number of loci is large enough that selection on each of them is weak relative to random drift. In the long term, directional selection will change allele frequencies, but even then, the effects of epistasis on the ultimate change in trait mean due to selection may be modest. Stabilising selection can maintain many traits close to their optima, even when the underlying alleles are weakly selected. However, the number of traits that can be optimised is apparently limited to ~4Ne by the ‘drift load’, and this is hard to reconcile with the apparent complexity of many organisms. Just as for the mutation load, this limit can be evaded by a particular form of negative epistasis. A more robust limit is set by the variance in reproductive success. This suggests that selection accumulates information most efficiently in the infinitesimal regime, when selection on individual alleles is weak, and comparable with random drift. A review of evidence on selection strength suggests that although most variance in fitness may be because of alleles with large Nes, substantial amounts of adaptation may be because of alleles in the infinitesimal regime, in which epistasis has modest effects.
AU - Barton, Nicholas H
ID - 1199
JF - Heredity
TI - How does epistasis influence the response to selection?
VL - 118
ER -
TY - JOUR
AB - We study parameter estimation in linear Gaussian covariance models, which are p-dimensional Gaussian models with linear constraints on the covariance matrix. Maximum likelihood estimation for this class of models leads to a non-convex optimization problem which typically has many local maxima. Using recent results on the asymptotic distribution of extreme eigenvalues of the Wishart distribution, we provide sufficient conditions for any hill climbing method to converge to the global maximum. Although we are primarily interested in the case in which n≫p, the proofs of our results utilize large sample asymptotic theory under the scheme n/p→γ>1. Remarkably, our numerical simulations indicate that our results remain valid for p as small as 2. An important consequence of this analysis is that, for sample sizes n≃14p, maximum likelihood estimation for linear Gaussian covariance models behaves as if it were a convex optimization problem. © 2016 The Royal Statistical Society and Blackwell Publishing Ltd.
AU - Zwiernik, Piotr
AU - Uhler, Caroline
AU - Richards, Donald
ID - 1208
IS - 4
JF - Journal of the Royal Statistical Society. Series B: Statistical Methodology
SN - 13697412
TI - Maximum likelihood estimation for linear Gaussian covariance models
VL - 79
ER -
TY - CONF
AB - Security of cryptographic applications is typically defined by security games. The adversary, within certain resources, cannot win with probability much better than 0 (for unpredictability applications, like one-way functions) or much better than 1/2 (indistinguishability applications for instance encryption schemes). In so called squared-friendly applications the winning probability of the adversary, for different values of the application secret randomness, is not only close to 0 or 1/2 on average, but also concentrated in the sense that its second central moment is small. The class of squared-friendly applications, which contains all unpredictability applications and many indistinguishability applications, is particularly important for key derivation. Barak et al. observed that for square-friendly applications one can beat the "RT-bound", extracting secure keys with significantly smaller entropy loss. In turn Dodis and Yu showed that in squared-friendly applications one can directly use a "weak" key, which has only high entropy, as a secure key. In this paper we give sharp lower bounds on square security assuming security for "weak" keys. We show that any application which is either (a) secure with weak keys or (b) allows for entropy savings for keys derived by universal hashing, must be square-friendly. Quantitatively, our lower bounds match the positive results of Dodis and Yu and Barak et al. (TCC\'13, CRYPTO\'11) Hence, they can be understood as a general characterization of squared-friendly applications. While the positive results on squared-friendly applications where derived by one clever application of the Cauchy-Schwarz Inequality, for tight lower bounds we need more machinery. In our approach we use convex optimization techniques and some theory of circular matrices.
AU - Skórski, Maciej
ID - 1174
SN - 18688969
TI - Lower bounds on key derivation for square-friendly applications
VL - 66
ER -
TY - CONF
AB - Termination is one of the basic liveness properties, and we study the termination problem for probabilistic programs with real-valued variables. Previous works focused on the qualitative problem that asks whether an input program terminates with probability~1 (almost-sure termination). A powerful approach for this qualitative problem is the notion of ranking supermartingales with respect to a given set of invariants. The quantitative problem (probabilistic termination) asks for bounds on the termination probability. A fundamental and conceptual drawback of the existing approaches to address probabilistic termination is that even though the supermartingales consider the probabilistic behavior of the programs, the invariants are obtained completely ignoring the probabilistic aspect. In this work we address the probabilistic termination problem for linear-arithmetic probabilistic programs with nondeterminism. We define the notion of {\em stochastic invariants}, which are constraints along with a probability bound that the constraints hold. We introduce a concept of {\em repulsing supermartingales}. First, we show that repulsing supermartingales can be used to obtain bounds on the probability of the stochastic invariants. Second, we show the effectiveness of repulsing supermartingales in the following three ways: (1)~With a combination of ranking and repulsing supermartingales we can compute lower bounds on the probability of termination; (2)~repulsing supermartingales provide witnesses for refutation of almost-sure termination; and (3)~with a combination of ranking and repulsing supermartingales we can establish persistence properties of probabilistic programs. We also present results on related computational problems and an experimental evaluation of our approach on academic examples.
AU - Chatterjee, Krishnendu
AU - Novotny, Petr
AU - Zikelic, Djordje
ID - 1194
IS - 1
SN - 07308566
TI - Stochastic invariants for probabilistic termination
VL - 52
ER -
TY - CONF
AB - The algorithm Argon2i-B of Biryukov, Dinu and Khovratovich is currently being considered by the IRTF (Internet Research Task Force) as a new de-facto standard for password hashing. An older version (Argon2i-A) of the same algorithm was chosen as the winner of the recent Password Hashing Competition. An important competitor to Argon2i-B is the recently introduced Balloon Hashing (BH) algorithm of Corrigan-Gibs, Boneh and Schechter. A key security desiderata for any such algorithm is that evaluating it (even using a custom device) requires a large amount of memory amortized across multiple instances. Alwen and Blocki (CRYPTO 2016) introduced a class of theoretical attacks against Argon2i-A and BH. While these attacks yield large asymptotic reductions in the amount of memory, it was not, a priori, clear if (1) they can be extended to the newer Argon2i-B, (2) the attacks are effective on any algorithm for practical parameter ranges (e.g., 1GB of memory) and (3) if they can be effectively instantiated against any algorithm under realistic hardware constrains. In this work we answer all three of these questions in the affirmative for all three algorithms. This is also the first work to analyze the security of Argon2i-B. In more detail, we extend the theoretical attacks of Alwen and Blocki (CRYPTO 2016) to the recent Argon2i-B proposal demonstrating severe asymptotic deficiencies in its security. Next we introduce several novel heuristics for improving the attack's concrete memory efficiency even when on-chip memory bandwidth is bounded. We then simulate our attacks on randomly sampled Argon2i-A, Argon2i-B and BH instances and measure the resulting memory consumption for various practical parameter ranges and for a variety of upperbounds on the amount of parallelism available to the attacker. Finally we describe, implement, and test a new heuristic for applying the Alwen-Blocki attack to functions employing a technique developed by Corrigan-Gibs et al. for improving concrete security of memory-hard functions. We analyze the collected data and show the effects various parameters have on the memory consumption of the attack. In particular, we can draw several interesting conclusions about the level of security provided by these functions. · For the Alwen-Blocki attack to fail against practical memory parameters, Argon2i-B must be instantiated with more than 10 passes on memory - beyond the "paranoid" parameter setting in the current IRTF proposal. · The technique of Corrigan-Gibs for improving security can also be overcome by the Alwen-Blocki attack under realistic hardware constraints. · On a positive note, both the asymptotic and concrete security of Argon2i-B seem to improve on that of Argon2i-A.
AU - Alwen, Joel F
AU - Blocki, Jeremiah
ID - 1176
SN - 978-150905761-0
TI - Towards practical attacks on Argon2i and balloon hashing
ER -
TY - JOUR
AB - We construct efficient authentication protocols and message authentication codes (MACs) whose security can be reduced to the learning parity with noise (LPN) problem. Despite a large body of work—starting with the (Formula presented.) protocol of Hopper and Blum in 2001—until now it was not even known how to construct an efficient authentication protocol from LPN which is secure against man-in-the-middle attacks. A MAC implies such a (two-round) protocol.
AU - Kiltz, Eike
AU - Pietrzak, Krzysztof Z
AU - Venturi, Daniele
AU - Cash, David
AU - Jain, Abhishek
ID - 1187
IS - 4
JF - Journal of Cryptology
TI - Efficient authentication from hard learning problems
VL - 30
ER -
TY - CONF
AB - The main result of this paper is a generalization of the classical blossom algorithm for finding perfect matchings. Our algorithm can efficiently solve Boolean CSPs where each variable appears in exactly two constraints (we call it edge CSP) and all constraints are even Δ-matroid relations (represented by lists of tuples). As a consequence of this, we settle the complexity classification of planar Boolean CSPs started by Dvorak and Kupec. Knowing that edge CSP is tractable for even Δ-matroid constraints allows us to extend the tractability result to a larger class of Δ-matroids that includes many classes that were known to be tractable before, namely co-independent, compact, local and binary.
AU - Kazda, Alexandr
AU - Kolmogorov, Vladimir
AU - Rolinek, Michal
ID - 1192
SN - 978-161197478-2
TI - Even delta-matroids and the complexity of planar Boolean CSPs
ER -
TY - JOUR
AB - In this article we define an algebraic vertex of a generalized polyhedron and show that the set of algebraic vertices is the smallest set of points needed to define the polyhedron. We prove that the indicator function of a generalized polytope P is a linear combination of indicator functions of simplices whose vertices are algebraic vertices of P. We also show that the indicator function of any generalized polyhedron is a linear combination, with integer coefficients, of indicator functions of cones with apices at algebraic vertices and line-cones. The concept of an algebraic vertex is closely related to the Fourier–Laplace transform. We show that a point v is an algebraic vertex of a generalized polyhedron P if and only if the tangent cone of P, at v, has non-zero Fourier–Laplace transform.
AU - Akopyan, Arseniy
AU - Bárány, Imre
AU - Robins, Sinai
ID - 1180
JF - Advances in Mathematics
SN - 00018708
TI - Algebraic vertices of non-convex polyhedra
VL - 308
ER -
TY - JOUR
AB - Auxin steers numerous physiological processes in plants, making the tight control of its endogenous levels and spatiotemporal distribution a necessity. This regulation is achieved by different mechanisms, including auxin biosynthesis, metabolic conversions, degradation, and transport. Here, we introduce cis-cinnamic acid (c-CA) as a novel and unique addition to a small group of endogenous molecules affecting in planta auxin concentrations. c-CA is the photo-isomerization product of the phenylpropanoid pathway intermediate trans-CA (t-CA). When grown on c-CA-containing medium, an evolutionary diverse set of plant species were shown to exhibit phenotypes characteristic for high auxin levels, including inhibition of primary root growth, induction of root hairs, and promotion of adventitious and lateral rooting. By molecular docking and receptor binding assays, we showed that c-CA itself is neither an auxin nor an anti-auxin, and auxin profiling data revealed that c-CA does not significantly interfere with auxin biosynthesis. Single cell-based auxin accumulation assays showed that c-CA, and not t-CA, is a potent inhibitor of auxin efflux. Auxin signaling reporters detected changes in spatiotemporal distribution of the auxin response along the root of c-CA-treated plants, and long-distance auxin transport assays showed no inhibition of rootward auxin transport. Overall, these results suggest that the phenotypes of c-CA-treated plants are the consequence of a local change in auxin accumulation, induced by the inhibition of auxin efflux. This work reveals a novel mechanism how plants may regulate auxin levels and adds a novel, naturally occurring molecule to the chemical toolbox for the studies of auxin homeostasis.
AU - Steenackers, Ward
AU - Klíma, Petr
AU - Quareshy, Mussa
AU - Cesarino, Igor
AU - Kumpf, Robert
AU - Corneillie, Sander
AU - Araújo, Pedro
AU - Viaene, Tom
AU - Goeminne, Geert
AU - Nowack, Moritz
AU - Ljung, Karin
AU - Friml, Jirí
AU - Blakeslee, Joshua
AU - Novák, Ondřej
AU - Zažímalová, Eva
AU - Napier, Richard
AU - Boerjan, Wout
AU - Vanholme, Bartel
ID - 1159
IS - 1
JF - Plant Physiology
SN - 0032-0889
TI - Cis-cinnamic acid is a novel natural auxin efflux inhibitor that promotes lateral root formation
VL - 173
ER -
TY - JOUR
AB - Dispersal is a crucial factor in natural evolution, since it determines the habitat experienced by any population and defines the spatial scale of interactions between individuals. There is compelling evidence for systematic differences in dispersal characteristics within the same population, i.e., genotype-dependent dispersal. The consequences of genotype-dependent dispersal on other evolutionary phenomena, however, are poorly understood. In this article we investigate the effect of genotype-dependent dispersal on spatial gene frequency patterns, using a generalization of the classical diffusion model of selection and dispersal. Dispersal is characterized by the variance of dispersal (diffusion coefficient) and the mean displacement (directional advection term). We demonstrate that genotype-dependent dispersal may change the qualitative behavior of Fisher waves, which change from being “pulled” to being “pushed” wave fronts as the discrepancy in dispersal between genotypes increases. The speed of any wave is partitioned into components due to selection, genotype-dependent variance of dispersal, and genotype-dependent mean displacement. We apply our findings to wave fronts maintained by selection against heterozygotes. Furthermore, we identify a benefit of increased variance of dispersal, quantify its effect on the speed of the wave, and discuss the implications for the evolution of dispersal strategies.
AU - Novak, Sebastian
AU - Kollár, Richard
ID - 1169
IS - 1
JF - Genetics
SN - 00166731
TI - Spatial gene frequency waves under genotype dependent dispersal
VL - 205
ER -
TY - JOUR
AB - We investigate fundamental nonlinear dynamics of ferrofluidic Taylor-Couette flow - flow confined be-tween two concentric independently rotating cylinders - consider small aspect ratio by solving the ferro-hydrodynamical equations, carrying out systematic bifurcation analysis. Without magnetic field, we find steady flow patterns, previously observed with a simple fluid, such as those containing normal one- or two vortex cells, as well as anomalous one-cell and twin-cell flow states. However, when a symmetry-breaking transverse magnetic field is present, all flow states exhibit stimulated, finite two-fold mode. Various bifurcations between steady and unsteady states can occur, corresponding to the transitions between the two-cell and one-cell states. While unsteady, axially oscillating flow states can arise, we also detect the emergence of new unsteady flow states. In particular, we uncover two new states: one contains only the azimuthally oscillating solution in the configuration of the twin-cell flow state, and an-other a rotating flow state. Topologically, these flow states are a limit cycle and a quasiperiodic solution on a two-torus, respectively. Emergence of new flow states in addition to observed ones with classical fluid, indicates that richer but potentially more controllable dynamics in ferrofluidic flows, as such flow states depend on the external magnetic field.
AU - Altmeyer, Sebastian
AU - Do, Younghae
AU - Lai, Ying
ID - 1160
JF - Scientific Reports
SN - 20452322
TI - Dynamics of ferrofluidic flow in the Taylor-Couette system with a small aspect ratio
VL - 7
ER -
TY - JOUR
AB - Selected universal experimental properties of high-temperature superconducting (HTS) cuprates have been singled out in the last decade. One of the pivotal challenges in this field is the designation of a consistent interpretation framework within which we can describe quantitatively the universal features of those systems. Here we analyze in a detailed manner the principal experimental data and compare them quantitatively with the approach based on a single-band model of strongly correlated electrons supplemented with strong antiferromagnetic (super)exchange interaction (the so-called t−J−U model). The model rationale is provided by estimating its microscopic parameters on the basis of the three-band approach for the Cu-O plane. We use our original full Gutzwiller wave-function solution by going beyond the renormalized mean-field theory (RMFT) in a systematic manner. Our approach reproduces very well the observed hole doping (δ) dependence of the kinetic-energy gain in the superconducting phase, one of the principal non-Bardeen-Cooper-Schrieffer features of the cuprates. The calculated Fermi velocity in the nodal direction is practically δ-independent and its universal value agrees very well with that determined experimentally. Also, a weak doping dependence of the Fermi wave vector leads to an almost constant value of the effective mass in a pure superconducting phase which is both observed in experiment and reproduced within our approach. An assessment of the currently used models (t−J, Hubbard) is carried out and the results of the canonical RMFT as a zeroth-order solution are provided for comparison to illustrate the necessity of the introduced higher-order contributions.
AU - Spałek, Jozef
AU - Zegrodnik, Michał
AU - Kaczmarczyk, Jan
ID - 1162
IS - 2
JF - Physical Review B - Condensed Matter and Materials Physics
SN - 24699950
TI - Universal properties of high temperature superconductors from real space pairing t-J-U model and its quantitative comparison with experiment
VL - 95
ER -
TY - JOUR
AB - We propose a new memetic strategy that can solve the multi-physics, complex inverse problems, formulated as the multi-objective optimization ones, in which objectives are misfits between the measured and simulated states of various governing processes. The multi-deme structure of the strategy allows for both, intensive, relatively cheap exploration with a moderate accuracy and more accurate search many regions of Pareto set in parallel. The special type of selection operator prefers the coherent alternative solutions, eliminating artifacts appearing in the particular processes. The additional accuracy increment is obtained by the parallel convex searches applied to the local scalarizations of the misfit vector. The strategy is dedicated for solving ill-conditioned problems, for which inverting the single physical process can lead to the ambiguous results. The skill of the selection in artifact elimination is shown on the benchmark problem, while the whole strategy was applied for identification of oil deposits, where the misfits are related to various frequencies of the magnetic and electric waves of the magnetotelluric measurements. 2016 Elsevier B.V.
AU - Gajda-Zagorska, Ewa P
AU - Schaefer, Robert
AU - Smołka, Maciej
AU - Pardo, David
AU - Alvarez Aramberri, Julen
ID - 1152
JF - Journal of Computational Science
SN - 18777503
TI - A multi objective memetic inverse solver reinforced by local optimization methods
VL - 18
ER -