TY - CONF AB - An automaton with advice is a finite state automaton which has access to an additional fixed infinite string called an advice tape. We refine the Myhill-Nerode theorem to characterize the languages of finite strings that are accepted by automata with advice. We do the same for tree automata with advice. AU - Kruckman, Alex AU - Rubin, Sasha AU - Sheridan, John AU - Zax, Ben ID - 495 T2 - Proceedings GandALF 2012 TI - A Myhill Nerode theorem for automata with advice VL - 96 ER - TY - JOUR AB - Understanding patterns and correlates of local adaptation in heterogeneous landscapes can provide important information in the selection of appropriate seed sources for restoration. We assessed the extent of local adaptation of fitness components in 12 population pairs of the perennial herb Rutidosis leptorrhynchoides (Asteraceae) and examined whether spatial scale (0.7-600 km), environmental distance, quantitative (QST) and neutral (FST) genetic differentiation, and size of the local and foreign populations could predict patterns of adaptive differentiation. Local adaptation varied among populations and fitness components. Including all population pairs, local adaptation was observed for seedling survival, but not for biomass, while foreign genotype advantage was observed for reproduction (number of inflorescences). Among population pairs, local adaptation increased with QST and local population size for biomass. QST was associated with environmental distance, suggesting ecological selection for phenotypic divergence. However, low FST and variation in population structure in small populations demonstrates the interaction of gene flow and drift in constraining local adaptation in R. leptorrhynchoides. Our study indicates that for species in heterogeneous landscapes, collecting seed from large populations from similar environments to candidate sites is likely to provide the most appropriate seed sources for restoration. AU - Pickup, Melinda AU - Field, David AU - Rowell, David AU - Young, Andrew ID - 498 IS - 8 JF - Evolutionary Applications TI - Predicting local adaptation in fragmented plant populations: Implications for restoration genetics VL - 5 ER - TY - CONF AB - We study the expressive power of logical interpretations on the class of scattered trees, namely those with countably many infinite branches. Scattered trees can be thought of as the tree analogue of scattered linear orders. Every scattered tree has an ordinal rank that reflects the structure of its infinite branches. We prove, roughly, that trees and orders of large rank cannot be interpreted in scattered trees of small rank. We consider a quite general notion of interpretation: each element of the interpreted structure is represented by a set of tuples of subsets of the interpreting tree. Our trees are countable, not necessarily finitely branching, and may have finitely many unary predicates as labellings. We also show how to replace injective set-interpretations in (not necessarily scattered) trees by 'finitary' set-interpretations. AU - Rabinovich, Alexander AU - Rubin, Sasha ID - 496 TI - Interpretations in trees with countably many branches ER - TY - JOUR AB - We solve the longstanding open problems of the blow-up involved in the translations, when possible, of a nondeterministic Büchi word automaton (NBW) to a nondeterministic co-Büchi word automaton (NCW) and to a deterministic co-Büchi word automaton (DCW). For the NBW to NCW translation, the currently known upper bound is 2o(nlog n) and the lower bound is 1.5n. We improve the upper bound to n2n and describe a matching lower bound of 2ω(n). For the NBW to DCW translation, the currently known upper bound is 2o(nlog n). We improve it to 2 o(n), which is asymptotically tight. Both of our upper-bound constructions are based on a simple subset construction, do not involve intermediate automata with richer acceptance conditions, and can be implemented symbolically. We continue and solve the open problems of translating nondeterministic Streett, Rabin, Muller, and parity word automata to NCW and to DCW. Going via an intermediate NBW is not optimal and we describe direct, simple, and asymptotically tight constructions, involving a 2o(n) blow-up. The constructions are variants of the subset construction, providing a unified approach for translating all common classes of automata to NCW and DCW. Beyond the theoretical importance of the results, we point to numerous applications of the new constructions. In particular, they imply a simple subset-construction based translation, when possible, of LTL to deterministic Büchi word automata. AU - Boker, Udi AU - Kupferman, Orna ID - 494 IS - 4 JF - ACM Transactions on Computational Logic (TOCL) TI - Translating to Co-Büchi made tight, unified, and useful VL - 13 ER - TY - JOUR AU - Sixt, Michael K ID - 506 IS - 3 JF - Journal of Cell Biology TI - Cell migration: Fibroblasts find a new way to get ahead VL - 197 ER - TY - CONF AB - One central issue in the formal design and analysis of reactive systems is the notion of refinement that asks whether all behaviors of the implementation is allowed by the specification. The local interpretation of behavior leads to the notion of simulation. Alternating transition systems (ATSs) provide a general model for composite reactive systems, and the simulation relation for ATSs is known as alternating simulation. The simulation relation for fair transition systems is called fair simulation. In this work our main contributions are as follows: (1) We present an improved algorithm for fair simulation with Büchi fairness constraints; our algorithm requires O(n 3·m) time as compared to the previous known O(n 6)-time algorithm, where n is the number of states and m is the number of transitions. (2) We present a game based algorithm for alternating simulation that requires O(m2)-time as compared to the previous known O((n·m)2)-time algorithm, where n is the number of states and m is the size of transition relation. (3) We present an iterative algorithm for alternating simulation that matches the time complexity of the game based algorithm, but is more space efficient than the game based algorithm. © Krishnendu Chatterjee, Siddhesh Chaubal, and Pritish Kamath. AU - Chatterjee, Krishnendu AU - Chaubal, Siddhesh AU - Kamath, Pritish ID - 497 TI - Faster algorithms for alternating refinement relations VL - 16 ER - TY - CONF AB - Computing the winning set for Büchi objectives in alternating games on graphs is a central problem in computer aided verification with a large number of applications. The long standing best known upper bound for solving the problem is Õ(n·m), where n is the number of vertices and m is the number of edges in the graph. We are the first to break the Õ(n·m) boundary by presenting a new technique that reduces the running time to O(n 2). This bound also leads to O(n 2) time algorithms for computing the set of almost-sure winning vertices for Büchi objectives (1) in alternating games with probabilistic transitions (improving an earlier bound of Õ(n·m)), (2) in concurrent graph games with constant actions (improving an earlier bound of O(n 3)), and (3) in Markov decision processes (improving for m > n 4/3 an earlier bound of O(min(m 1.5, m·n 2/3)). We also show that the same technique can be used to compute the maximal end-component decomposition of a graph in time O(n 2), which is an improvement over earlier bounds for m > n 4/3. Finally, we show how to maintain the winning set for Büchi objectives in alternating games under a sequence of edge insertions or a sequence of edge deletions in O(n) amortized time per operation. This is the first dynamic algorithm for this problem. AU - Chatterjee, Krishnendu AU - Henzinger, Monika H ID - 3165 T2 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms TI - An O(n2) time algorithm for alternating Büchi games ER - TY - CONF AB - Two-player games on graphs are central in many problems in formal verification and program analysis such as synthesis and verification of open systems. In this work we consider solving recursive game graphs (or pushdown game graphs) that can model the control flow of sequential programs with recursion. While pushdown games have been studied before with qualitative objectives, such as reachability and parity objectives, in this work we study for the first time such games with the most well-studied quantitative objective, namely, mean payoff objectives. In pushdown games two types of strategies are relevant: (1) global strategies, that depend on the entire global history; and (2) modular strategies, that have only local memory and thus do not depend on the context of invocation, but only on the history of the current invocation of the module. Our main results are as follows: (1) One-player pushdown games with mean-payoff objectives under global strategies are decidable in polynomial time. (2) Two-player pushdown games with mean-payoff objectives under global strategies are undecidable. (3) One-player pushdown games with mean-payoff objectives under modular strategies are NP-hard. (4) Two-player pushdown games with mean-payoff objectives under modular strategies can be solved in NP (i.e., both one-player and two-player pushdown games with mean-payoff objectives under modular strategies are NP-complete). We also establish the optimal strategy complexity showing that global strategies for mean-payoff objectives require infinite memory even in one-player pushdown games; and memoryless modular strategies are sufficient in two-player pushdown games. Finally we also show that all the problems have the same computational complexity if the stack boundedness condition is added, where along with the mean-payoff objective the player must also ensure that the stack height is bounded. AU - Chatterjee, Krishnendu AU - Velner, Yaron ID - 2956 T2 - Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science TI - Mean payoff pushdown games ER - TY - GEN AB - Two-player games on graphs are central in many problems in formal verification and program analysis such as synthesis and verification of open systems. In this work we consider solving recursive game graphs (or pushdown game graphs) that can model the control flow of sequential programs with recursion. While pushdown games have been studied before with qualitative objectives, such as reachability and ω-regular objectives, in this work we study for the first time such games with the most well-studied quantitative objective, namely, mean-payoff objectives. In pushdown games two types of strategies are relevant: (1) global strategies, that depend on the entire global history; and (2) modular strategies, that have only local memory and thus do not depend on the context of invocation, but only on the history of the current invocation of the module. Our main results are as follows: (1) One-player pushdown games with mean-payoff objectives under global strategies are decidable in polynomial time. (2) Two- player pushdown games with mean-payoff objectives under global strategies are undecidable. (3) One-player pushdown games with mean-payoff objectives under modular strategies are NP- hard. (4) Two-player pushdown games with mean-payoff objectives under modular strategies can be solved in NP (i.e., both one-player and two-player pushdown games with mean-payoff objectives under modular strategies are NP-complete). We also establish the optimal strategy complexity showing that global strategies for mean-payoff objectives require infinite memory even in one-player pushdown games; and memoryless modular strategies are sufficient in two- player pushdown games. Finally we also show that all the problems have the same complexity if the stack boundedness condition is added, where along with the mean-payoff objective the player must also ensure that the stack height is bounded. AU - Chatterjee, Krishnendu AU - Velner, Yaron ID - 5377 SN - 2664-1690 TI - Mean-payoff pushdown games ER - TY - GEN AB - One central issue in the formal design and analysis of reactive systems is the notion of refinement that asks whether all behaviors of the implementation is allowed by the specification. The local interpretation of behavior leads to the notion of simulation. Alternating transition systems (ATSs) provide a general model for composite reactive systems, and the simulation relation for ATSs is known as alternating simulation. The simulation relation for fair transition systems is called fair simulation. In this work our main contributions are as follows: (1) We present an improved algorithm for fair simulation with Büchi fairness constraints; our algorithm requires O(n3 · m) time as compared to the previous known O(n6)-time algorithm, where n is the number of states and m is the number of transitions. (2) We present a game based algorithm for alternating simulation that requires O(m2)-time as compared to the previous known O((n · m)2)-time algorithm, where n is the number of states and m is the size of transition relation. (3) We present an iterative algorithm for alternating simulation that matches the time complexity of the game based algorithm, but is more space efficient than the game based algorithm. AU - Chatterjee, Krishnendu AU - Chaubal, Siddhesh AU - Kamath, Pritish ID - 5378 SN - 2664-1690 TI - Faster algorithms for alternating refinement relations ER - TY - CONF AB - We consider two-player stochastic games played on finite graphs with reachability objectives where the first player tries to ensure a target state to be visited almost-surely (i.e., with probability 1), or positively (i.e., with positive probability), no matter the strategy of the second player. We classify such games according to the information and the power of randomization available to the players. On the basis of information, the game can be one-sided with either (a) player 1, or (b) player 2 having partial observation (and the other player has perfect observation), or two-sided with (c) both players having partial observation. On the basis of randomization, the players (a) may not be allowed to use randomization (pure strategies), or (b) may choose a probability distribution over actions but the actual random choice is external and not visible to the player (actions invisible), or (c) may use full randomization. Our main results for pure strategies are as follows. (1) For one-sided games with player 1 having partial observation we show that (in contrast to full randomized strategies) belief-based (subset-construction based) strategies are not sufficient, and we present an exponential upper bound on memory both for almostsure and positive winning strategies; we show that the problem of deciding the existence of almost-sure and positive winning strategies for player 1 is EXPTIME-complete. (2) For one-sided games with player 2 having partial observation we show that non-elementary memory is both necessary and sufficient for both almost-sure and positive winning strategies. (3) We show that for the general (two-sided) case finite-memory strategies are sufficient for both positive and almost-sure winning, and at least non-elementary memory is required. We establish the equivalence of the almost-sure winning problems for pure strategies and for randomized strategies with actions invisible. Our equivalence result exhibits serious flaws in previous results of the literature: we show a non-elementary memory lower bound for almost-sure winning whereas an exponential upper bound was previously claimed. AU - Chatterjee, Krishnendu AU - Doyen, Laurent ID - 2955 T2 - Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science TI - Partial-observation stochastic games: How to win when belief fails ER - TY - CONF AB - We consider two-player stochastic games played on a finite state space for an infinite number of rounds. The games are concurrent: in each round, the two players (player 1 and player 2) choose their moves independently and simultaneously; the current state and the two moves determine a probability distribution over the successor states. We also consider the important special case of turn-based stochastic games where players make moves in turns, rather than concurrently. We study concurrent games with \omega-regular winning conditions specified as parity objectives. The value for player 1 for a parity objective is the maximal probability with which the player can guarantee the satisfaction of the objective against all strategies of the opponent. We study the problem of continuity and robustness of the value function in concurrent and turn-based stochastic parity gameswith respect to imprecision in the transition probabilities. We present quantitative bounds on the difference of the value function (in terms of the imprecision of the transition probabilities) and show the value continuity for structurally equivalent concurrent games (two games are structurally equivalent if the support of the transition function is same and the probabilities differ). We also show robustness of optimal strategies for structurally equivalent turn-based stochastic parity games. Finally we show that the value continuity property breaks without the structurally equivalent assumption (even for Markov chains) and show that our quantitative bound is asymptotically optimal. Hence our results are tight (the assumption is both necessary and sufficient) and optimal (our quantitative bound is asymptotically optimal). AU - Chatterjee, Krishnendu ID - 3341 TI - Robustness of structurally equivalent concurrent parity games VL - 7213 ER - TY - CONF AB - We consider probabilistic automata on infinite words with acceptance defined by parity conditions. We consider three qualitative decision problems: (i) the positive decision problem asks whether there is a word that is accepted with positive probability; (ii) the almost decision problem asks whether there is a word that is accepted with probability 1; and (iii) the limit decision problem asks whether words are accepted with probability arbitrarily close to 1. We unify and generalize several decidability results for probabilistic automata over infinite words, and identify a robust (closed under union and intersection) subclass of probabilistic automata for which all the qualitative decision problems are decidable for parity conditions. We also show that if the input words are restricted to lasso shape (regular) words, then the positive and almost problems are decidable for all probabilistic automata with parity conditions. For most decidable problems we show an optimal PSPACE-complete complexity bound. AU - Chatterjee, Krishnendu AU - Tracol, Mathieu ID - 2957 T2 - Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science TI - Decidable problems for probabilistic automata on infinite words ER - TY - JOUR AB - Boolean notions of correctness are formalized by preorders on systems. Quantitative measures of correctness can be formalized by real-valued distance functions between systems, where the distance between implementation and specification provides a measure of "fit" or "desirability". We extend the simulation preorder to the quantitative setting by making each player of a simulation game pay a certain price for her choices. We use the resulting games with quantitative objectives to define three different simulation distances. The correctness distance measures how much the specification must be changed in order to be satisfied by the implementation. The coverage distance measures how much the implementation restricts the degrees of freedom offered by the specification. The robustness distance measures how much a system can deviate from the implementation description without violating the specification. We consider these distances for safety as well as liveness specifications. The distances can be computed in polynomial time for safety specifications, and for liveness specifications given by weak fairness constraints. We show that the distance functions satisfy the triangle inequality, that the distance between two systems does not increase under parallel composition with a third system, and that the distance between two systems can be bounded from above and below by distances between abstractions of the two systems. These properties suggest that our simulation distances provide an appropriate basis for a quantitative theory of discrete systems. We also demonstrate how the robustness distance can be used to measure how many transmission errors are tolerated by error correcting codes. AU - Cerny, Pavol AU - Henzinger, Thomas A AU - Radhakrishna, Arjun ID - 3249 IS - 1 JF - Theoretical Computer Science TI - Simulation distances VL - 413 ER - TY - CONF AB - We consider the problem of inference in a graphical model with binary variables. While in theory it is arguably preferable to compute marginal probabilities, in practice researchers often use MAP inference due to the availability of efficient discrete optimization algorithms. We bridge the gap between the two approaches by introducing the Discrete Marginals technique in which approximate marginals are obtained by minimizing an objective function with unary and pairwise terms over a discretized domain. This allows the use of techniques originally developed for MAP-MRF inference and learning. We explore two ways to set up the objective function - by discretizing the Bethe free energy and by learning it from training data. Experimental results show that for certain types of graphs a learned function can outperform the Bethe approximation. We also establish a link between the Bethe free energy and submodular functions. AU - Korc, Filip AU - Kolmogorov, Vladimir AU - Lampert, Christoph ID - 3124 TI - Approximating marginals using discrete energy minimization ER - TY - GEN AB - We consider the problem of inference in agraphical model with binary variables. While in theory it is arguably preferable to compute marginal probabilities, in practice researchers often use MAP inference due to the availability of efficient discrete optimization algorithms. We bridge the gap between the two approaches by introducing the Discrete Marginals technique in which approximate marginals are obtained by minimizing an objective function with unary and pair-wise terms over a discretized domain. This allows the use of techniques originally devel-oped for MAP-MRF inference and learning. We explore two ways to set up the objective function - by discretizing the Bethe free energy and by learning it from training data. Experimental results show that for certain types of graphs a learned function can out-perform the Bethe approximation. We also establish a link between the Bethe free energy and submodular functions. AU - Korc, Filip AU - Kolmogorov, Vladimir AU - Lampert, Christoph ID - 5396 SN - 2664-1690 TI - Approximating marginals using discrete energy minimization ER - TY - GEN AB - This document is created as a part of the project “Repository for Research Data on IST Austria”. It summarises the actual state of research data at IST Austria, based on survey results. It supports the choice of appropriate software, which would best fit the requirements of their users, the researchers. AU - Porsche, Jana ID - 5398 TI - Actual state of research data @ ISTAustria ER - TY - JOUR AB - Canny's edge detection algorithm is a classical and robust method for edge detection in gray-scale images. The two significant features of this method are introduction of NMS (Non-Maximum Suppression) and double thresholding of the gradient image. Due to poor illumination, the region boundaries in an image may become vague, creating uncertainties in the gradient image. In this paper, we have proposed an algorithm based on the concept of type-2 fuzzy sets to handle uncertainties that automatically selects the threshold values needed to segment the gradient image using classical Canny’s edge detection algorithm. The results show that our algorithm works significantly well on different benchmark images as well as medical images (hand radiography images). AU - Biswas, Ranita AU - Sil, Jaya ID - 5839 JF - Procedia Technology SN - 2212-0173 TI - An Improved Canny Edge Detection Algorithm Based on Type-2 Fuzzy Sets VL - 4 ER - TY - JOUR AB - The human Mediator complex controls RNA polymerase II (pol II) function in ways that remain incompletely understood. Activator-Mediator binding alters Mediator structure, and these activator-induced structural shifts appear to play key roles in regulating transcription. A recent cryo-electron microscopy (EM) analysis revealed that pol II adopted a stable orientation within a Mediator-pol II-TFIIF assembly in which Mediator was bound to the activation domain of viral protein 16 (VP16). Whereas TFIIF was shown to be important for orienting pol II within this assembly, the potential role of the activator was not assessed. To determine how activator binding might affect pol II orientation, we isolated human Mediator-pol II-TFIIF complexes in which Mediator was not bound to an activator. Cryo-EM analysis of this assembly, coupled with pol II crystal structure docking, revealed that pol II binds Mediator at the same general location; however, in contrast to VP16-bound Mediator, pol II does not appear to stably orient in the absence of an activator. Variability in pol II orientation might be important mechanistically, perhaps to enable sense and antisense transcription at human promoters. Because Mediator interacts extensively with pol II, these results suggest that Mediator structural shifts induced by activator binding help stably orient pol II prior to transcription initiation. AU - Bernecky, Carrie A AU - Taatjes, Dylan ID - 596 IS - 5 JF - Journal of Molecular Biology TI - Activator-mediator binding stabilizes RNA polymerase II orientation within the human mediator-RNA polymerase II-TFIIF assembly VL - 417 ER - TY - JOUR AB - Tonic receptors convey stimulus duration and intensity and are implicated in homeostatic control. However, how tonic homeostatic signals are generated and how they reconfigure neural circuits and modify animal behavior is poorly understood. Here we show that Caenorhabditis elegans O2-sensing neurons are tonic receptors that continuously signal ambient [O2] to set the animal's behavioral state. Sustained signaling relied on a Ca2+ relay involving L-type voltage-gated Ca2+ channels, the ryanodine and the inositol-1,4,5-trisphosphate receptors. Tonic activity evoked continuous neuropeptide release, which helps elicit the enduring behavioral state associated with high [O2]. Sustained O2 receptor signaling was propagated to downstream neural circuits, including the hub interneuron RMG. O2 receptors evoked similar locomotory states at particular O2 concentrations, regardless of previous d[O2]/dt. However, a phasic component of the URX receptors' response to high d[O2]/dt, as well as tonic-to-phasic transformations in downstream interneurons, enabled transient reorientation movements shaped by d[O2]/dt. Our results highlight how tonic homeostatic signals can generate both transient and enduring behavioral change. AU - Busch, Karl Emanuel AU - Laurent, Patrick AU - Soltesz, Zoltan AU - Murphy, Robin Joseph AU - Faivre, Olivier AU - Hedwig, Berthold AU - Thomas, Martin AU - Smith, Heather L AU - de Bono, Mario ID - 6136 IS - 4 JF - Nature Neuroscience SN - 1097-6256 TI - Tonic signaling from O2 sensors sets neural circuit activity and behavioral state VL - 15 ER - TY - CONF AB - This paper proposes a novel cooperative approach for two-hop amplify-and-forward (A&F) relaying that exploits both the signal forwarded by the relay and the one directly transmitted by the source in impulse-radio ultra-wideband (IR-UWB) systems. Specifically, we focus on a non-coherent setup employing a double-differential encoding scheme at the source node and a single differential demodulation at the relay and destination. The log-likelihood ratio based decision rule is derived at the destination node. A semi-analytical power allocation strategy is presented by evaluating a closed-form expression for the effective signal to noise ratio (SNR) at the destination, which is maximized by exhaustive search. Numerical simulations show that the proposed system outperforms both the direct transmission with single differential encoding and the non-cooperative multi-hop approach in different scenarios. AU - Mondelli, Marco AU - Zhou, Qi AU - Ma, Xiaoli AU - Lottici, Vincenzo ID - 6746 SN - 1520-6149 T2 - 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) TI - A cooperative approach for amplify-and-forward differential transmitted reference IR-UWB relay systems ER - TY - JOUR AB - The Seebeck coefficients, electrical resistivities, total thermal conductivities, and magnetization are reported for temperatures between 5 and 350 K for n-type Bi0.88Sb0.12 nano-composite alloys made by Ho-doping at the 0, 1, and 3 % atomic levels. The alloys were prepared using a dc hot-pressing method, and are shown to be single phase for both Ho contents with grain sizes on the average of 900 nm. We find the parent compound has a maximum of ZT = 0.28 at 231 K, while doping 1 % Ho increases the maximum ZT to 0.31 at 221 K and the 3 % doped sample suppresses the maximum ZT = 0.24 at a temperature of 260 K. AU - Lukas, K. C. AU - Joshi, G. AU - Modic, Kimberly A AU - Ren, Z. F. AU - Opeil, C. P. ID - 7074 IS - 15 JF - Journal of Materials Science SN - 0022-2461 TI - Thermoelectric properties of Ho-doped Bi0.88Sb0.12 VL - 47 ER - TY - JOUR AB - Carbon has been used widely as the basis of porous cathodes for nonaqueous Li–O2 cells. However, the stability of carbon and the effect of carbon on electrolyte decomposition in such cells are complex and depend on the hydrophobicity/hydrophilicity of the carbon surface. Analyzing carbon cathodes, cycled in Li–O2 cells between 2 and 4 V, using acid treatment and Fenton’s reagent, and combined with differential electrochemical mass spectrometry and FTIR, demonstrates the following: Carbon is relatively stable below 3.5 V (vs Li/Li+) on discharge or charge, especially so for hydrophobic carbon, but is unstable on charging above 3.5 V (in the presence of Li2O2), oxidatively decomposing to form Li2CO3. Direct chemical reaction with Li2O2 accounts for only a small proportion of the total carbon decomposition on cycling. Carbon promotes electrolyte decomposition during discharge and charge in a Li–O2 cell, giving rise to Li2CO3 and Li carboxylates (DMSO and tetraglyme electrolytes). The Li2CO3 and Li carboxylates present at the end of discharge and those that form on charge result in polarization on the subsequent charge. Li2CO3 (derived from carbon and from the electrolyte) as well as the Li carboxylates (derived from the electrolyte) decompose and form on charging. Oxidation of Li2CO3 on charging to ∼4 V is incomplete; Li2CO3 accumulates on cycling resulting in electrode passivation and capacity fading. Hydrophilic carbon is less stable and more catalytically active toward electrolyte decomposition than carbon with a hydrophobic surface. If the Li–O2 cell could be charged at or below 3.5 V, then carbon may be relatively stable, however, its ability to promote electrolyte decomposition, presenting problems for its use in a practical Li–O2 battery. The results emphasize that stable cycling of Li2O2 at the cathode in a Li–O2 cell depends on the synergy between electrolyte and electrode; the stability of the electrode and the electrolyte cannot be considered in isolation. AU - Ottakam Thotiyl, Muhammed M. AU - Freunberger, Stefan Alexander AU - Peng, Zhangquan AU - Bruce, Peter G. ID - 7308 IS - 1 JF - Journal of the American Chemical Society SN - 0002-7863 TI - The carbon electrode in nonaqueous Li–O2 cells VL - 135 ER - TY - JOUR AB - Energy‐storage technologies, including electrical double‐layer capacitors and rechargeable batteries, have attracted significant attention for applications in portable electronic devices, electric vehicles, bulk electricity storage at power stations, and “load leveling” of renewable sources, such as solar energy and wind power. Transforming lithium batteries and electric double‐layer capacitors requires a step change in the science underpinning these devices, including the discovery of new materials, new electrochemistry, and an increased understanding of the processes on which the devices depend. The Review will consider some of the current scientific issues underpinning lithium batteries and electric double‐layer capacitors. AU - Choi, Nam-Soon AU - Chen, Zonghai AU - Freunberger, Stefan Alexander AU - Ji, Xiulei AU - Sun, Yang-Kook AU - Amine, Khalil AU - Yushin, Gleb AU - Nazar, Linda F. AU - Cho, Jaephil AU - Bruce, Peter G. ID - 7309 IS - 40 JF - Angewandte Chemie International Edition SN - 1433-7851 TI - Challenges facing Lithium batteries and electrical double-layer capacitors VL - 51 ER - TY - JOUR AB - The rechargeable nonaqueous lithium-air (Li-O2) battery is receiving a great deal of interest because, theoretically, its specific energy far exceeds the best that can be achieved with lithium-ion cells. Operation of the rechargeable Li-O2 battery depends critically on repeated and highly reversible formation/decomposition of lithium peroxide (Li2O2) at the cathode upon cycling. Here, we show that this process is possible with the use of a dimethyl sulfoxide electrolyte and a porous gold electrode (95% capacity retention from cycles 1 to 100), whereas previously only partial Li2O2 formation/decomposition and limited cycling could occur. Furthermore, we present data indicating that the kinetics of Li2O2 oxidation on charge is approximately 10 times faster than on carbon electrodes. AU - Peng, Z. AU - Freunberger, Stefan Alexander AU - Chen, Y. AU - Bruce, P. G. ID - 7310 IS - 6094 JF - Science SN - 0036-8075 TI - A reversible and higher-rate Li-O2 battery VL - 337 ER - TY - JOUR AB - Stability of the electrolyte toward reduced oxygen species generated at the cathode is a crucial challenge for the rechargeable nonaqueous Li–O2 battery. Here, we investigate dimethylformamide as the basis of an electrolyte. Although reactions at the O2 cathode on the first discharge–charge cycle are dominated by reversible Li2O2 formation/decomposition, there is also electrolyte decomposition, which increases on cycling. The products of decomposition at the cathode on discharge are Li2O2, Li2CO3, HCO2Li, CH3CO2Li, NO, H2O, and CO2. Li2CO3 accumulates in the electrode with cycling. The stability of dimethylformamide toward reduced oxygen species is insufficient for its use in the rechargeable nonaqueous Li–O2 battery. AU - Chen, Yuhui AU - Freunberger, Stefan Alexander AU - Peng, Zhangquan AU - Bardé, Fanny AU - Bruce, Peter G. ID - 7311 IS - 18 JF - Journal of the American Chemical Society SN - 0002-7863 TI - Li–O2 battery with a dimethylformamide electrolyte VL - 134 ER - TY - CONF AB - Decades of research in distributed computing have led to a variety of perspectives on what it means for a concurrent algorithm to be efficient, depending on model assumptions, progress guarantees, and complexity metrics. It is therefore natural to ask whether one could compose algorithms that perform efficiently under different conditions, so that the composition preserves the performance of the original components when their conditions are met. In this paper, we evaluate the cost of composing shared-memory algorithms. First, we formally define the notion of safely composable algorithms and we show that every sequential type has a safely composable implementation, as long as enough state is transferred between modules. Since such generic implementations are inherently expensive, we present a more general light-weight specification that allows the designer to transfer very little state between modules, by taking advantage of the semantics of the implemented object. Using this framework, we implement a composed longlived test-and-set object, with the property that each of its modules is asymptotically optimal with respect to the progress condition it ensures, while the entire implementation only uses objects with consensus number at most two. Thus, we show that the overhead of composition can be negligible in the case of some important shared-memory abstractions. AU - Alistarh, Dan-Adrian AU - Guerraoui, Rachid AU - Kuznetsov, Petr AU - Losa, Giuliano ID - 762 TI - On the cost of composing shared-memory algorithms ER - TY - CONF AB - Renaming is a fundamental problem in distributed computing, in which a set of n processes need to pick unique names from a namespace of limited size. In this paper, we present the first early-deciding upper bounds for synchronous renaming, in which the running time adapts to the actual number of failures f in the execution. We show that, surprisingly, renaming can be solved in constant time if the number of failures f is limited to O(√n), while for general f ≤ n - 1 renaming can always be solved in O(log f) communication rounds. In the wait-free case, i.e. for f = n - 1, our upper bounds match the Ω(log n) lower bound of Chaudhuri et al. [13]. AU - Alistarh, Dan-Adrian AU - Attiya, Hagit AU - Guerraoui, Rachid AU - Travers, Corentin ID - 763 TI - Early deciding synchronous renaming in O(log f) rounds or less VL - 7355 LNCS ER - TY - JOUR AB - Set agreement is a fundamental problem in distributed computing in which processes collectively choose a small subset of values from a larger set of proposals. The impossibility of fault-tolerant set agreement in asynchronous networks is one of the seminal results in distributed computing. In synchronous networks, too, the complexity of set agreement has been a significant research challenge that has now been resolved. Real systems, however, are neither purely synchronous nor purely asynchronous. Rather, they tend to alternate between periods of synchrony and periods of asynchrony. Nothing specific is known about the complexity of set agreement in such a "partially synchronous" setting. In this paper, we address this challenge, presenting the first (asymptotically) tight bound on the complexity of set agreement in such systems. We introduce a novel technique for simulating, in a fault-prone asynchronous shared memory, executions of an asynchronous and failure-prone message-passing system in which some fragments appear synchronous to some processes. We use this simulation technique to derive a lower bound on the round complexity of set agreement in a partially synchronous system by a reduction from asynchronous wait-free set agreement. Specifically, we show that every set agreement protocol requires at least $\lfloor\frac t k \rfloor + 2$ synchronous rounds to decide. We present an (asymptotically) matching algorithm that relies on a distributed asynchrony detection mechanism to decide as soon as possible during periods of synchrony. From these two results, we derive the size of the minimal window of synchrony needed to solve set agreement. By relating synchronous, asynchronous and partially synchronous environments, our simulation technique is of independent interest. In particular, it allows us to obtain a new lower bound on the complexity of early deciding k-set agreement complementary to that of Gafni et al. (in SIAM J. Comput. 40(1):63-78, 2011), and to re-derive the combinatorial topology lower bound of Guerraoui et al. (in Theor. Comput. Sci. 410(6-7):570-580, 2009) in an algorithmic way. AU - Alistarh, Dan-Adrian AU - Gilbert, Seth AU - Guerraoui, Rachid AU - Travers, Corentin ID - 764 IS - 1-2 JF - Algorithmica (New York) TI - Of choices, failures and asynchrony: the many faces of set agreement VL - 62 ER - TY - CONF AB - Asynchronous task allocation is a fundamental problem in distributed computing in which p asynchronous processes must execute a set of m tasks. Also known as write-all or do-all, this problem been studied extensively, both independently and as a key building block for various distributed algorithms. In this paper, we break new ground on this classic problem: we introduce the To-Do Tree concurrent data structure, which improves on the best known randomized and deterministic upper bounds. In the presence of an adaptive adversary, the randomized To-Do Tree algorithm has O(m + p log p log2 m) work complexity. We then show that there exists a deterministic variant of the To-Do Tree algorithm with work complexity O(m + p log5 m log2 max(m, p)). For all values of m and p, our algorithms are within log factors of the Ω(m + p log p) lower bound for this problem. The key technical ingredient in our results is a new approach for analyzing concurrent executions against a strong adaptive scheduler. This technique allows us to handle the complex dependencies between the processes' coin flips and their scheduling, and to tightly bound the work needed to perform subsets of the tasks. AU - Alistarh, Dan-Adrian AU - Bender, Michael AU - Gilbert, Seth AU - Guerraoui, Rachid ID - 766 TI - How to allocate tasks asynchronously ER - TY - JOUR AB - Synchronous distributed algorithms are easier to design and prove correct than algorithms that tolerate asynchrony. Yet, in the real world, networks experience asynchrony and other timing anomalies. In this paper, we address the question of how to efficiently transform an algorithm that relies on synchronous timing into an algorithm that tolerates asynchronous executions. We introduce a transformation technique from synchronous algorithms to indulgent algorithms (Guerraoui, in PODC, pp. 289-297, 2000), which induces only a constant overhead in terms of time complexity in well-behaved executions. Our technique is based on a new abstraction we call an asynchrony detector, which the participating processes implement collectively. The resulting transformation works for the class of colorless distributed tasks, including consensus and set agreement. Interestingly, we also show that our technique is relevant for colored tasks, by applying it to the renaming problem, to obtain the first indulgent renaming algorithm. AU - Alistarh, Dan-Adrian AU - Gilbert, Seth AU - Guerraoui, Rachid AU - Travers, Corentin ID - 767 IS - 4 JF - Theory of Computing Systems TI - Generating Fast Indulgent Algorithms VL - 51 ER - TY - JOUR AB - Although studies on laboratory species and natural populations of vertebrates have shown reproduction to impair later performance, little is known of the age‐specific associations between reproduction and survival, and how such findings apply to the ageing of large, long‐lived species. Herein we develop a framework to examine population‐level patterns of reproduction and survival across lifespan in long‐lived organisms, and decompose those changes into individual‐level effects, and the effects of age‐specific trade‐offs between fitness components. We apply this to an extensive longitudinal dataset on female semi‐captive Asian timber elephants (Elephas maximus) and report the first evidence of age‐specific fitness declines that are driven by age‐specific associations between fitness components in a long‐lived mammal. Associations between reproduction and survival are positive in early life, but negative in later life with up to 71% of later‐life survival declines associated with investing in the production of offspring within this population of this critically endangered species. AU - Robinson, Matthew Richard AU - Mar, Khyne U AU - Lummaa, Virpi ID - 7749 IS - 3 JF - Ecology Letters SN - 1461-023X TI - Senescence and age-specific trade-offs between reproduction and survival in female Asian elephants VL - 15 ER - TY - JOUR AB - Female mate choice acts as an important evolutionary force, yet the influence of the environment on both its expression and the selective pressures acting upon it remains unknown. We found consistent heritable differences between females in their choice of mate based on ornament size during a 25‐year study of a population of collared flycatchers. However, the fitness consequences of mate choice were dependent on environmental conditions experienced whilst breeding. Females breeding with highly ornamented males experienced high relative fitness during dry summer conditions, but low relative fitness during wetter years. Our results imply that sexual selection within a population can be highly variable and dependent upon the prevailing weather conditions experienced by individuals. AU - Robinson, Matthew Richard AU - Sander van Doorn, G. AU - Gustafsson, Lars AU - Qvarnström, Anna ID - 7748 IS - 6 JF - Ecology Letters SN - 1461-023X TI - Environment-dependent selection on mate choice in a natural population of birds VL - 15 ER - TY - JOUR AB - We present an analysis of finite-size effects in jammed packings of N soft, frictionless spheres at zero temperature. There is a 1/N correction to the discrete jump in the contact number at the transition so that jammed packings exist only above isostaticity. As a result, the canonical power-law scalings of the contact number and elastic moduli break down at low pressure. These quantities exhibit scaling collapse with a nontrivial scaling function, demonstrating that the jamming transition can be considered a phase transition. Scaling is achieved as a function of N in both two and three dimensions, indicating an upper critical dimension of 2. AU - Goodrich, Carl Peter AU - Liu, Andrea J. AU - Nagel, Sidney R. ID - 7776 IS - 9 JF - Physical Review Letters SN - 0031-9007 TI - Finite-size scaling at the jamming transition VL - 109 ER - TY - JOUR AB - Fungal cell walls frequently contain a polymer of mannose and galactose called galactomannan. In the pathogenic filamentous fungus Aspergillus fumigatus, this polysaccharide is made of a linear mannan backbone with side chains of galactofuran and is anchored to the plasma membrane via a glycosylphosphatidylinositol or is covalently linked to the cell wall. To date, the biosynthesis and significance of this polysaccharide are unknown. The present data demonstrate that deletion of the Golgi UDP-galactofuranose transporter GlfB or the GDP-mannose transporter GmtA leads to the absence of galactofuran or galactomannan, respectively. This indicates that the biosynthesis of galactomannan probably occurs in the lumen of the Golgi apparatus and thus contrasts with the biosynthesis of other fungal cell wall polysaccharides studied to date that takes place at the plasma membrane. Transglycosylation of galactomannan from the membrane to the cell wall is hypothesized because both the cell wall-bound and membrane-bound polysaccharide forms are affected in the generated mutants. Considering the severe growth defect of the A. fumigatus GmtA-deficient mutant, proving this paradigm might provide new targets for antifungal therapy. AU - Engel, Jakob AU - Schmalhorst, Philipp S AU - Routier, Françoise ID - 801 IS - 53 JF - Journal of Biological Chemistry TI - Biosynthesis of the fungal cell wall polysaccharide galactomannan requires intraluminal GDP-mannose VL - 287 ER - TY - JOUR AB - In dynamical models of cortical networks, the recurrent connectivity can amplify the input given to the network in two distinct ways. One is induced by the presence of near-critical eigenvalues in the connectivity matrix W, producing large but slow activity fluctuations along the corresponding eigenvectors (dynamical slowing). The other relies on W not being normal, which allows the network activity to make large but fast excursions along specific directions. Here we investigate the trade-off between non-normal amplification and dynamical slowing in the spontaneous activity of large random neuronal networks composed of excitatory and inhibitory neurons. We use a Schur decomposition of W to separate the two amplification mechanisms. Assuming linear stochastic dynamics, we derive an exact expression for the expected amount of purely non-normal amplification. We find that amplification is very limited if dynamical slowing must be kept weak. We conclude that, to achieve strong transient amplification with little slowing, the connectivity must be structured. We show that unidirectional connections between neurons of the same type together with reciprocal connections between neurons of different types, allow for amplification already in the fast dynamical regime. Finally, our results also shed light on the differences between balanced networks in which inhibition exactly cancels excitation and those where inhibition dominates. AU - Hennequin, Guillaume AU - Vogels, Tim P AU - Gerstner, Wulfram ID - 8024 IS - 1 JF - Physical Review E SN - 1539-3755 TI - Non-normal amplification in random balanced neuronal networks VL - 86 ER - TY - JOUR AB - Using correlated live-cell imaging and electron tomography we found that actin branch junctions in protruding and treadmilling lamellipodia are not concentrated at the front as previously supposed, but link actin filament subsets in which there is a continuum of distances from a junction to the filament plus ends, for up to at least 1 mm. When branch sites were observed closely spaced on the same filament their separation was commonly a multiple of the actin helical repeat of 36 nm. Image averaging of branch junctions in the tomograms yielded a model for the in vivo branch at 2.9 nm resolution, which was comparable with that derived for the in vitro actin- Arp2/3 complex. Lamellipodium initiation was monitored in an intracellular wound-healing model and was found to involve branching from the sides of actin filaments oriented parallel to the plasmalemma. Many filament plus ends, presumably capped, terminated behind the lamellipodium tip and localized on the dorsal and ventral surfaces of the actin network. These findings reveal how branching events initiate and maintain a network of actin filaments of variable length, and provide the first structural model of the branch junction in vivo. A possible role of filament capping in generating the lamellipodium leaflet is discussed and a mathematical model of protrusion is also presented. AU - Vinzenz, Marlene AU - Nemethova, Maria AU - Schur, Florian AU - Mueller, Jan AU - Narita, Akihiro AU - Urban, Edit AU - Winkler, Christoph AU - Schmeiser, Christian AU - Koestler, Stefan AU - Rottner, Klemens AU - Resch, Guenter AU - Maéda, Yuichiro AU - Small, John ID - 808 IS - 11 JF - Journal of Cell Science TI - Actin branching in the initiation and maintenance of lamellipodia VL - 125 ER - TY - JOUR AB - The Staphylococcus aureus cell wall stress stimulon (CWSS) is activated by cell envelope-targeting antibiotics or depletion of essential cell wall biosynthesis enzymes. The functionally uncharacterized S. aureus LytR-CpsA-Psr (LCP) proteins, MsrR, SA0908 and SA2103, all belong to the CWSS. Although not essential, deletion of all three LCP proteins severely impairs cell division. We show here that VraSR-dependent CWSS expression was up to 250-fold higher in single, double and triple LCP mutants than in wild type S. aureus in the absence of external stress. The LCP triple mutant was virtually depleted of wall teichoic acids (WTA), which could be restored to different degrees by any of the single LCP proteins. Subinhibitory concentrations of tunicamycin, which inhibits the first WTA synthesis enzyme TarO (TagO), could partially complement the severe growth defect of the LCP triple mutant. Both of the latter findings support a role for S. aureus LCP proteins in late WTA synthesis, as in Bacillus subtilis where LCP proteins were recently proposed to transfer WTA from lipid carriers to the cell wall peptidoglycan. Intrinsic activation of the CWSS upon LCP deletion and the fact that LCP proteins were essential for WTA-loading of the cell wall, highlight their important role(s) in S. aureus cell envelope biogenesis. AU - Dengler, Vanina AU - Meier, Patricia Stutzmann AU - Heusser, Ronald AU - Kupferschmied, Peter AU - Fazekas, Judit AU - Friebe, Sarah AU - Staufer, Sibylle Burger AU - Majcherczyk, Paul A. AU - Moreillon, Philippe AU - Berger-Bächi, Brigitte AU - McCallum, Nadine ID - 8246 IS - 2 JF - FEMS Microbiology Letters SN - 0378-1097 TI - Deletion of hypothetical wall teichoic acid ligases in Staphylococcus aureus activates the cell wall stress response VL - 333 ER - TY - JOUR AB - Plants exhibit a unique developmental flexibility to ever-changing environmental conditions. To achieve their profound adaptability, plants are able to maintain permanent stem cell populations and form new organs during the entire plant life cycle. Signaling substances, called plant hormones, such as auxin, cytokinin, abscisic acid, brassinosteroid, ethylene, gibberellin, jasmonic acid, and strigolactone, govern and coordinate these developmental processes. Physiological and genetic studies have dissected the molecular components of signal perception and transduction of the individual hormonal pathways. However, over recent years it has become evident that hormones do not act only in a linear pathway. Hormonal pathways are interconnected by a complex network of interactions and feedback circuits that determines the final outcome of the individual hormone actions. This raises questions about the molecular mechanisms underlying hormonal cross talk and about how these hormonal networks are established, maintained, and modulated throughout plant development. AU - Vanstraelen, Marleen AU - Eva Benková ID - 826 JF - Annual Review of Cell and Developmental Biology TI - Hormonal interactions in the regulation of plant development VL - 28 ER - TY - JOUR AB - The architecture of a plant's root system, established postembryonically, results from both coordinated root growth and lateral root branching. The plant hormones auxin and cytokinin are central endogenous signaling molecules that regulate lateral root organogenesis positively and negatively, respectively. Tight control and mutual balance of their antagonistic activities are particularly important during the early phases of lateral root organogenesis to ensure continuous lateral root initiation (LRI) and proper development of lateral root primordia (LRP). Here, we show that the early phases of lateral root organogenesis, including priming and initiation, take place in root zones with a repressed cytokinin response. Accordingly, ectopic overproduction of cytokinin in the root basal meristem most efficiently inhibits LRI. Enhanced cytokinin responses in pericycle cells between existing LRP might restrict LRI near existing LRP and, when compromised, ectopic LRI occurs. Furthermore, our results demonstrate that young LRP are more sensitive to perturbations in the cytokinin activity than are developmentally more advanced primordia. We hypothesize that the effect of cytokinin on the development of primordia possibly depends on the robustness and stability of the auxin gradient. AU - Bielach, Agnieszka AU - Podlesakova, Katerina AU - Peter Marhavy AU - Duclercq, Jérôme AU - Candela Cuesta AU - Muller, Bruno AU - Grunewald, Wim AU - Tarkowski, Petr AU - Eva Benková ID - 829 IS - 10 JF - The Plant Cell TI - Spatiotemporal regulation of lateral root organogenesis in Arabidopsis by cytokinin VL - 24 ER - TY - JOUR AB - Whether or not evolutionary change is inherently irreversible remains a controversial topic. Some examples of evolutionary irreversibility are known; however, this question has not been comprehensively addressed at the molecular level. Here, we use data from 221 human genes with known pathogenic mutations to estimate the rate of irreversibility in protein evolution. For these genes, we reconstruct ancestral amino acid sequences along the mammalian phylogeny and identify ancestral amino acid states that match known pathogenic mutations. Such cases represent inherent evolutionary irreversibility because, at the present moment, reversals to these ancestral amino acid states are impossible for the human lineage. We estimate that approximately 10% of all amino acid substitutions along the mammalian phylogeny are irreversible, such that a return to the ancestral amino acid state would lead to a pathogenic phenotype. For a subset of 51 genes with high rates of irreversibility, as much as 40% of all amino acid evolution was estimated to be irreversible. Because pathogenic phenotypes do not resemble ancestral phenotypes, the molecular nature of the high rate of irreversibility in proteins is best explained by evolution with a high prevalence of compensatory, epistatic interactions between amino acid sites. Under such mode of protein evolution, once an amino acid substitution is fixed, the probability of its reversal declines as the protein sequence accumulates changes that affect the phenotypic manifestation of the ancestral state. The prevalence of epistasis in evolution indicates that the observed high rate of irreversibility in protein evolution is an inherent property of protein structure and function. AU - Soylemez, Onuralp AU - Fyodor Kondrashov ID - 846 IS - 12 JF - Genome Biology and Evolution TI - Estimating the rate of irreversibility in protein evolution VL - 4 ER - TY - JOUR AB - The 1H dipolar network, which is the major obstacle for applying proton detection in the solid-state, can be reduced by deuteration, employing the RAP (Reduced Adjoining Protonation) labeling scheme, which yields random protonation at non-exchangeable sites. We present here a systematic study on the optimal degree of random sidechain protonation in RAP samples as a function of the MAS (magic angle spinning) frequency. In particular, we compare 1H sensitivity and linewidth of a microcrystalline protein, the SH3 domain of chicken α-spectrin, for samples, prepared with 5–25 % H2O in the E. coli growth medium, in the MAS frequency range of 20–60 kHz. At an external field of 19.96 T (850 MHz), we find that using a proton concentration between 15 and 25 % in the M9 medium yields the best compromise in terms of sensitivity and resolution, with an achievable average 1H linewidth on the order of 40–50 Hz. Comparing sensitivities at a MAS frequency of 60 versus 20 kHz, a gain in sensitivity by a factor of 4–4.5 is observed in INEPT-based 1H detected 1D 1H,13C correlation experiments. In total, we find that spectra recorded with a 1.3 mm rotor at 60 kHz have almost the same sensitivity as spectra recorded with a fully packed 3.2 mm rotor at 20 kHz, even though ~20× less material is employed. The improved sensitivity is attributed to 1H line narrowing due to fast MAS and to the increased efficiency of the 1.3 mm coil. AU - Asami, Sam AU - Szekely, Kathrin AU - Schanda, Paul AU - Meier, Beat H. AU - Reif, Bernd ID - 8463 IS - 2 JF - Journal of Biomolecular NMR SN - 0925-2738 TI - Optimal degree of protonation for 1H detection of aliphatic sites in randomly deuterated proteins as a function of the MAS frequency VL - 54 ER - TY - JOUR AB - We demonstrate that conformational exchange processes in proteins on microsecond-to-millisecond time scales can be detected and quantified by solid-state NMR spectroscopy. We show two independent approaches that measure the effect of conformational exchange on transverse relaxation parameters, namely Carr–Purcell–Meiboom–Gill relaxation-dispersion experiments and measurement of differential multiple-quantum coherence decay. Long coherence lifetimes, as required for these experiments, are achieved by the use of highly deuterated samples and fast magic-angle spinning. The usefulness of the approaches is demonstrated by application to microcrystalline ubiquitin. We detect a conformational exchange process in a region of the protein for which dynamics have also been observed in solution. Interestingly, quantitative analysis of the data reveals that the exchange process is more than 1 order of magnitude slower than in solution, and this points to the impact of the crystalline environment on free energy barriers. AU - Tollinger, Martin AU - Sivertsen, Astrid C. AU - Meier, Beat H. AU - Ernst, Matthias AU - Schanda, Paul ID - 8465 IS - 36 JF - Journal of the American Chemical Society SN - 0002-7863 TI - Site-resolved measurement of microsecond-to-millisecond conformational-exchange processes in proteins by solid-state NMR spectroscopy VL - 134 ER - TY - JOUR AB - Recent advances in NMR spectroscopy and the availability of high magnetic field strengths now offer the possibility to record real-time 3D NMR spectra of short-lived protein states, e.g., states that become transiently populated during protein folding. Here we present a strategy for obtaining sequential NMR assignments as well as atom-resolved information on structural and dynamic features within a folding intermediate of the amyloidogenic protein β2-microglobulin that has a half-lifetime of only 20 min. AU - Rennella, Enrico AU - Cutuil, Thomas AU - Schanda, Paul AU - Ayala, Isabel AU - Forge, Vincent AU - Brutscher, Bernhard ID - 8466 IS - 19 JF - Journal of the American Chemical Society SN - 0002-7863 TI - Real-time NMR characterization of structure and dynamics in a transiently populated protein folding intermediate VL - 134 ER - TY - JOUR AB - Partial deuteration is a powerful tool to increase coherence life times and spectral resolution in proton solid-state NMR. The J coupling to deuterium needs, however, to be decoupled to maintain the good resolution in the (usually indirect) 13C dimension(s). We present a simple and reversible way to expand a commercial 1.3 mm HCN MAS probe with a 2H channel with sufficient field strength for J-decoupling of deuterium, namely 2–3 kHz. The coil is placed at the outside of the stator and requires no significant modifications to the probe. The performance and the realizable gains in sensitivity and resolution are demonstrated using perdeuterated ubiquitin, with selectively CHD2-labeled methyl groups. AU - Huber, Matthias AU - With, Oliver AU - Schanda, Paul AU - Verel, René AU - Ernst, Matthias AU - Meier, Beat H. ID - 8467 JF - Journal of Magnetic Resonance SN - 1090-7807 TI - A supplementary coil for 2H decoupling with commercial HCN MAS probes VL - 214 ER - TY - JOUR AB - The famous ergodic hypothesis suggests that for a typical Hamiltonian on a typical energy surface nearly all trajectories are dense. KAM theory disproves it. Ehrenfest (The Conceptual Foundations of the Statistical Approach in Mechanics. Ithaca, NY: Cornell University Press, 1959) and Birkhoff (Collected Math Papers. Vol 2, New York: Dover, pp 462–465, 1968) stated the quasi-ergodic hypothesis claiming that a typical Hamiltonian on a typical energy surface has a dense orbit. This question is wide open. Herman (Proceedings of the International Congress of Mathematicians, Vol II (Berlin, 1998). Doc Math 1998, Extra Vol II, Berlin: Int Math Union, pp 797–808, 1998) proposed to look for an example of a Hamiltonian near H0(I)=⟨I,I⟩2 with a dense orbit on the unit energy surface. In this paper we construct a Hamiltonian H0(I)+εH1(θ,I,ε) which has an orbit dense in a set of maximal Hausdorff dimension equal to 5 on the unit energy surface. AU - Kaloshin, Vadim AU - Saprykina, Maria ID - 8502 IS - 3 JF - Communications in Mathematical Physics KW - Mathematical Physics KW - Statistical and Nonlinear Physics SN - 0010-3616 TI - An example of a nearly integrable Hamiltonian system with a trajectory dense in a set of maximal Hausdorff dimension VL - 315 ER - TY - JOUR AB - ackground: The evolution and genomic stop codon frequencies have not been rigorously studied with the exception of coding of non-canonical amino acids. Here we study the rate of evolution and frequency distribution of stop codons in bacterial genomes.Results: We show that in bacteria stop codons evolve slower than synonymous sites, suggesting the action of weak negative selection. However, the frequency of stop codons relative to genomic nucleotide content indicated that this selection regime is not straightforward. The frequency of TAA and TGA stop codons is GC-content dependent, with TAA decreasing and TGA increasing with GC-content, while TAG frequency is independent of GC-content. Applying a formal, analytical model to these data we found that the relationship between stop codon frequencies and nucleotide content cannot be explained by mutational biases or selection on nucleotide content. However, with weak nucleotide content-dependent selection on TAG, -0.5 < Nes < 1.5, the model fits all of the data and recapitulates the relationship between TAG and nucleotide content. For biologically plausible rates of mutations we show that, in bacteria, TAG stop codon is universally associated with lower fitness, with TAA being the optimal for G-content < 16% while for G-content > 16% TGA has a higher fitness than TAG.Conclusions: Our data indicate that TAG codon is universally suboptimal in the bacterial lineage, such that TAA is likely to be the preferred stop codon for low GC content while the TGA is the preferred stop codon for high GC content. The optimization of stop codon usage may therefore be useful in genome engineering or gene expression optimization applications.Reviewers: This article was reviewed by Michail Gelfand, Arcady Mushegian and Shamil Sunyaev. For the full reviews, please go to the Reviewers' Comments section. AU - Povolotskaya, Inna AU - Fyodor Kondrashov AU - Ledda, Alice AU - Vlasov, Peter K ID - 858 JF - Biology Direct TI - Stop codons in bacteria are not selectively equivalent VL - 7 ER - TY - JOUR AB - The main forces directing long-term molecular evolution remain obscure. A sizable fraction of amino-acid substitutions seem to be fixed by positive selection, but it is unclear to what degree long-term protein evolution is constrained by epistasis, that is, instances when substitutions that are accepted in one genotype are deleterious in another. Here we obtain a quantitative estimate of the prevalence of epistasis in long-term protein evolution by relating data on amino-acid usage in 14 organelle proteins and 2 nuclear-encoded proteins to their rates of short-term evolution. We studied multiple alignments of at least 1,000 orthologues for each of these 16 proteins from species from a diverse phylogenetic background and found that an average site contained approximately eight different amino acids. Thus, without epistasis an average site should accept two-fifths of all possible amino acids, and the average rate of amino-acid substitutions should therefore be about three-fifths lower than the rate of neutral evolution. However, we found that the measured rate of amino-acid substitution in recent evolution is 20 times lower than the rate of neutral evolution and an order of magnitude lower than that expected in the absence of epistasis. These data indicate that epistasis is pervasive throughout protein evolution: about 90 per cent of all amino-acid substitutions have a neutral or beneficial impact only in the genetic backgrounds in which they occur, and must therefore be deleterious in a different background of other species. Our findings show that most amino-acid substitutions have different fitness effects in different species and that epistasis provides the primary conceptual framework to describe the tempo and mode of long-term protein evolution. AU - Breen, Michael S AU - Kemena, Carsten AU - Vlasov, Peter K AU - Notredame, Cédric AU - Fyodor Kondrashov ID - 900 IS - 7421 JF - Nature TI - Epistasis as the primary factor in molecular evolution VL - 490 ER - TY - JOUR AB - In this Letter, we explore experimentally the phase behavior of a dense active suspension of self-propelled colloids. In addition to a solidlike and gaslike phase observed for high and low densities, a novel cluster phase is reported at intermediate densities. This takes the form of a stationary assembly of dense aggregates—resulting from a permanent dynamical merging and separation of active colloids—whose average size grows with activity as a linear function of the self-propelling velocity. While different possible scenarios can be considered to account for these observations—such as a generic velocity weakening instability recently put forward—we show that the experimental results are reproduced mathematically by a chemotactic aggregation mechanism, originally introduced to account for bacterial aggregation and accounting here for diffusiophoretic chemical interaction between colloidal swimmers. AU - Theurkauff, I. AU - Cottin-Bizonne, C. AU - Palacci, Jérémie A AU - Ybert, C. AU - Bocquet, L. ID - 9014 IS - 26 JF - Physical Review Letters SN - 00319007 TI - Dynamic clustering in active colloidal suspensions with chemical signaling VL - 108 ER - TY - JOUR AB - We demonstrate how to appropriately estimate the zero-frequency (static) hyperpolarizability of an organic molecule from its charge distribution, and we explore applications of these estimates for identifying and evaluating new organic nonlinear optical (NLO) materials. First, we calculate hyperpolarizabilities from Hartree-Fock-derived charge distributions and find order-of-magnitude agreement with experimental values. We show that these simple arithmetic calculations will enable systematic searches for new organic NLO molecules. Second, we derive hyperpolarizabilities from crystallographic data using a multipolar charge-density analysis and find good agreement with empirical calculations. This demonstrates an experimental determination of the full static hyperpolarizability tensor in a solid-state sample. AU - Higginbotham, Andrew P AU - Cole, Jacqueline AU - Blood Forsythe, Martin AU - Hickstein, Daniel ID - 91 IS - 3 JF - Journal of Applied Physics TI - Identifying and evaluating organic nonlinear optical materials via molecular moments VL - 111 ER - TY - JOUR AB - In models of radiative–convective equilibrium it is known that convection can spontaneously aggregate into one single localized moist region if the domain is large enough. The large changes in the mean climate state and radiative fluxes accompanying this self-aggregation raise questions as to what simulations at lower resolutions with parameterized convection, in similar homogeneous geometries, should be expected to produce to be considered successful in mimicking a cloud-resolving model. The authors investigate this self-aggregation in a nonrotating, three-dimensional cloud-resolving model on a square domain without large-scale forcing. It is found that self-aggregation is sensitive not only to the domain size, but also to the horizontal resolution. With horizontally homogeneous initial conditions, convective aggregation only occurs on domains larger than about 200km and with resolutions coarser than about 2km in the model examined. The system exhibits hysteresis, so that with aggregated initial conditions, convection remains aggregated even at our finest resolution, 500m, as long as the domain is greater than 200–300km. The sensitivity of self-aggregation to resolution and domain size in this model is due to the sensitivity of the distribution of low clouds to these two parameters. Indeed, the mechanism responsible for the aggregation of convection is the dynamical response to the longwave radiative cooling from low clouds. Strong longwave cooling near cloud top in dry regions forces downward motion, which by continuity generates inflow near cloud top and near-surface outflow from dry regions. This circulation results in the net export of moist static energy from regions with low moist static energy, yielding a positive feedback. AU - Muller, Caroline J AU - Held, Isaac M. ID - 9142 IS - 8 JF - Journal of the Atmospheric Sciences KW - Atmospheric Science SN - 0022-4928 TI - Detailed investigation of the self-aggregation of convection in cloud-resolving simulations VL - 69 ER - TY - JOUR AB - The Arabidopsis thaliana central cell, the companion cell of the egg, undergoes DNA demethylation before fertilization, but the targeting preferences, mechanism, and biological significance of this process remain unclear. Here, we show that active DNA demethylation mediated by the DEMETER DNA glycosylase accounts for all of the demethylation in the central cell and preferentially targets small, AT-rich, and nucleosome-depleted euchromatic transposable elements. The vegetative cell, the companion cell of sperm, also undergoes DEMETER-dependent demethylation of similar sequences, and lack of DEMETER in vegetative cells causes reduced small RNA–directed DNA methylation of transposons in sperm. Our results demonstrate that demethylation in companion cells reinforces transposon methylation in plant gametes and likely contributes to stable silencing of transposable elements across generations. AU - Ibarra, Christian A. AU - Feng, Xiaoqi AU - Schoft, Vera K. AU - Hsieh, Tzung-Fu AU - Uzawa, Rie AU - Rodrigues, Jessica A. AU - Zemach, Assaf AU - Chumak, Nina AU - Machlicova, Adriana AU - Nishimura, Toshiro AU - Rojas, Denisse AU - Fischer, Robert L. AU - Tamaru, Hisashi AU - Zilberman, Daniel ID - 9451 IS - 6100 JF - Science SN - 0036-8075 TI - Active DNA demethylation in plant companion cells reinforces transposon methylation in gametes VL - 337 ER - TY - JOUR AB - The most well-studied function of DNA methylation in eukaryotic cells is the transcriptional silencing of genes and transposons. More recent results showed that many eukaryotes methylate the bodies of genes as well and that this methylation correlates with transcriptional activity rather than repression. The purpose of gene body methylation remains mysterious, but is potentially related to the histone variant H2A.Z. Studies in plants and animals have shown that the genome-wide distributions of H2A.Z and DNA methylation are strikingly anticorrelated. Furthermore, we and other investigators have shown that this relationship is likely to be the result of an ancient but unknown mechanism by which DNA methylation prevents the incorporation of H2A.Z. Recently, we discovered strong correlations between the presence of H2A.Z within gene bodies, the degree to which a gene's expression varies across tissue types or environmental conditions, and transcriptional misregulation in an h2a.z mutant. We propose that one basal function of gene body methylation is the establishment of constitutive expression patterns within housekeeping genes by excluding H2A.Z from their bodies. AU - Coleman-Derr, D. AU - Zilberman, Daniel ID - 9535 JF - Cold Spring Harbor Symposia on Quantitative Biology SN - 0091-7451 TI - DNA methylation, H2A.Z, and the regulation of constitutive expression VL - 77 ER - TY - JOUR AB - Due to the omnipresent risk of epidemics, insect societies have evolved sophisticated disease defences at the individual and colony level. An intriguing yet little understood phenomenon is that social contact to pathogen-exposed individuals reduces susceptibility of previously naive nestmates to this pathogen. We tested whether such social immunisation in Lasius ants against the entomopathogenic fungus Metarhizium anisopliae is based on active upregulation of the immune system of nestmates following contact to an infectious individual or passive protection via transfer of immune effectors among group members—that is, active versus passive immunisation. We found no evidence for involvement of passive immunisation via transfer of antimicrobials among colony members. Instead, intensive allogrooming behaviour between naive and pathogen-exposed ants before fungal conidia firmly attached to their cuticle suggested passage of the pathogen from the exposed individuals to their nestmates. By tracing fluorescence-labelled conidia we indeed detected frequent pathogen transfer to the nestmates, where they caused low-level infections as revealed by growth of small numbers of fungal colony forming units from their dissected body content. These infections rarely led to death, but instead promoted an enhanced ability to inhibit fungal growth and an active upregulation of immune genes involved in antifungal defences (defensin and prophenoloxidase, PPO). Contrarily, there was no upregulation of the gene cathepsin L, which is associated with antibacterial and antiviral defences, and we found no increased antibacterial activity of nestmates of fungus-exposed ants. This indicates that social immunisation after fungal exposure is specific, similar to recent findings for individual-level immune priming in invertebrates. Epidemiological modeling further suggests that active social immunisation is adaptive, as it leads to faster elimination of the disease and lower death rates than passive immunisation. Interestingly, humans have also utilised the protective effect of low-level infections to fight smallpox by intentional transfer of low pathogen doses (“variolation” or “inoculation”). AU - Konrad, Matthias AU - Vyleta, Meghan AU - Theis, Fabian AU - Stock, Miriam AU - Tragust, Simon AU - Klatt, Martina AU - Drescher, Verena AU - Marr, Carsten AU - Ugelvig, Line V AU - Cremer, Sylvia ID - 3242 IS - 4 JF - PLoS Biology TI - Social transfer of pathogenic fungus promotes active immunisation in ant colonies VL - 10 ER - TY - GEN AB - Due to the omnipresent risk of epidemics, insect societies have evolved sophisticated disease defences at the individual and colony level. An intriguing yet little understood phenomenon is that social contact to pathogen-exposed individuals reduces susceptibility of previously naive nestmates to this pathogen. We tested whether such social immunisation in Lasius ants against the entomopathogenic fungus Metarhizium anisopliae is based on active upregulation of the immune system of nestmates following contact to an infectious individual or passive protection via transfer of immune effectors among group members—that is, active versus passive immunisation. We found no evidence for involvement of passive immunisation via transfer of antimicrobials among colony members. Instead, intensive allogrooming behaviour between naive and pathogen-exposed ants before fungal conidia firmly attached to their cuticle suggested passage of the pathogen from the exposed individuals to their nestmates. By tracing fluorescence-labelled conidia we indeed detected frequent pathogen transfer to the nestmates, where they caused low-level infections as revealed by growth of small numbers of fungal colony forming units from their dissected body content. These infections rarely led to death, but instead promoted an enhanced ability to inhibit fungal growth and an active upregulation of immune genes involved in antifungal defences (defensin and prophenoloxidase, PPO). Contrarily, there was no upregulation of the gene cathepsin L, which is associated with antibacterial and antiviral defences, and we found no increased antibacterial activity of nestmates of fungus-exposed ants. This indicates that social immunisation after fungal exposure is specific, similar to recent findings for individual-level immune priming in invertebrates. Epidemiological modeling further suggests that active social immunisation is adaptive, as it leads to faster elimination of the disease and lower death rates than passive immunisation. Interestingly, humans have also utilised the protective effect of low-level infections to fight smallpox by intentional transfer of low pathogen doses (“variolation” or “inoculation”). AU - Konrad, Matthias AU - Vyleta, Meghan AU - Theis, Fabian AU - Stock, Miriam AU - Klatt, Martina AU - Drescher, Verena AU - Marr, Carsten AU - Ugelvig, Line V AU - Cremer, Sylvia ID - 9755 TI - Data from: Social transfer of pathogenic fungus promotes active immunisation in ant colonies ER - TY - GEN AB - We propose a two-step procedure for estimating multiple migration rates in an approximate Bayesian computation (ABC) framework, accounting for global nuisance parameters. The approach is not limited to migration, but generally of interest for inference problems with multiple parameters and a modular structure (e.g. independent sets of demes or loci). We condition on a known, but complex demographic model of a spatially subdivided population, motivated by the reintroduction of Alpine ibex (Capra ibex) into Switzerland. In the first step, the global parameters ancestral mutation rate and male mating skew have been estimated for the whole population in Aeschbacher et al. (Genetics 2012; 192: 1027). In the second step, we estimate in this study the migration rates independently for clusters of demes putatively connected by migration. For large clusters (many migration rates), ABC faces the problem of too many summary statistics. We therefore assess by simulation if estimation per pair of demes is a valid alternative. We find that the trade-off between reduced dimensionality for the pairwise estimation on the one hand and lower accuracy due to the assumption of pairwise independence on the other depends on the number of migration rates to be inferred: the accuracy of the pairwise approach increases with the number of parameters, relative to the joint estimation approach. To distinguish between low and zero migration, we perform ABC-type model comparison between a model with migration and one without. Applying the approach to microsatellite data from Alpine ibex, we find no evidence for substantial gene flow via migration, except for one pair of demes in one direction. AU - Aeschbacher, Simon AU - Futschik, Andreas AU - Beaumont, Mark ID - 9758 TI - Data from: Approximate Bayesian computation for modular inference problems with many parameters: the example of migration rates ER - TY - GEN AB - To fight infectious diseases, host immune defences are employed at multiple levels. Sanitary behaviour, such as pathogen avoidance and removal, acts as a first line of defence to prevent infection [1] before activation of the physiological immune system. Insect societies have evolved a wide range of collective hygiene measures and intensive health care towards pathogen-exposed group members [2]. One of the most common behaviours is allogrooming, in which nestmates remove infectious particles from the body surfaces of exposed individuals [3]. Here we show that, in invasive garden ants, grooming of fungus-exposed brood is effective beyond the sheer mechanical removal of fungal conidiospores as it also includes chemical disinfection through the application of poison produced by the ants themselves. Formic acid is the main active component of the poison. It inhibits fungal growth of conidiospores remaining on the brood surface after grooming and also those collected in the mouth of the grooming ant. This dual function is achieved by uptake of the poison droplet into the mouth through acidopore self-grooming and subsequent application onto the infectious brood via brood grooming. This extraordinary behaviour extends current understanding of grooming and the establishment of social immunity in insect societies. AU - Tragust, Simon AU - Mitteregger, Barbara AU - Barone, Vanessa AU - Konrad, Matthias AU - Ugelvig, Line V AU - Cremer, Sylvia ID - 9757 TI - Data from: Ants disinfect fungus-exposed brood by oral uptake and spread of their poison ER - TY - JOUR AB - In this paper we present a surprising example of a Cr unimodal map of an interval f:I→I whose number of periodic points Pn(f)=∣{x∈I:fnx=x}∣ grows faster than any ahead given sequence along a subsequence nk=3k. This example also shows that ‘non-flatness’ of critical points is necessary for the Martens–de Melo–van Strien theorem [M. Martens, W. de Melo and S. van Strien. Julia–Fatou–Sullivan theory for real one-dimensional dynamics. Acta Math.168(3–4) (1992), 273–318] to hold. AU - Kaloshin, Vadim AU - KOZLOVSKI, O. S. ID - 8504 IS - 1 JF - Ergodic Theory and Dynamical Systems KW - Applied Mathematics KW - General Mathematics SN - 0143-3857 TI - A Cr unimodal map with an arbitrary fast growth of the number of periodic points VL - 32 ER - TY - JOUR AB - We prove there are finitely many isometry classes of planar central configurations (also called relative equilibria) in the Newtonian 5-body problem, except perhaps if the 5-tuple of positive masses belongs to a given codimension 2 subvariety of the mass space. AU - Albouy, Alain AU - Kaloshin, Vadim ID - 8503 IS - 1 JF - Annals of Mathematics SN - 0003-486X TI - Finiteness of central configurations of five bodies in the plane VL - 176 ER - TY - JOUR AB - A subject of extensive study in evolutionary theory has been the issue of how neutral, redundant copies can be maintained in the genome for long periods of time. Concurrently, examples of adaptive gene duplications to various environmental conditions in different species have been described. At this point, it is too early to tell whether or not a substantial fraction of gene copies have initially achieved fixation by positive selection for increased dosage. Nevertheless, enough examples have accumulated in the literature that such a possibility should be considered. Here, I review the recent examples of adaptive gene duplications and make an attempt to draw generalizations on what types of genes may be particularly prone to be selected for under certain environmental conditions. The identification of copy-number variation in ecological field studies of species adapting to stressful or novel environmental conditions may improve our understanding of gene duplications as a mechanism of adaptation and its relevance to the long-term persistence of gene duplications. AU - Fyodor Kondrashov ID - 887 IS - 1749 JF - Proceedings of the Royal Society of London Series B Biological Sciences TI - Gene duplication as a mechanism of genomic adaptation to a changing environment VL - 279 ER - TY - JOUR AB - Diffusiophoretic motion of colloids and macromolecules under salt gradients exhibits a logarithmic-sensing, i.e. the particle velocity is proportional to the spatial gradient of the logarithm of the salt concentration, as VDP = DDP∇logc. Here we explore experimentally the implications of this log-sensing behavior, on the basis of a hydrogel microfluidic device allowing to build spatially and temporally controlled gradients. We first demonstrate that the non-linearity of the salt-taxis leads to a trapping of particles under concentration gradient oscillations via a rectification of the motion. As an alternative, we make use of the high sensitivity of diffusiophoretic migration to vanishing salt concentration due to the log-sensing: in a counter-intuitive way, a vanishing gradient can lead to measurable velocity provided that the solute concentration is low enough, thus keeping ∇c/c finite. We show that this leads to a strong segregation of particles in osmotic shock configuration, resulting from a step change of the salt concentration at the boundaries. These various phenomena are rationalized on the basis of a theoretical description for the time-dependent Smoluchowski equation for the colloidal density. AU - Palacci, Jérémie A AU - Cottin-Bizonne, Cécile AU - Ybert, Christophe AU - Bocquet, Lydéric ID - 9049 IS - 4 JF - Soft Matter SN - 1744-683X TI - Osmotic traps for colloids and macromolecules based on logarithmic sensing in salt taxis VL - 8 ER - TY - JOUR AB - We study theoretically the morphologies of biological tubes affected by various pathologies. When epithelial cells grow, the negative tension produced by their division provokes a buckling instability. Several shapes are investigated: varicose, dilated, sinuous, or sausagelike. They are all found in pathologies of tracheal, renal tubes, or arteries. The final shape depends crucially on the mechanical parameters of the tissues: Young's modulus, wall-to-lumen ratio, homeostatic pressure. We argue that since tissues must be in quasistatic mechanical equilibrium, abnormal shapes convey information as to what causes the pathology. We calculate a phase diagram of tubular instabilities which could be a helpful guide for investigating the underlying genetic regulation. AU - Hannezo, Edouard B AU - Prost, Jacques AU - Joanny, Jean ID - 922 IS - 1 JF - Physical Review Letters TI - Mechanical instabilities of biological tubes VL - 109 ER - TY - JOUR AB - EMBRYONIC FLOWER1 (EMF1) is a plant-specific gene crucial to Arabidopsis vegetative development. Loss of function mutants in the EMF1 gene mimic the phenotype caused by mutations in Polycomb Group protein (PcG) genes, which encode epigenetic repressors that regulate many aspects of eukaryotic development. In Arabidopsis, Polycomb Repressor Complex 2 (PRC2), made of PcG proteins, catalyzes trimethylation of lysine 27 on histone H3 (H3K27me3) and PRC1-like proteins catalyze H2AK119 ubiquitination. Despite functional similarity to PcG proteins, EMF1 lacks sequence homology with known PcG proteins; thus, its role in the PcG mechanism is unclear. To study the EMF1 functions and its mechanism of action, we performed genome-wide mapping of EMF1 binding and H3K27me3 modification sites in Arabidopsis seedlings. The EMF1 binding pattern is similar to that of H3K27me3 modification on the chromosomal and genic level. ChIPOTLe peak finding and clustering analyses both show that the highly trimethylated genes also have high enrichment levels of EMF1 binding, termed EMF1_K27 genes. EMF1 interacts with regulatory genes, which are silenced to allow vegetative growth, and with genes specifying cell fates during growth and differentiation. H3K27me3 marks not only these genes but also some genes that are involved in endosperm development and maternal effects. Transcriptome analysis, coupled with the H3K27me3 pattern, of EMF1_K27 genes in emf1 and PRC2 mutants showed that EMF1 represses gene activities via diverse mechanisms and plays a novel role in the PcG mechanism. AU - Kim, Sang Yeol AU - Lee, Jungeun AU - Eshed-Williams, Leor AU - Zilberman, Daniel AU - Sung, Z. Renee ID - 9499 IS - 3 JF - PLoS Genetics SN - 1553-7390 TI - EMF1 and PRC2 cooperate to repress key regulators of Arabidopsis development VL - 8 ER - TY - JOUR AB - The regulation of eukaryotic chromatin relies on interactions between many epigenetic factors, including histone modifications, DNA methylation, and the incorporation of histone variants. H2A.Z, one of the most conserved but enigmatic histone variants that is enriched at the transcriptional start sites of genes, has been implicated in a variety of chromosomal processes. Recently, we reported a genome-wide anticorrelation between H2A.Z and DNA methylation, an epigenetic hallmark of heterochromatin that has also been found in the bodies of active genes in plants and animals. Here, we investigate the basis of this anticorrelation using a novel h2a.z loss-of-function line in Arabidopsis thaliana. Through genome-wide bisulfite sequencing, we demonstrate that loss of H2A.Z in Arabidopsis has only a minor effect on the level or profile of DNA methylation in genes, and we propose that the global anticorrelation between DNA methylation and H2A.Z is primarily caused by the exclusion of H2A.Z from methylated DNA. RNA sequencing and genomic mapping of H2A.Z show that H2A.Z enrichment across gene bodies, rather than at the TSS, is correlated with lower transcription levels and higher measures of gene responsiveness. Loss of H2A.Z causes misregulation of many genes that are disproportionately associated with response to environmental and developmental stimuli. We propose that H2A.Z deposition in gene bodies promotes variability in levels and patterns of gene expression, and that a major function of genic DNA methylation is to exclude H2A.Z from constitutively expressed genes. AU - Coleman-Derr, Devin AU - Zilberman, Daniel ID - 9497 IS - 10 JF - PLoS Genetics SN - 1553-7390 TI - Deposition of histone variant H2A.Z within gene bodies regulates responsive genes VL - 8 ER - TY - JOUR AB - Accumulating evidence points toward diverse functions for plant chromatin. Remarkable progress has been made over the last few years in elucidating the mechanisms for a number of these functions. Activity of the histone demethylase IBM1 accurately targets DNA methylation to silent repeats and transposable elements, not to genes. A genetic screen uncovered the surprising role of H2A.Z-containing nucleosomes in sensing precise differences in ambient temperature and consequent gene regulation. Precise maintenance of chromosome number is assured by a histone modification that suppresses inappropriate DNA replication and by centromeric histone H3 regulation of chromosome segregation. Histones and noncoding RNAs regulate FLOWERING LOCUS C, the expression of which quantitatively measures the duration of cold exposure, functioning as memory of winter. These findings are a testament to the power of using plants to research chromatin organization, and demonstrate examples of how chromatin functions to achieve biological accuracy, precision, and memory. AU - Huff, Jason T. AU - Zilberman, Daniel ID - 9528 IS - 2 JF - Current Opinion in Genetics and Development SN - 0959-437X TI - Regulation of biological accuracy, precision, and memory by plant chromatin organization VL - 22 ER - TY - JOUR AB - Motivated by recent experiments on Ba3NiSb2O 9, we investigate possible quantum spin liquid ground states for spin S=1 Heisenberg models on the triangular lattice. We use variational Monte Carlo techniques to calculate the energies of microscopic spin liquid wave functions where spin is represented by three flavors of fermionic spinon operators. These energies are compared with the energies of various competing three-sublattice ordered states. Our approach shows that the antiferromagnetic Heisenberg model with biquadratic term and single-ion anisotropy does not have a low-temperature spin liquid phase. However, for an SU(3)-invariant model with sufficiently strong ring-exchange terms, we find a paired chiral quantum spin liquid with a Fermi surface of deconfined spinons that is stable against all types of ordering patterns we considered. We discuss the physics of this exotic spin liquid state in relation to the recent experiment and suggest new ways to test this scenario. AU - Bieri, Samuel AU - Maksym Serbyn AU - Senthil, Todadri S AU - Lee, Patrick ID - 966 IS - 22 JF - Physical Review B - Condensed Matter and Materials Physics TI - Paired chiral spin liquid with a Fermi surface in S=1 model on the triangular lattice VL - 86 ER - TY - JOUR AB - Little is known about the stability of trophic relationships in complex natural communities over evolutionary timescales. Here, we use sequence data from 18 nuclear loci to reconstruct and compare the intraspecific histories of major Pleistocene refugial populations in the Middle East, the Balkans and Iberia in a guild of four Chalcid parasitoids (Cecidostiba fungosa, Cecidostiba semifascia, Hobbya stenonota and Mesopolobus amaenus) all attacking Cynipid oak galls. We develop a likelihood method to numerically estimate models of divergence between three populations from multilocus data. We investigate the power of this framework on simulated data, and-using triplet alignments of intronic loci-quantify the support for all possible divergence relationships between refugial populations in the four parasitoids. Although an East to West order of population divergence has highest support in all but one species, we cannot rule out alternative population tree topologies. Comparing the estimated times of population splits between species, we find that one species, M. amaenus, has a significantly older history than the rest of the guild and must have arrived in central Europe at least one glacial cycle prior to other guild members. This suggests that although all four species may share a common origin in the East, they expanded westwards into Europe at different times. © 2012 Blackwell Publishing Ltd. AU - Lohse, Konrad AU - Barton, Nicholas H AU - Melika, George AU - Stone, Graham ID - 2968 IS - 18 JF - Molecular Ecology TI - A likelihood based comparison of population histories in a parasitoid guild VL - 21 ER - TY - GEN AB - Little is known about the stability of trophic relationships in complex natural communities over evolutionary timescales. Here, we use sequence data from 18 nuclear loci to reconstruct and compare the intraspecific histories of major Pleistocene refugial populations in the Middle East, the Balkans and Iberia in a guild of four Chalcid parasitoids (Cecidostiba fungosa, C. semifascia, Hobbya stenonota and Mesopolobus amaenus) all attacking Cynipid oak galls. We develop a likelihood method to numerically estimate models of divergence between three populations from multilocus data. We investigate the power of this framework on simulated data, and - using triplet alignments of intronic loci - quantify the support for all possible divergence relationships between refugial populations in the four parasitoids. Although an East to West order of population divergence has highest support in all but one species, we cannot rule out alternative population tree topologies. Comparing the estimated times of population splits between species, we find that one species, M. amaenus, has a significantly older history than the rest of the guild and must have arrived in central Europe at least one glacial cycle prior to other guild members. This suggests that although all four species may share a common origin in the East, they expanded westwards into Europe at different times. AU - Lohse, Konrad AU - Barton, Nicholas H AU - Stone, Graham AU - Melika, George ID - 13075 TI - Data from: A likelihood-based comparison of population histories in a parasitoid guild ER - TY - JOUR AB - We show that diamagnetic particles can be remotely manipulated by a magnet by the reversible adsorption of dual-responsive, light-switchable/superparamagnetic nanoparticles down to their surface. Adsorption occurs upon exposure to UV light, and can be reversed thermally or by ambient light. The dynamic self-assembly of thin films of the dual-responsive nanoparticles induces attractive interactions between diamagnetic particles. We demonstrate that catalytic amounts of the dual-responsive nanoparticles are sufficient to magnetically guide and deliver the diamagnetic particles to desired locations, where they can then be released by disassembling the dynamic layers of superparamagnetic nanoparticles with visible light. AU - Chovnik, Olga AU - Balgley, Renata AU - Goldman, Joel R. AU - Klajn, Rafal ID - 13407 IS - 48 JF - Journal of the American Chemical Society KW - Colloid and Surface Chemistry KW - Biochemistry KW - General Chemistry KW - Catalysis SN - 0002-7863 TI - Dynamically self-assembling carriers enable guiding of diamagnetic particles by weak magnets VL - 134 ER - TY - JOUR AB - Well-defined metallic nanobowls can be prepared by extending the concept of a protecting group to colloidal synthesis. Magnetic nanoparticles are employed as “protecting groups” during the galvanic replacement of silver with gold. The replacement reaction is accompanied by spontantous dissociation of the protecting groups, leaving behind metallic nanobowls. AU - Ridelman, Yonatan AU - Singh, Gurvinder AU - Popovitz-Biro, Ronit AU - Wolf, Sharon G. AU - Das, Sanjib AU - Klajn, Rafal ID - 13408 IS - 5 JF - Small KW - Biomaterials KW - Biotechnology KW - General Materials Science KW - General Chemistry SN - 1613-6810 TI - Metallic nanobowls by galvanic replacement reaction on heterodimeric nanoparticles VL - 8 ER - TY - CONF AB - We propose a logic-based framework for automated reasoning about sequential programs manipulating singly-linked lists and arrays with unbounded data. We introduce the logic SLAD, which allows combining shape constraints, written in a fragment of Separation Logic, with data and size constraints. We address the problem of checking the entailment between SLAD formulas, which is crucial in performing pre-post condition reasoning. Although this problem is undecidable in general for SLAD, we propose a sound and powerful procedure that is able to solve this problem for a large class of formulas, beyond the capabilities of existing techniques and tools. We prove that this procedure is complete, i.e., it is actually a decision procedure for this problem, for an important fragment of SLAD including known decidable logics. We implemented this procedure and shown its preciseness and its efficiency on a significant benchmark of formulas. AU - Bouajjani, Ahmed AU - Dragoi, Cezara AU - Enea, Constantin AU - Sighireanu, Mihaela ID - 10903 SN - 0302-9743 T2 - Automated Technology for Verification and Analysis TI - Accurate invariant checking for programs manipulating lists and arrays with infinite data VL - 7561 ER - TY - CONF AB - Energy games belong to a class of turn-based two-player infinite-duration games played on a weighted directed graph. It is one of the rare and intriguing combinatorial problems that lie in NP ∩ co−NP, but are not known to be in P. While the existence of polynomial-time algorithms has been a major open problem for decades, there is no algorithm that solves any non-trivial subclass in polynomial time. In this paper, we give several results based on the weight structures of the graph. First, we identify a notion of penalty and present a polynomial-time algorithm when the penalty is large. Our algorithm is the first polynomial-time algorithm on a large class of weighted graphs. It includes several counter examples that show that many previous algorithms, such as value iteration and random facet algorithms, require at least sub-exponential time. Our main technique is developing the first non-trivial approximation algorithm and showing how to convert it to an exact algorithm. Moreover, we show that in a practical case in verification where weights are clustered around a constant number of values, the energy game problem can be solved in polynomial time. We also show that the problem is still as hard as in general when the clique-width is bounded or the graph is strongly ergodic, suggesting that restricting graph structures need not help. AU - Chatterjee, Krishnendu AU - Henzinger, Monika H AU - Krinninger, Sebastian AU - Nanongkai, Danupon ID - 10905 SN - 0302-9743 T2 - Algorithms – ESA 2012 TI - Polynomial-time algorithms for energy games with special weight structures VL - 7501 ER - TY - CONF AB - HSF(C) is a tool that automates verification of safety and liveness properties for C programs. This paper describes the verification approach taken by HSF(C) and provides instructions on how to install and use the tool. AU - Grebenshchikov, Sergey AU - Gupta, Ashutosh AU - Lopes, Nuno P. AU - Popeea, Corneliu AU - Rybalchenko, Andrey ED - Flanagan, Cormac ED - König, Barbara ID - 10906 SN - 0302-9743 T2 - Tools and Algorithms for the Construction and Analysis of Systems TI - HSF(C): A software verifier based on Horn clauses VL - 7214 ER - TY - CHAP AU - Gupta, Ashutosh ID - 5745 SN - 0302-9743 T2 - Automated Technology for Verification and Analysis TI - Improved Single Pass Algorithms for Resolution Proof Reduction VL - 7561 ER - TY - CONF AB - Many infinite state systems can be seen as well-structured transition systems (WSTS), i.e., systems equipped with a well-quasi-ordering on states that is also a simulation relation. WSTS are an attractive target for formal analysis because there exist generic algorithms that decide interesting verification problems for this class. Among the most popular algorithms are acceleration-based forward analyses for computing the covering set. Termination of these algorithms can only be guaranteed for flattable WSTS. Yet, many WSTS of practical interest are not flattable and the question whether any given WSTS is flattable is itself undecidable. We therefore propose an analysis that computes the covering set and captures the essence of acceleration-based algorithms, but sacrifices precision for guaranteed termination. Our analysis is an abstract interpretation whose abstract domain builds on the ideal completion of the well-quasi-ordered state space, and a widening operator that mimics acceleration and controls the loss of precision of the analysis. We present instances of our framework for various classes of WSTS. Our experience with a prototype implementation indicates that, despite the inherent precision loss, our analysis often computes the precise covering set of the analyzed system. AU - Zufferey, Damien AU - Wies, Thomas AU - Henzinger, Thomas A ID - 3251 TI - Ideal abstractions for well structured transition systems VL - 7148 ER - TY - JOUR AB - Colorectal tumours that are wild type for KRAS are often sensitive to EGFR blockade, but almost always develop resistance within several months of initiating therapy. The mechanisms underlying this acquired resistance to anti-EGFR antibodies are largely unknown. This situation is in marked contrast to that of small-molecule targeted agents, such as inhibitors of ABL, EGFR, BRAF and MEK, in which mutations in the genes encoding the protein targets render the tumours resistant to the effects of the drugs. The simplest hypothesis to account for the development of resistance to EGFR blockade is that rare cells with KRAS mutations pre-exist at low levels in tumours with ostensibly wild-type KRAS genes. Although this hypothesis would seem readily testable, there is no evidence in pre-clinical models to support it, nor is there data from patients. To test this hypothesis, we determined whether mutant KRAS DNA could be detected in the circulation of 28 patients receiving monotherapy with panitumumab, a therapeutic anti-EGFR antibody. We found that 9 out of 24 (38%) patients whose tumours were initially KRAS wild type developed detectable mutations in KRAS in their sera, three of which developed multiple different KRAS mutations. The appearance of these mutations was very consistent, generally occurring between 5 and 6months following treatment. Mathematical modelling indicated that the mutations were present in expanded subclones before the initiation of panitumumab treatment. These results suggest that the emergence of KRAS mutations is a mediator of acquired resistance to EGFR blockade and that these mutations can be detected in a non-invasive manner. They explain why solid tumours develop resistance to targeted therapies in a highly reproducible fashion. AU - Diaz Jr, Luis AU - Williams, Richard AU - Wu, Jian AU - Kinde, Isaac AU - Hecht, Joel AU - Berlin, Jordan AU - Allen, Benjamin AU - Božić, Ivana AU - Reiter, Johannes AU - Nowak, Martin AU - Kinzler, Kenneth AU - Oliner, Kelly AU - Vogelstein, Bert ID - 3157 IS - 7404 JF - Nature TI - The molecular evolution of acquired resistance to targeted EGFR blockade in colorectal cancers VL - 486 ER - TY - JOUR AB - Many scenarios in the living world, where individual organisms compete for winning positions (or resources), have properties of auctions. Here we study the evolution of bids in biological auctions. For each auction, n individuals are drawn at random from a population of size N. Each individual makes a bid which entails a cost. The winner obtains a benefit of a certain value. Costs and benefits are translated into reproductive success (fitness). Therefore, successful bidding strategies spread in the population. We compare two types of auctions. In “biological all-pay auctions”, the costs are the bid for every participating individual. In “biological second price all-pay auctions”, the cost for everyone other than the winner is the bid, but the cost for the winner is the second highest bid. Second price all-pay auctions are generalizations of the “war of attrition” introduced by Maynard Smith. We study evolutionary dynamics in both types of auctions. We calculate pairwise invasion plots and evolutionarily stable distributions over the continuous strategy space. We find that the average bid in second price all-pay auctions is higher than in all-pay auctions, but the average cost for the winner is similar in both auctions. In both cases, the average bid is a declining function of the number of participants, n. The more individuals participate in an auction the smaller is the chance of winning, and thus expensive bids must be avoided. AU - Chatterjee, Krishnendu AU - Reiter, Johannes AU - Nowak, Martin ID - 3260 IS - 1 JF - Theoretical Population Biology TI - Evolutionary dynamics of biological auctions VL - 81 ER - TY - JOUR AB - CA3 pyramidal neurons are important for memory formation and pattern completion in the hippocampal network. It is generally thought that proximal synapses from the mossy fibers activate these neurons most efficiently, whereas distal inputs from the perforant path have a weaker modulatory influence. We used confocally targeted patch-clamp recording from dendrites and axons to map the activation of rat CA3 pyramidal neurons at the subcellular level. Our results reveal two distinct dendritic domains. In the proximal domain, action potentials initiated in the axon backpropagate actively with large amplitude and fast time course. In the distal domain, Na+ channel–mediated dendritic spikes are efficiently initiated by waveforms mimicking synaptic events. CA3 pyramidal neuron dendrites showed a high Na+-to-K+ conductance density ratio, providing ideal conditions for active backpropagation and dendritic spike initiation. Dendritic spikes may enhance the computational power of CA3 pyramidal neurons in the hippocampal network. AU - Kim, Sooyun AU - Guzmán, José AU - Hu, Hua AU - Jonas, Peter M ID - 3258 IS - 4 JF - Nature Neuroscience SN - 1546-1726 TI - Active dendrites support efficient initiation of dendritic spikes in hippocampal CA3 pyramidal neurons VL - 15 ER - TY - THES AB - CA3 pyramidal neurons are important for memory formation and pattern completion in the hippocampal network. These neurons receive multiple excitatory inputs from numerous sources. Therefore, the rules of spatiotemporal integration of multiple synaptic inputs and propagation of action potentials are important to understand how CA3 neurons contribute to higher brain functions at cellular level. By using confocally targeted patch-clamp recording techniques, we investigated the biophysical properties of rat CA3 pyramidal neuron dendrites. We found two distinct dendritic domains critical for action potential initiation and propagation: In the proximal domain, action potentials initiated in the axon backpropagate actively with large amplitude and fast time course. In the distal domain, Na+-channel mediated dendritic spikes are efficiently evoked by local dendritic depolarization or waveforms mimicking synaptic events. These findings can be explained by a high Na+-to-K+ conductance density ratio of CA3 pyramidal neuron dendrites. The results challenge the prevailing view that proximal mossy fiber inputs activate CA3 pyramidal neurons more efficiently than distal perforant inputs by showing that the distal synapses trigger a different form of activity represented by dendritic spikes. The high probability of dendritic spike initiation in the distal area may enhance the computational power of CA3 pyramidal neurons in the hippocampal network. AU - Kim, Sooyun ID - 2964 SN - 2663-337X TI - Active properties of hippocampal CA3 pyramidal neuron dendrites ER - TY - JOUR AB - Visualizing and analyzing shape changes at various scales, ranging from single molecules to whole organisms, are essential for understanding complex morphogenetic processes, such as early embryonic development. Embryo morphogenesis relies on the interplay between different tissues, the properties of which are again determined by the interaction between their constituent cells. Cell interactions, on the other hand, are controlled by various molecules, such as signaling and adhesion molecules, which in order to exert their functions need to be spatiotemporally organized within and between the interacting cells. In this review, we will focus on the role of cell adhesion functioning at different scales to organize cell, tissue and embryo morphogenesis. We will specifically ask how the subcellular distribution of adhesion molecules controls the formation of cell-cell contacts, how cell-cell contacts determine tissue shape, and how tissue interactions regulate embryo morphogenesis. AU - Barone, Vanessa AU - Heisenberg, Carl-Philipp J ID - 3246 IS - 1 JF - Current Opinion in Cell Biology TI - Cell adhesion in embryo morphogenesis VL - 24 ER - TY - JOUR AB - The Arabidopsis thaliana central cell, the companion cell of the egg, undergoes DNA demethylation before fertilization, but the targeting preferences, mechanism, and biological significance of this process remain unclear. Here, we show that active DNA demethylation mediated by the DEMETER DNA glycosylase accounts for all of the demethylation in the central cell and preferentially targets small, AT-rich, and nucleosome-depleted euchromatic transposable elements. The vegetative cell, the companion cell of sperm, also undergoes DEMETER-dependent demethylation of similar sequences, and lack of DEMETER in vegetative cells causes reduced small RNA–directed DNA methylation of transposons in sperm. Our results demonstrate that demethylation in companion cells reinforces transposon methylation in plant gametes and likely contributes to stable silencing of transposable elements across generations. AU - Ibarra, Christian A. AU - Feng, Xiaoqi AU - Schoft, Vera K. AU - Hsieh, Tzung-Fu AU - Uzawa, Rie AU - Rodrigues, Jessica A. AU - Zemach, Assaf AU - Chumak, Nina AU - Machlicova, Adriana AU - Nishimura, Toshiro AU - Rojas, Denisse AU - Fischer, Robert L. AU - Tamaru, Hisashi AU - Zilberman, Daniel ID - 12198 IS - 6100 JF - Science KW - Multidisciplinary SN - 0036-8075 TI - Active DNA demethylation in plant companion cells reinforces transposon methylation in gametes VL - 337 ER - TY - JOUR AB - First we note that the best polynomial approximation to vertical bar x vertical bar on the set, which consists of an interval on the positive half-axis and a point on the negative half-axis, can be given by means of the classical Chebyshev polynomials. Then we explore the cases when a solution of the related problem on two intervals can be given in elementary functions. AU - Pausinger, Florian ID - 6588 IS - 1 JF - Journal of Mathematical Physics, Analysis, Geometry SN - 1812-9471 TI - Elementary solutions of the Bernstein problem on two intervals VL - 8 ER - TY - CONF AB - We introduce the idea of using an explicit triangle mesh to track the air/fluid interface in a smoothed particle hydrodynamics (SPH) simulator. Once an initial surface mesh is created, this mesh is carried forward in time using nearby particle velocities to advect the mesh vertices. The mesh connectivity remains mostly unchanged across time-steps; it is only modified locally for topology change events or for the improvement of triangle quality. In order to ensure that the surface mesh does not diverge from the underlying particle simulation, we periodically project the mesh surface onto an implicit surface defined by the physics simulation. The mesh surface gives us several advantages over previous SPH surface tracking techniques. We demonstrate a new method for surface tension calculations that clearly outperforms the state of the art in SPH surface tension for computer graphics. We also demonstrate a method for tracking detailed surface information (like colors) that is less susceptible to numerical diffusion than competing techniques. Finally, our temporally-coherent surface mesh allows us to simulate high-resolution surface wave dynamics without being limited by the particle resolution of the SPH simulation. AU - Yu, Jihun AU - Wojtan, Christopher J AU - Turk, Greg AU - Yap, Chee ID - 3123 IS - 2 SN - 0167-7055 T2 - Computer Graphics Forum TI - Explicit mesh surfaces for particle based fluids VL - 31 ER - TY - JOUR AB - Bibliothekare haben die Aufgabe, sich mit neuen Medienformen auseinanderzusetzen. AU - Danowski, Patrick ID - 3244 IS - 4 JF - BuB - Forum Bibliothek und Information SN - 1869 -1137 TI - Die Zeit des Abwartens ist vorbei! VL - 64 ER - TY - JOUR AB - Wie wandelt sich das Berufsbild in Wissenschaftlichen Bibliotheken? Patrick Danowski gibt seine Einschätzung ab. AU - Danowski, Patrick ID - 3243 IS - 1 JF - Büchereiperspektiven SN - 1607-7172 TI - Zwischen Technologie und Information VL - 2012 ER - TY - CONF AU - Kroemer, Oliver AU - Lampert, Christoph AU - Peters, Jan ID - 2915 TI - Multi-modal learning for dynamic tactile sensing ER - TY - JOUR AU - Edelsbrunner, Herbert AU - Strelkova, Nataliya ID - 2912 IS - 6 JF - Russian Mathematical Surveys TI - On the configuration space for the shortest networks VL - 67 ER - TY - CONF AB - When searching for characteristic subpatterns in potentially noisy graph data, it appears self-evident that having multiple observations would be better than having just one. However, it turns out that the inconsistencies introduced when different graph instances have different edge sets pose a serious challenge. In this work we address this challenge for the problem of finding maximum weighted cliques. We introduce the concept of most persistent soft-clique. This is subset of vertices, that 1) is almost fully or at least densely connected, 2) occurs in all or almost all graph instances, and 3) has the maximum weight. We present a measure of clique-ness, that essentially counts the number of edge missing to make a subset of vertices into a clique. With this measure, we show that the problem of finding the most persistent soft-clique problem can be cast either as: a) a max-min two person game optimization problem, or b) a min-min soft margin optimization problem. Both formulations lead to the same solution when using a partial Lagrangian method to solve the optimization problems. By experiments on synthetic data and on real social network data, we show that the proposed method is able to reliably find soft cliques in graph data, even if that is distorted by random noise or unreliable observations. AU - Quadrianto, Novi AU - Lampert, Christoph AU - Chen, Chao ID - 3127 T2 - Proceedings of the 29th International Conference on Machine Learning TI - The most persistent soft-clique in a set of sampled graphs ER - TY - JOUR AB - Generalized van der Corput sequences are onedimensional, infinite sequences in the unit interval. They are generated from permutations in integer base b and are the building blocks of the multi-dimensional Halton sequences. Motivated by recent progress of Atanassov on the uniform distribution behavior of Halton sequences, we study, among others, permutations of the form P(i) = ai (mod b) for coprime integers a and b. We show that multipliers a that either divide b - 1 or b + 1 generate van der Corput sequences with weak distribution properties. We give explicit lower bounds for the asymptotic distribution behavior of these sequences and relate them to sequences generated from the identity permutation in smaller bases, which are, due to Faure, the weakest distributed generalized van der Corput sequences. AU - Pausinger, Florian ID - 2904 IS - 3 JF - Journal de Theorie des Nombres des Bordeaux SN - 1246-7405 TI - Weak multipliers for generalized van der Corput sequences VL - 24 ER - TY - JOUR AB - We present an algorithm for simplifying linear cartographic objects and results obtained with a computer program implementing this algorithm. AU - Edelsbrunner, Herbert AU - Musin, Oleg AU - Ukhalov, Alexey AU - Yakimova, Olga AU - Alexeev, Vladislav AU - Bogaevskaya, Victoriya AU - Gorohov, Andrey AU - Preobrazhenskaya, Margarita ID - 2902 IS - 6 JF - Modeling and Analysis of Information Systems TI - Fractal and computational geometry for generalizing cartographic objects VL - 19 ER - TY - JOUR AB - We perform numerical simulations to study self-assembly of nanoparticles mediated by an elastic planar surface. We show how the nontrivial elastic response to deformations of these surfaces leads to anisotropic interactions between the particles resulting in aggregates having different geometrical features. The morphology of the patterns can be controlled by the mechanical properties of the surface and the strength of the particle adhesion. We use simple scaling arguments to understand the formation of the different structures, and we show how the adhering particles can cause the underlying elastic substrate to wrinkle if two of its opposite edges are clamped. Finally, we discuss the implications of our results and suggest how elastic surfaces could be used in nanofabrication. AU - Šarić, Anđela AU - Cacciuto, Angelo ID - 10389 IS - 18 JF - Soft Matter KW - condensed matter physics KW - general chemistry SN - 1744-683X TI - Soft elastic surfaces as a platform for particle self-assembly VL - 7 ER - TY - JOUR AB - We present experimentally derived potential curves 1?and spin-orbit interaction functions for the strongly perturbed AΣu+ 3?and bΠu states of the cesium dimer. The results are based on data from several sources. Laser-induced fluorescence Fourier transform spectroscopy (LIF FTS) was used some time ago in the Laboratoire Aimé Cotton primarily to study the XΣg+ state. More recent work at Tsinghua University provides information from moderate 3?resolution spectroscopy on the lowest levels of the bΠ0u± state as well as additional high-resolution data. From Innsbruck University, we have precision data obtained with cold Cs2 molecules. Recent data from Temple University was obtained using the optical-optical double resonance polarization spectroscopy technique, and finally, a group at the University of Latvia has added additional LIF FTS data. In the Hamiltonian matrix, we have used analytic potentials (the expanded Morse oscillator form) with both finite-difference (FD) coupled-channel and discrete variable representation (DVR) calculations of the term values. Fitted diagonal and off-diagonal spin-orbit functions are obtained and compared with ab initio results from Temple and Moscow State universities. AU - Bai, Jianmei AU - Ahmed, Ergin AU - Beser, Bediha AU - Guan, Yafei AU - Kotochigova, Svetlana AU - Lyyra, Marjatta AU - Ashman, Seth AU - Wolfe, Christopher AU - Huennekens, John AU - Xie, Feng AU - Li, Dan AU - Li, Li AU - Tamanis, Maris AU - Ferber, Ruvin AU - Drozdova, Anastasia AU - Pazyuk, Elena AU - Stolyarov, Andrey AU - Danzl, Johann G AU - Nägerl, Hanns AU - Bouloufa, Nadia AU - Dulieu, Olivier AU - Amiot, Claude AU - Salami, Houssam AU - Bergeman, Thomas ID - 1050 IS - 3 JF - Physical Review A - Atomic, Molecular, and Optical Physics TI - Global analysis of data on the spin-orbit-coupled A 1Σu+ and b 3Πu inf states of Cs2 VL - 83 ER - TY - JOUR AB - We produce an ultracold and dense sample of rovibronic ground state Cs 2 molecules close to the regime of quantum degeneracy, in a single hyperfine level, in the presence of an optical lattice. The molecules are individually trapped, in the motional ground state of an optical lattice well, with a lifetime of 8 s. For preparation, we start with a zero-temperature atomic Mott-insulator state with optimized double-site occupancy and efficiently associate weakly-bound dimer molecules on a Feshbach resonance. Despite extremely weak Franck-Condon wavefunction overlap, the molecules are subsequently transferred with >50% efficiency to the rovibronic ground state by a stimulated four-photon process. Our results present a crucial step towards the generation of Bose-Einstein condensates of ground-state molecules and, when suitably generalized to polar heteronuclear molecules such as RbCs, the realization of dipolar many-body quantum-gas phases in periodic potentials. AU - Nägerl, Hanns AU - Mark, Manfred AU - Haller, Elmar AU - Gustavsson, Mattias AU - Hart, Russell AU - Danzl, Johann G ID - 1048 IS - 1 JF - Journal of Physics: Conference Series TI - Ultracold and dense samples of ground-state molecules in lattice potentials VL - 264 ER - TY - JOUR AB - The present paper aims at finding optimal parameters for trapping of Cs 2 molecules in optical lattices, with the perspective of creating a quantum degenerate gas of ground-state molecules. We have calculated dynamic polarizabilities of Cs 2 molecules subject to an oscillating electric field, using accurate potential curves and electronic transition dipole moments. We show that for some particular wavelengths of the optical lattice, called "magic wavelengths", the polarizability of the ground-state molecules is equal to the one of a Feshbach molecule. As the creation of the sample of ground-state molecules relies on an adiabatic population transfer from weakly-bound molecules created on a Feshbach resonance, such a coincidence ensures that both the initial and final states are favorably trapped by the lattice light, allowing optimized transfer in agreement with the experimental observation. AU - Vexiau, Romain AU - Bouloufa, Nadia AU - Aymar, Mireille AU - Danzl, Johann G AU - Mark, Manfred AU - Nägerl, Hanns AU - Dulieu, Olivier ID - 1052 IS - 1-2 JF - European Physical Journal D TI - Optimal trapping wavelengths of Cs 2 molecules in an optical lattice VL - 65 ER - TY - JOUR AB - We demonstrate the temporal Talbot effect for trapped matter waves using ultracold atoms in an optical lattice. We investigate the phase evolution of an array of essentially non-interacting matter waves and observe matter-wave collapse and revival in the form of a Talbot interference pattern. By using long expansion times, we image momentum space with sub-recoil resolution, allowing us to observe fractional Talbot fringes up to tenth order. AU - Mark, Manfred AU - Haller, Elmar AU - Danzl, Johann G AU - Lauber, Katharina AU - Gustavsson, Mattias AU - Nägerl, Hanns ID - 1051 JF - New Journal of Physics TI - Demonstration of the temporal matter-wave Talbot effect for trapped matter waves VL - 13 ER - TY - JOUR AB - We perform precision measurements on a Mott-insulator quantum state of ultracold atoms with tunable interactions. We probe the dependence of the superfluid-to-Mott-insulator transition on the interaction strength and explore the limits of the standard Bose-Hubbard model description. By tuning the on-site interaction energies to values comparable to the interband separation, we are able to quantitatively measure number-dependent shifts in the excitation spectrum caused by effective multibody interactions. AU - Mark, Manfred AU - Haller, Elmar AU - Lauber, Katharina AU - Danzl, Johann G AU - Daley, Andrew AU - Nägerl, Hanns ID - 1053 IS - 17 JF - Physical Review Letters TI - Precision measurements on a tunable Mott insulator of ultracold atoms VL - 107 ER - TY - JOUR AB - We investigate local three-body correlations for bosonic particles in three dimensions and one dimension as a function of the interaction strength. The three-body correlation function g(3) is determined by measuring the three-body recombination rate in an ultracold gas of Cs atoms. In three dimensions, we measure the dependence of g(3) on the gas parameter in a BEC, finding good agreement with the theoretical prediction accounting for beyond-mean-field effects. In one dimension, we observe a reduction of g( 3) by several orders of magnitude upon increasing interactions from the weakly interacting BEC to the strongly interacting Tonks-Girardeau regime, in good agreement with predictions from the Lieb-Liniger model for all strengths of interaction. AU - Haller, Elmar AU - Rabie, Mahmoud AU - Mark, Manfred AU - Danzl, Johann G AU - Hart, Russell AU - Lauber, Katharina AU - Pupillo, Guido AU - Nägerl, Hanns ID - 1054 IS - 23 JF - Physical Review Letters TI - Three-body correlation functions and recombination rates for bosons in three dimensions and one dimension VL - 107 ER - TY - JOUR AB - Nuclear pore complexes (NPCs) assemble at the end of mitosis during nuclear envelope (NE) reformation and into an intact NE as cells progress through interphase. Although recent studies have shown that NPC formation occurs by two different molecular mechanisms at two distinct cell cycle stages, little is known about the molecular players that mediate the fusion of the outer and inner nuclear membranes to form pores. In this paper, we provide evidence that the transmembrane nucleoporin (Nup), POM121, but not the Nup107–160 complex, is present at new pore assembly sites at a time that coincides with inner nuclear membrane (INM) and outer nuclear membrane (ONM) fusion. Overexpression of POM121 resulted in juxtaposition of the INM and ONM. Additionally, Sun1, an INM protein that is known to interact with the cytoskeleton, was specifically required for interphase assembly and localized with POM121 at forming pores. We propose a model in which POM121 and Sun1 interact transiently to promote early steps of interphase NPC assembly. AU - Talamas, Jessica A. AU - HETZER, Martin W ID - 11094 IS - 1 JF - Journal of Cell Biology KW - Cell Biology SN - 0021-9525 TI - POM121 and Sun1 play a role in early steps of interphase NPC assembly VL - 194 ER - TY - JOUR AB - As the gatekeepers of the eukaryotic cell nucleus, nuclear pore complexes (NPCs) mediate all molecular trafficking between the nucleoplasm and the cytoplasm. In recent years, transport-independent functions of NPC components, nucleoporins, have been identified including roles in chromatin organization and gene regulation. Here, we summarize our current view of the NPC as a dynamic hub for the integration of chromatin regulation and nuclear trafficking and discuss the functional interplay between nucleoporins and the nuclear genome. AU - Liang, Yun AU - HETZER, Martin W ID - 11096 IS - 1 JF - Current Opinion in Cell Biology KW - Cell Biology SN - 0955-0674 TI - Functional interactions between nucleoporins and chromatin VL - 23 ER - TY - JOUR AU - HETZER, Martin W AU - Cavalli, Giacomo ID - 11095 IS - 3 JF - Current Opinion in Cell Biology KW - Cell Biology SN - 0955-0674 TI - Editorial overview VL - 23 ER -