@article{2911, abstract = {We have selected problems that may not yet be well known, but have the potential to push the research in interesting directions. In particular, we state problems that do not require specific knowledge outside the standard circle of ideas in discrete geometry. Despite the relatively simple statements, these problems are related to current research and their solutions are likely to require new ideas and approaches. We have chosen problems from different fields to make this short paper attractive to a wide range of specialists.}, author = {Herbert Edelsbrunner and Ivanov, Alexander and Karasev, Roman}, journal = {Automatic Control and Computer Sciences}, publisher = {Springer}, title = {{Open problems in discrete and computational geometry}}, volume = {in print}, year = {2012}, } @inproceedings{2930, abstract = {In this paper we investigate k-submodular functions. This natural family of discrete functions includes submodular and bisubmodular functions as the special cases k = 1 and k = 2 respectively. In particular we generalize the known Min-Max-Theorem for submodular and bisubmodular functions. This theorem asserts that the minimum of the (bi)submodular function can be found by solving a maximization problem over a (bi)submodular polyhedron. We define a k-submodular polyhedron, prove a Min-Max-Theorem for k-submodular functions, and give a greedy algorithm to construct the vertices of the polyhedron. }, author = {Huber, Anna and Kolmogorov, Vladimir}, location = {Athens, Greece}, pages = {451 -- 462}, publisher = {Springer}, title = {{Towards minimizing k-submodular functions}}, doi = {10.1007/978-3-642-32147-4_40}, volume = {7422}, year = {2012}, } @unpublished{2928, abstract = { This paper addresses the problem of approximate MAP-MRF inference in general graphical models. Following [36], we consider a family of linear programming relaxations of the problem where each relaxation is specified by a set of nested pairs of factors for which the marginalization constraint needs to be enforced. We develop a generalization of the TRW-S algorithm [9] for this problem, where we use a decomposition into junction chains, monotonic w.r.t. some ordering on the nodes. This generalizes the monotonic chains in [9] in a natural way. We also show how to deal with nested factors in an efficient way. Experiments show an improvement over min-sum diffusion, MPLP and subgradient ascent algorithms on a number of computer vision and natural language processing problems. }, author = {Kolmogorov, Vladimir and Schoenemann, Thomas}, booktitle = {arXiv}, pages = {16}, publisher = {ArXiv}, title = {{Generalized sequential tree-reweighted message passing}}, year = {2012}, } @techreport{2929, author = {Vladimir Kolmogorov}, publisher = {Unknown}, title = {{The power of linear programming for valued CSPs: a constructive characterization}}, year = {2012}, } @inproceedings{2937, abstract = {Developers building cryptography into security-sensitive applications face a daunting task. Not only must they understand the security guarantees delivered by the constructions they choose, they must also implement and combine them correctly and efficiently. Cryptographic compilers free developers from this task by turning high-level specifications of security goals into efficient implementations. Yet, trusting such tools is hard as they rely on complex mathematical machinery and claim security properties that are subtle and difficult to verify. In this paper we present ZKCrypt, an optimizing cryptographic compiler achieving an unprecedented level of assurance without sacrificing practicality for a comprehensive class of cryptographic protocols, known as Zero-Knowledge Proofs of Knowledge. The pipeline of ZKCrypt integrates purpose-built verified compilers and verifying compilers producing formal proofs in the CertiCrypt framework. By combining the guarantees delivered by each stage, ZKCrypt provides assurance that the output implementation securely realizes the abstract proof goal given as input. We report on the main characteristics of ZKCrypt, highlight new definitions and concepts at its foundations, and illustrate its applicability through a representative example of an anonymous credential system.}, author = {Almeida, José and Barbosa, Manuel and Bangerter, Endre and Barthe, Gilles and Krenn, Stephan and Béguelin, Santiago}, booktitle = {Proceedings of the 2012 ACM conference on Computer and communications security}, location = {Raleigh, NC, USA}, pages = {488 -- 500}, publisher = {ACM}, title = {{Full proof cryptography: Verifiable compilation of efficient zero-knowledge protocols}}, doi = {10.1145/2382196.2382249}, year = {2012}, } @inproceedings{2936, abstract = {The notion of delays arises naturally in many computational models, such as, in the design of circuits, control systems, and dataflow languages. In this work, we introduce automata with delay blocks (ADBs), extending finite state automata with variable time delay blocks, for deferring individual transition output symbols, in a discrete-time setting. We show that the ADB languages strictly subsume the regular languages, and are incomparable in expressive power to the context-free languages. We show that ADBs are closed under union, concatenation and Kleene star, and under intersection with regular languages, but not closed under complementation and intersection with other ADB languages. We show that the emptiness and the membership problems are decidable in polynomial time for ADBs, whereas the universality problem is undecidable. Finally we consider the linear-time model checking problem, i.e., whether the language of an ADB is contained in a regular language, and show that the model checking problem is PSPACE-complete. Copyright 2012 ACM.}, author = {Chatterjee, Krishnendu and Henzinger, Thomas A and Prabhu, Vinayak}, booktitle = {roceedings of the tenth ACM international conference on Embedded software}, location = {Tampere, Finland}, pages = {43 -- 52}, publisher = {ACM}, title = {{Finite automata with time delay blocks}}, doi = {10.1145/2380356.2380370}, year = {2012}, } @article{2938, abstract = {Social insects have a very high potential to become invasive pest species. Here, we explore how their social lifestyle and their interaction with parasites may contribute to this invasive success. Similar to solitary species, parasite release followed by the evolution of increased competitive ability can promote establishment of introduced social insect hosts in their introduced range. Genetic bottlenecks during introduction of low numbers of founder individuals decrease the genetic diversity at three levels: the population, the colony and the individual, with the colony level being specific to social insects. Reduced genetic diversity can affect both the individual immune system and the collective colony-level disease defences (social immunity). Still, the dual immune system is likely to make social insects more robust to parasite attack. Changes in social structure from small, family-based, territorially aggressive societies in native populations towards huge networks of cooperating nests (unicoloniality) occur in some invasive social insects, for example, most invasive ants and some termites. Unicoloniality is likely to affect disease dynamics in multiple ways. The free exchange of individuals within the population leads to an increased genetic heterogeneity among individuals of a single nest, thereby decreasing disease transmission. However, the multitude of reproductively active queens per colony buffers the effect of individual diseased queens and their offspring, which may result in a higher level of vertical disease transmission in unicolonial societies. Lastly, unicoloniality provides a competitive advantage over native species, allowing them to quickly become the dominant species in the habitat, which in turn selects for parasite adaptation to this common host genotype and thus eventually a high parasite pressure. Overall, invasions by insect societies are characterized by general features applying to all introduced species, as well as idiosyncrasies that emerge from their social lifestyle. It is important to study these effects in concert to be able to develop efficient management and biocontrol strategies. © 2012 British Ecological Society.}, author = {Ugelvig, Line V and Cremer, Sylvia}, journal = {Functional Ecology}, number = {6}, pages = {1300 -- 1312}, publisher = {Wiley-Blackwell}, title = {{Effects of social immunity and unicoloniality on host parasite interactions in invasive insect societies}}, doi = {10.1111/1365-2435.12013}, volume = {26}, year = {2012}, } @article{2931, abstract = {In this paper, we present a new approach for establishing correspondences between sparse image features related by an unknown nonrigid mapping and corrupted by clutter and occlusion, such as points extracted from images of different instances of the same object category. We formulate this matching task as an energy minimization problem by defining an elaborate objective function of the appearance and the spatial arrangement of the features. Optimization of this energy is an instance of graph matching, which is in general an NP-hard problem. We describe a novel graph matching optimization technique, which we refer to as dual decomposition (DD), and demonstrate on a variety of examples that this method outperforms existing graph matching algorithms. In the majority of our examples, DD is able to find the global minimum within a minute. The ability to globally optimize the objective allows us to accurately learn the parameters of our matching model from training examples. We show on several matching tasks that our learned model yields results superior to those of state-of-the-art methods. }, author = {Torresani, Lorenzo and Kolmogorov, Vladimir and Rother, Carsten}, journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence}, number = {2}, pages = {259 -- 271}, publisher = {IEEE}, title = {{A dual decomposition approach to feature correspondence}}, doi = {10.1109/TPAMI.2012.105}, volume = {35}, year = {2012}, } @inproceedings{2942, abstract = {Interface theories provide a formal framework for component-based development of software and hardware which supports the incremental design of systems and the independent implementability of components. These capabilities are ensured through mathematical properties of the parallel composition operator and the refinement relation for components. More recently, a conjunction operation was added to interface theories in order to provide support for handling multiple viewpoints, requirements engineering, and component reuse. Unfortunately, the conjunction operator does not allow independent implementability in general. In this paper, we study conditions that need to be imposed on interface models in order to enforce independent implementability with respect to conjunction. We focus on multiple viewpoint specifications and propose a new compatibility criterion between two interfaces, which we call orthogonality. We show that orthogonal interfaces can be refined separately, while preserving both orthogonality and composability with other interfaces. We illustrate the independent implementability of different viewpoints with a FIFO buffer example.}, author = {Henzinger, Thomas A and Nickovic, Dejan}, booktitle = { Conference proceedings Monterey Workshop 2012}, location = {Oxford, UK}, pages = {380 -- 395}, publisher = {Springer}, title = {{Independent implementability of viewpoints}}, doi = {10.1007/978-3-642-34059-8_20}, volume = {7539}, year = {2012}, } @article{2943, abstract = {We examine whether the Escherichia coli chromosome is folded into a self-adherent nucleoprotein complex, or alternately is a confined but otherwise unconstrained self-avoiding polymer. We address this through in vivo visualization, using an inducible GFP fusion to the nucleoid-associated protein Fis to non-specifically decorate the entire chromosome. For a range of different growth conditions, the chromosome is a compact structure that does not fill the volume of the cell, and which moves from the new pole to the cell centre. During rapid growth, chromosome segregation occurs well before cell division, with daughter chromosomes coupled by a thin inter-daughter filament before complete segregation, whereas during slow growth chromosomes stay adjacent until cell division occurs. Image correlation analysis indicates that sub-nucleoid structure is stable on a 1min timescale, comparable to the timescale for redistribution time measured for GFP-Fis after photobleaching. Optical deconvolution and writhe calculation analysis indicate that the nucleoid has a large-scale coiled organization rather than being an amorphous mass. Our observations are consistent with the chromosome having a self-adherent filament organization.}, author = {Hadizadeh Yazdi, Nastaran and Guet, Calin C and Johnson, Reid and Marko, John}, journal = {Molecular Microbiology}, number = {6}, pages = {1318 -- 1333}, publisher = {Wiley-Blackwell}, title = {{Variation of the folding and dynamics of the Escherichia coli chromosome with growth conditions}}, doi = {10.1111/mmi.12071}, volume = {86}, year = {2012}, } @article{2941, author = {Dolbilin, Nikolai and Edelsbrunner, Herbert and Musin, Oleg}, journal = {Russian Mathematical Surveys}, number = {4}, pages = {781 -- 783}, publisher = {IOP Publishing}, title = {{On the optimality of functionals over triangulations of Delaunay sets}}, doi = {10.1070/RM2012v067n04ABEH004807}, volume = {67}, year = {2012}, } @article{2946, abstract = {MicroRNAs (miRNAs) are small noncoding RNAs that function in literally all cellular processes. miRNAs interact with Argonaute (Ago) proteins and guide them to specific target sites located in the 3′-untranslated region (3′-UTR) of target mRNAs leading to translational repression and deadenylation-induced mRNA degradation. Most miRNAs are processed from hairpin-structured precursors by the consecutive action of the RNase III enzymes Drosha and Dicer. However, processing of miR-451 is Dicer independent and cleavage is mediated by the endonuclease Ago2. Here we have characterized miR-451 sequence and structure requirements for processing as well as sorting of miRNAs into different Ago proteins. Pre-miR-451 appears to be optimized for Ago2 cleavage and changes result in reduced processing. In addition, we show that the mature miR-451 only associates with Ago2 suggesting that mature miRNAs are not exchanged between different members of the Ago protein family. Based on cloning and deep sequencing of endogenous miRNAs associated with Ago1-3, we do not find evidence for miRNA sorting in human cells. However, Ago identity appears to influence the length of some miRNAs, while others remain unaffected.}, author = {Dueck, Anne and Ziegler, Christian and Eichner, Alexander and Berezikov, Eugène and Meister, Gunter}, journal = {Nucleic Acids Research}, number = {19}, pages = {9850 -- 9862}, publisher = {Oxford University Press}, title = {{MicroRNAs associated with the different human Argonaute proteins}}, doi = {10.1093/nar/gks705}, volume = {40}, year = {2012}, } @inproceedings{2947, abstract = {We introduce games with probabilistic uncertainty, a model for controller synthesis in which the controller observes the state through imprecise sensors that provide correct information about the current state with a fixed probability. That is, in each step, the sensors return an observed state, and given the observed state, there is a probability distribution (due to the estimation error) over the actual current state. The controller must base its decision on the observed state (rather than the actual current state, which it does not know). On the other hand, we assume that the environment can perfectly observe the current state. We show that controller synthesis for qualitative ω-regular objectives in our model can be reduced in polynomial time to standard partial-observation stochastic games, and vice-versa. As a consequence we establish the precise decidability frontier for the new class of games, and establish optimal complexity results for all the decidable problems.}, author = {Chatterjee, Krishnendu and Chmelik, Martin and Majumdar, Ritankar}, location = {Thiruvananthapuram, India}, pages = {385 -- 399}, publisher = {Springer}, title = {{Equivalence of games with probabilistic uncertainty and partial observation games}}, doi = {10.1007/978-3-642-33386-6_30}, volume = {7561}, year = {2012}, } @article{2945, abstract = {In search of foreign antigens, lymphocytes recirculate from the blood, through lymph nodes, into lymphatics and back to the blood. Dendritic cells also migrate to lymph nodes for optimal interaction with lymphocytes. This continuous trafficking of immune cells into and out of lymph nodes is essential for immune surveillance of foreign invaders. In this article, we review our current understanding of the functions of high endothelial venules (HEVs), stroma and lymphatics in the entry, positioning and exit of immune cells in lymph nodes during homeostasis, and we highlight the unexpected role of dendritic cells in the control of lymphocyte homing through HEVs.}, author = {Girard, Jean and Moussion, Christine and Förster, Reinhold}, journal = {Nature Reviews Immunology}, number = {11}, pages = {762 -- 773}, publisher = {Nature Publishing Group}, title = {{HEVs, lymphatics and homeostatic immune cell trafficking in lymph nodes}}, doi = {10.1038/nri3298}, volume = {12}, year = {2012}, } @article{2949, author = {Dupret, David and Csicsvari, Jozsef L}, journal = {Nature Neuroscience}, number = {11}, pages = {1471 -- 1472}, publisher = {Nature Publishing Group}, title = {{The medial entorhinal cortex keeps Up}}, doi = {10.1038/nn.3245}, volume = {15}, year = {2012}, } @article{2954, abstract = {Spontaneous postsynaptic currents (PSCs) provide key information about the mechanisms of synaptic transmission and the activity modes of neuronal networks. However, detecting spontaneous PSCs in vitro and in vivo has been challenging, because of the small amplitude, the variable kinetics, and the undefined time of generation of these events. Here, we describe a, to our knowledge, new method for detecting spontaneous synaptic events by deconvolution, using a template that approximates the average time course of spontaneous PSCs. A recorded PSC trace is deconvolved from the template, resulting in a series of delta-like functions. The maxima of these delta-like events are reliably detected, revealing the precise onset times of the spontaneous PSCs. Among all detection methods, the deconvolution-based method has a unique temporal resolution, allowing the detection of individual events in high-frequency bursts. Furthermore, the deconvolution-based method has a high amplitude resolution, because deconvolution can substantially increase the signal/noise ratio. When tested against previously published methods using experimental data, the deconvolution-based method was superior for spontaneous PSCs recorded in vivo. Using the high-resolution deconvolution-based detection algorithm, we show that the frequency of spontaneous excitatory postsynaptic currents in dentate gyrus granule cells is 4.5 times higher in vivo than in vitro.}, author = {Pernia-Andrade, Alejandro and Goswami, Sarit and Stickler, Yvonne and Fröbe, Ulrich and Schlögl, Alois and Jonas, Peter M}, journal = {Biophysical Journal}, number = {7}, pages = {1429 -- 1439}, publisher = {Biophysical}, title = {{A deconvolution based method with high sensitivity and temporal resolution for detection of spontaneous synaptic currents in vitro and in vivo}}, doi = {10.1016/j.bpj.2012.08.039}, volume = {103}, year = {2012}, } @article{2950, abstract = {Contractile actomyosin rings drive various fundamental morphogenetic processes ranging from cytokinesis to wound healing. Actomyosin rings are generally thought to function by circumferential contraction. Here, we show that the spreading of the enveloping cell layer (EVL) over the yolk cell during zebrafish gastrulation is driven by a contractile actomyosin ring. In contrast to previous suggestions, we find that this ring functions not only by circumferential contraction but also by a flow-friction mechanism. This generates a pulling force through resistance against retrograde actomyosin flow. EVL spreading proceeds normally in situations where circumferential contraction is unproductive, indicating that the flow-friction mechanism is sufficient. Thus, actomyosin rings can function in epithelial morphogenesis through a combination of cable-constriction and flow-friction mechanisms.}, author = {Behrndt, Martin and Salbreux, Guillaume and Campinho, Pedro and Hauschild, Robert and Oswald, Felix and Roensch, Julia and Grill, Stephan and Heisenberg, Carl-Philipp J}, journal = {Science}, number = {6104}, pages = {257 -- 260}, publisher = {American Association for the Advancement of Science}, title = {{Forces driving epithelial spreading in zebrafish gastrulation}}, doi = {10.1126/science.1224143}, volume = {338}, year = {2012}, } @article{2951, abstract = {Differential cell adhesion and cortex tension are thought to drive cell sorting by controlling cell-cell contact formation. Here, we show that cell adhesion and cortex tension have different mechanical functions in controlling progenitor cell-cell contact formation and sorting during zebrafish gastrulation. Cortex tension controls cell-cell contact expansion by modulating interfacial tension at the contact. By contrast, adhesion has little direct function in contact expansion, but instead is needed to mechanically couple the cortices of adhering cells at their contacts, allowing cortex tension to control contact expansion. The coupling function of adhesion is mediated by E-cadherin and limited by the mechanical anchoring of E-cadherin to the cortex. Thus, cell adhesion provides the mechanical scaffold for cell cortex tension to drive cell sorting during gastrulation.}, author = {Maître, Jean-Léon and Berthoumieux, Hélène and Krens, Gabriel and Salbreux, Guillaume and Julicher, Frank and Paluch, Ewa and Heisenberg, Carl-Philipp J}, journal = {Science}, number = {6104}, pages = {253 -- 256}, publisher = {American Association for the Advancement of Science}, title = {{Adhesion functions in cell sorting by mechanically coupling the cortices of adhering cells}}, doi = {10.1126/science.1225399}, volume = {338}, year = {2012}, } @article{2952, abstract = {Body axis elongation represents a common and fundamental morphogenetic process in development. A key mechanism triggering body axis elongation without additional growth is convergent extension (CE), whereby a tissue undergoes simultaneous narrowing and extension. Both collective cell migration and cell intercalation are thought to drive CE and are used to different degrees in various species as they elongate their body axis. Here, we provide an overview of CE as a general strategy for body axis elongation and discuss conserved and divergent mechanisms underlying CE among different species.}, author = {Tada, Masazumi and Heisenberg, Carl-Philipp J}, journal = {Development}, number = {21}, pages = {3897 -- 3904}, publisher = {Company of Biologists}, title = {{Convergent extension Using collective cell migration and cell intercalation to shape embryos}}, doi = {10.1242/dev.073007}, volume = {139}, year = {2012}, } @article{2953, author = {Heisenberg, Carl-Philipp J and Fässler, Reinhard}, journal = {Current Opinion in Cell Biology}, number = {5}, pages = {559 -- 561}, publisher = {Elsevier}, title = {{Cell-cell adhesion and extracellular matrix diversity counts}}, doi = {10.1016/j.ceb.2012.09.002}, volume = {24}, year = {2012}, } @article{2958, abstract = {The activity of hippocampal pyramidal cells reflects both the current position of the animal and information related to its current behavior. Here we investigated whether single hippocampal neurons can encode several independent features defining trials during a memory task. We also tested whether task-related information is represented by partial remapping of the place cell population or, instead, via firing rate modulation of spatially stable place cells. To address these two questions, the activity of hippocampal neurons was recorded in rats performing a conditional discrimination task on a modified T-maze in which the identity of a food reward guided behavior. When the rat was on the central arm of the maze, the firing rate of pyramidal cells changed depending on two independent factors: (1) the identity of the food reward given to the animal and (2) the previous location of the animal on the maze. Importantly, some pyramidal cells encoded information relative to both factors. This trial-type specific and retrospective coding did not interfere with the spatial representation of the maze: hippocampal cells had stable place fields and their theta-phase precession profiles were unaltered during the task, indicating that trial-related information was encoded via rate remapping. During error trials, encoding of both trial-related information and spatial location was impaired. Finally, we found that pyramidal cells also encode trial-related information via rate remapping during the continuous version of the rewarded alternation task without delays. These results suggest that hippocampal neurons can encode several task-related cognitive aspects via rate remapping.}, author = {Allen, Kevin and Rawlins, J Nick and Bannerman, David and Csicsvari, Jozsef L}, journal = {Journal of Neuroscience}, number = {42}, pages = {14752 -- 14766}, publisher = {Society for Neuroscience}, title = {{Hippocampal place cells can encode multiple trial-dependent features through rate remapping}}, doi = {10.1523/JNEUROSCI.6175-11.2012}, volume = {32}, year = {2012}, } @article{2959, abstract = {We study maximum likelihood estimation in Gaussian graphical models from a geometric point of view. An algebraic elimination criterion allows us to find exact lower bounds on the number of observations needed to ensure that the maximum likelihood estimator (MLE) exists with probability one. This is applied to bipartite graphs, grids and colored graphs. We also study the ML degree, and we present the first instance of a graph for which the MLE exists with probability one, even when the number of observations equals the treewidth.}, author = {Uhler, Caroline}, journal = {Annals of Statistics}, number = {1}, pages = {238 -- 261}, publisher = {Institute of Mathematical Statistics}, title = {{Geometry of maximum likelihood estimation in Gaussian graphical models}}, doi = {10.1214/11-AOS957}, volume = {40}, year = {2012}, } @article{2966, abstract = {Background: The outcome of male-male competition can be predicted from the relative fighting qualities of the opponents, which often depend on their age. In insects, freshly emerged and still sexually inactive males are morphologically indistinct from older, sexually active males. These young inactive males may thus be easy targets for older males if they cannot conceal themselves from their attacks. The ant Cardiocondyla obscurior is characterised by lethal fighting between wingless (" ergatoid" ) males. Here, we analyse for how long young males are defenceless after eclosion, and how early adult males can detect the presence of rival males.Results: We found that old ergatoid males consistently won fights against ergatoid males younger than two days. Old males did not differentiate between different types of unpigmented pupae several days before emergence, but had more frequent contact to ready-to-eclose pupae of female sexuals and winged males than of workers and ergatoid males. In rare cases, old ergatoid males displayed alleviated biting of pigmented ergatoid male pupae shortly before adult eclosion, as well as copulation attempts to dark pupae of female sexuals and winged males. Ergatoid male behaviour may be promoted by a closer similarity of the chemical profile of ready-to-eclose pupae to the profile of adults than that of young pupae several days prior to emergence.Conclusion: Young ergatoid males of C. obscurior would benefit greatly by hiding their identity from older, resident males, as they are highly vulnerable during the first two days of their adult lives. In contrast to the winged males of the same species, which are able to prevent ergatoid male attacks by chemical female mimicry, young ergatoids do not seem to be able to produce a protective chemical profile. Conflicts in male-male competition between ergatoid males of different age thus seem to be resolved in favour of the older males. This might represent selection at the colony level rather than the individual level. © 2012 Cremer et al.; licensee BioMed Central Ltd.}, author = {Cremer, Sylvia and Suefuji, Masaki and Schrempf, Alexandra and Heinze, Jürgen}, journal = {BMC Ecology}, publisher = {BioMed Central}, title = {{The dynamics of male-male competition in Cardiocondyla obscurior ants}}, doi = {10.1186/1472-6785-12-7}, volume = {12}, year = {2012}, } @article{2962, abstract = {The choice of summary statistics is a crucial step in approximate Bayesian computation (ABC). Since statistics are often not sufficient, this choice involves a trade-off between loss of information and reduction of dimensionality. The latter may increase the efficiency of ABC. Here, we propose an approach for choosing summary statistics based on boosting, a technique from the machine learning literature. We consider different types of boosting and compare them to partial least squares regression as an alternative. To mitigate the lack of sufficiency, we also propose an approach for choosing summary statistics locally, in the putative neighborhood of the true parameter value. We study a demographic model motivated by the re-introduction of Alpine ibex (Capra ibex) into the Swiss Alps. The parameters of interest are the mean and standard deviation across microsatellites of the scaled ancestral mutation rate (θanc = 4 Ne u), and the proportion of males obtaining access to matings per breeding season (ω). By simulation, we assess the properties of the posterior distribution obtained with the various methods. According to our criteria, ABC with summary statistics chosen locally via boosting with the L2-loss performs best. Applying that method to the ibex data, we estimate θanc ≈ 1.288, and find that most of the variation across loci of the ancestral mutation rate u is between 7.7×10−4 and 3.5×10−3 per locus per generation. The proportion of males with access to matings is estimated to ω ≈ 0.21, which is in good agreement with recent independent estimates.}, author = {Aeschbacher, Simon and Beaumont, Mark and Futschik, Andreas}, journal = {Genetics}, number = {3}, pages = {1027 -- 1047}, publisher = {Genetics Society of America}, title = {{A novel approach for choosing summary statistics in approximate Bayesian computation}}, doi = {10.1534/genetics.112.143164}, volume = {192}, year = {2012}, } @article{2965, abstract = {Dieser Artikel soll die sechs verschiedenen Creative Commons Lizenzen erläutern und ihre Bedeutung im Rahmen des wissenschaftlichen Publizierens und des Open Access erklären (CC-BY, CC-BY-SA, CC-BY-NC, CC-BY-ND, CC-BYNC-SA, CC-BY-NC-ND).}, author = {Danowski, Patrick}, journal = {Mitteilungen der Vereinigung Österreichischer Bibliothekarinnen & Bibliothekare}, number = {2}, pages = {200 -- 212}, publisher = {VÖB}, title = {{Kontext Open Access: Creative Commons}}, volume = {65}, year = {2012}, } @article{2963, abstract = {Zebra finches are an ubiquitous model system for the study of vocal learning in animal communication. Their song has been well described, but its possible function(s) in social communication are only partly understood. The so-called ‘directed song’ is a high-intensity, high-performance song given during courtship in close proximity to the female, which is known to mediate mate choice and mating. However, this singing mode constitutes only a fraction of zebra finch males’ prolific song output. Potential communicative functions of their second, ‘undirected’ singing mode remain unresolved in the face of contradicting reports of both facilitating and inhibiting effects of social company on singing. We addressed this issue by experimentally manipulating social contexts in a within-subject design, comparing a solo versus male or female only company condition, each lasting for 24 hours. Males’ total song output was significantly higher when a conspecific was in audible and visible distance than when they were alone. Male and female company had an equally facilitating effect on song output. Our findings thus indicate that singing motivation is facilitated rather than inhibited by social company, suggesting that singing in zebra finches might function both in inter- and intrasexual communication. }, author = {Jesse, Fabienne and Riebel, Katharina}, journal = {Behavioural Processes}, number = {3}, pages = {262 -- 266}, publisher = {Elsevier}, title = {{Social facilitation of male song by male and female conspecifics in the zebra finch, Taeniopygia guttata}}, doi = {10.1016/j.beproc.2012.09.006}, volume = {91}, year = {2012}, } @inproceedings{2974, abstract = {We construct a perfectly binding string commitment scheme whose security is based on the learning parity with noise (LPN) assumption, or equivalently, the hardness of decoding random linear codes. Our scheme not only allows for a simple and efficient zero-knowledge proof of knowledge for committed values (essentially a Σ-protocol), but also for such proofs showing any kind of relation amongst committed values, i.e. proving that messages m_0,...,m_u, are such that m_0=C(m_1,...,m_u) for any circuit C. To get soundness which is exponentially small in a security parameter t, and when the zero-knowledge property relies on the LPN problem with secrets of length l, our 3 round protocol has communication complexity O(t|C|l log(l)) and computational complexity of O(t|C|l) bit operations. The hidden constants are small, and the computation consists mostly of computing inner products of bit-vectors.}, author = {Jain, Abhishek and Krenn, Stephan and Pietrzak, Krzysztof Z and Tentes, Aris}, editor = {Wang, Xiaoyun and Sako, Kazue}, location = {Beijing, China}, pages = {663 -- 680}, publisher = {Springer}, title = {{Commitments and efficient zero knowledge proofs from learning parity with noise}}, doi = {10.1007/978-3-642-34961-4_40}, volume = {7658}, year = {2012}, } @article{2969, abstract = {The coupling between presynaptic Ca^(2+) channels and Ca^(2+) sensors of exocytosis is a key determinant of synaptic transmission. Evoked release from parvalbumin (PV)-expressing interneurons is triggered by nanodomain coupling of P/Q-type Ca^(2+) channels, whereas release from cholecystokinin (CCK)-containing interneurons is generated by microdomain coupling of N-type channels. Nanodomain coupling has several functional advantages, including speed and efficacy of transmission. One potential disadvantage is that stochastic opening of presynaptic Ca^(2+) channels may trigger spontaneous transmitter release. We addressed this possibility in rat hippocampal granule cells, which receive converging inputs from different inhibitory sources. Both reduction of extracellular Ca^(2+) concentration and the unselective Ca^(2+) channel blocker Cd^(2+) reduced the frequency of miniature IPSCs (mIPSCs) in granule cells by ~50%, suggesting that the opening of presynaptic Ca^(2+) channels contributes to spontaneous release. Application of the selective P/Q-type Ca^(2+) channel blocker ω-agatoxin IVa had no detectable effects, whereas both the N-type blocker ω-conotoxin GVIa and the L-type blocker nimodipine reduced mIPSC frequency. Furthermore, both the fast Ca^(2+) chelator BAPTA-AM and the slow chelator EGTA-AM reduced the mIPSC frequency, suggesting that Ca^(2+)-dependent spontaneous release is triggered by microdomain rather than nanodomain coupling. The CB_(1) receptor agonist WIN 55212-2 also decreased spontaneous release; this effect was occluded by prior application of ω-conotoxin GVIa, suggesting that a major fraction of Ca^(2+)-dependent spontaneous release was generated at the terminals of CCK-expressing interneurons. Tonic inhibition generated by spontaneous opening of presynaptic N- and L-type Ca^(2+) channels may be important for hippocampal information processing. }, author = {Goswami, Sarit and Bucurenciu, Iancu and Jonas, Peter M}, journal = {Journal of Neuroscience}, number = {41}, pages = {14294 -- 14304}, publisher = {Society for Neuroscience}, title = {{Miniature IPSCs in hippocampal granule cells are triggered by voltage-gated Ca^(2+) channels via microdomain coupling}}, doi = {10.1523/JNEUROSCI.6104-11.2012}, volume = {32}, year = {2012}, } @article{2970, abstract = {Morphogen gradients regulate the patterning and growth of many tissues, hence a key question is how they are established and maintained during development. Theoretical descriptions have helped to explain how gradient shape is controlled by the rates of morphogen production, spreading and degradation. These effective rates have been measured using fluorescence recovery after photobleaching (FRAP) and photoactivation. To unravel which molecular events determine the effective rates, such tissue-level assays have been combined with genetic analysis, high-resolution assays, and models that take into account interactions with receptors, extracellular components and trafficking. Nevertheless, because of the natural and experimental data variability, and the underlying assumptions of transport models, it remains challenging to conclusively distinguish between cellular mechanisms.}, author = {Kicheva, Anna and Bollenbach, Mark Tobias and Wartlick, Ortrud and Julicher, Frank and Gonzalez Gaitan, Marcos}, journal = {Current Opinion in Genetics & Development}, number = {6}, pages = {527 -- 532}, publisher = {Elsevier}, title = {{Investigating the principles of morphogen gradient formation: from tissues to cells}}, doi = {10.1016/j.gde.2012.08.004}, volume = {22}, year = {2012}, } @inproceedings{2971, abstract = {We study the task of interactive semantic labeling of a segmentation hierarchy. To this end we propose a framework interleaving two components: an automatic labeling step, based on a Conditional Random Field whose dependencies are defined by the inclusion tree of the segmentation hierarchy, and an interaction step that integrates incremental input from a human user. Evaluated on two distinct datasets, the proposed interactive approach efficiently integrates human interventions and illustrates the advantages of structured prediction in an interactive framework. }, author = {Zankl, Georg and Haxhimusa, Yll and Ion, Adrian}, location = {Graz, Austria}, pages = {11 -- 20}, publisher = {Springer}, title = {{Interactive labeling of image segmentation hierarchies}}, doi = {10.1007/978-3-642-32717-9_2}, volume = {7476}, year = {2012}, } @article{3105, abstract = {Growth and development are coordinated by an array of intercellular communications. Known plant signaling molecules include phytohormones and hormone peptides. Although both classes can be implicated in the same developmental processes, little is known about the interplay between phytohormone action and peptide signaling within the cellular microenvironment. We show that genes coding for small secretory peptides, designated GOLVEN (GLV), modulate the distribution of the phytohormone auxin. The deregulation of the GLV function impairs the formation of auxin gradients and alters the reorientation of shoots and roots after a gravity stimulus. Specifically, the GLV signal modulates the trafficking dynamics of the auxin efflux carrier PIN-FORMED2 involved in root tropic responses and meristem organization. Our work links the local action of secretory peptides with phytohormone transport. Root growth factor (RGF) or GOLVEN (GLV) secreted peptides have previously been implicated in meristem regulation. Whitford et al. now show that RGF/GLV peptides induce rapid relocalization of the auxin efflux regulator PIN2, regulate auxin gradients, and modulate auxin-dependent root responses to specific stimuli.}, author = {Whitford, Ryan and Fernandez, Ana and Tejos, Ricardo and Pérez, Amparo Cuéllar and Kleine-Vehn, Jürgen and Vanneste, Steffen and Drozdzecki, Andrzej and Leitner, Johannes and Abas, Lindy and Aerts, Maarten and Hoogewijs, Kurt and Pawel Baster and De Groodt, Ruth and Lin, Yao-Cheng and Storme, Véronique and Van de Peer, Yves and Beeckman, Tom and Madder, Annemieke and Devreese, Bart and Luschnig, Christian and Jirí Friml and Hilson, Pierre}, journal = {Developmental Cell}, number = {3}, pages = {678 -- 685}, publisher = {Cell Press}, title = {{GOLVEN secretory peptides regulate auxin carrier turnover during plant gravitropic responses}}, doi = {10.1016/j.devcel.2012.02.002}, volume = {22}, year = {2012}, } @article{3109, abstract = {Receptor-mediated endocytosis is an integral part of signal transduction as it mediates signal attenuation and provides spatial and temporal dimensions to signaling events. One of the best-studied leucine-rich repeat receptor-like kinases in plants, BRASSINOSTEROID INSENSITIVE 1 (BRI1), perceives its ligand, the brassinosteroid (BR) hormone, at the cell surface and is constitutively endocytosed. However, the importance of endocytosis for BR signaling remains unclear. Here we developed a bioactive, fluorescent BR analog, Alexa Fluor 647-castasterone (AFCS), and visualized the endocytosis of BRI1-AFCS complexes in living Arabidopsis thaliana cells. Impairment of endocytosis dependent on clathrin and the guanine nucleotide exchange factor for ARF GTPases (ARF-GEF) GNOM enhanced BR signaling by retaining active BRI1-ligand complexes at the plasma membrane. Increasing the trans-Golgi network/early endosome pool of BRI1-BR complexes did not affect BR signaling. Our findings provide what is to our knowledge the first visualization of receptor-ligand complexes in plants and reveal clathrin-and ARF-GEF-dependent endocytic regulation of BR signaling from the plasma membrane.}, author = {Irani, Niloufer G and Di Rubbo, Simone and Mylle, Evelien and Van Den Begin, Jos and Schneider-Pizoń, Joanna and Hniliková, Jaroslava and Šíša, Miroslav and Buyst, Dieter and Vilarrasa-Blasi, Josep and Szatmári, Anna-Maria and Van Damme, Daniël and Mishev, Kiril and Codreanu, Mirela-Corina and Kohout, Ladislav and Strnad, Miroslav and Caño-Delgado, Ana I and Jirí Friml and Madder, Annemieke and Russinova, Eugenia}, journal = {Nature Chemical Biology}, number = {6}, pages = {583 -- 589}, publisher = {Nature Publishing Group}, title = {{Fluorescent castasterone reveals BRI1 signaling from the plasma membrane}}, doi = {10.1038/nchembio.958}, volume = {8}, year = {2012}, } @article{3104, abstract = { Gradients of the plant hormone auxin, which depend on its active intercellular transport, are crucial for the maintenance of root meristematic activity. This directional transport is largely orchestrated by a complex interaction of specific influx and efflux carriers that mediate the auxin flow into and out of cells, respectively. Besides these transport proteins, plant-specific polyphenolic compounds knownasflavonols have beenshownto act as endogenous regulators of auxin transport. However, only limited information is available on how flavonol synthesis is developmentally regulated. Using reduction-of-function and overexpression approaches in parallel, we demonstrate that the WRKY23 transcription factor is needed for proper root growth and development by stimulating the local biosynthesis of flavonols. The expression of WRKY23 itself is controlled by auxin through the AUXIN RESPONSE FACTOR 7 (ARF7) and ARF19 transcriptional response pathway. Our results suggest a model in which WRKY23 is part of a transcriptional feedback loop of auxin on its own transport through local regulation of flavonol biosynthesis.}, author = {Grunewald, Wim and De Smet, Ive and Lewis, Daniel R and Löfke, Christian and Jansen, Leentje and Goeminne, Geert and Vanden Bossche, Robin and Karimi, Mansour and De Rybel, Bert and Vanholme, Bartel and Teichmann, Thomas and Boerjan, Wout and Van Montagu, Marc C and Gheysen, Godelieve and Muday, Gloria K and Jirí Friml and Beeckman, Tom}, journal = {PNAS}, number = {5}, pages = {1554 -- 1559}, publisher = {National Academy of Sciences}, title = {{Transcription factor WRKY23 assists auxin distribution patterns during Arabidopsis root development through local control on flavonol biosynthesis}}, doi = {10.1073/pnas.1121134109}, volume = {109}, year = {2012}, } @article{3108, abstract = {The phytohormone auxin acts as a prominent signal, providing, by its local accumulation or depletion in selected cells, a spatial and temporal reference for changes in the developmental program. The distribution of auxin depends on both auxin metabolism (biosynthesis, conjugation and degradation) and cellular auxin transport. We identified in silico a novel putative auxin transport facilitator family, called PIN-LIKES (PILS). Here we illustrate that PILS proteins are required for auxin-dependent regulation of plant growth by determining the cellular sensitivity to auxin. PILS proteins regulate intracellular auxin accumulation at the endoplasmic reticulum and thus auxin availability for nuclear auxin signalling. PILS activity affects the level of endogenous auxin indole-3-acetic acid (IAA), presumably via intracellular accumulation and metabolism. Our findings reveal that the transport machinery to compartmentalize auxin within the cell is of an unexpected molecular complexity and demonstrate this compartmentalization to be functionally important for a number of developmental processes.}, author = {Barbez, Elke and Kubeš, Martin and Rolčík, Jakub and Béziat, Chloe and Pěnčík, Aleš and Wang, Bangjun and Rosquete, Michel Ruiz and Zhu, Jinsheng and Dobrev, Petre I and Lee, Yuree and Zašímalová, Eva and Petrášek, Jan and Geisler, Markus and Jirí Friml and Kleine-Vehn, Jürgen}, journal = {Nature}, number = {7396}, pages = {119 -- 122}, publisher = {Nature Publishing Group}, title = {{A novel putative auxin carrier family regulates intracellular auxin homeostasis in plants}}, doi = {10.1038/nature11001}, volume = {485}, year = {2012}, } @article{3106, abstract = {Cell polarization via asymmetrical distribution of structures or molecules is essential for diverse cellular functions and development of organisms, but how polarity is developmentally controlled has been poorly understood. In plants, the asymmetrical distribution of the PIN-FORMED (PIN) proteins involved in the cellular efflux of the quintessential phytohormone auxin plays a central role in developmental patterning, morphogenesis, and differential growth. Recently we showed that auxin promotes cell interdigitation by activating the Rho family ROP GTPases in leaf epidermal pavement cells. Here we found that auxin activation of the ROP2 signaling pathway regulates the asymmetric distribution of PIN1 by inhibiting its endocytosis. ROP2 inhibits PIN1 endocytosis via the accumulation of cortical actin microfilaments induced by the ROP2 effector protein RIC4. Our findings suggest a link between the developmental auxin signal and polar PIN1 distribution via Rho-dependent cytoskeletal reorganization and reveal the conservation of a design principle for cell polarization that is based on Rho GTPase-mediated inhibition of endocytosis.}, author = {Nagawa, Shingo and Xu, Tongda and Lin, Deshu and Dhonukshe, Pankaj and Zhang, Xingxing and Jirí Friml and Scheres, Ben and Fu, Ying and Yang, Zhenbiao}, journal = {PLoS Biology}, number = {4}, publisher = {Public Library of Science}, title = {{ROP GTPase-dependent actin microfilaments promote PIN1 polarization by localized inhibition of clathrin-dependent endocytosis}}, doi = {10.1371/journal.pbio.1001299}, volume = {10}, year = {2012}, } @misc{3107, author = {Vanneste, Steffen and Friml, Jirí}, booktitle = {Nature Chemical Biology}, number = {5}, pages = {415 -- 416}, publisher = {Nature Publishing Group}, title = {{Plant signaling: Deconstructing auxin sensing}}, doi = {10.1038/nchembio.943}, volume = {8}, year = {2012}, } @inproceedings{3119, abstract = {We present an approach for artist-directed animation of liquids using multiple levels of control over the simulation, ranging from the overall tracking of desired shapes to highly detailed secondary effects such as dripping streams, separating sheets of fluid, surface waves and ripples. The first portion of our technique is a volume preserving morph that allows the animator to produce a plausible fluid-like motion from a sparse set of control meshes. By rasterizing the resulting control meshes onto the simulation grid, the mesh velocities act as boundary conditions during the projection step of the fluid simulation. We can then blend this motion together with uncontrolled fluid velocities to achieve a more relaxed control over the fluid that captures natural inertial effects. Our method can produce highly detailed liquid surfaces with control over sub-grid details by using a mesh-based surface tracker on top of a coarse grid-based fluid simulation. We can create ripples and waves on the fluid surface attracting the surface mesh to the control mesh with spring-like forces and also by running a wave simulation over the surface mesh. Our video results demonstrate how our control scheme can be used to create animated characters and shapes that are made of water. }, author = {Raveendran, Karthik and Thuerey, Nils and Wojtan, Christopher J and Turk, Greg}, booktitle = {Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation}, location = {Aire-la-Ville, Switzerland}, pages = {255 -- 264}, publisher = {ACM}, title = {{Controlling liquids using meshes}}, year = {2012}, } @article{3118, abstract = {We present a method for recovering a temporally coherent, deforming triangle mesh with arbitrarily changing topology from an incoherent sequence of static closed surfaces. We solve this problem using the surface geometry alone, without any prior information like surface templates or velocity fields. Our system combines a proven strategy for triangle mesh improvement, a robust multi-resolution non-rigid registration routine, and a reliable technique for changing surface mesh topology. We also introduce a novel topological constraint enforcement algorithm to ensure that the output and input always have similar topology. We apply our technique to a series of diverse input data from video reconstructions, physics simulations, and artistic morphs. The structured output of our algorithm allows us to efficiently track information like colors and displacement maps, recover velocity information, and solve PDEs on the mesh as a post process.}, author = {Bojsen-Hansen, Morten and Li, Hao and Wojtan, Christopher J}, journal = {ACM Transactions on Graphics}, number = {4}, publisher = {ACM}, title = {{Tracking surfaces with evolving topology}}, doi = {10.1145/2185520.2185549}, volume = {31}, year = {2012}, } @article{3122, abstract = {Since Darwin's pioneering research on plant reproductive biology (e.g. Darwin 1877), understanding the mechanisms maintaining the diverse sexual strategies of plants has remained an important challenge for evolutionary biologists. In some species, populations are sexually polymorphic and contain two or more mating morphs (sex phenotypes). Differences in morphology or phenology among the morphs influence patterns of non-random mating. In these populations, negative frequency-dependent selection arising from disassortative (intermorph) mating is usually required for the evolutionary maintenance of sexual polymorphism, but few studies have demonstrated the required patterns of non-random mating. In the current issue of Molecular Ecology, Shang (2012) make an important contribution to our understanding of how disassortative mating influences sex phenotype ratios in Acer pictum subsp. mono (painted maple), a heterodichogamous, deciduous tree of eastern China. They monitored sex expression in 97 adults and used paternity analysis of open-pollinated seed to examine disassortative mating among three sex phenotypes. Using a deterministic 'pollen transfer' model, Shang et al. present convincing evidence that differences in the degree of disassortative mating in progeny arrays of the sex phenotypes can explain their uneven frequencies in the adult population. This study provides a useful example of how the deployment of genetic markers, demographic monitoring and modelling can be integrated to investigate the maintenance of sexual diversity in plants. }, author = {Field, David and Barrett, Spencer}, journal = {Molecular Ecology}, number = {15}, pages = {3640 -- 3643}, publisher = {Wiley-Blackwell}, title = {{Disassortative mating and the maintenance of sexual polymorphism in painted maple}}, doi = {10.1111/j.1365-294X.2012.05643.x}, volume = {21}, year = {2012}, } @article{3121, abstract = {Voltage-activated Ca(2+) channels (VACCs) mediate Ca(2+) influx to trigger action potential-evoked neurotransmitter release, but the mechanism by which Ca(2+) regulates spontaneous transmission is unclear. We found that VACCs are the major physiological triggers for spontaneous release at mouse neocortical inhibitory synapses. Moreover, despite the absence of a synchronizing action potential, we found that spontaneous fusion of a GABA-containing vesicle required the activation of multiple tightly coupled VACCs of variable type.}, author = {Williams, Courtney and Chen, Wenyan and Lee, Chia and Yaeger, Daniel and Vyleta, Nicholas and Smith, Stephen}, journal = {Nature Neuroscience}, number = {9}, pages = {1195 -- 1197}, publisher = {Nature Publishing Group}, title = {{Coactivation of multiple tightly coupled calcium channels triggers spontaneous release of GABA}}, doi = {10.1038/nn.3162}, volume = {15}, year = {2012}, } @article{3120, abstract = {We introduce a strategy based on Kustin-Miller unprojection that allows us to construct many hundreds of Gorenstein codimension 4 ideals with 9 × 16 resolutions (that is, nine equations and sixteen first syzygies). Our two basic games are called Tom and Jerry; the main application is the biregular construction of most of the anticanonically polarised Mori Fano 3-folds of Altinok's thesis. There are 115 cases whose numerical data (in effect, the Hilbert series) allow a Type I projection. In every case, at least one Tom and one Jerry construction works, providing at least two deformation families of quasismooth Fano 3-folds having the same numerics but different topology. © 2012 Copyright Foundation Compositio Mathematica.}, author = {Brown, Gavin and Kerber, Michael and Reid, Miles}, journal = {Compositio Mathematica}, number = {4}, pages = {1171 -- 1194}, publisher = {Cambridge University Press}, title = {{Fano 3 folds in codimension 4 Tom and Jerry Part I}}, doi = {10.1112/S0010437X11007226}, volume = {148}, year = {2012}, } @article{3117, abstract = {We consider the problem of minimizing a function represented as a sum of submodular terms. We assume each term allows an efficient computation of exchange capacities. This holds, for example, for terms depending on a small number of variables, or for certain cardinality-dependent terms. A naive application of submodular minimization algorithms would not exploit the existence of specialized exchange capacity subroutines for individual terms. To overcome this, we cast the problem as a submodular flow (SF) problem in an auxiliary graph in such a way that applying most existing SF algorithms would rely only on these subroutines. We then explore in more detail Iwata's capacity scaling approach for submodular flows (Iwata 1997 [19]). In particular, we show how to improve its complexity in the case when the function contains cardinality-dependent terms.}, author = {Kolmogorov, Vladimir}, journal = {Discrete Applied Mathematics}, number = {15}, pages = {2246 -- 2258}, publisher = {Elsevier}, title = {{Minimizing a sum of submodular functions}}, doi = {10.1016/j.dam.2012.05.025}, volume = {160}, year = {2012}, } @article{3131, abstract = {In large populations, many beneficial mutations may be simultaneously available and may compete with one another, slowing adaptation. By finding the probability of fixation of a favorable allele in a simple model of a haploid sexual population, we find limits to the rate of adaptive substitution, Λ, that depend on simple parameter combinations. When variance in fitness is low and linkage is loose, the baseline rate of substitution is Λ 0=2NU〈s〉 is the population size, U is the rate of beneficial mutations per genome, and 〈s〉 is their mean selective advantage. Heritable variance ν in log fitness due to unlinked loci reduces Λ by e -4ν under polygamy and e -8ν under monogamy. With a linear genetic map of length R Morgans, interference is yet stronger. We use a scaling argument to show that the density of adaptive substitutions depends on s, N, U, and R only through the baseline density: Λ/R=F(Λ 0/R). Under the approximation that the interference due to different sweeps adds up, we show that Λ/R~(Λ 0/R)/(1+2Λ 0/R), implying that interference prevents the rate of adaptive substitution from exceeding one per centimorgan per 200 generations. Simulations and numerical calculations confirm the scaling argument and confirm the additive approximation for Λ 0/R 1; for higher Λ 0/R, the rate of adaptation grows above R/2, but only very slowly. We also consider the effect of sweeps on neutral diversity and show that, while even occasional sweeps can greatly reduce neutral diversity, this effect saturates as sweeps become more common-diversity can be maintained even in populations experiencing very strong interference. Our results indicate that for some organisms the rate of adaptive substitution may be primarily recombination-limited, depending only weakly on the mutation supply and the strength of selection.}, author = {Weissman, Daniel and Barton, Nicholas H}, journal = {PLoS Genetics}, number = {6}, publisher = {Public Library of Science}, title = {{Limits to the rate of adaptive substitution in sexual populations}}, doi = {10.1371/journal.pgen.1002740}, volume = {8}, year = {2012}, } @article{3130, abstract = {Essential genes code for fundamental cellular functions required for the viability of an organism. For this reason, essential genes are often highly conserved across organisms. However, this is not always the case: orthologues of genes that are essential in one organism are sometimes not essential in other organisms or are absent from their genomes. This suggests that, in the course of evolution, essential genes can be rendered nonessential. How can a gene become non-essential? Here we used genetic manipulation to deplete the products of 26 different essential genes in Escherichia coli. This depletion results in a lethal phenotype, which could often be rescued by the overexpression of a non-homologous, non-essential gene, most likely through replacement of the essential function. We also show that, in a smaller number of cases, the essential genes can be fully deleted from the genome, suggesting that complete functional replacement is possible. Finally, we show that essential genes whose function can be replaced in the laboratory are more likely to be non-essential or not present in other taxa. These results are consistent with the notion that patterns of evolutionary conservation of essential genes are influenced by their compensability-that is, by how easily they can be functionally replaced, for example through increased expression of other genes.}, author = {Bergmiller, Tobias and Ackermann, Martin and Silander, Olin}, journal = {PLoS Genetics}, number = {6}, publisher = {Public Library of Science}, title = {{Patterns of evolutionary conservation of essential genes correlate with their compensability}}, doi = {10.1371/journal.pgen.1002803}, volume = {8}, year = {2012}, } @inproceedings{3136, abstract = {Continuous-time Markov chains (CTMC) with their rich theory and efficient simulation algorithms have been successfully used in modeling stochastic processes in diverse areas such as computer science, physics, and biology. However, systems that comprise non-instantaneous events cannot be accurately and efficiently modeled with CTMCs. In this paper we define delayed CTMCs, an extension of CTMCs that allows for the specification of a lower bound on the time interval between an event's initiation and its completion, and we propose an algorithm for the computation of their behavior. Our algorithm effectively decomposes the computation into two stages: a pure CTMC governs event initiations while a deterministic process guarantees lower bounds on event completion times. Furthermore, from the nature of delayed CTMCs, we obtain a parallelized version of our algorithm. We use our formalism to model genetic regulatory circuits (biological systems where delayed events are common) and report on the results of our numerical algorithm as run on a cluster. We compare performance and accuracy of our results with results obtained by using pure CTMCs. © 2012 Springer-Verlag.}, author = {Guet, Calin C and Gupta, Ashutosh and Henzinger, Thomas A and Mateescu, Maria and Sezgin, Ali}, location = {Berkeley, CA, USA}, pages = {294 -- 309}, publisher = {Springer}, title = {{Delayed continuous time Markov chains for genetic regulatory circuits}}, doi = {10.1007/978-3-642-31424-7_24}, volume = {7358 }, year = {2012}, } @inproceedings{3135, abstract = {We introduce consumption games, a model for discrete interactive system with multiple resources that are consumed or reloaded independently. More precisely, a consumption game is a finite-state graph where each transition is labeled by a vector of resource updates, where every update is a non-positive number or ω. The ω updates model the reloading of a given resource. Each vertex belongs either to player □ or player ◇, where the aim of player □ is to play so that the resources are never exhausted. We consider several natural algorithmic problems about consumption games, and show that although these problems are computationally hard in general, they are solvable in polynomial time for every fixed number of resource types (i.e., the dimension of the update vectors) and bounded resource updates. }, author = {Brázdil, Brázdil and Chatterjee, Krishnendu and Kučera, Antonín and Novotny, Petr}, location = {Berkeley, CA, USA}, pages = {23 -- 38}, publisher = {Springer}, title = {{Efficient controller synthesis for consumption games with multiple resource types}}, doi = {10.1007/978-3-642-31424-7_8}, volume = {7358}, year = {2012}, } @inproceedings{3133, abstract = {This note contributes to the point calculus of persistent homology by extending Alexander duality from spaces to real-valued functions. Given a perfect Morse function f: S n+1 →[0, 1 and a decomposition S n+1 = U ∪ V into two (n + 1)-manifolds with common boundary M, we prove elementary relationships between the persistence diagrams of f restricted to U, to V, and to M. }, author = {Edelsbrunner, Herbert and Kerber, Michael}, booktitle = {Proceedings of the twenty-eighth annual symposium on Computational geometry }, location = {Chapel Hill, NC, USA}, pages = {249 -- 258}, publisher = {ACM}, title = {{Alexander duality for functions: The persistent behavior of land and water and shore}}, doi = {10.1145/2261250.2261287}, year = {2012}, } @inproceedings{3134, abstract = {It has been an open question whether the sum of finitely many isotropic Gaussian kernels in n ≥ 2 dimensions can have more modes than kernels, until in 2003 Carreira-Perpiñán and Williams exhibited n +1 isotropic Gaussian kernels in ℝ n with n + 2 modes. We give a detailed analysis of this example, showing that it has exponentially many critical points and that the resilience of the extra mode grows like √n. In addition, we exhibit finite configurations of isotropic Gaussian kernels with superlinearly many modes. }, author = {Edelsbrunner, Herbert and Fasy, Brittany and Rote, Günter}, booktitle = {Proceedings of the twenty-eighth annual symposium on Computational geometry }, location = {Chapel Hill, NC, USA}, pages = {91 -- 100}, publisher = {ACM}, title = {{Add isotropic Gaussian kernels at own risk: More and more resilient modes in higher dimensions}}, doi = {10.1145/2261250.2261265}, year = {2012}, } @article{3132, abstract = {Reproductive division of labour is a characteristic trait of social insects. The dominant reproductive individual, often the queen, uses chemical communication and/or behaviour to maintain her social status. Queens of many social insects communicate their fertility status via cuticle-bound substances. As these substances usually possess a low volatility, their range in queen–worker communication is potentially limited. Here, we investigate the range and impact of behavioural and chemical queen signals on workers of the ant Temnothorax longispinosus. We compared the behaviour and ovary development of workers subjected to three different treatments: workers with direct chemical and physical contact to the queen, those solely under the influence of volatile queen substances and those entirely separated from the queen. In addition to short-ranged queen signals preventing ovary development in workers, we discovered a novel secondary pathway influencing worker behaviour. Workers with no physical contact to the queen, but exposed to volatile substances, started to develop their ovaries, but did not change their behaviour compared to workers in direct contact to the queen. In contrast, workers in queen-separated groups showed both increased ovary development and aggressive dominance interactions. We conclude that T. longispinosus queens influence worker ovary development and behaviour via two independent signals, both ensuring social harmony within the colony.}, author = {Konrad, Matthias and Pamminger, Tobias and Foitzik, Susanne}, journal = {Naturwissenschaften}, number = {8}, pages = {627 -- 636}, publisher = {Springer}, title = {{Two pathways ensuring social harmony}}, doi = {10.1007/s00114-012-0943-z}, volume = {99}, year = {2012}, } @article{3161, abstract = {Some inflammatory stimuli trigger activation of the NLRP3 inflammasome by inducing efflux of cellular potassium. Loss of cellular potassium is known to potently suppress protein synthesis, leading us to test whether the inhibition of protein synthesis itself serves as an activating signal for the NLRP3 inflammasome. Murine bone marrow-derived macrophages, either primed by LPS or unprimed, were exposed to a panel of inhibitors of ribosomal function: ricin, cycloheximide, puromycin, pactamycin, and anisomycin. Macrophages were also exposed to nigericin, ATP, monosodium urate (MSU), and poly I:C. Synthesis of pro-IL-ß and release of IL-1ß from cells in response to these agents was detected by immunoblotting and ELISA. Release of intracellular potassium was measured by mass spectrometry. Inhibition of translation by each of the tested translation inhibitors led to processing of IL-1ß, which was released from cells. Processing and release of IL-1ß was reduced or absent from cells deficient in NLRP3, ASC, or caspase-1, demonstrating the role of the NLRP3 inflammasome. Despite the inability of these inhibitors to trigger efflux of intracellular potassium, the addition of high extracellular potassium suppressed activation of the NLRP3 inflammasome. MSU and double-stranded RNA, which are known to activate the NLRP3 inflammasome, also substantially inhibited protein translation, supporting a close association between inhibition of translation and inflammasome activation. These data demonstrate that translational inhibition itself constitutes a heretofore-unrecognized mechanism underlying IL-1ß dependent inflammatory signaling and that other physical, chemical, or pathogen-associated agents that impair translation may lead to IL-1ß-dependent inflammation through activation of the NLRP3 inflammasome. For agents that inhibit translation through decreased cellular potassium, the application of high extracellular potassium restores protein translation and suppresses activation of the NLRP inflammasome. For agents that inhibit translation through mechanisms that do not involve loss of potassium, high extracellular potassium suppresses IL-1ß processing through a mechanism that remains undefined.}, author = {Vyleta, Meghan and Wong, John and Magun, Bruce}, journal = {PLoS One}, number = {5}, publisher = {Public Library of Science}, title = {{Suppression of ribosomal function triggers innate immune signaling through activation of the NLRP3 inflammasome}}, doi = {10.1371/journal.pone.0036044}, volume = {7}, year = {2012}, }