TY - CONF AB - We introduce a new class of functions that can be minimized in polynomial time in the value oracle model. These are functions f satisfying f(x) + f(y) ≥ f(x ∏ y) + f(x ∐ y) where the domain of each variable x i corresponds to nodes of a rooted binary tree, and operations ∏,∐ are defined with respect to this tree. Special cases include previously studied L-convex and bisubmodular functions, which can be obtained with particular choices of trees. We present a polynomial-time algorithm for minimizing functions in the new class. It combines Murota's steepest descent algorithm for L-convex functions with bisubmodular minimization algorithms. AU - Vladimir Kolmogorov ID - 3204 TI - Submodularity on a tree: Unifying Submodularity on a tree: Unifying L-convex and bisubmodular functions convex and bisubmodular functions VL - 6907 ER - TY - CONF AB - In this paper we address the problem of finding the most probable state of discrete Markov random field (MRF) with associative pairwise terms. Although of practical importance, this problem is known to be NP-hard in general. We propose a new type of MRF decomposition, submod-ular decomposition (SMD). Unlike existing decomposition approaches SMD decomposes the initial problem into sub-problems corresponding to a specific class label while preserving the graph structure of each subproblem. Such decomposition enables us to take into account several types of global constraints in an efficient manner. We study theoretical properties of the proposed approach and demonstrate its applicability on a number of problems. AU - Osokin, Anton AU - Vetrov, Dmitry AU - Vladimir Kolmogorov ID - 3206 TI - Submodular decomposition framework for inference in associative Markov networks with global constraints ER - TY - CONF AB - This paper proposes a novel Linear Programming (LP) based algorithm, called Dynamic Tree-Block Coordinate Ascent (DT-BCA), for performing maximum a posteriori (MAP) inference in probabilistic graphical models. Unlike traditional message passing algorithms, which operate uniformly on the whole factor graph, our method dynamically chooses regions of the factor graph on which to focus message-passing efforts. We propose two criteria for selecting regions, including an efficiently computable upper-bound on the increase in the objective possible by passing messages in any particular region. This bound is derived from the theory of primal-dual methods from combinatorial optimization, and the forest that maximizes the bounds can be chosen efficiently using a maximum-spanning-tree-like algorithm. Experimental results show that our dynamic schedules significantly speed up state-of-the-art LP-based message-passing algorithms on a wide variety of real-world problems. AU - Tarlow, Daniel AU - Batra, Druv AU - Kohli, Pushmeet AU - Vladimir Kolmogorov ID - 3205 TI - Dynamic tree block coordinate ascent ER - TY - CONF AB - Cosegmentation is typically defined as the task of jointly segmenting something similar in a given set of images. Existing methods are too generic and so far have not demonstrated competitive results for any specific task. In this paper we overcome this limitation by adding two new aspects to cosegmentation: (1) the "something" has to be an object, and (2) the "similarity" measure is learned. In this way, we are able to achieve excellent results on the recently introduced iCoseg dataset, which contains small sets of images of either the same object instance or similar objects of the same class. The challenge of this dataset lies in the extreme changes in viewpoint, lighting, and object deformations within each set. We are able to considerably outperform several competitors. To achieve this performance, we borrow recent ideas from object recognition: the use of powerful features extracted from a pool of candidate object-like segmentations. We believe that our work will be beneficial to several application areas, such as image retrieval. AU - Vicente, Sara AU - Rother, Carsten AU - Vladimir Kolmogorov ID - 3207 TI - Object cosegmentation ER - TY - CONF AB - The famous Leftover Hash Lemma (LHL) states that (almost) universal hash functions are good randomness extractors. Despite its numerous applications, LHL-based extractors suffer from the following two limitations: - Large Entropy Loss: to extract v bits from distribution X of min-entropy m which are ε-close to uniform, one must set v ≤ m - 2log(1/ε), meaning that the entropy loss L = def m - v ≥ 2 log(1/ε). For many applications, such entropy loss is too large. - Large Seed Length: the seed length n of (almost) universal hash function required by the LHL must be at least n ≥ min (u - v, v + 2log(1/ε)) - O(1), where u is the length of the source, and must grow with the number of extracted bits. Quite surprisingly, we show that both limitations of the LHL - large entropy loss and large seed - can be overcome (or, at least, mitigated) in various important scenarios. First, we show that entropy loss could be reduced to L = log(1/ε) for the setting of deriving secret keys for a wide range of cryptographic applications. Specifically, the security of these schemes with an LHL-derived key gracefully degrades from ε to at most ε + √ε2-L. (Notice that, unlike standard LHL, this bound is meaningful even when one extracts more bits than the min-entropy we have!) Based on these results we build a general computational extractor that enjoys low entropy loss and can be used to instantiate a generic key derivation function for any cryptographic application. Second, we study the soundness of the natural expand-then-extract approach, where one uses a pseudorandom generator (PRG) to expand a short "input seed" S into a longer "output seed" S′, and then use the resulting S′ as the seed required by the LHL (or, more generally, by any randomness extractor). We show that, in general, the expand-then-extract approach is not sound if the Decisional Diffie-Hellman assumption is true. Despite that, we show that it is sound either: (1) when extracting a "small" (logarithmic in the security of the PRG) number of bits; or (2) in minicrypt. Implication (2) suggests that the expand-then-extract approach is likely secure when used with "practical" PRGs, despite lacking a reductionist proof of security! © 2011 International Association for Cryptologic Research. AU - Barak, Boaz AU - Dodis, Yevgeniy AU - Krawczyk, Hugo AU - Pereira, Olivier AU - Krzysztof Pietrzak AU - Standaert, François-Xavier AU - Yu, Yu ID - 3240 TI - Leftover hash lemma revisited VL - 6841 ER - TY - CONF AB - Verification of programs with procedures, multi-threaded programs, and higher-order functional programs can be effectively au- tomated using abstraction and refinement schemes that rely on spurious counterexamples for abstraction discovery. The analysis of counterexam- ples can be automated by a series of interpolation queries, or, alterna- tively, as a constraint solving query expressed by a set of recursion free Horn clauses. (A set of interpolation queries can be formulated as a single constraint over Horn clauses with linear dependency structure between the unknown relations.) In this paper we present an algorithm for solving recursion free Horn clauses over a combined theory of linear real/rational arithmetic and uninterpreted functions. Our algorithm performs resolu- tion to deal with the clausal structure and relies on partial solutions to deal with (non-local) instances of functionality axioms. AU - Gupta, Ashutosh AU - Popeea, Corneliu AU - Rybalchenko, Andrey ED - Yang, Hongseok ID - 3264 TI - Solving recursion-free Horn clauses over LI+UIF VL - 7078 ER - TY - CONF AB - We present a joint image segmentation and labeling model (JSL) which, given a bag of figure-ground segment hypotheses extracted at multiple image locations and scales, constructs a joint probability distribution over both the compatible image interpretations (tilings or image segmentations) composed from those segments, and over their labeling into categories. The process of drawing samples from the joint distribution can be interpreted as first sampling tilings, modeled as maximal cliques, from a graph connecting spatially non-overlapping segments in the bag [1], followed by sampling labels for those segments, conditioned on the choice of a particular tiling. We learn the segmentation and labeling parameters jointly, based on Maximum Likelihood with a novel Incremental Saddle Point estimation procedure. The partition function over tilings and labelings is increasingly more accurately approximated by including incorrect configurations that a not-yet-competent model rates probable during learning. We show that the proposed methodologymatches the current state of the art in the Stanford dataset [2], as well as in VOC2010, where 41.7% accuracy on the test set is achieved. AU - Ion, Adrian AU - Carreira, Joao AU - Sminchisescu, Cristian ID - 3266 T2 - NIPS Proceedings TI - Probabilistic joint image segmentation and labeling VL - 24 ER - TY - JOUR AB - The unintentional scattering of light between neighboring surfaces in complex projection environments increases the brightness and decreases the contrast, disrupting the appearance of the desired imagery. To achieve satisfactory projection results, the inverse problem of global illumination must be solved to cancel this secondary scattering. In this paper, we propose a global illumination cancellation method that minimizes the perceptual difference between the desired imagery and the actual total illumination in the resulting physical environment. Using Gauss-Newton and active set methods, we design a fast solver for the bound constrained nonlinear least squares problem raised by the perceptual error metrics. Our solver is further accelerated with a CUDA implementation and multi-resolution method to achieve 1–2 fps for problems with approximately 3000 variables. We demonstrate the global illumination cancellation algorithm with our multi-projector system. Results show that our method preserves the color fidelity of the desired imagery significantly better than previous methods. AU - Sheng, Yu AU - Cutler, Barbara AU - Chen, Chao AU - Nasman, Joshua ID - 3269 IS - 4 JF - Computer Graphics Forum TI - Perceptual global illumination cancellation in complex projection environments VL - 30 ER - TY - JOUR AB - We address the problem of localizing homology classes, namely, finding the cycle representing a given class with the most concise geometric measure. We study the problem with different measures: volume, diameter and radius. For volume, that is, the 1-norm of a cycle, two main results are presented. First, we prove that the problem is NP-hard to approximate within any constant factor. Second, we prove that for homology of dimension two or higher, the problem is NP-hard to approximate even when the Betti number is O(1). The latter result leads to the inapproximability of the problem of computing the nonbounding cycle with the smallest volume and computing cycles representing a homology basis with the minimal total volume. As for the other two measures defined by pairwise geodesic distance, diameter and radius, we show that the localization problem is NP-hard for diameter but is polynomial for radius. Our work is restricted to homology over the ℤ2 field. AU - Chen, Chao AU - Freedman, Daniel ID - 3267 IS - 3 JF - Discrete & Computational Geometry TI - Hardness results for homology localization VL - 45 ER - TY - CHAP AB - Algebraic topology is generally considered one of the purest subfield of mathematics. However, over the last decade two interesting new lines of research have emerged, one focusing on algorithms for algebraic topology, and the other on applications of algebraic topology in engineering and science. Amongst the new areas in which the techniques have been applied are computer vision and image processing. In this paper, we survey the results of these endeavours. Because algebraic topology is an area of mathematics with which most computer vision practitioners have no experience, we review the machinery behind the theories of homology and persistent homology; our review emphasizes intuitive explanations. In terms of applications to computer vision, we focus on four illustrative problems: shape signatures, natural image statistics, image denoising, and segmentation. Our hope is that this review will stimulate interest on the part of computer vision researchers to both use and extend the tools of this new field. AU - Freedman, Daniel AU - Chen, Chao ID - 3268 T2 - Computer Vision TI - Algebraic topology for computer vision ER - TY - JOUR AB - The zonula adherens (ZA) of epithelial cells is a site of cell-cell adhesion where cellular forces are exerted and resisted. Increasing evidence indicates that E-cadherin adhesion molecules at the ZA serve to sense force applied on the junctions and coordinate cytoskeletal responses to those forces. Efforts to understand the role that cadherins play in mechanotransduction have been limited by the lack of assays to measure the impact of forces on the ZA. In this study we used 4D imaging of GFP-tagged E-cadherin to analyse the movement of the ZA. Junctions in confluent epithelial monolayers displayed prominent movements oriented orthogonal (perpendicular) to the ZA itself. Two components were identified in these movements: a relatively slow unidirectional (translational) component that could be readily fitted by least-squares regression analysis, upon which were superimposed more rapid oscillatory movements. Myosin IIB was a dominant factor responsible for driving the unilateral translational movements. In contrast, frequency spectrum analysis revealed that depletion of Myosin IIA increased the power of the oscillatory movements. This implies that Myosin IIA may serve to dampen oscillatory movements of the ZA. This extends our recent analysis of Myosin II at the ZA to demonstrate that Myosin IIA and Myosin IIB make distinct contributions to junctional movement at the ZA. AU - Smutny, Michael AU - Wu, Selwin AU - Gomez, Guillermo AU - Mangold, Sabine AU - Yap, Alpha AU - Hamilton, Nicholas ID - 3288 IS - 7 JF - PLoS One TI - Multicomponent analysis of junctional movements regulated by Myosin II isoforms at the epithelial zonula adherens VL - 6 ER - TY - JOUR AB - Cationic antimicrobial peptides (CAMPs) selectively target bacterial membranes by electrostatic interactions with negatively charged lipids. It turned out that for inhibition of microbial growth a high CAMP membrane concentration is required, which can be realized by the incorporation of hydrophobic groups within the peptide. Increasing hydrophobicity, however, reduces the CAMP selectivity for bacterial over eukaryotic host membranes, thereby causing the risk of detrimental side-effects. In this study we addressed how cationic amphipathic peptides—in particular a CAMP with Lysine–Leucine–Lysine repeats (termed KLK)—affect the localization and dynamics of molecules in eukaryotic membranes. We found KLK to selectively inhibit the endocytosis of a subgroup of membrane proteins and lipids by electrostatically interacting with negatively charged sialic acid moieties. Ultrastructural characterization revealed the formation of membrane invaginations representing fission or fusion intermediates, in which the sialylated proteins and lipids were immobilized. Experiments on structurally different cationic amphipathic peptides (KLK, 6-MO-LF11-322 and NK14-2) indicated a cooperation of electrostatic and hydrophobic forces that selectively arrest sialylated membrane constituents. AU - Weghuber, Julian AU - Aichinger, Michael C. AU - Brameshuber, Mario AU - Stefan Wieser AU - Verena Ruprecht AU - Plochberger, Birgit AU - Madl, Josef AU - Horner, Andreas AU - Reipert, Siegfried AU - Lohner, Karl AU - Henics, Tamas AU - Schuetz, Gerhard J ID - 3286 IS - 10 JF - Biochimica et Biophysica Acta (BBA) - Biomembranes TI - Cationic amphipathic peptides accumulate sialylated proteins and lipids in the plasma membrane of eukaryotic host cells VL - 1808 ER - TY - JOUR AB - Diffusing membrane constituents are constantly exposed to a variety of forces that influence their stochastic path. Single molecule experiments allow for resolving trajectories at extremely high spatial and temporal accuracy, thereby offering insights into en route interactions of the tracer. In this review we discuss approaches to derive information about the underlying processes, based on single molecule tracking experiments. In particular, we focus on a new versatile way to analyze single molecule diffusion in the absence of a full analytical treatment. The method is based on comprehensive comparison of an experimental data set against the hypothetical outcome of multiple experiments performed on the computer. Since Monte Carlo simulations can be easily and rapidly performed even on state-of-the-art PCs, our method provides a simple way for testing various - even complicated - diffusion models. We describe the new method in detail, and show the applicability on two specific examples: firstly, kinetic rate constants can be derived for the transient interaction of mobile membrane proteins; secondly, residence time and corral size can be extracted for confined diffusion. AU - Ruprecht, Verena AU - Axmann, Markus AU - Wieser, Stefan AU - Schuetz, Gerhard ID - 3287 IS - 8 JF - Current Protein & Peptide Science TI - What can we learn from single molecule trajectories? VL - 12 ER - TY - JOUR AB - Resolving the dynamical interplay of proteins and lipids in the live-cell plasma membrane represents a central goal in current cell biology. Superresolution concepts have introduced a means of capturing spatial heterogeneity at a nanoscopic length scale. Similar concepts for detecting dynamical transitions (superresolution chronoscopy) are still lacking. Here, we show that recently introduced spot-variation fluorescence correlation spectroscopy allows for sensing transient confinement times of membrane constituents at dramatically improved resolution. Using standard diffraction-limited optics, spot-variation fluorescence correlation spectroscopy captures signatures of single retardation events far below the transit time of the tracer through the focal spot. We provide an analytical description of special cases of transient binding of a tracer to pointlike traps, or association of a tracer with nanodomains. The influence of trap mobility and the underlying binding kinetics are quantified. Experimental approaches are suggested that allow for gaining quantitative mechanistic insights into the interaction processes of membrane constituents. AU - Ruprecht, Verena AU - Wieser, Stefan AU - Marguet, Didier AU - Schuetz, Gerhard ID - 3285 IS - 11 JF - Biophysical Journal TI - Spot variation fluorescence correlation spectroscopy allows for superresolution chronoscopy of confinement times in membranes VL - 100 ER - TY - CONF AB - Cloud computing aims to give users virtually unlimited pay-per-use computing resources without the burden of managing the underlying infrastructure. We present a new job execution environment Flextic that exploits scal- able static scheduling techniques to provide the user with a flexible pricing model, such as a tradeoff between dif- ferent degrees of execution speed and execution price, and at the same time, reduce scheduling overhead for the cloud provider. We have evaluated a prototype of Flextic on Amazon EC2 and compared it against Hadoop. For various data parallel jobs from machine learning, im- age processing, and gene sequencing that we considered, Flextic has low scheduling overhead and reduces job du- ration by up to 15% compared to Hadoop, a dynamic cloud scheduler. AU - Henzinger, Thomas A AU - Singh, Anmol AU - Singh, Vasu AU - Wies, Thomas AU - Zufferey, Damien ID - 3302 TI - Static scheduling in clouds ER - TY - CONF AB - The chemical master equation is a differential equation describing the time evolution of the probability distribution over the possible “states” of a biochemical system. The solution of this equation is of interest within the systems biology field ever since the importance of the molec- ular noise has been acknowledged. Unfortunately, most of the systems do not have analytical solutions, and numerical solutions suffer from the course of dimensionality and therefore need to be approximated. Here, we introduce the concept of tail approximation, which retrieves an approximation of the probabilities in the tail of a distribution from the total probability of the tail and its conditional expectation. This approximation method can then be used to numerically compute the solution of the chemical master equation on a subset of the state space, thus fighting the explosion of the state space, for which this problem is renowned. AU - Henzinger, Thomas A AU - Mateescu, Maria ID - 3301 TI - Tail approximation for the chemical master equation ER - TY - CONF AB - We introduce propagation models, a formalism designed to support general and efficient data structures for the transient analysis of biochemical reaction networks. We give two use cases for propagation abstract data types: the uniformization method and numerical integration. We also sketch an implementation of a propagation abstract data type, which uses abstraction to approximate states. AU - Henzinger, Thomas A AU - Mateescu, Maria ID - 3299 TI - Propagation models for computing biochemical reaction networks ER - TY - CONF AB - In addition to being correct, a system should be robust, that is, it should behave reasonably even after receiving unexpected inputs. In this paper, we summarize two formal notions of robustness that we have introduced previously for reactive systems. One of the notions is based on assigning costs for failures on a user-provided notion of incorrect transitions in a specification. Here, we define a system to be robust if a finite number of incorrect inputs does not lead to an infinite number of incorrect outputs. We also give a more refined notion of robustness that aims to minimize the ratio of output failures to input failures. The second notion is aimed at liveness. In contrast to the previous notion, it has no concept of recovery from an error. Instead, it compares the ratio of the number of liveness constraints that the system violates to the number of liveness constraints that the environment violates. AU - Bloem, Roderick AU - Chatterjee, Krishnendu AU - Greimel, Karin AU - Henzinger, Thomas A AU - Jobstmann, Barbara ID - 3316 T2 - 6th IEEE International Symposium on Industrial and Embedded Systems TI - Specification-centered robustness ER - TY - JOUR AB - Parvalbumin is thought to act in a manner similar to EGTA, but how a slow Ca2+ buffer affects nanodomain-coupling regimes at GABAergic synapses is unclear. Direct measurements of parvalbumin concentration and paired recordings in rodent hippocampus and cerebellum revealed that parvalbumin affects synaptic dynamics only when expressed at high levels. Modeling suggests that, in high concentrations, parvalbumin may exert BAPTA-like effects, modulating nanodomain coupling via competition with local saturation of endogenous fixed buffers. AU - Eggermann, Emmanuel AU - Jonas, Peter M ID - 3318 JF - Nature Neuroscience TI - How the “slow” Ca(2+) buffer parvalbumin affects transmitter release in nanodomain coupling regimes at GABAergic synapses VL - 15 ER - TY - CHAP AB - We study the topology of the Megaparsec Cosmic Web in terms of the scale-dependent Betti numbers, which formalize the topological information content of the cosmic mass distribution. While the Betti numbers do not fully quantify topology, they extend the information beyond conventional cosmological studies of topology in terms of genus and Euler characteristic. The richer information content of Betti numbers goes along the availability of fast algorithms to compute them. For continuous density fields, we determine the scale-dependence of Betti numbers by invoking the cosmologically familiar filtration of sublevel or superlevel sets defined by density thresholds. For the discrete galaxy distribution, however, the analysis is based on the alpha shapes of the particles. These simplicial complexes constitute an ordered sequence of nested subsets of the Delaunay tessellation, a filtration defined by the scale parameter, α. As they are homotopy equivalent to the sublevel sets of the distance field, they are an excellent tool for assessing the topological structure of a discrete point distribution. In order to develop an intuitive understanding for the behavior of Betti numbers as a function of α, and their relation to the morphological patterns in the Cosmic Web, we first study them within the context of simple heuristic Voronoi clustering models. These can be tuned to consist of specific morphological elements of the Cosmic Web, i.e. clusters, filaments, or sheets. To elucidate the relative prominence of the various Betti numbers in different stages of morphological evolution, we introduce the concept of alpha tracks. Subsequently, we address the topology of structures emerging in the standard LCDM scenario and in cosmological scenarios with alternative dark energy content. The evolution of the Betti numbers is shown to reflect the hierarchical evolution of the Cosmic Web. We also demonstrate that the scale-dependence of the Betti numbers yields a promising measure of cosmological parameters, with a potential to help in determining the nature of dark energy and to probe primordial non-Gaussianities. We also discuss the expected Betti numbers as a function of the density threshold for superlevel sets of a Gaussian random field. Finally, we introduce the concept of persistent homology. It measures scale levels of the mass distribution and allows us to separate small from large scale features. Within the context of the hierarchical cosmic structure formation, persistence provides a natural formalism for a multiscale topology study of the Cosmic Web. AU - Van De Weygaert, Rien AU - Vegter, Gert AU - Edelsbrunner, Herbert AU - Jones, Bernard AU - Pranav, Pratyush AU - Park, Changbom AU - Hellwing, Wojciech AU - Eldering, Bob AU - Kruithof, Nico AU - Bos, Patrick AU - Hidding, Johan AU - Feldbrugge, Job AU - Ten Have, Eline AU - Van Engelen, Matti AU - Caroli, Manuel AU - Teillaud, Monique ED - Gavrilova, Marina ED - Tan, Kenneth ED - Mostafavi, Mir ID - 3335 T2 - Transactions on Computational Science XIV TI - Alpha, Betti and the Megaparsec Universe: On the topology of the Cosmic Web VL - 6970 ER - TY - CONF AB - We consider the offset-deconstruction problem: Given a polygonal shape Q with n vertices, can it be expressed, up to a tolerance µ in Hausdorff distance, as the Minkowski sum of another polygonal shape P with a disk of fixed radius? If it does, we also seek a preferably simple-looking solution shape P; then, P's offset constitutes an accurate, vertex-reduced, and smoothened approximation of Q. We give an O(n log n)-time exact decision algorithm that handles any polygonal shape, assuming the real-RAM model of computation. An alternative algorithm, based purely on rational arithmetic, answers the same deconstruction problem, up to an uncertainty parameter, and its running time depends on the parameter δ (in addition to the other input parameters: n, δ and the radius of the disk). If the input shape is found to be approximable, the rational-arithmetic algorithm also computes an approximate solution shape for the problem. For convex shapes, the complexity of the exact decision algorithm drops to O(n), which is also the time required to compute a solution shape P with at most one more vertex than a vertex-minimal one. Our study is motivated by applications from two different domains. However, since the offset operation has numerous uses, we anticipate that the reverse question that we study here will be still more broadly applicable. We present results obtained with our implementation of the rational-arithmetic algorithm. AU - Berberich, Eric AU - Halperin, Dan AU - Kerber, Michael AU - Pogalnikova, Roza ID - 3329 T2 - Proceedings of the twenty-seventh annual symposium on Computational geometry TI - Deconstructing approximate offsets ER - TY - JOUR AB - Given an algebraic hypersurface O in ℝd, how many simplices are necessary for a simplicial complex isotopic to O? We address this problem and the variant where all vertices of the complex must lie on O. We give asymptotically tight worst-case bounds for algebraic plane curves. Our results gradually improve known bounds in higher dimensions; however, the question for tight bounds remains unsolved for d ≥ 3. AU - Kerber, Michael AU - Sagraloff, Michael ID - 3332 IS - 3 JF - Graphs and Combinatorics TI - A note on the complexity of real algebraic hypersurfaces VL - 27 ER - TY - CONF AB - We consider the problem of approximating all real roots of a square-free polynomial f. Given isolating intervals, our algorithm refines each of them to a width at most 2-L, that is, each of the roots is approximated to L bits after the binary point. Our method provides a certified answer for arbitrary real polynomials, only requiring finite approximations of the polynomial coefficient and choosing a suitable working precision adaptively. In this way, we get a correct algorithm that is simple to implement and practically efficient. Our algorithm uses the quadratic interval refinement method; we adapt that method to be able to cope with inaccuracies when evaluating f, without sacrificing its quadratic convergence behavior. We prove a bound on the bit complexity of our algorithm in terms of degree, coefficient size and discriminant. Our bound improves previous work on integer polynomials by a factor of deg f and essentially matches best known theoretical bounds on root approximation which are obtained by very sophisticated algorithms. AU - Kerber, Michael AU - Sagraloff, Michael ID - 3330 TI - Root refinement for real polynomials ER - TY - CONF AB - We report on a generic uni- and bivariate algebraic kernel that is publicly available with CGAL 3.7. It comprises complete, correct, though efficient state-of-the-art implementations on polynomials, roots of polynomial systems, and the support to analyze algebraic curves defined by bivariate polynomials. The kernel design is generic, that is, various number types and substeps can be exchanged. It is accompanied with a ready-to-use interface to enable arrangements induced by algebraic curves, that have already been used as basis for various geometric applications, as arrangements on Dupin cyclides or the triangulation of algebraic surfaces. We present two novel applications: arrangements of rotated algebraic curves and Boolean set operations on polygons bounded by segments of algebraic curves. We also provide experiments showing that our general implementation is competitive and even often clearly outperforms existing implementations that are explicitly tailored for specific types of non-linear curves that are available in CGAL. AU - Berberich, Eric AU - Hemmer, Michael AU - Kerber, Michael ID - 3328 TI - A generic algebraic kernel for non linear geometric applications ER - TY - JOUR AU - Edelsbrunner, Herbert AU - Pach, János AU - Ziegler, Günter ID - 3334 IS - 1 JF - Discrete & Computational Geometry TI - Letter from the new editors-in-chief VL - 45 ER - TY - JOUR AB - Compositional theories are crucial when designing large and complex systems from smaller components. In this work we propose such a theory for synchronous concurrent systems. Our approach follows so-called interface theories, which use game-theoretic interpretations of composition and refinement. These are appropriate for systems with distinct inputs and outputs, and explicit conditions on inputs that must be enforced during composition. Our interfaces model systems that execute in an infinite sequence of synchronous rounds. At each round, a contract must be satisfied. The contract is simply a relation specifying the set of valid input/output pairs. Interfaces can be composed by parallel, serial or feedback composition. A refinement relation between interfaces is defined, and shown to have two main properties: (1) it is preserved by composition, and (2) it is equivalent to substitutability, namely, the ability to replace an interface by another one in any context. Shared refinement and abstraction operators, corresponding to greatest lower and least upper bounds with respect to refinement, are also defined. Input-complete interfaces, that impose no restrictions on inputs, and deterministic interfaces, that produce a unique output for any legal input, are discussed as special cases, and an interesting duality between the two classes is exposed. A number of illustrative examples are provided, as well as algorithms to compute compositions, check refinement, and so on, for finite-state interfaces. AU - Tripakis, Stavros AU - Lickly, Ben AU - Henzinger, Thomas A AU - Lee, Edward ID - 3353 IS - 4 JF - ACM Transactions on Programming Languages and Systems (TOPLAS) TI - A theory of synchronous relational interfaces VL - 33 ER - TY - CONF AB - Byzantine Fault Tolerant (BFT) protocols aim to improve the reliability of distributed systems. They enable systems to tolerate arbitrary failures in a bounded number of nodes. BFT protocols are usually proven correct for certain safety and liveness properties. However, recent studies have shown that the performance of state-of-the-art BFT protocols decreases drastically in the presence of even a single malicious node. This motivates a formal quantitative analysis of BFT protocols to investigate their performance characteristics under different scenarios. We present HyPerf, a new hybrid methodology based on model checking and simulation techniques for evaluating the performance of BFT protocols. We build a transition system corresponding to a BFT protocol and systematically explore the set of behaviors allowed by the protocol. We associate certain timing information with different operations in the protocol, like cryptographic operations and message transmission. After an elaborate state exploration, we use the time information to evaluate the performance characteristics of the protocol using simulation techniques. We integrate our framework in Mace, a tool for building and verifying distributed systems. We evaluate the performance of PBFT using our framework. We describe two different use-cases of our methodology. For the benign operation of the protocol, we use the time information as random variables to compute the probability distribution of the execution times. In the presence of faults, we estimate the worst-case performance of the protocol for various attacks that can be employed by malicious nodes. Our results show the importance of hybrid techniques in systematically analyzing the performance of large-scale systems. AU - Halalai, Raluca AU - Henzinger, Thomas A AU - Singh, Vasu ID - 3355 TI - Quantitative evaluation of BFT protocols ER - TY - CONF AB - A controller for a discrete game with ω-regular objectives requires attention if, intuitively, it requires measuring the state and switching from the current control action. Minimum attention controllers are preferable in modern shared implementations of cyber-physical systems because they produce the least burden on system resources such as processor time or communication bandwidth. We give algorithms to compute minimum attention controllers for ω-regular objectives in imperfect information discrete two-player games. We show a polynomial-time reduction from minimum attention controller synthesis to synthesis of controllers for mean-payoff parity objectives in games of incomplete information. This gives an optimal EXPTIME-complete synthesis algorithm. We show that the minimum attention controller problem is decidable for infinite state systems with finite bisimulation quotients. In particular, the problem is decidable for timed and rectangular automata. AU - Chatterjee, Krishnendu AU - Majumdar, Ritankar ED - Fahrenberg, Uli ED - Tripakis, Stavros ID - 3350 TI - Minimum attention controller synthesis for omega regular objectives VL - 6919 ER - TY - CONF AB - In two-player games on graph, the players construct an infinite path through the game graph and get a reward computed by a payoff function over infinite paths. Over weighted graphs, the typical and most studied payoff functions compute the limit-average or the discounted sum of the rewards along the path. Besides their simple definition, these two payoff functions enjoy the property that memoryless optimal strategies always exist. In an attempt to construct other simple payoff functions, we define a class of payoff functions which compute an (infinite) weighted average of the rewards. This new class contains both the limit-average and the discounted sum functions, and we show that they are the only members of this class which induce memoryless optimal strategies, showing that there is essentially no other simple payoff functions. AU - Chatterjee, Krishnendu AU - Doyen, Laurent AU - Singh, Rohit ED - Owe, Olaf ED - Steffen, Martin ED - Telle, Jan Arne ID - 3351 TI - On memoryless quantitative objectives VL - 6914 ER - TY - JOUR AB - We consider two-player 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 the successor state. We consider ω-regular winning conditions specified as parity objectives. Both players are allowed to use randomization when choosing their moves. We study the computation of the limit-winning set of states, consisting of the states where the sup-inf value of the game for player 1 is 1: in other words, a state is limit-winning if player 1 can ensure a probability of winning arbitrarily close to 1. We show that the limit-winning set can be computed in O(n2d+2) time, where n is the size of the game structure and 2d is the number of priorities (or colors). The membership problem of whether a state belongs to the limit-winning set can be decided in NP ∩ coNP. While this complexity is the same as for the simpler class of turn-based parity games, where in each state only one of the two players has a choice of moves, our algorithms are considerably more involved than those for turn-based games. This is because concurrent games do not satisfy two of the most fundamental properties of turn-based parity games. First, in concurrent games limit-winning strategies require randomization; and second, they require infinite memory. AU - Chatterjee, Krishnendu AU - De Alfaro, Luca AU - Henzinger, Thomas A ID - 3354 IS - 4 JF - ACM Transactions on Computational Logic (TOCL) TI - Qualitative concurrent parity games VL - 12 ER - TY - CONF AB - Games on graphs provide a natural model for reactive non-terminating systems. In such games, the interaction of two players on an arena results in an infinite path that describes a run of the system. Different settings are used to model various open systems in computer science, as for instance turn-based or concurrent moves, and deterministic or stochastic transitions. In this paper, we are interested in turn-based games, and specifically in deterministic parity games and stochastic reachability games (also known as simple stochastic games). We present a simple, direct and efficient reduction from deterministic parity games to simple stochastic games: it yields an arena whose size is linear up to a logarithmic factor in size of the original arena. AU - Chatterjee, Krishnendu AU - Fijalkow, Nathanaël ID - 3349 TI - A reduction from parity games to simple stochastic games VL - 54 ER - TY - JOUR AB - Recently reported synthetic routes for the production of hollow nanoparticles have stimulated significant interest for the possibilities this novel geometry offers. While advantageous properties have been found and innovative applications have been proposed, the development of the full potential of these new nanostructures is still strongly tied to the extent of control that can be accomplished over their characteristics (e.g., composition, size, shell thickness, and nanocrystalline structure). In the present work, we investigate the means and limits of control over these parameters that can be obtained by the Kirkendall effect synthetic route on cadmium chalcogenide nanocrystalline shells. We demonstrate that the selection of the reactants and oxidation conditions allows some extent of control of the nanocrystalline structure and thickness of the shell. However, the tuning range is limited by the intrinsic restrictions of the synthetic procedure and by the dependence of the particle geometry on the same reaction conditions. Thus, we further explore the range of control over the shell parameters that can be accomplished through post-synthesis processes, such as chemical etching and thermal annealing. AU - Ibáñez, Maria AU - Fan, Jiandong AU - Li, Wenhua AU - Cadavid, Doris AU - Nafria, Raquel AU - Carrete, Alex AU - Cabot, Andreu ID - 335 IS - 12 JF - Chemistry of Materials TI - Means and limits of control of the shell parameters in hollow nanoparticles obtained by the Kirkendall effect VL - 23 ER - TY - JOUR AB - Exploring the connection of biology with reactive systems to better understand living systems. AU - Fisher, Jasmin AU - Harel, David AU - Henzinger, Thomas A ID - 3352 IS - 10 JF - Communications of the ACM TI - Biology as reactivity VL - 54 ER - TY - CONF AB - State-transition systems communicating by shared variables have been the underlying model of choice for applications of model checking. Such formalisms, however, have difficulty with modeling process creation or death and communication reconfigurability. Here, we introduce “dynamic reactive modules” (DRM), a state-transition modeling formalism that supports dynamic reconfiguration and creation/death of processes. The resulting formalism supports two types of variables, data variables and reference variables. Reference variables enable changing the connectivity between processes and referring to instances of processes. We show how this new formalism supports parallel composition and refinement through trace containment. DRM provide a natural language for modeling (and ultimately reasoning about) biological systems and multiple threads communicating through shared variables. AU - Fisher, Jasmin AU - Henzinger, Thomas A AU - Nickovic, Dejan AU - Piterman, Nir AU - Singh, Anmol AU - Vardi, Moshe ID - 3362 TI - Dynamic reactive modules VL - 6901 ER - TY - CONF AB - We present the tool Quasy, a quantitative synthesis tool. Quasy takes qualitative and quantitative specifications and automatically constructs a system that satisfies the qualitative specification and optimizes the quantitative specification, if such a system exists. The user can choose between a system that satisfies and optimizes the specifications (a) under all possible environment behaviors or (b) under the most-likely environment behaviors given as a probability distribution on the possible input sequences. Quasy solves these two quantitative synthesis problems by reduction to instances of 2-player games and Markov Decision Processes (MDPs) with quantitative winning objectives. Quasy can also be seen as a game solver for quantitative games. Most notable, it can solve lexicographic mean-payoff games with 2 players, MDPs with mean-payoff objectives, and ergodic MDPs with mean-payoff parity objectives. AU - Chatterjee, Krishnendu AU - Henzinger, Thomas A AU - Jobstmann, Barbara AU - Singh, Rohit ID - 3365 TI - QUASY: quantitative synthesis tool VL - 6605 ER - TY - CONF AB - In this paper, we present the first output-sensitive algorithm to compute the persistence diagram of a filtered simplicial complex. For any Γ>0, it returns only those homology classes with persistence at least Γ. Instead of the classical reduction via column operations, our algorithm performs rank computations on submatrices of the boundary matrix. For an arbitrary constant δ ∈ (0,1), the running time is O(C(1-δ)ΓR(n)log n), where C(1-δ)Γ is the number of homology classes with persistence at least (1-δ)Γ, n is the total number of simplices, and R(n) is the complexity of computing the rank of an n x n matrix with O(n) nonzero entries. Depending on the choice of the rank algorithm, this yields a deterministic O(C(1-δ)Γn2.376) algorithm, a O(C(1-δ)Γn2.28) Las-Vegas algorithm, or a O(C(1-δ)Γn2+ε) Monte-Carlo algorithm for an arbitrary ε>0. AU - Chen, Chao AU - Kerber, Michael ID - 3367 TI - An output sensitive algorithm for persistent homology ER - TY - GEN AB - We consider probabilistic automata on infinite words with acceptance defined by safety, reachability, Büchi, coBüchi, and limit-average conditions. We consider quantitative and qualitative decision problems. We present extensions and adaptations of proofs for probabilistic finite automata and present a complete characterization of the decidability and undecidability frontier of the quantitative and qualitative decision problems for probabilistic automata on infinite words. AU - Chatterjee, Krishnendu AU - Henzinger, Thomas A AU - Tracol, Mathieu ID - 3363 TI - The decidability frontier for probabilistic automata on infinite words ER - TY - JOUR AB - Nowak et al.1 argue that inclusive fitness theory has been of little value in explaining the natural world, and that it has led to negligible progress in explaining the evolution of eusociality. However, we believe that their arguments are based upon a misunderstanding of evolutionary theory and a misrepresentation of the empirical literature. We will focus our comments on three general issues. AU - Abbot, Patrick AU - Abe, Jun AU - Alcock, John AU - Alizon, Samuel AU - Alpedrinha, Joao AU - Andersson, Malte AU - Andre, Jean AU - Van Baalen, Minus AU - Balloux, Francois AU - Balshine, Sigal AU - Barton, Nicholas H AU - Beukeboom, Leo AU - Biernaskie, Jay AU - Bilde, Trine AU - Borgia, Gerald AU - Breed, Michael AU - Brown, Sam AU - Bshary, Redouan AU - Buckling, Angus AU - Burley, Nancy AU - Burton Chellew, Max AU - Cant, Michael AU - Chapuisat, Michel AU - Charnov, Eric AU - Clutton Brock, Tim AU - Cockburn, Andrew AU - Cole, Blaine AU - Colegrave, Nick AU - Cosmides, Leda AU - Couzin, Iain AU - Coyne, Jerry AU - Creel, Scott AU - Crespi, Bernard AU - Curry, Robert AU - Dall, Sasha AU - Day, Troy AU - Dickinson, Janis AU - Dugatkin, Lee AU - El Mouden, Claire AU - Emlen, Stephen AU - Evans, Jay AU - Ferriere, Regis AU - Field, Jeremy AU - Foitzik, Susanne AU - Foster, Kevin AU - Foster, William AU - Fox, Charles AU - Gadau, Juergen AU - Gandon, Sylvain AU - Gardner, Andy AU - Gardner, Michael AU - Getty, Thomas AU - Goodisman, Michael AU - Grafen, Alan AU - Grosberg, Rick AU - Grozinger, Christina AU - Gouyon, Pierre AU - Gwynne, Darryl AU - Harvey, Paul AU - Hatchwell, Ben AU - Heinze, Jürgen AU - Helantera, Heikki AU - Helms, Ken AU - Hill, Kim AU - Jiricny, Natalie AU - Johnstone, Rufus AU - Kacelnik, Alex AU - Kiers, E Toby AU - Kokko, Hanna AU - Komdeur, Jan AU - Korb, Judith AU - Kronauer, Daniel AU - Kümmerli, Rolf AU - Lehmann, Laurent AU - Linksvayer, Timothy AU - Lion, Sébastien AU - Lyon, Bruce AU - Marshall, James AU - Mcelreath, Richard AU - Michalakis, Yannis AU - Michod, Richard AU - Mock, Douglas AU - Monnin, Thibaud AU - Montgomerie, Robert AU - Moore, Allen AU - Mueller, Ulrich AU - Noë, Ronald AU - Okasha, Samir AU - Pamilo, Pekka AU - Parker, Geoff AU - Pedersen, Jes AU - Pen, Ido AU - Pfennig, David AU - Queller, David AU - Rankin, Daniel AU - Reece, Sarah AU - Reeve, Hudson AU - Reuter, Max AU - Roberts, Gilbert AU - Robson, Simon AU - Roze, Denis AU - Rousset, Francois AU - Rueppell, Olav AU - Sachs, Joel AU - Santorelli, Lorenzo AU - Schmid Hempel, Paul AU - Schwarz, Michael AU - Scott Phillips, Tom AU - Shellmann Sherman, Janet AU - Sherman, Paul AU - Shuker, David AU - Smith, Jeff AU - Spagna, Joseph AU - Strassmann, Beverly AU - Suarez, Andrew AU - Sundström, Liselotte AU - Taborsky, Michael AU - Taylor, Peter AU - Thompson, Graham AU - Tooby, John AU - Tsutsui, Neil AU - Tsuji, Kazuki AU - Turillazzi, Stefano AU - Úbeda, Francisco AU - Vargo, Edward AU - Voelkl, Bernard AU - Wenseleers, Tom AU - West, Stuart AU - West Eberhard, Mary AU - Westneat, David AU - Wiernasz, Diane AU - Wild, Geoff AU - Wrangham, Richard AU - Young, Andrew AU - Zeh, David AU - Zeh, Jeanne AU - Zink, Andrew ID - 3372 IS - 7339 JF - Nature TI - Inclusive fitness theory and eusociality VL - 471 ER - TY - JOUR AB - The Minisymposium “Cell Migration and Motility” was attended by approximately 500 visitors and covered a broad range of questions in the field using diverse model systems. Topics comprised actin dynamics, cell polarity, force transduction, signal transduction, bar- rier transmigration, and chemotactic guidance. AU - Sixt, Michael K AU - Parent, Carole ID - 3371 IS - 6 JF - Molecular Biology and Evolution TI - Cells on the move in Philadelphia VL - 22 ER - TY - JOUR AB - Genetic regulatory networks enable cells to respond to changes in internal and external conditions by dynamically coordinating their gene expression profiles. Our ability to make quantitative measurements in these biochemical circuits has deepened our understanding of what kinds of computations genetic regulatory networks can perform, and with what reliability. These advances have motivated researchers to look for connections between the architecture and function of genetic regulatory networks. Transmitting information between a network's inputs and outputs has been proposed as one such possible measure of function, relevant in certain biological contexts. Here we summarize recent developments in the application of information theory to gene regulatory networks. We first review basic concepts in information theory necessary for understanding recent work. We then discuss the functional complexity of gene regulation, which arises from the molecular nature of the regulatory interactions. We end by reviewing some experiments that support the view that genetic networks responsible for early development of multicellular organisms might be maximizing transmitted 'positional information'. AU - Tkacik, Gasper AU - Walczak, Aleksandra ID - 3374 IS - 15 JF - Journal of Physics: Condensed Matter TI - Information transmission in genetic regulatory networks a review VL - 23 ER - TY - JOUR AB - Tissue surface tension (TST) is an important mechanical property influencing cell sorting and tissue envelopment. The study by Manning et al. (1) reported on a mathematical model describing TST on the basis of the balance between adhesive and tensile properties of the constituent cells. The model predicts that, in high-adhesion cell aggregates, surface cells will be stretched to maintain the same area of cell–cell contact as interior bulk cells, resulting in an elongated and flattened cell shape. The authors (1) observed flat and elongated cells at the surface of high-adhesion zebrafish germ-layer explants, which they argue are undifferentiated stretched germ-layer progenitor cells, and they use this observation as a validation of their model. AU - Krens, Gabriel AU - Möllmert, Stephanie AU - Heisenberg, Carl-Philipp J ID - 3368 IS - 3 JF - PNAS TI - Enveloping cell layer differentiation at the surface of zebrafish germ layer tissue explants VL - 108 ER - TY - JOUR AB - Supertree methods are widely applied and give rise to new conclusions about phylogenies (e.g., Bininda-Emonds et al. 2007). Although several desiderata for supertree methods exist (Wilkinson, Thorley, et al. 2004), only few of them have been studied in greater detail, examples include shape bias (Wilkinson et al. 2005) or pareto properties (Wilkinson et al. 2007). Here I look more closely at two matrix representation methods, matrix representation with compatibility (MRC) and matrix representation with parsimony (MRP). Different null models of random data are studied and the resulting tree shapes are investigated. Thereby I consider unrooted trees and a bias in tree shape is determined by a tree balance measure. The measure for unrooted trees is a modification of a tree balance measure for rooted trees. I observe that depending on the underlying null model of random data, the methods may resolve conflict in favor of more balanced tree shapes. The analyses refer only to trees with the same taxon set, also known as the consensus setting (e.g., Wilkinson et al. 2007), but I will be able to draw conclusions on how to deal with missing data. AU - Kupczok, Anne ID - 3370 IS - 2 JF - Systematic Biology TI - Consequences of different null models on the tree shape bias of supertree methods VL - 60 ER - TY - JOUR AB - Rab3 interacting molecules (RIMs) are highly enriched in the active zones of presynaptic terminals. It is generally thought that they operate as effectors of the small G protein Rab3. Three recent papers, by Han et al. (this issue of Neuron), Deng et al. (this issue of Neuron), and Kaeser et al. (a recent issue of Cell), shed new light on the functional role of RIM in presynaptic terminals. First, RIM tethers Ca2+ channels to active zones. Second, RIM contributes to priming of synaptic vesicles by interacting with another presynaptic protein, Munc13. AU - Pernia-Andrade, Alejandro AU - Jonas, Peter M ID - 3369 IS - 2 JF - Neuron TI - The multiple faces of RIM VL - 69 ER - TY - JOUR AB - Facial branchiomotor neurons (FBMNs) in zebrafish and mouse embryonic hindbrain undergo a characteristic tangential migration from rhombomere (r) 4, where they are born, to r6/7. Cohesion among neuroepithelial cells (NCs) has been suggested to function in FBMN migration by inhibiting FBMNs positioned in the basal neuroepithelium such that they move apically between NCs towards the midline of the neuroepithelium instead of tangentially along the basal side of the neuroepithelium towards r6/7. However, direct experimental evaluation of this hypothesis is still lacking. Here, we have used a combination of biophysical cell adhesion measurements and high-resolution time-lapse microscopy to determine the role of NC cohesion in FBMN migration. We show that reducing NC cohesion by interfering with Cadherin 2 (Cdh2) activity results in FBMNs positioned at the basal side of the neuroepithelium moving apically towards the neural tube midline instead of tangentially towards r6/7. In embryos with strongly reduced NC cohesion, ectopic apical FBMN movement frequently results in fusion of the bilateral FBMN clusters over the apical midline of the neural tube. By contrast, reducing cohesion among FBMNs by interfering with Contactin 2 (Cntn2) expression in these cells has little effect on apical FBMN movement, but reduces the fusion of the bilateral FBMN clusters in embryos with strongly diminished NC cohesion. These data provide direct experimental evidence that NC cohesion functions in tangential FBMN migration by restricting their apical movement. AU - Stockinger, Petra AU - Heisenberg, Carl-Philipp J AU - Maître, Jean-Léon ID - 3396 IS - 21 JF - Development TI - Defective neuroepithelial cell cohesion affects tangential branchiomotor neuron migration in the zebrafish neural tube VL - 138 ER - TY - JOUR AB - Random genetic drift shifts clines in space, alters their width, and distorts their shape. Such random fluctuations complicate inferences from cline width and position. Notably, the effect of genetic drift on the expected shape of the cline is opposite to the naive (but quite common) misinterpretation of classic results on the expected cline. While random drift on average broadens the overall cline in expected allele frequency, it narrows the width of any particular cline. The opposing effects arise because locally, drift drives alleles to fixation—but fluctuations in position widen the expected cline. The effect of genetic drift can be predicted from standardized variance in allele frequencies, averaged across the habitat: 〈F〉. A cline maintained by spatially varying selection (step change) is expected to be narrower by a factor of relative to the cline in the absence of drift. The expected cline is broader by the inverse of this factor. In a tension zone maintained by underdominance, the expected cline width is narrower by about 1 – 〈F〉relative to the width in the absence of drift. Individual clines can differ substantially from the expectation, and we give quantitative predictions for the variance in cline position and width. The predictions apply to clines in almost one-dimensional circumstances such as hybrid zones in rivers, deep valleys, or along a coast line and give a guide to what patterns to expect in two dimensions. AU - Polechova, Jitka AU - Barton, Nicholas H ID - 3394 IS - 1 JF - Genetics TI - Genetic drift widens the expected cline but narrows the expected cline width VL - 189 ER - TY - JOUR AB - What determines the genetic contribution that an individual makes to future generations? With biparental reproduction, each individual leaves a 'pedigree' of descendants, determined by the biparental relationships in the population. The pedigree of an individual constrains the lines of descent of each of its genes. An individual's reproductive value is the expected number of copies of each of its genes that is passed on to distant generations conditional on its pedigree. For the simplest model of biparental reproduction analogous to the Wright-Fisher model, an individual's reproductive value is determined within ~10 generations, independent of population size. Partial selfing and subdivision do not greatly slow this convergence. Our central result is that the probability that a gene will survive is proportional to the reproductive value of the individual that carries it, and that conditional on survival, after a few tens of generations, the distribution of the number of surviving copies is the same for all individuals, whatever their reproductive value. These results can be generalized to the joint distribution of surviving blocks of ancestral genome. Selection on unlinked loci in the genetic background may greatly increase the variance in reproductive value, but the above results nevertheless still hold. The almost linear relationship between survival probability and reproductive value also holds for weakly favored alleles. Thus, the influence of the complex pedigree of descendants on an individual's genetic contribution to the population can be summarized through a single number: its reproductive value. AU - Barton, Nicholas H AU - Etheridge, Alison ID - 3390 IS - 4 JF - Genetics TI - The relation between reproductive value and genetic contribution VL - 188 ER - TY - JOUR AB - Evolutionary biology shares many concepts with statistical physics: both deal with populations, whether of molecules or organisms, and both seek to simplify evolution in very many dimensions. Often, methodologies have undergone parallel and independent development, as with stochastic methods in population genetics. Here, we discuss aspects of population genetics that have embraced methods from physics: non-equilibrium statistical mechanics, travelling waves and Monte-Carlo methods, among others, have been used to study polygenic evolution, rates of adaptation and range expansions. These applications indicate that evolutionary biology can further benefit from interactions with other areas of statistical physics; for example, by following the distribution of paths taken by a population through time AU - de Vladar, Harold AU - Barton, Nicholas H ID - 3391 IS - 8 JF - Trends in Ecology and Evolution TI - The contribution of statistical physics to evolutionary biology VL - 26 ER - TY - JOUR AB - Recent advances in microscopy techniques and biophysical measurements have provided novel insight into the molecular, cellular and biophysical basis of cell adhesion. However, comparably little is known about a core element of cell–cell adhesion—the energy of adhesion at the cell–cell contact. In this review, we discuss approaches to understand the nature and regulation of adhesion energy, and propose strategies to determine adhesion energy between cells in vitro and in vivo. AU - Maître, Jean-Léon AU - Heisenberg, Carl-Philipp J ID - 3397 IS - 5 JF - Current Opinion in Cell Biology TI - The role of adhesion energy in controlling cell-cell contacts VL - 23 ER - TY - JOUR AB - Glutamate is the major excitatory neurotransmitter in the mammalian central nervous system and gates non-selective cation channels. The origins of glutamate receptors are not well understood as they differ structurally and functionally from simple bacterial ligand-gated ion channels. Here we report the discovery of an ionotropic glutamate receptor that combines the typical eukaryotic domain architecture with the 'TXVGYG' signature sequence of the selectivity filter found in K+ channels. This receptor exhibits functional properties intermediate between bacterial and eukaryotic glutamate-gated ion channels, suggesting a link in the evolution of ionotropic glutamate receptors. AU - Janovjak, Harald L AU - Sandoz, Guillaume AU - Isacoff, Ehud ID - 3405 IS - 232 JF - Nature Communications TI - Modern ionotropic glutamate receptor with a K+ selectivity signature sequence VL - 2 ER - TY - JOUR AB - An oriented attachment and growth mechanism allows an accurate control of the size and morphology of Cu2-xS nanocrystals, from spheres and disks to tetradecahedrons and dodecahedrons. The synthesis conditions and the growth mechanism are detailed here. AU - Li, Wenhua AU - Shavel, Alexey AU - Guzman, Roger AU - Rubio Garcia, Javier AU - Flox, Cristina AU - Fan, Jiandong AU - Cadavid, Doris AU - Ibáñez, Maria AU - Arbiol, Jordi AU - Morante, Joan AU - Cabot, Andreu ID - 341 IS - 37 JF - Chemical Communications TI - Morphology evolution of Cu2−xS nanoparticles: from spheres to dodecahedrons VL - 47 ER -