TY - JOUR AB - We show that the following algorithmic problem is decidable: given a 2-dimensional simplicial complex, can it be embedded (topologically, or equivalently, piecewise linearly) in R3? By a known reduction, it suffices to decide the embeddability of a given triangulated 3-manifold X into the 3-sphere S3. The main step, which allows us to simplify X and recurse, is in proving that if X can be embedded in S3, then there is also an embedding in which X has a short meridian, that is, an essential curve in the boundary of X bounding a disk in S3 \ X with length bounded by a computable function of the number of tetrahedra of X. AU - Matoušek, Jiří AU - Sedgwick, Eric AU - Tancer, Martin AU - Wagner, Uli ID - 425 IS - 1 JF - Journal of the ACM TI - Embeddability in the 3-Sphere is decidable VL - 65 ER - TY - JOUR AB - Maladapted individuals can only colonise a new habitat if they can evolve a positive growth rate fast enough to avoid extinction, a process known as evolutionary rescue. We treat log fitness at low density in the new habitat as a single polygenic trait and thus use the infinitesimal model to follow the evolution of the growth rate; this assumes that the trait values of offspring of a sexual union are normally distributed around the mean of the parents’ trait values, with variance that depends only on the parents’ relatedness. The probability that a single migrant can establish depends on just two parameters: the mean and genetic variance of the trait in the source population. The chance of success becomes small if migrants come from a population with mean growth rate in the new habitat more than a few standard deviations below zero; this chance depends roughly equally on the probability that the initial founder is unusually fit, and on the subsequent increase in growth rate of its offspring as a result of selection. The loss of genetic variation during the founding event is substantial, but highly variable. With continued migration at rate M, establishment is inevitable; when migration is rare, the expected time to establishment decreases inversely with M. However, above a threshold migration rate, the population may be trapped in a ‘sink’ state, in which adaptation is held back by gene flow; above this threshold, the expected time to establishment increases exponentially with M. This threshold behaviour is captured by a deterministic approximation, which assumes a Gaussian distribution of the trait in the founder population with mean and variance evolving deterministically. By assuming a constant genetic variance, we also develop a diffusion approximation for the joint distribution of population size and trait mean, which extends to include stabilising selection and density regulation. Divergence of the population from its ancestors causes partial reproductive isolation, which we measure through the reproductive value of migrants into the newly established population. AU - Barton, Nicholas H AU - Etheridge, Alison ID - 564 IS - 7 JF - Theoretical Population Biology TI - Establishment in a new habitat by polygenic adaptation VL - 122 ER - TY - JOUR AB - Social dilemmas occur when incentives for individuals are misaligned with group interests 1-7 . According to the 'tragedy of the commons', these misalignments can lead to overexploitation and collapse of public resources. The resulting behaviours can be analysed with the tools of game theory 8 . The theory of direct reciprocity 9-15 suggests that repeated interactions can alleviate such dilemmas, but previous work has assumed that the public resource remains constant over time. Here we introduce the idea that the public resource is instead changeable and depends on the strategic choices of individuals. An intuitive scenario is that cooperation increases the public resource, whereas defection decreases it. Thus, cooperation allows the possibility of playing a more valuable game with higher payoffs, whereas defection leads to a less valuable game. We analyse this idea using the theory of stochastic games 16-19 and evolutionary game theory. We find that the dependence of the public resource on previous interactions can greatly enhance the propensity for cooperation. For these results, the interaction between reciprocity and payoff feedback is crucial: neither repeated interactions in a constant environment nor single interactions in a changing environment yield similar cooperation rates. Our framework shows which feedbacks between exploitation and environment - either naturally occurring or designed - help to overcome social dilemmas. AU - Hilbe, Christian AU - Šimsa, Štepán AU - Chatterjee, Krishnendu AU - Nowak, Martin ID - 157 IS - 7713 JF - Nature TI - Evolution of cooperation in stochastic games VL - 559 ER - TY - JOUR AB - Can orthologous proteins differ in terms of their ability to be secreted? To answer this question, we investigated the distribution of signal peptides within the orthologous groups of Enterobacterales. Parsimony analysis and sequence comparisons revealed a large number of signal peptide gain and loss events, in which signal peptides emerge or disappear in the course of evolution. Signal peptide losses prevail over gains, an effect which is especially pronounced in the transition from the free-living or commensal to the endosymbiotic lifestyle. The disproportionate decline in the number of signal peptide-containing proteins in endosymbionts cannot be explained by the overall reduction of their genomes. Signal peptides can be gained and lost either by acquisition/elimination of the corresponding N-terminal regions or by gradual accumulation of mutations. The evolutionary dynamics of signal peptides in bacterial proteins represents a powerful mechanism of functional diversification. AU - Hönigschmid, Peter AU - Bykova, Nadya AU - Schneider, René AU - Ivankov, Dmitry AU - Frishman, Dmitrij ID - 384 IS - 3 JF - Genome Biology and Evolution TI - Evolutionary interplay between symbiotic relationships and patterns of signal peptide gain and loss VL - 10 ER - TY - JOUR AB - In continuous populations with local migration, nearby pairs of individuals have on average more similar genotypes than geographically well separated pairs. A barrier to gene flow distorts this classical pattern of isolation by distance. Genetic similarity is decreased for sample pairs on different sides of the barrier and increased for pairs on the same side near the barrier. Here, we introduce an inference scheme that utilizes this signal to detect and estimate the strength of a linear barrier to gene flow in two-dimensions. We use a diffusion approximation to model the effects of a barrier on the geographical spread of ancestry backwards in time. This approach allows us to calculate the chance of recent coalescence and probability of identity by descent. We introduce an inference scheme that fits these theoretical results to the geographical covariance structure of bialleleic genetic markers. It can estimate the strength of the barrier as well as several demographic parameters. We investigate the power of our inference scheme to detect barriers by applying it to a wide range of simulated data. We also showcase an example application to a Antirrhinum majus (snapdragon) flower color hybrid zone, where we do not detect any signal of a strong genome wide barrier to gene flow. AU - Ringbauer, Harald AU - Kolesnikov, Alexander AU - Field, David AU - Barton, Nicholas H ID - 563 IS - 3 JF - Genetics TI - Estimating barriers to gene flow from distorted isolation-by-distance patterns VL - 208 ER -