News Article | April 19, 2017
When we make a decision about whether or not to cooperate with someone, we usually base our decision on past experiences -- how has this person behaved in the past? -- and on future reciprocity--will they return the favor? -- and weigh these against the possible benefits of defecting. However, when analyzing strategies for repeated dilemmas, modeling long-term memory in cooperative strategies quickly becomes computationally intractable, and in the past, researchers have either restricted the possible strategy types, or only allowed players to make their decisions based on the previous round ("memory-1"). One basic but important example of a social situation is the prisoner's dilemma. In this situation, two prisoners are given the same options: remain silent or snitch on the other. If they both remain silent, they each get one year in jail. If one talks, and the other remains silent, the one who talks goes free, and the other gets three years in jail. If they both talk, they both get two years. For repeated versions of this game, a variety of successful memory-1 strategies have been found, including "Win-Stay Lose-Shift" (WSLS), where prisoners continue to cooperate or defect until this strategy gives the less desirable outcome. However, if players can remember the last two rounds (memory-2), there are 65'536 possible strategies, and if they can remember up to three rounds (memory-3), this increases to 1.84x10^19--this is already computationally infeasible, not to mention other kinds of social situations with more than two players. To overcome this computational challenge, IST Austria scientists and their collaborators have proposed an alternative approach to the problem of simulating these dilemmas: they have distilled a set of axioms that every robust cooperative strategy should have, and characterize the strategies that satisfy these conditions. In this way, they reduce the computation necessary for an open-ended search of all possible strategies. In particular, their axioms state that a successful cooperative strategy should be: (1) mutually cooperative, (2) able to correct errors, and (3) sufficiently retaliatory against defectors (in Figure A, MCk, ECk, and REk correspond to properties (1), (2), and (3), respectively. "C" indicates cooperation, "D" indicates defection.). The first condition corresponds to continuing to cooperate after rounds of mutual cooperation. The second means that even if a player makes a mistake, after a certain number of rounds, the players return to mutual cooperation. The last protects the group from players who might take advantage of altruism, or who might make the group too altruistic, and thus vulnerable. They found that players with these strategies and memories of length k (that is, they remember the past k rounds of play) will only cooperate if all players took the same actions for the last k rounds (i.e. if they all cooperated or if they all defected)--giving rise to the name all-or-none (AONk) strategies. The WSLS strategy, in particular, is AON1. They moreover show that these strategies evolve naturally in a variety of different social dilemmas, and for groups of arbitrary size. Of course, not every cooperative strategy needs to be AONk to be stable. However, the authors have numerical results that indicate that all-or-none strategies (or delayed versions thereof) in fact make up all memory-2 strategies for the prisoner's dilemma. They also make several predictions: First, if cooperation evolves in the context of a social dilemma, it is the result of all-or-none-type strategies. Second, cooperation evolves more readily in memory-2 strategies than in memory-1 strategies, under reasonable conditions. In other words, a longer-term memory increases the chance that cooperation will evolve. The group further examined the implications of players remembering only how often other players cooperated (and not when). In this case, longer memory did not lead to a greater degree of cooperation, thus indicating that successful strategies depend not only on the degree of past cooperation, but also its context. Krishnendu Chatterjee joined IST Austria in 2009, and became full professor in 2014. He and his group are broadly interested in game theory and computer-aided verification, and one specialty of the group is evolutionary game theory. Post-doc Christian Hilbe is particularly interested in the applications of evolutionary game theory in economics and biology: "It's fascinating to see how mathematics can be used to describe human and animal behavior in a wide range of different situations."
News Article | April 20, 2017
Bacterial populations pose an intriguing puzzle: in so-called isogenic populations, all bacteria have the same genes, but they still behave differently, for example grow at different speeds. Researchers at the Institute of Science and Technology Austria (IST Austria) now solved a part of this puzzle by studying how the bacterium Escherichia coli divides up a protein complex that detoxifies cells by pumping multiple drugs such as antibiotics out of the cell. They found that when a bacterium divides into two, the pump proteins are distributed so that one cell inherits more of the pump proteins than the other cell. Bacterial cells that inherit more pump proteins grow more quickly in low concentrations of antibiotics. Partitioning the pump protein is one way to achieve different behaviors in a bacterial population, and could be a stepping-stone to developing antibiotic resistance. The study, published today in Science, was carried out by an interdisciplinary duo: an experimentalist, Tobias Bergmiller, and a theorist, Anna Andersson, from the groups of C?lin Guet and Gašper Tkačik at IST Austria. A bacterial population is made up of thousands of individual bacteria, all with the same genetic make-up. But these individuals can have a range of phenotypes, i.e. look and behave differently, due to random processes in the cells that influence how the genetic instructions are used. For proteins in the cytosol, the liquid inside the cell, these random molecular processes include differences in the break-down of proteins, or random partitioning into the two cells that form during cell division. In the current study, the researchers looked at how a protein complex in the cell envelope, which surrounds the cell, contributes to this heterogeneity or diversity of phenotypes. AcrAB-TolC, the protein complex studied, is the main protein complex that pumps drugs out of Escherichia coli cells. It is found in the cell envelope, where proteins cluster together as "islands". Unlike in the cytosol, where proteins are generally well-mixed by diffusion, proteins in the envelope can segregate asymmetrically. Some of these clusters form at the cell poles, the rounded ends of rod-shaped bacteria like Escherichia coli. In these bacteria, the cells that are "born" at cell division can be distinguished by their poles. One cell, the mother cell, keeps an old cell pole that originated in a past division, where efflux pump proteins have formed stable clusters. The authors show that AcrAB-TolC accumulates at these old cell poles in mother cells. These mother cells can pump out drugs more efficiently than the daughter cells which did not inherit old cell poles. At low concentrations of antibiotics, the mother cells grow faster than daughter cells. Based on these observations, the researchers developed a mathematical model to identify how this biased partitioning of the drug pump affects the bacterial population. They found that mother cells which can pump out drugs quickly become more common. The population becomes heterogeneous as this extreme phenotype becomes more prevalent as this heterogeneity is long lived. C?lin Guet explains how biased partitioning may be one step on the road to antibiotic resistance: "Recent research by other groups has shown that mutations that cause antibiotic resistance can emerge quickly at low concentrations of antibiotics. Such low concentrations are increasingly found in natural habitats or in patients during drug treatments. Indeed, studies looking at selection due to antibiotics have found that AcrAB, the genes we studied, were amplified. Heterogeneity in a bacterial population that arises through a mechanism of biased partitioning of drug efflux pumps, as we identified in our study, could be a stepping-stone on the path of bacterial populations towards antibiotic resistance." Explore further: New mechanism to fight multi-resistant bacteria revealed More information: "Biased partitioning of the multidrug efflux pump AcrAB-TolC underlies long-lived phenotypic heterogeneity," Science (2017). science.sciencemag.org/cgi/doi/10.1126/science.aaf4762
News Article | May 4, 2017
Neurons and glia are the cells that make up our brain. In the cortex, the brain area that enables us to think, speak and be conscious, neurons and most glia are produced by a type of neural stem cell, called radial glia progenitors (RGPs). It is vital that no errors occur in this process as disruptions can lead to neurodevelopmental disorders such as microcephaly, a condition in which a baby's head and cortex are significantly smaller than that of other babies. But how is this production of neurons and glia cells controlled? Simon Hippenmeyer and his group at the Institute of Science and Technology Austria (IST Austria), including first author Robert Beattie, as well as colleagues at North Carolina State University and the Fred Hutchinson Cancer Research Center in USA, found that a gene called Lgl1 controls the production of certain neurons in the cortex of mouse embryos, and plays a role in the production of other types of neurons and glia after birth. This is the result of a study published in Neuron. The production of neurons and glia in the developing cortex is tightly regulated. RGPs produce the majority of them. In previous studies, Hippenmeyer and colleagues have shown that the division pattern of RGPs is not random. They have demonstrated that each individual RGP produces a predefined unit of neurons and glia cells in a precisely orchestrated developmental program which ensures that the brain faithfully grows to its normal size. In the present Neuron study, the authors asked what mechanisms control the exact output of RGPs. In particular, the researchers investigated the role of the gene Lgl1, which had been predicted to regulate RGP proliferation. The gene's precise role was previously unknown and Hippenmeyer and colleagues now used a technique called MADM, short for Mosaic Analysis with Double Markers in order to decipher the function of Lgl1 in RGPs at unprecedented single cell resolution. Using MADM, Hippenmeyer and colleagues eliminated Lgl1 either in just single RGPs, or in all RGPs. At the same time, individual cells are labelled fluorescently, so that they can be studied under the microscope. The authors show that Lgl1 controls the generation of neurons and glia cells in the developing cortex in two different ways. First, for the generation of neurons in the early embryo the function of Lgl1 is simultaneously required in the entire population of RGPs. If Lgl1 function is absent in all RGPs, but not if absent in just individual RGP cells, dynamic community effects lead to malformation of the cortex resembling 'Double Cortex Syndrome', a severe human brain disorder. Second, for the production of glia cells and neurons in the postnatal brain, Lgl1 function is 'only' required in the individual stem cell which is just in the process of generating a neuron or glia cell. This type of Lgl1 gene function is called cell-autonomous or intrinsic while the requirement of Lgl1 gene function in the entire community is called non-cell-autonomous. In other words, you require the entire orchestra for a symphony (generate neurons in embryonic cortex) but only an individual soloist for a solo (produce neurons or glia cells in postnatal brain). Simon Hippenmeyer explains how this research will influence the way how the role of genes during development should be analysed in the future: "Our study emphasizes that both intrinsic gene functions and community-based environmental contributions are important for the control of radial glia progenitor cells in the cortex in particular, and for neural stem cells in general. It will thus be important in future genetic loss-of-function experiments to precisely dissect the relative contributions of cell-autonomous, intrinsic, gene functions and the influence of the stem cell niche microenvironment to the overall interpretation of a gene function."
News Article | May 4, 2017
Postdoc Joël Alwen and Professor Krzysztof Pietrzak -- together with their US collaborators -- have been awarded the best paper award at the Eurocrypt '17 conference. Their prize-winning work proves the existence of "memory-hard" functions, cryptographic functions that are designed to be "egalitarian" in the sense that they can't be computed at lower cost on dedicated hardware as compared to standard CPUs. These functions are crucial to securing password servers and have applications in the next generation of decentralized cryptocurrencies. A server will usually not store a user's password in the clear, but will instead apply a cryptographic hash function to it and store only the output, known as the hash value. This way a server can still verify a password by applying the hash function and checking if the output is the same as the stored value. However, if the password file is stolen -- something "which unfortunately seems to happen pretty much constantly," says Pietrzak -- the passwords are not immediately compromised: To find the password corresponding to a hash value, the adversary must hash different password candidates until the hash matches the stored value. For a typical human-generated password this requires hashing in the order of a billion values. Unfortunately a billion is not really much, so to make the adversaries task even harder, one uses a "moderately hard" hash function, which is expensive, but not too expensive, to compute -- this is not much of a burden for the server, who computes the function once per login attempt, but should make computing billions of hashes extremely costly for the adversary. The classical approach towards constructing moderately hard functions is to simply iterate a standard hash function a few thousand times. Unfortunately, this does not gain nearly as much security as one might hope: while servers use standard CPUs, an adversary can use special-purpose hardware on which evaluating such functions is several orders of magnitude cheaper in terms of hardware and energy cost. Thus brute-forcing passwords was nowhere near as costly as anticipated! To address this problem, in 2009, Colin Percival put forth the notion of "memory-hard" functions (MHFs)--moderately hard functions whose evaluation cost is dominated by memory cost. MHFs would be egalitarian: as memory cost is about the same over different hardware platforms, having special hardware would no longer benefit the adversary. Moreover, Percival also proposed a candidate MHF called scrypt, which became widely deployed. A first formal definition capturing memory-hardness (called parallel cumulative memory complexity) was only given six years later, in 2015, by IST Austria postdoc Joël Alwen and Vladimir Serbinenko of ETH Zurich. A variety of candidate MHFs--including a winner of a two-year password-hashing competition--were shown to not meet this definition. The status of Percival's original function scrypt, however, remained unresolved. In 2016, the cryptography groups at IST Austria and the University of California Santa Barbara presented initial progress in this direction. Now, a year later, together with Leonid Reyzin of Boston University -- who in 2016 spend a sabbatical at IST Austria -- they have succeeded in making the final steps, and have finally proved that scrypt is memory-hard. Their result, which will be presented in Paris at this year's Eurocrypt conference -- one of the two main cryptography conferences -- enhances our understanding of memory-hard functions in general, and scrypt in particular. This not only increases our trust in using scrypt for password hashing, but also a variety of decentralized cryptocurrencies, such as Litecoin and Dogecoin, already make use of scrypt. "This line of research still holds many exciting open problems that we are currently working on" says Pietrzak, "for example, the current models only capture hardware cost, but achieving egalitarianism in terms of energy cost is not yet well understood." Joël Alwen joined IST Austria as a postdoc in 2014, and has interests ranging from lattice-based cryptography to leakage resilience. He has also been involved a variety of programming projects, including the Netflix Challenge and designing attacks on password hashing functions. Professor Krzysztof Piertzak has headed the cryptography group at IST Austria since 2011, and explores a broad range of theoretical and practical aspects of cryptography, including memory-hard functions, cryptography for lightweight devices, symmetric cryptography, and sustainable cryptocurrencies. The Institute of Science and Technology (IST Austria) is a PhD granting research institution located in Klosterneuburg, 18 km from the center of Vienna, Austria. Inaugurated in 2009, the Institute is dedicated to basic research in the natural and mathematical sciences. IST Austria employs professors on a tenure-track system, postdoctoral fellows, and doctoral students at its international graduate school. While dedicated to the principle of curiosity-driven research, the Institute owns the rights to all scientific discoveries and is committed to promote their use. The first president of IST Austria is Thomas A. Henzinger, a leading computer scientist and former professor at the University of California in Berkeley, USA, und der EPFL in Lausanne, Switzerland.
News Article | July 25, 2017
Genes do not exist in isolation. Like beads on a string, they sit next to each other on long DNA molecules called chromosomes. So far, little has been known about how the position of a gene on a chromosome affects its evolution. A new study by Calin Guet, Professor at the Institute of Science and Technology Austria (IST Austria), and Magdalena Steinrück, PhD student in Guet's group, shows that a gene's neighborhood can influence whether and how the activity of a gene changes. The study was published today in the open access journal eLife. From bacteria to humans, the way organisms look and function depends a lot on how much product is made from each gene, in other words how active their genes are. The activity of a gene can be changed by mutations, alterations in the DNA that can be inherited. This can make the organism better adapted to its environment - or worse. For example, a bacterium that produces more of a protein that helps it get rid of an antibiotic may survive, while its competitors are killed by the antibiotic. In their study, Steinrück and Guet used experimental evolution to investigate how the position of a gene on the chromosome influences mutations that increase the activity of the gene. The researchers engineered the DNA of the gut bacterium Escherichia coli to place an antibiotic resistance gene at different positions of its chromosome. This gene allows the bacterium to pump the antibiotic tetracycline out of the cell. At the start of the experiment, the gene was almost completely switched off. The researchers then added more and more tetracycline to the bacteria's environment. This challenges the bacteria to switch the gene on by mutation, as producing more of the antibiotic resistance gene allows them to pump the antibiotic out, so that they multiply and survive. The authors found that the bacteria were much more likely to survive with the resistance gene in some places of the chromosome than at others. This is because the gene's neighborhood affects which types of mutations can occur - some forms of mutations can only occur if the neighboring genes permit them to. "We show that genes can influence the mutation and adaptive potential of nearby genes. The organization of genes on a chromosome is both cause and consequence of evolutionary change", explains Calin Guet. Their research has vital implications, for example for the global health problem of antibiotic resistance. Magdalena Steinrück: "It is similar to the way humans develop: People in your neighborhood can influence greatly how your future looks like. Our study shows that antibiotic resistance developing from gene activating mutations depends strongly on the gene's neighborhood." Chromosome neighborhood effects have not been looked at in detail so far. In future, such findings could help to better estimate whether new antibiotic resistance is to be expected. The Institute of Science and Technology (IST Austria) is a PhD granting research institution located in Klosterneuburg, 18 km from the center of Vienna, Austria. Inaugurated in 2009, the Institute is dedicated to basic research in the natural and mathematical sciences. IST Austria employs professors on a tenure-track system, postdoctoral fellows, and doctoral students at its international graduate school. While dedicated to the principle of curiosity-driven research, the Institute owns the rights to all scientific discoveries and is committed to promote their use. The first president of IST Austria is Thomas A. Henzinger, a leading computer scientist and former professor at the University of California in Berkeley, USA, and the EPFL in Lausanne, Switzerland. http://www. Original publication: Magdalena Steinrueck and Calin Guet: "Complex chromosomal neighborhood effects determine the adaptive potential of a gene under selection", elife July 25, 2017 https:/
News Article | February 28, 2017
How do molecules rotate in a solvent? Answering this question is a complicated task since the molecular rotation is perturbed by a very large number of surrounding atoms. For a long time, large-scale computer simulations have been the main approach to model molecule-solvent interactions. However, they are extremely time consuming and sometimes completely infeasible. Now, Mikhail Lemeshko from the Institute of Science and Technology Austria (IST Austria) has proven that angulons -- a certain type of quasiparticle he proposed two years ago - do in fact form when a molecule is immersed in superfluid helium. This offers a quick and simple description for rotation of molecules in solvents. In physics, the concept of quasiparticles is used as a technique to simplify the description of many-particle systems. Namely, instead of modeling strong interactions between trillions of individual particles, one identifies building blocks of the system that are interacting with one another only weakly. These building blocks are called quasiparticles and might consist of groups of particles. For example, to describe air bubbles rising up in water from first principles, one would need to solve an enormous set of equations describing the position and momentum of each water molecule. On the other hand, one could notice that the bubbles themselves can be treated as individual particles -- or quasiparticles -- which drastically simplifies the description of the system. As another example, consider a running horse engulfed in a cloud of dust. One can think of it as a quasiparticle consisting of the horse itself and the dust cloud moving along with it. Understanding what is going on in terms of such a 'quasi-horse' is substantially easier compared to treating every dust grain, as well as the horse, separately in a complicated simulation. The latter example is similar to what Mikhail Lemeshko did in his study. Instead of treating the rotating molecule and all the atoms of the surrounding material separately, he used angulons to look at the problem from a different perspective. Angulon quasiparticles, which form when a rotating object interacts with a surrounding environment, were predicted theoretically two years ago by Lemeshko and Schmidt. Until now, however, they were considered only theoretically and their actual existence was still to be demonstrated. Lemeshko's study, which was published today in Physical Review Letters, is based on experimental data collected by several laboratories over the last two decades. All the experiments had one thing in common: molecules of different types were observed to rotate inside tiny droplets of superfluid helium. As Lemeshko has shown, independent of which molecule was studied, be it heavy or light species, methane, water, carbon dioxide or ammonia, the outcome of the angulon theory was always in good agreement with the measurements. This indicates that the angulon quasiparticles indeed form inside helium droplets. "In our first study we proposed angulons as a possibility for describing rotation of molecules in solvents. Now we have provided strong evidence that angulons actually exist," says Lemeshko. This substantially simplifies existing many-particle theories and could lead to applications in molecular physics, theoretical chemistry, and even biology. A first application of the angulon theory was already found by Enderalp Yakaboylu, a postdoc in Lemeshko's group. The authors predicted that even a medium that is non-polarizable can shield an immersed impurity from an external electromagnetic field. This effect, which seems to contradict intuition, is called "anomalous screening" and is caused by an exchange of angular momentum on quantum level. The discovery, which the authors also publish in Physical Review Letters, was made possible by describing the charged particle and the interacting surroundings as angulon quasiparticle. Future measurements will show if the prediction can be proven experimentally. Mikhail Lemeshko joined IST Austria in 2014 after having spent three years as an independent postdoctoral fellow at Harvard University. His research group entitled "Theoretical Atomic, Molecular, and Optical Physics" currently includes three postdocs and one PhD student. The main focus of study is the physics of quantum impurities possessing orbital angular momentum. He was recently awarded a standalone grant by the Austrian Science Fund (FWF) to continue his work on angulons. Enderalp Yakaboylu is a postdoc in IST Austria's ISTFELLOW program which is partially funded by the European Union.
Chevereau G.,IST Austria |
Bollenbach T.,IST Austria
Molecular Systems Biology | Year: 2015
Abstract Drug combinations are increasingly important in disease treatments, for combating drug resistance, and for elucidating fundamental relationships in cell physiology. When drugs are combined, their individual effects on cells may be amplified or weakened. Such drug interactions are crucial for treatment efficacy, but their underlying mechanisms remain largely unknown. To uncover the causes of drug interactions, we developed a systematic approach based on precise quantification of the individual and joint effects of antibiotics on growth of genome-wide Escherichia coli gene deletion strains. We found that drug interactions between antibiotics representing the main modes of action are highly robust to genetic perturbation. This robustness is encapsulated in a general principle of bacterial growth, which enables the quantitative prediction of mutant growth rates under drug combinations. Rare violations of this principle exposed recurring cellular functions controlling drug interactions. In particular, we found that polysaccharide and ATP synthesis control multiple drug interactions with previously unexplained mechanisms, and small molecule adjuvants targeting these functions synthetically reshape drug interactions in predictable ways. These results provide a new conceptual framework for the design of multidrug combinations and suggest that there are universal mechanisms at the heart of most drug interactions. Synopsis A general principle of bacterial growth enables the prediction of mutant growth rates under drug combinations. Rare violations of this principle expose cellular functions that control drug interactions and can be targeted by small molecules to alter drug interactions in predictable ways. Drug interactions between antibiotics are highly robust to genetic perturbations. A general principle of bacterial growth enables the prediction of mutant growth rates under drug combinations. Rare violations of this principle expose cellular functions that control drug interactions. Diverse drug interactions are controlled by recurring cellular functions, including LPS synthesis and ATP synthesis. A general principle of bacterial growth enables the prediction of mutant growth rates under drug combinations. Rare violations of this principle expose cellular functions that control drug interactions and can be targeted by small molecules to alter drug interactions in predictable ways. © 2015 The Authors.
Bollenbach T.,IST Austria
Current Opinion in Microbiology | Year: 2015
Combining antibiotics is a promising strategy for increasing treatment efficacy and for controlling resistance evolution. When drugs are combined, their effects on cells may be amplified or weakened, that is the drugs may show synergistic or antagonistic interactions. Recent work revealed the underlying mechanisms of such drug interactions by elucidating the drugs' joint effects on cell physiology. Moreover, new treatment strategies that use drug combinations to exploit evolutionary tradeoffs were shown to affect the rate of resistance evolution in predictable ways. High throughput studies have further identified drug candidates based on their interactions with established antibiotics and general principles that enable the prediction of drug interactions were suggested. Overall, the conceptual and technical foundation for the rational design of potent drug combinations is rapidly developing. © 2015 The Authors.
Csicsvari J.,IST Austria
Philosophical transactions of the Royal Society of London. Series B, Biological sciences | Year: 2014
Sharp wave/ripple (SWR, 150-250 Hz) hippocampal events have long been postulated to be involved in memory consolidation. However, more recent work has investigated SWRs that occur during active waking behaviour: findings that suggest that SWRs may also play a role in cell assembly strengthening or spatial working memory. Do such theories of SWR function apply to animal learning? This review discusses how general theories linking SWRs to memory-related function may explain circuit mechanisms related to rodent spatial learning and to the associated stabilization of new cognitive maps.
Maitre J.-L.,EMBL |
Heisenberg C.-P.,IST Austria
Current Biology | Year: 2013
Cadherins are transmembrane proteins that mediate cell-cell adhesion in animals. By regulating contact formation and stability, cadherins play a crucial role in tissue morphogenesis and homeostasis. Here, we review the three major functions of cadherins in cell-cell contact formation and stability. Two of those functions lead to a decrease in interfacial tension at the forming cell-cell contact, thereby promoting contact expansion - first, by providing adhesion tension that lowers interfacial tension at the cell-cell contact, and second, by signaling to the actomyosin cytoskeleton in order to reduce cortex tension and thus interfacial tension at the contact. The third function of cadherins in cell-cell contact formation is to stabilize the contact by resisting mechanical forces that pull on the contact. © 2013 Elsevier Ltd.