@article{106, abstract = {The goal of this article is to introduce the reader to the theory of intrinsic geometry of convex surfaces. We illustrate the power of the tools by proving a theorem on convex surfaces containing an arbitrarily long closed simple geodesic. Let us remind ourselves that a curve in a surface is called geodesic if every sufficiently short arc of the curve is length minimizing; if, in addition, it has no self-intersections, we call it simple geodesic. A tetrahedron with equal opposite edges is called isosceles. The axiomatic method of Alexandrov geometry allows us to work with the metrics of convex surfaces directly, without approximating it first by a smooth or polyhedral metric. Such approximations destroy the closed geodesics on the surface; therefore it is difficult (if at all possible) to apply approximations in the proof of our theorem. On the other hand, a proof in the smooth or polyhedral case usually admits a translation into Alexandrov’s language; such translation makes the result more general. In fact, our proof resembles a translation of the proof given by Protasov. Note that the main theorem implies in particular that a smooth convex surface does not have arbitrarily long simple closed geodesics. However we do not know a proof of this corollary that is essentially simpler than the one presented below.}, author = {Akopyan, Arseniy and Petrunin, Anton}, journal = {Mathematical Intelligencer}, number = {3}, pages = {26 -- 31}, publisher = {Springer}, title = {{Long geodesics on convex surfaces}}, doi = {10.1007/s00283-018-9795-5}, volume = {40}, year = {2018}, } @article{1064, abstract = {In 1945, A.W. Goodman and R.E. Goodman proved the following conjecture by P. Erdős: Given a family of (round) disks of radii r1, … , rn in the plane, it is always possible to cover them by a disk of radius R= ∑ ri, provided they cannot be separated into two subfamilies by a straight line disjoint from the disks. In this note we show that essentially the same idea may work for different analogues and generalizations of their result. In particular, we prove the following: Given a family of positive homothetic copies of a fixed convex body K⊂ Rd with homothety coefficients τ1, … , τn> 0 , it is always possible to cover them by a translate of d+12(∑τi)K, provided they cannot be separated into two subfamilies by a hyperplane disjoint from the homothets.}, author = {Akopyan, Arseniy and Balitskiy, Alexey and Grigorev, Mikhail}, issn = {14320444}, journal = {Discrete & Computational Geometry}, number = {4}, pages = {1001--1009}, publisher = {Springer}, title = {{On the circle covering theorem by A.W. Goodman and R.E. Goodman}}, doi = {10.1007/s00454-017-9883-x}, volume = {59}, year = {2018}, } @article{107, abstract = {We introduce the notion of “non-malleable codes” which relaxes the notion of error correction and error detection. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a completely unrelated value. In contrast to error correction and error detection, non-malleability can be achieved for very rich classes of modifications. We construct an efficient code that is non-malleable with respect to modifications that affect each bit of the codeword arbitrarily (i.e., leave it untouched, flip it, or set it to either 0 or 1), but independently of the value of the other bits of the codeword. Using the probabilistic method, we also show a very strong and general statement: there exists a non-malleable code for every “small enough” family F of functions via which codewords can be modified. Although this probabilistic method argument does not directly yield efficient constructions, it gives us efficient non-malleable codes in the random-oracle model for very general classes of tampering functions—e.g., functions where every bit in the tampered codeword can depend arbitrarily on any 99% of the bits in the original codeword. As an application of non-malleable codes, we show that they provide an elegant algorithmic solution to the task of protecting functionalities implemented in hardware (e.g., signature cards) against “tampering attacks.” In such attacks, the secret state of a physical system is tampered, in the hopes that future interaction with the modified system will reveal some secret information. This problem was previously studied in the work of Gennaro et al. in 2004 under the name “algorithmic tamper proof security” (ATP). We show that non-malleable codes can be used to achieve important improvements over the prior work. In particular, we show that any functionality can be made secure against a large class of tampering attacks, simply by encoding the secret state with a non-malleable code while it is stored in memory.}, author = {Dziembowski, Stefan and Pietrzak, Krzysztof Z and Wichs, Daniel}, journal = {Journal of the ACM}, number = {4}, publisher = {ACM}, title = {{Non-malleable codes}}, doi = {10.1145/3178432}, volume = {65}, year = {2018}, } @inproceedings{108, abstract = {Universal hashing found a lot of applications in computer science. In cryptography the most important fact about universal families is the so called Leftover Hash Lemma, proved by Impagliazzo, Levin and Luby. In the language of modern cryptography it states that almost universal families are good extractors. In this work we provide a somewhat surprising characterization in the opposite direction. Namely, every extractor with sufficiently good parameters yields a universal family on a noticeable fraction of its inputs. Our proof technique is based on tools from extremal graph theory applied to the \'collision graph\' induced by the extractor, and may be of independent interest. We discuss possible applications to the theory of randomness extractors and non-malleable codes.}, author = {Obremski, Marciej and Skorski, Maciej}, location = {Vail, CO, USA}, publisher = {IEEE}, title = {{Inverted leftover hash lemma}}, doi = {10.1109/ISIT.2018.8437654}, volume = {2018}, year = {2018}, } @misc{9807, abstract = {Table S1. Genes with highest betweenness. Table S2. Local and Master regulators up-regulated. Table S3. Local and Master regulators down-regulated (XLSX 23 kb).}, author = {Higareda Almaraz, Juan and Karbiener, Michael and Giroud, Maude and Pauler, Florian and Gerhalter, Teresa and Herzig, Stephan and Scheideler, Marcel}, publisher = {Springer Nature}, title = {{Additional file 1: Of Norepinephrine triggers an immediate-early regulatory network response in primary human white adipocytes}}, doi = {10.6084/m9.figshare.7295339.v1}, year = {2018}, } @misc{9808, abstract = {Table S4. Counts per Gene per Million Reads Mapped. (XLSX 2751 kb).}, author = {Higareda Almaraz, Juan and Karbiener, Michael and Giroud, Maude and Pauler, Florian and Gerhalter, Teresa and Herzig, Stephan and Scheideler, Marcel}, publisher = {Springer Nature}, title = {{Additional file 3: Of Norepinephrine triggers an immediate-early regulatory network response in primary human white adipocytes}}, doi = {10.6084/m9.figshare.7295369.v1}, year = {2018}, } @misc{9810, author = {Chaudhry, Waqas and Pleska, Maros and Shah, Nilang and Weiss, Howard and Mccall, Ingrid and Meyer, Justin and Gupta, Animesh and Guet, Calin C and Levin, Bruce}, publisher = {Public Library of Science}, title = {{Numerical data used in figures}}, doi = {10.1371/journal.pbio.2005971.s008}, year = {2018}, } @misc{9811, abstract = {This document contains additional supporting evidence presented as supplemental tables. (XLSX 50Â kb)}, author = {Zapata, Luis and Pich, Oriol and Serrano, Luis and Kondrashov, Fyodor and Ossowski, Stephan and Schaefer, Martin}, publisher = {Springer Nature}, title = {{Additional file 1: Of negative selection in tumor genome evolution acts on essential cellular functions and the immunopeptidome}}, doi = {10.6084/m9.figshare.6401390.v1}, year = {2018}, } @misc{9812, abstract = {This document contains the full list of genes with their respective significance and dN/dS values. (TXT 4499Â kb)}, author = {Zapata, Luis and Pich, Oriol and Serrano, Luis and Kondrashov, Fyodor and Ossowski, Stephan and Schaefer, Martin}, publisher = {Springer Nature}, title = {{Additional file 2: Of negative selection in tumor genome evolution acts on essential cellular functions and the immunopeptidome}}, doi = {10.6084/m9.figshare.6401414.v1}, year = {2018}, } @misc{9813, abstract = {File S1 contains figures that clarify the following features: (i) effect of population size on the average number/frequency of SI classes, (ii) changes in the minimal completeness deficit in time for a single class, and (iii) diversification diagrams for all studied pathways, including the summary figure for k = 8. File S2 contains the code required for a stochastic simulation of the SLF system with an example. This file also includes the output in the form of figures and tables.}, author = {Bod'ová, Katarína and Priklopil, Tadeas and Field, David and Barton, Nicholas H and Pickup, Melinda}, publisher = {Genetics Society of America}, title = {{Supplemental material for Bodova et al., 2018}}, doi = {10.25386/genetics.6148304.v1}, year = {2018}, } @misc{9831, abstract = {Implementation of the inference method in Matlab, including three applications of the method: The first one for the model of ant motion, the second one for bacterial chemotaxis, and the third one for the motion of fish.}, author = {Bod’Ová, Katarína and Mitchell, Gabriel and Harpaz, Roy and Schneidman, Elad and Tkačik, Gašper}, publisher = {Public Library of Science}, title = {{Implementation of the inference method in Matlab}}, doi = {10.1371/journal.pone.0193049.s001}, year = {2018}, } @misc{9837, abstract = {Both classical and recent studies suggest that chromosomal inversion polymorphisms are important in adaptation and speciation. However, biases in discovery and reporting of inversions make it difficult to assess their prevalence and biological importance. Here, we use an approach based on linkage disequilibrium among markers genotyped for samples collected across a transect between contrasting habitats to detect chromosomal rearrangements de novo. We report 17 polymorphic rearrangements in a single locality for the coastal marine snail, Littorina saxatilis. Patterns of diversity in the field and of recombination in controlled crosses provide strong evidence that at least the majority of these rearrangements are inversions. Most show clinal changes in frequency between habitats, suggestive of divergent selection, but only one appears to be fixed for different arrangements in the two habitats. Consistent with widespread evidence for balancing selection on inversion polymorphisms, we argue that a combination of heterosis and divergent selection can explain the observed patterns and should be considered in other systems spanning environmental gradients.}, author = {Faria, Rui and Chaube, Pragya and Morales, Hernán E. and Larsson, Tomas and Lemmon, Alan R. and Lemmon, Emily M. and Rafajlović, Marina and Panova, Marina and Ravinet, Mark and Johannesson, Kerstin and Westram, Anja M and Butlin, Roger K.}, publisher = {Dryad}, title = {{Data from: Multiple chromosomal rearrangements in a hybrid zone between Littorina saxatilis ecotypes}}, doi = {10.5061/dryad.72cg113}, year = {2018}, } @misc{9838, abstract = {Facial shape is the basis for facial recognition and categorization. Facial features reflect the underlying geometry of the skeletal structures. Here we reveal that cartilaginous nasal capsule (corresponding to upper jaw and face) is shaped by signals generated by neural structures: brain and olfactory epithelium. Brain-derived Sonic Hedgehog (SHH) enables the induction of nasal septum and posterior nasal capsule, whereas the formation of a capsule roof is controlled by signals from the olfactory epithelium. Unexpectedly, the cartilage of the nasal capsule turned out to be important for shaping membranous facial bones during development. This suggests that conserved neurosensory structures could benefit from protection and have evolved signals inducing cranial cartilages encasing them. Experiments with mutant mice revealed that the genomic regulatory regions controlling production of SHH in the nervous system contribute to facial cartilage morphogenesis, which might be a mechanism responsible for the adaptive evolution of animal faces and snouts.}, author = {Kaucka, Marketa and Petersen, Julian and Tesarova, Marketa and Szarowska, Bara and Kastriti, Maria Eleni and Xie, Meng and Kicheva, Anna and Annusver, Karl and Kasper, Maria and Symmons, Orsolya and Pan, Leslie and Spitz, Francois and Kaiser, Jozef and Hovorakova, Maria and Zikmund, Tomas and Sunadome, Kazunori and Matise, Michael P and Wang, Hui and Marklund, Ulrika and Abdo, Hind and Ernfors, Patrik and Maire, Pascal and Wurmser, Maud and Chagin, Andrei S and Fried, Kaj and Adameyko, Igor}, publisher = {Dryad}, title = {{Data from: Signals from the brain and olfactory epithelium control shaping of the mammalian nasal capsule cartilage}}, doi = {10.5061/dryad.f1s76f2}, year = {2018}, } @misc{9840, abstract = {Herd immunity, a process in which resistant individuals limit the spread of a pathogen among susceptible hosts has been extensively studied in eukaryotes. Even though bacteria have evolved multiple immune systems against their phage pathogens, herd immunity in bacteria remains unexplored. Here we experimentally demonstrate that herd immunity arises during phage epidemics in structured and unstructured Escherichia coli populations consisting of differing frequencies of susceptible and resistant cells harboring CRISPR immunity. In addition, we develop a mathematical model that quantifies how herd immunity is affected by spatial population structure, bacterial growth rate, and phage replication rate. Using our model we infer a general epidemiological rule describing the relative speed of an epidemic in partially resistant spatially structured populations. Our experimental and theoretical findings indicate that herd immunity may be important in bacterial communities, allowing for stable coexistence of bacteria and their phages and the maintenance of polymorphism in bacterial immunity.}, author = {Payne, Pavel and Geyrhofer, Lukas and Barton, Nicholas H and Bollback, Jonathan P}, publisher = {Dryad}, title = {{Data from: CRISPR-based herd immunity limits phage epidemics in bacterial populations}}, doi = {10.5061/dryad.42n44}, year = {2018}, } @misc{9841, abstract = {Around 150 million years ago, eusocial termites evolved from within the cockroaches, 50 million years before eusocial Hymenoptera, such as bees and ants, appeared. Here, we report the 2-Gb genome of the German cockroach, Blattella germanica, and the 1.3-Gb genome of the drywood termite Cryptotermes secundus. We show evolutionary signatures of termite eusociality by comparing the genomes and transcriptomes of three termites and the cockroach against the background of 16 other eusocial and non-eusocial insects. Dramatic adaptive changes in genes underlying the production and perception of pheromones confirm the importance of chemical communication in the termites. These are accompanied by major changes in gene regulation and the molecular evolution of caste determination. Many of these results parallel molecular mechanisms of eusocial evolution in Hymenoptera. However, the specific solutions are remarkably different, thus revealing a striking case of convergence in one of the major evolutionary transitions in biological complexity.}, author = {Harrison, Mark C. and Jongepier, Evelien and Robertson, Hugh M. and Arning, Nicolas and Bitard-Feildel, Tristan and Chao, Hsu and Childers, Christopher P. and Dinh, Huyen and Doddapaneni, Harshavardhan and Dugan, Shannon and Gowin, Johannes and Greiner, Carolin and Han, Yi and Hu, Haofu and Hughes, Daniel S. T. and Huylmans, Ann K and Kemena, Carsten and Kremer, Lukas P. M. and Lee, Sandra L. and Lopez-Ezquerra, Alberto and Mallet, Ludovic and Monroy-Kuhn, Jose M. and Moser, Annabell and Murali, Shwetha C. and Muzny, Donna M. and Otani, Saria and Piulachs, Maria-Dolors and Poelchau, Monica and Qu, Jiaxin and Schaub, Florentine and Wada-Katsumata, Ayako and Worley, Kim C. and Xie, Qiaolin and Ylla, Guillem and Poulsen, Michael and Gibbs, Richard A. and Schal, Coby and Richards, Stephen and Belles, Xavier and Korb, Judith and Bornberg-Bauer, Erich}, publisher = {Dryad}, title = {{Data from: Hemimetabolous genomes reveal molecular basis of termite eusociality}}, doi = {10.5061/dryad.51d4r}, year = {2018}, } @article{9915, abstract = {The evolution of assortative mating is a key part of the speciation process. Stronger assortment, or greater divergence in mating traits, between species pairs with overlapping ranges is commonly observed, but possible causes of this pattern of reproductive character displacement are difficult to distinguish. We use a multidisciplinary approach to provide a rare example where it is possible to distinguish among hypotheses concerning the evolution of reproductive character displacement. We build on an earlier comparative analysis that illustrated a strong pattern of greater divergence in penis form between pairs of sister species with overlapping ranges than between allopatric sister-species pairs, in a large clade of marine gastropods (Littorinidae). We investigate both assortative mating and divergence in male genitalia in one of the sister-species pairs, discriminating among three contrasting processes each of which can generate a pattern of reproductive character displacement: reinforcement, reproductive interference and the Templeton effect. We demonstrate reproductive character displacement in assortative mating, but not in genital form between this pair of sister species and use demographic models to distinguish among the different processes. Our results support a model with no gene flow since secondary contact and thus favor reproductive interference as the cause of reproductive character displacement for mate choice, rather than reinforcement. High gene flow within species argues against the Templeton effect. Secondary contact appears to have had little impact on genital divergence.}, author = {Hollander, Johan and Montaño-Rendón, Mauricio and Bianco, Giuseppe and Yang, Xi and Westram, Anja M and Duvaux, Ludovic and Reid, David G. and Butlin, Roger K.}, issn = {2056-3744}, journal = {Evolution Letters}, number = {6}, pages = {557--566}, publisher = {Wiley}, title = {{Are assortative mating and genital divergence driven by reinforcement?}}, doi = {10.1002/evl3.85}, volume = {2}, year = {2018}, } @article{9917, abstract = {Adaptive divergence and speciation may happen despite opposition by gene flow. Identifying the genomic basis underlying divergence with gene flow is a major task in evolutionary genomics. Most approaches (e.g., outlier scans) focus on genomic regions of high differentiation. However, not all genomic architectures potentially underlying divergence are expected to show extreme differentiation. Here, we develop an approach that combines hybrid zone analysis (i.e., focuses on spatial patterns of allele frequency change) with system-specific simulations to identify loci inconsistent with neutral evolution. We apply this to a genome-wide SNP set from an ideally suited study organism, the intertidal snail Littorina saxatilis, which shows primary divergence between ecotypes associated with different shore habitats. We detect many SNPs with clinal patterns, most of which are consistent with neutrality. Among non-neutral SNPs, most are located within three large putative inversions differentiating ecotypes. Many non-neutral SNPs show relatively low levels of differentiation. We discuss potential reasons for this pattern, including loose linkage to selected variants, polygenic adaptation and a component of balancing selection within populations (which may be expected for inversions). Our work is in line with theory predicting a role for inversions in divergence, and emphasizes that genomic regions contributing to divergence may not always be accessible with methods purely based on allele frequency differences. These conclusions call for approaches that take spatial patterns of allele frequency change into account in other systems.}, author = {Westram, Anja M and Rafajlović, Marina and Chaube, Pragya and Faria, Rui and Larsson, Tomas and Panova, Marina and Ravinet, Mark and Blomberg, Anders and Mehlig, Bernhard and Johannesson, Kerstin and Butlin, Roger}, issn = {2056-3744}, journal = {Evolution Letters}, number = {4}, pages = {297--309}, publisher = {Wiley}, title = {{Clines on the seashore: The genomic architecture underlying rapid divergence in the face of gene flow}}, doi = {10.1002/evl3.74}, volume = {2}, year = {2018}, } @misc{9929, abstract = {The evolution of assortative mating is a key part of the speciation process. Stronger assortment, or greater divergence in mating traits, between species pairs with overlapping ranges is commonly observed, but possible causes of this pattern of reproductive character displacement are difficult to distinguish. We use a multidisciplinary approach to provide a rare example where it is possible to distinguish among hypotheses concerning the evolution of reproductive character displacement. We build on an earlier comparative analysis that illustrated a strong pattern of greater divergence in penis form between pairs of sister species with overlapping ranges than between allopatric sister-species pairs, in a large clade of marine gastropods (Littorinidae). We investigate both assortative mating and divergence in male genitalia in one of the sister-species pairs, discriminating among three contrasting processes each of which can generate a pattern of reproductive character displacement: reinforcement, reproductive interference and the Templeton effect. We demonstrate reproductive character displacement in assortative mating, but not in genital form between this pair of sister species and use demographic models to distinguish among the different processes. Our results support a model with no gene flow since secondary contact and thus favour reproductive interference as the cause of reproductive character displacement for mate choice, rather than reinforcement. High gene flow within species argues against the Templeton effect. Secondary contact appears to have had little impact on genital divergence.}, author = {Hollander, Johan and Montaño-Rendón, Mauricio and Bianco, Giuseppe and Yang, Xi and Westram, Anja M and Duvaux, Ludovic and Reid, David G. and Butlin, Roger K.}, publisher = {Dryad}, title = {{Data from: Are assortative mating and genital divergence driven by reinforcement?}}, doi = {10.5061/dryad.51sd2p5}, year = {2018}, } @misc{9930, abstract = {Adaptive divergence and speciation may happen despite opposition by gene flow. Identifying the genomic basis underlying divergence with gene flow is a major task in evolutionary genomics. Most approaches (e.g. outlier scans) focus on genomic regions of high differentiation. However, not all genomic architectures potentially underlying divergence are expected to show extreme differentiation. Here, we develop an approach that combines hybrid zone analysis (i.e. focuses on spatial patterns of allele frequency change) with system-specific simulations to identify loci inconsistent with neutral evolution. We apply this to a genome-wide SNP set from an ideally-suited study organism, the intertidal snail Littorina saxatilis, which shows primary divergence between ecotypes associated with different shore habitats. We detect many SNPs with clinal patterns, most of which are consistent with neutrality. Among non-neutral SNPs, most are located within three large putative inversions differentiating ecotypes. Many non-neutral SNPs show relatively low levels of differentiation. We discuss potential reasons for this pattern, including loose linkage to selected variants, polygenic adaptation and a component of balancing selection within populations (which may be expected for inversions). Our work is in line with theory predicting a role for inversions in divergence, and emphasises that genomic regions contributing to divergence may not always be accessible with methods purely based on allele frequency differences. These conclusions call for approaches that take spatial patterns of allele frequency change into account in other systems.}, author = {Westram, Anja M and Rafajlović, Marina and Chaube, Pragya and Faria, Rui and Larsson, Tomas and Panova, Marina and Ravinet, Mark and Blomberg, Anders and Mehlig, Bernhard and Johannesson, Kerstin and Butlin, Roger}, publisher = {Dryad}, title = {{Data from: Clines on the seashore: the genomic architecture underlying rapid divergence in the face of gene flow}}, doi = {10.5061/dryad.bp25b65}, year = {2018}, } @inproceedings{34, abstract = {Partially observable Markov decision processes (POMDPs) are widely used in probabilistic planning problems in which an agent interacts with an environment using noisy and imprecise sensors. We study a setting in which the sensors are only partially defined and the goal is to synthesize “weakest” additional sensors, such that in the resulting POMDP, there is a small-memory policy for the agent that almost-surely (with probability 1) satisfies a reachability objective. We show that the problem is NP-complete, and present a symbolic algorithm by encoding the problem into SAT instances. We illustrate trade-offs between the amount of memory of the policy and the number of additional sensors on a simple example. We have implemented our approach and consider three classical POMDP examples from the literature, and show that in all the examples the number of sensors can be significantly decreased (as compared to the existing solutions in the literature) without increasing the complexity of the policies.}, author = {Chatterjee, Krishnendu and Chemlík, Martin and Topcu, Ufuk}, location = {Delft, Netherlands}, pages = {47 -- 55}, publisher = {AAAI Press}, title = {{Sensor synthesis for POMDPs with reachability objectives}}, volume = {2018}, year = {2018}, }