@inproceedings{7123, abstract = {Population protocols are a popular model of distributed computing, in which n agents with limited local state interact randomly, and cooperate to collectively compute global predicates. Inspired by recent developments in DNA programming, an extensive series of papers, across different communities, has examined the computability and complexity characteristics of this model. Majority, or consensus, is a central task in this model, in which agents need to collectively reach a decision as to which one of two states A or B had a higher initial count. Two metrics are important: the time that a protocol requires to stabilize to an output decision, and the state space size that each agent requires to do so. It is known that majority requires Ω(log log n) states per agent to allow for fast (poly-logarithmic time) stabilization, and that O(log2 n) states are sufficient. Thus, there is an exponential gap between the space upper and lower bounds for this problem. This paper addresses this question. On the negative side, we provide a new lower bound of Ω(log n) states for any protocol which stabilizes in O(n1–c) expected time, for any constant c > 0. This result is conditional on monotonicity and output assumptions, satisfied by all known protocols. Technically, it represents a departure from previous lower bounds, in that it does not rely on the existence of dense configurations. Instead, we introduce a new generalized surgery technique to prove the existence of incorrect executions for any algorithm which would contradict the lower bound. Subsequently, our lower bound also applies to general initial configurations, including ones with a leader. On the positive side, we give a new algorithm for majority which uses O(log n) states, and stabilizes in O(log2 n) expected time. Central to the algorithm is a new leaderless phase clock technique, which allows agents to synchronize in phases of Θ(n log n) consecutive interactions using O(log n) states per agent, exploiting a new connection between population protocols and power-of-two-choices load balancing mechanisms. We also employ our phase clock to build a leader election algorithm with a state space of size O(log n), which stabilizes in O(log2 n) expected time.}, author = {Alistarh, Dan-Adrian and Aspnes, James and Gelashvili, Rati}, booktitle = {Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms}, isbn = {9781611975031}, location = {New Orleans, LA, United States}, pages = {2221--2239}, publisher = {ACM}, title = {{Space-optimal majority in population protocols}}, doi = {10.1137/1.9781611975031.144}, 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}, } @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{8618, abstract = {The reversibly switchable fluorescent proteins (RSFPs) commonly used for RESOLFT nanoscopy have been developed from fluorescent proteins of the GFP superfamily. These proteins are bright, but exhibit several drawbacks such as relatively large size, oxygen-dependence, sensitivity to low pH, and limited switching speed. Therefore, RSFPs from other origins with improved properties need to be explored. Here, we report the development of two RSFPs based on the LOV domain of the photoreceptor protein YtvA from Bacillus subtilis. LOV domains obtain their fluorescence by association with the abundant cellular cofactor flavin mononucleotide (FMN). Under illumination with blue and ultraviolet light, they undergo a photocycle, making these proteins inherently photoswitchable. Our first improved variant, rsLOV1, can be used for RESOLFT imaging, whereas rsLOV2 proved useful for STED nanoscopy of living cells with a resolution of down to 50 nm. In addition to their smaller size compared to GFP-related proteins (17 kDa instead of 27 kDa) and their usability at low pH, rsLOV1 and rsLOV2 exhibit faster switching kinetics, switching on and off 3 times faster than rsEGFP2, the fastest-switching RSFP reported to date. Therefore, LOV-domain-based RSFPs have potential for applications where the switching speed of GFP-based proteins is limiting.}, author = {Gregor, Carola and Sidenstein, Sven C. and Andresen, Martin and Sahl, Steffen J. and Danzl, Johann G and Hell, Stefan W.}, issn = {2045-2322}, journal = {Scientific Reports}, keywords = {Multidisciplinary}, publisher = {Springer Nature}, title = {{Novel reversibly switchable fluorescent proteins for RESOLFT and STED nanoscopy engineered from the bacterial photoreceptor YtvA}}, doi = {10.1038/s41598-018-19947-1}, volume = {8}, year = {2018}, } @article{10881, abstract = {Strigolactones (SLs) are a relatively recent addition to the list of plant hormones that control different aspects of plant development. SL signalling is perceived by an α/β hydrolase, DWARF 14 (D14). A close homolog of D14, KARRIKIN INSENSTIVE2 (KAI2), is involved in perception of an uncharacterized molecule called karrikin (KAR). Recent studies in Arabidopsis identified the SUPPRESSOR OF MAX2 1 (SMAX1) and SMAX1-LIKE 7 (SMXL7) to be potential SCF–MAX2 complex-mediated proteasome targets of KAI2 and D14, respectively. Genetic studies on SMXL7 and SMAX1 demonstrated distinct developmental roles for each, but very little is known about these repressors in terms of their sequence features. In this study, we performed an extensive comparative analysis of SMXLs and determined their phylogenetic and evolutionary history in the plant lineage. Our results show that SMXL family members can be sub-divided into four distinct phylogenetic clades/classes, with an ancient SMAX1. Further, we identified the clade-specific motifs that have evolved and that might act as determinants of SL-KAR signalling specificity. These specificities resulted from functional diversities among the clades. Our results suggest that a gradual co-evolution of SMXL members with their upstream receptors D14/KAI2 provided an increased specificity to both the SL perception and response in land plants.}, author = {Moturu, Taraka Ramji and Thula, Sravankumar and Singh, Ravi Kumar and Nodzyński, Tomasz and Vařeková, Radka Svobodová and Friml, Jiří and Simon, Sibu}, issn = {1460-2431}, journal = {Journal of Experimental Botany}, keywords = {Plant Science, Physiology}, number = {9}, pages = {2367--2378}, publisher = {Oxford University Press}, title = {{Molecular evolution and diversification of the SMXL gene family}}, doi = {10.1093/jxb/ery097}, volume = {69}, year = {2018}, } @article{10880, abstract = {Acquisition of evolutionary novelties is a fundamental process for adapting to the external environment and invading new niches and results in the diversification of life, which we can see in the world today. How such novel phenotypic traits are acquired in the course of evolution and are built up in developing embryos has been a central question in biology. Whole-genome duplication (WGD) is a process of genome doubling that supplies raw genetic materials and increases genome complexity. Recently, it has been gradually revealed that WGD and subsequent fate changes of duplicated genes can facilitate phenotypic evolution. Here, we review the current understanding of the relationship between WGD and the acquisition of evolutionary novelties. We show some examples of this link and discuss how WGD and subsequent duplicated genes can facilitate phenotypic evolution as well as when such genomic doubling can be advantageous for adaptation.}, author = {Yuuta, Moriyama and Koshiba-Takeuchi, Kazuko}, issn = {2041-2657}, journal = {Briefings in Functional Genomics}, keywords = {Genetics, Molecular Biology, Biochemistry, General Medicine}, number = {5}, pages = {329--338}, publisher = {Oxford University Press}, title = {{Significance of whole-genome duplications on the emergence of evolutionary novelties}}, doi = {10.1093/bfgp/ely007}, volume = {17}, 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}, } @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}, } @inproceedings{10882, abstract = {We introduce Intelligent Annotation Dialogs for bounding box annotation. We train an agent to automatically choose a sequence of actions for a human annotator to produce a bounding box in a minimal amount of time. Specifically, we consider two actions: box verification [34], where the annotator verifies a box generated by an object detector, and manual box drawing. We explore two kinds of agents, one based on predicting the probability that a box will be positively verified, and the other based on reinforcement learning. We demonstrate that (1) our agents are able to learn efficient annotation strategies in several scenarios, automatically adapting to the image difficulty, the desired quality of the boxes, and the detector strength; (2) in all scenarios the resulting annotation dialogs speed up annotation compared to manual box drawing alone and box verification alone, while also outperforming any fixed combination of verification and drawing in most scenarios; (3) in a realistic scenario where the detector is iteratively re-trained, our agents evolve a series of strategies that reflect the shifting trade-off between verification and drawing as the detector grows stronger.}, author = {Uijlings, Jasper and Konyushkova, Ksenia and Lampert, Christoph and Ferrari, Vittorio}, booktitle = {2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition}, isbn = {9781538664209}, issn = {2575-7075}, location = {Salt Lake City, UT, United States}, pages = {9175--9184}, publisher = {IEEE}, title = {{Learning intelligent dialogs for bounding box annotation}}, doi = {10.1109/cvpr.2018.00956}, year = {2018}, } @inproceedings{6558, abstract = {This paper studies the problem of distributed stochastic optimization in an adversarial setting where, out of m machines which allegedly compute stochastic gradients every iteration, an α-fraction are Byzantine, and may behave adversarially. Our main result is a variant of stochastic gradient descent (SGD) which finds ε-approximate minimizers of convex functions in T=O~(1/ε²m+α²/ε²) iterations. In contrast, traditional mini-batch SGD needs T=O(1/ε²m) iterations, but cannot tolerate Byzantine failures. Further, we provide a lower bound showing that, up to logarithmic factors, our algorithm is information-theoretically optimal both in terms of sample complexity and time complexity.}, author = {Alistarh, Dan-Adrian and Allen-Zhu, Zeyuan and Li, Jerry}, booktitle = {Advances in Neural Information Processing Systems}, location = {Montreal, Canada}, pages = {4613--4623}, publisher = {Neural Information Processing Systems Foundation}, title = {{Byzantine stochastic gradient descent}}, volume = {2018}, year = {2018}, }