@inproceedings{18308, abstract = {We study in this paper the problem of maintaining a solution to k-median and k-means clustering in a fully dynamic setting. To do so, we present an algorithm to efficiently maintain a coreset, a compressed version of the dataset, that allows easy computation of a clustering solution at query time. Our coreset algorithm has near-optimal update time of Õ(k) in general metric spaces, which reduces to Õ(d) in the Euclidean space ℝ^d. The query time is O(k²) in general metrics, and O(kd) in ℝ^d. To maintain a constant-factor approximation for k-median and k-means clustering in Euclidean space, this directly leads to an algorithm with update time Õ(d), and query time Õ(kd + k²). To maintain a O(polylog k)-approximation, the query time is reduced to Õ(kd).}, author = {La Tour, Max Dupré and Henzinger, Monika H and Saulpic, David}, booktitle = {32nd Annual European Symposium on Algorithms}, isbn = {9783959773386}, issn = {1868-8969}, location = {London, United Kingdom}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Fully dynamic k-means coreset in near-optimal update time}}, doi = {10.4230/LIPIcs.ESA.2024.100}, volume = {308}, year = {2024}, } @inproceedings{18309, abstract = {The problem of designing connectivity oracles supporting vertex failures is one of the basic data structures problems for undirected graphs. It is already well understood: previous works [Duan-Pettie STOC'10; Long-Saranurak FOCS'22] achieve query time linear in the number of failed vertices, and it is conditionally optimal as long as we require preprocessing time polynomial in the size of the graph and update time polynomial in the number of failed vertices. We revisit this problem in the paradigm of algorithms with predictions: we ask if the query time can be improved if the set of failed vertices can be predicted beforehand up to a small number of errors. More specifically, we design a data structure that, given a graph G = (V,E) and a set of vertices predicted to fail D̂ ⊆ V of size d = |D̂|, preprocesses it in time Õ(d|E|) and then can receive an update given as the symmetric difference between the predicted and the actual set of failed vertices D̂△D = (D̂ ⧵ D) ∪ (D ⧵ D̂) of size η = |D̂△D|, process it in time Õ(η⁴), and after that answer connectivity queries in G ⧵ D in time O(η). Viewed from another perspective, our data structure provides an improvement over the state of the art for the fully dynamic subgraph connectivity problem in the sensitivity setting [Henzinger-Neumann ESA'16]. We argue that the preprocessing time and query time of our data structure are conditionally optimal under standard fine-grained complexity assumptions.}, author = {Hu, Bingbing and Kosinas, Evangelos and Polak, Adam}, booktitle = {32nd Annual European Symposium on Algorithms}, isbn = {9783959773386}, issn = {1868-8969}, location = {London, United Kingdom}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Connectivity oracles for predictable vertex failures}}, doi = {10.4230/LIPIcs.ESA.2024.72}, volume = {308}, year = {2024}, } @inproceedings{18115, abstract = {We study the data selection problem, whose aim is to select a small representative subset of data that can be used to efficiently train a machine learning model. We present a new data selection approach based on k-means clustering and sensitivity sampling. Assuming access to an embedding representation of the data with respect to which the model loss is Holder continuous, our approach provably allows selecting a set of “typical” k+1/ε2 elements whose average loss corresponds to the average loss of the whole dataset, up to a multiplicative (1±ε) factor and an additive ελΦk, where Φk represents the k-means cost for the input embeddings and λ is the Holder constant. We furthermore demonstrate the performance and scalability of our approach on fine-tuning foundation models and show that it outperforms state-of-the-art methods. We also show how it can be applied on linear regression, leading to a new sampling strategy that surprisingly matches the performance of leverage score sampling, while being conceptually simpler and more scalable.}, author = {Axiotis, Kyriakos and Cohen-Addad, Vincent and Henzinger, Monika H and Jerome, Sammy and Mirrokni, Vahab and Saulpic, David and Woodruff, David P. and Wunder, Michael}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, issn = {2640-3498}, location = {Vienna, Austria}, pages = {2086--2107}, publisher = {ML Research Press}, title = {{Data-efficient learning via clustering-based sensitivity sampling: Foundation models and beyond}}, volume = {235}, year = {2024}, } @inproceedings{18503, abstract = {In 1996, Karger [Kar96] gave a startling randomized algorithm that finds a minimum-cut in a (weighted) graph in time O(m log3 n) which he termed near-linear time meaning linear (in the size of the input) times a polylogarthmic factor. In this paper, we give the first deterministic algorithm which runs in near-linear time for weighted graphs. Previously, the breakthrough results of Kawarabayashi and Thorup [KT19] gave a near-linear time algorithm for simple graphs (which was improved to have running time O(m log2 n log log n) in [HRW20].) The main technique here is a clustering procedure that perfectly preserves minimum cuts. Recently, Li [Li21] gave an m1+o(1) deterministic minimum-cut algorithm for weighted graphs; this form of running time has been termed “almost-linear”. Li uses almost-linear time deterministic expander decompositions which do not perfectly preserve minimum cuts, but he can use these clusterings to, in a sense, “derandomize” the methods of Karger. In terms of techniques, we provide a structural theorem that says there exists a sparse clustering that preserves minimum cuts in a weighted graph with o(1) error. In addition, we construct it deterministically in near linear time. This was done exactly for simple graphs in [KT19, HRW20] and with polylogarithmic error for weighted graphs in [Li21]. Extending the techniques in [KT19, HRW20] to weighted graphs presents significant challenges, and moreover, the algorithm can only polylogarithmically approximately preserve minimum cuts. A remaining challenge is to reduce the polylogarithmic-approximate clusterings to 1 + o(1/ log n)-approximate so that they can be applied recursively as in [Li21] over O(log n) many levels. This is an additional challenge that requires building on properties of tree-packings in the presence of a wide range of edge weights to, for example, find sources for local flow computations which identify minimum cuts that cross clusters.}, author = {Henzinger, Monika H and Li, Jason and Rao, Satish and Wang, Di}, booktitle = {35th Annual ACM-SIAM Symposium on Discrete Algorithms}, location = {Alexandria, VA, United States}, pages = {3089--3139}, publisher = {Society for Industrial and Applied Mathematics}, title = {{Deterministic near-linear time minimum cut in weighted graphs}}, doi = {10.1137/1.9781611977912.111}, year = {2024}, } @inproceedings{18116, abstract = {As a staple of data analysis and unsupervised learning, the problem of private clustering has been widely studied, under various privacy models. Centralized differential privacy is the first of them, and the problem has also been studied for the local and the shuffle variation. In each case, the goal is to design an algorithm that computes privately a clustering, with the smallest possible error. The study of each variation gave rise to new algorithm: the landscape of private clustering algorithm is therefore quite intricate. In this paper, we show that a 20 year-old algorithm can be slightly modified to work for any of those models. This provides a unified picture: while matching almost all previously known results, it allows us to improve some of them, and extend to a new privacy model, the continual observation setting, where the input is changing over time and the algorithm must output a new solution at each time step.}, author = {La Tour, Max Dupré and Henzinger, Monika H and Saulpic, David}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, issn = {2640-3498}, location = {Vienna, Austria}, pages = {12046--12086}, publisher = {ML Research Press}, title = {{Making old things new: A unified algorithm for differentially private clustering}}, volume = {235}, year = {2024}, } @inproceedings{15253, abstract = {We study the problem of maintaining a differentially private decaying sum under continual observation. We give a unifying framework and an efficient algorithm for this problem for any sufficiently smooth function. Our algorithm is the first differentially private algorithm that does not have a multiplicative error for polynomially decaying weights. Our algorithm improves on all prior works on differentially private decaying sums under continual observation and recovers exactly the additive error for the special case of continual counting from Henzinger et al. (SODA 2023) as a corollary. Our algorithm is a variant of the matrix mechanism whose error depends on the γ2 and γF norm of the underlying matrix. We give a constructive proof for an almost exact upper bound on the γ2 and γF norm and an almost tight lower bound on the γ2 norm for a large class of lower-triangular matrices. This is the first non-trivial lower bound for lower-triangular matrices whose non-zero entries are not all the same. It includes matrices for all continual decaying sums problems, resulting in an upper bound on the additive error of any differentially private decaying sums algorithm under continual observation. We also explore some implications of our result in discrepancy theory and operator algebra. Given the importance of the γ2 norm in computer science and the extensive work in mathematics, we believe our result will have further applications.}, author = {Henzinger, Monika H and Upadhyay, Jalaj and Upadhyay, Sarvagya}, booktitle = {Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms}, location = {Alexandria, VA, United States}, pages = {995--1018}, publisher = {Society for Industrial and Applied Mathematics}, title = {{A unifying framework for differentially private sums under continual observation}}, doi = {10.1137/1.9781611977912.38}, volume = {2024}, year = {2024}, } @inproceedings{18928, abstract = {Algorithms with predictions is a new research direction that leverages machine learned predictions for algorithm design. So far a plethora of recent works have incorporated predictions to improve on worst-case bounds for online problems. In this paper, we initiate the study of complexity of dynamic data structures with predictions, including dynamic graph algorithms. Unlike online algorithms, the goal in dynamic data structures is to maintain the solution efficiently with every update. We investigate three natural models of prediction: (1) δ-accurate predictions where each predicted request matches the true request with probability δ, (2) list-accurate predictions where a true request comes from a list of possible requests, and (3) bounded delay predictions where the true requests are a permutation of the predicted requests. We give general reductions among the prediction models, showing that bounded delay is the strongest prediction model, followed by list-accurate, and δ-accurate. Further, we identify two broad problem classes based on lower bounds due to the Online Matrix Vector (OMv) conjecture. Specifically, we show that locally correctable dynamic problems have strong conditional lower bounds for list-accurate predictions that are equivalent to the non-prediction setting, unless list-accurate predictions are perfect. Moreover, we show that locally reducible dynamic problems have time complexity that degrades gracefully with the quality of bounded delay predictions. We categorize problems with known OMv lower bounds accordingly and give several upper bounds in the delay model that show that our lower bounds are almost tight. We note that concurrent work by v.d.Brand et al. [SODA '24] and Liu and Srinivas [arXiv:2307.08890] independently study dynamic graph algorithms with predictions, but their work is mostly focused on showing upper bounds.}, author = {Henzinger, Monika H and Saha, Barna and Seybold, Martin P. and Ye, Christopher}, booktitle = {15th Innovations in Theoretical Computer Science Conference}, isbn = {9783959773096}, issn = {1868-8969}, location = {Berkeley, CA, United States}, pages = {62:1--62:25}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{On the complexity of algorithms with predictions for dynamic graph problems}}, doi = {10.4230/LIPIcs.ITCS.2024.62}, volume = {287}, year = {2024}, } @article{17479, abstract = {Phonon polaritons (PhPs), light coupled to lattice vibrations, in the highly anisotropic polar layered material molybdenum trioxide (α-MoO3) are currently the focus of intense research efforts due to their extreme subwavelength field confinement, directional propagation, and unprecedented low losses. Nevertheless, prior research has primarily concentrated on exploiting the squeezing and steering capabilities of α-MoO3 PhPs, without inquiring much into the dominant microscopic mechanism that determines their long lifetimes, which is key for their implementation in nanophotonic applications. This study delves into the fundamental processes that govern PhP damping in α-MoO3 by combining ab initio calculations with scattering-type scanning near-field optical microscopy (s-SNOM) and Fourier transform infrared (FTIR) spectroscopy measurements across a broad temperature range (8–300 K). The remarkable agreement between our theoretical predictions and experimental observations allows us to identify third-order anharmonic phonon–phonon scattering as the main damping mechanism of α-MoO3 PhPs. These findings shed light on the fundamental limits of low-loss PhPs, which is a crucial factor for assessing their implementation into nanophotonic devices.}, author = {Taboada-Gutiérrez, Javier and Zhou, Yixi and Tresguerres-Mata, Ana I.F. and Lanza, Christian and Martínez-Suárez, Abel and Álvarez-Pérez, Gonzalo and Duan, Jiahua and Martín, José Ignacio and Vélez, María and Prieto Gonzalez, Ivan and Bercher, Adrien and Teyssier, Jérémie and Errea, Ion and Nikitin, Alexey Y. and Martín-Sánchez, Javier and Kuzmenko, Alexey B. and Alonso-González, Pablo}, issn = {2330-4022}, journal = {ACS Photonics}, number = {9}, pages = {3570--3577}, publisher = {American Chemical Society}, title = {{Unveiling the mechanism of phonon-polariton damping in α‑MoO3}}, doi = {10.1021/acsphotonics.4c00485}, volume = {11}, year = {2024}, } @inproceedings{18906, abstract = {Expander decompositions of graphs have significantly advanced the understanding of many classical graph problems and led to numerous fundamental theoretical results. However, their adoption in practice has been hindered due to their inherent intricacies and large hidden factors in their asymptotic running times. Here, we introduce the first practically efficient algorithm for computing expander decompositions and their hierarchies and demonstrate its effectiveness and utility by incorporating it as the core component in a novel solver for the normalized cut graph clustering objective. Our extensive experiments on a variety of large graphs show that our expander-based algorithm outperforms state-of-the-art solvers for normalized cut with respect to solution quality by a large margin on a variety of graph classes such as citation, e-mail, and social networks or web graphs while remaining competitive in running time.}, author = {Hanauer, Kathrin and Henzinger, Monika H and Münk, Robin and Räcke, Harald and Vötsch, Maximilian}, booktitle = {Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining}, isbn = {9798400704901}, location = {Barcelona, Spain}, pages = {1016--1027}, publisher = {ACM}, title = {{Expander hierarchies for normalized cuts on graphs}}, doi = {10.1145/3637528.3671978}, year = {2024}, } @article{17188, abstract = {In a delegation problem, a principal P with commitment power tries to pick one out of 𝑛 options. Each option is drawn independently from a known distribution. Instead of inspecting the options herself, P delegates the information acquisition to a rational and self-interested agent A. After inspection, A proposes one of the options, and P can accept or reject. Delegation is a classic setting in economic information design with many prominent applications, but the computational problems are only poorly understood. In this paper, we study a natural online variant of delegation, in which the agent searches through the options in an online fashion. For each option, he has to irrevocably decide if he wants to propose the current option or discard it, before seeing information on the next option(s). How can we design algorithms for P that approximate the utility of her best option in hindsight? We show that in general P can obtain a Θ(1∕𝑛)-approximation and extend this result to ratios of Θ(𝑘∕𝑛) in case (1) A has a lookahead of 𝑘 rounds, or (2) A can propose up to 𝑘 different options. We provide fine-grained bounds independent of 𝑛 based on three parameters. If the ratio of maximum and minimum utility for A is bounded by a factor 𝛼, we obtain an Ω(loglog 𝛼∕ log 𝛼)- approximation algorithm, and we show that this is best possible. Additionally, if P cannot distinguish options with the same value for herself, we show that ratios polynomial in 1∕𝛼 cannot be avoided. If there are at most 𝛽 different utility values for A, we show a Θ(1∕𝛽)-approximation. If the utilities of P and A for each option are related by a factor 𝛾, we obtain an Ω(1∕ log 𝛾)- approximation, where 𝑂(log log 𝛾∕ log 𝛾) is best possible.}, author = {Braun, Pirmin and Hahn, Niklas and Hoefer, Martin and Schecker, Conrad}, issn = {0004-3702}, journal = {Artificial Intelligence}, publisher = {Elsevier}, title = {{Delegated online search}}, doi = {10.1016/j.artint.2024.104171}, volume = {334}, year = {2024}, } @article{17238, abstract = {We know that heritable variation is abundant, and that selection causes all but the smallest populations to rapidly shift beyond their original trait distribution. So then, what limits the range of a species? There are physical constraints and also population genetic limits to the effectiveness of selection, ultimately set by population size. Global adaptation, where the same genotype is favoured over the whole range, is most efficient when based on a multitude of weakly selected alleles and is effective even when local demes are small, provided that there is some gene flow. In contrast, local adaptation is sensitive to gene flow and may require alleles with substantial effect. How can populations combine the advantages of large effective size with the ability to specialise into local niches? To what extent does reproductive isolation help resolve this tension? I address these questions using eco-evolutionary models of polygenic adaptation, contrasting discrete demes with continuousspace.}, author = {Barton, Nicholas H}, issn = {1420-9101}, journal = {Journal of Evolutionary Biology}, number = {6}, pages = {605--615}, publisher = {Oxford University Press}, title = {{Limits to species' range: The tension between local and global adaptation}}, doi = {10.1093/jeb/voae052}, volume = {37}, year = {2024}, } @article{17237, abstract = {The impact of climate change on populations will be contingent upon their contemporary adaptive evolution. In this study, we investigated the contemporary evolution of 4 populations of the cold-water kelp Laminaria digitata by analyzing their spatial and temporal genomic variations using ddRAD-sequencing. These populations were sampled from the center to the southern margin of its north-eastern Atlantic distribution at 2 time points, spanning at least 2 generations. Through genome scans for local adaptation at a single time point, we identified candidate loci that showed clinal variation correlated with changes in sea surface temperature (SST) along latitudinal gradients. This finding suggests that SST may drive the adaptive response of these kelp populations, although factors such as species’ demographic history should also be considered. Additionally, we performed a simulation approach to distinguish the effect of selection from genetic drift in allele frequency changes over time. This enabled the detection of loci in the southernmost population that exhibited temporal differentiation beyond what would be expected from genetic drift alone: these are candidate loci which could have evolved under selection over time. In contrast, we did not detect any outlier locus based on temporal differentiation in the population from the North Sea, which also displayed low and decreasing levels of genetic diversity. The diverse evolutionary scenarios observed among populations can be attributed to variations in the prevalence of selection relative to genetic drift across different environments. Therefore, our study highlights the potential of temporal genomics to offer valuable insights into the contemporary evolution of marine foundation species facing climate change.}, author = {Reynes, Lauric and Fouqueau, Louise and Aurelle, Didier and Mauger, Stephane and Destombe, Christophe and Valero, Myriam}, issn = {1420-9101}, journal = {Journal of Evolutionary Biology}, number = {6}, pages = {677--692}, publisher = {Oxford University Press}, title = {{Temporal genomics help in deciphering neutral and adaptive patterns in the contemporary evolution of kelp populations}}, doi = {10.1093/jeb/voae048}, volume = {37}, year = {2024}, } @inproceedings{18922, abstract = {Let G be a directed graph with m edges and n vertices. We present a deterministic linear-time algorithm for computing the 3-edge-connected components of G. This is a significant improvement over the previous best bound by Georgiadis et al. [SODA 2023], which is Õ(m√{m}) and randomized. Our result is based on a novel characterization of 2-edge cuts in directed graphs and on a new technique that exploits the concept of divergent spanning trees and 2-connectivity-light graphs, and requires a careful modification of the minset-poset technique of Gabow [TALG 2016]. As a side result, our new technique yields also an oracle for providing in constant time a minimum edge-cut for any two vertices that are not 3-edge-connected. The oracle uses space O(n) and can be built in O(mlog n) time: given two query vertices, it determines in constant time whether they are 3-edge-connected, or provides a k-edge cut, with k≤ 2, that separates them.}, author = {Georgiadis, Loukas and Italiano, Giuseppe F. and Kosinas, Evangelos}, booktitle = {65th Annual Symposium on Foundations of Computer Science}, isbn = {9798331516741}, location = {Chicago, IL, United States}, pages = {62--85}, publisher = {IEEE}, title = {{Computing the 3-edge-connected components of directed graphs in linear time}}, doi = {10.1109/focs61266.2024.00015}, year = {2024}, } @article{17207, author = {Fouqueau, Louise and Polechova, Jitka}, issn = {1420-9101}, journal = {Journal of evolutionary biology}, number = {6}, pages = {579--587}, publisher = {Oxford University Press}, title = {{Eco-evolutionary dynamics in changing environments: Integrating theory with data}}, doi = {10.1093/jeb/voae067}, volume = {37}, year = {2024}, } @article{17888, abstract = {Context: Biotic resource exploitation is a critical determinant of species’ distributions. However, quantifying resource exploitation patterns through space and time can be difficult, complicating their incorporation in spatial ecology studies. Therefore, understanding the local drivers of spatial patterns of resource exploitation may contribute to better large-scale species distribution models. Objectives: We investigated (1) how the resource exploitation patterns of two trophic interactions (plant–insect) are explained by insect behaviour, resource aggregation, and potential insect-insect interactions. We also analyzed how (2) resource patch size and (3) resource accessibility in a heterogeneous landscape affected host exploitation patterns. Methods: We quantified nectar robbing by insects in the genus Bombus (bumblebees) and seed predation by Brachypterolus vestitus larvae (Antirrhinum beetle) on Antirrhinum majus L. (wild snapdragons) in the Pyrenees Mountains, Catalonia, Spain. We tested hypotheses about resource exploitation by integrating spatial analyses at multiple scales. Results: Both trophic interactions were aggregated, explained by the aggregation of their resource. At some scales, nectar robbing is more aggregated than the resource. Trophic interaction abundance is proportional to resource patch size, following the ideal free distribution model. Landscape features do not explain the locations exploited. Nectar robbing and seed predation occur together more often than expected. Conclusions: Our findings suggest that multiple biotic and ecological spatial factors may simultaneously affect resource exploitation at a local scale. These findings should be considered when developing agricultural projects, management plans and conservation policies.}, author = {Pocull Belles, Guillem and Baskett, Carina and Barton, Nicholas H}, issn = {1572-9761}, journal = {Landscape Ecology}, number = {9}, publisher = {Springer Nature}, title = {{Multiscale spatial analysis of two plant–insect interactions: Effects of landscape, resource distribution, and other insects}}, doi = {10.1007/s10980-024-01899-9}, volume = {39}, year = {2024}, } @article{14850, abstract = {Elaborate sexual signals are thought to have evolved and be maintained to serve as honest indicators of signaller quality. One measure of quality is health, which can be affected by parasite infection. Cnemaspis mysoriensis is a diurnal gecko that is often infested with ectoparasites in the wild, and males of this species express visual (coloured gular patches) and chemical (femoral gland secretions) traits that receivers could assess during social interactions. In this paper, we tested whether ectoparasites affect individual health, and whether signal quality is an indicator of ectoparasite levels. In wild lizards, we found that ectoparasite level was negatively correlated with body condition in both sexes. Moreover, some characteristics of both visual and chemical traits in males were strongly associated with ectoparasite levels. Specifically, males with higher ectoparasite levels had yellow gular patches with lower brightness and chroma, and chemical secretions with a lower proportion of aromatic compounds. We then determined whether ectoparasite levels in males influence female behaviour. Using sequential choice trials, wherein females were provided with either the visual or the chemical signals of wild-caught males that varied in ectoparasite level, we found that only chemical secretions evoked an elevated female response towards less parasitised males. Simultaneous choice trials in which females were exposed to the chemical secretions from males that varied in parasite level further confirmed a preference for males with lower parasites loads. Overall, we find that although health (body condition) or ectoparasite load can be honestly advertised through multiple modalities, the parasite-mediated female response is exclusively driven by chemical signals.}, author = {Pal, Arka and Joshi, Mihir and Thaker, Maria}, issn = {0022-0949}, journal = {Journal of Experimental Biology}, keywords = {Insect Science, Molecular Biology, Animal Science and Zoology, Aquatic Science, Physiology, Ecology, Evolution, Behavior and Systematics}, number = {1}, publisher = {The Company of Biologists}, title = {{Too much information? Males convey parasite levels using more signal modalities than females utilise}}, doi = {10.1242/jeb.246217}, volume = {227}, year = {2024}, } @article{15358, abstract = {We consider how a population of N haploid individuals responds to directional selection on standing variation, with no new variation from recombination or mutation. Individuals have trait values z1,…,zN, which are drawn from a distribution ψ; the fitness of individual i is proportional to [Formula: see text] . For illustration, we consider the Laplace and Gaussian distributions, which are parametrised only by the variance V0, and show that for large N, there is a scaling limit which depends on a single parameter NV0. When selection is weak relative to drift (NV0≪1), the variance decreases exponentially at rate 1/N, and the expected ultimate gain in log fitness (scaled by V0), is just NV0, which is the same as Robertson's (1960) prediction for a sexual population. In contrast, when selection is strong relative to drift (NV0≫1), the ultimate gain can be found by approximating the establishment of alleles by a branching process in which each allele competes independently with the population mean and the fittest allele to establish is certain to fix. Then, if the probability of survival to time t∼1/V0 of an allele with value z is P(z), with mean P¯, the winning allele is the fittest of NP¯ survivors drawn from a distribution ψP/P¯. The expected ultimate change is ∼2log(1.15NV0) for a Gaussian distribution, and ∼-12log0.36NV0-log-log0.36NV0 for a Laplace distribution. This approach also predicts the variability of the process, and its dynamics; we show that in the strong selection regime, the expected genetic variance decreases as ∼t-3 at large times. We discuss how these results may be related to selection on standing variation that is spread along a linear chromosome.}, author = {Barton, Nicholas H and Sachdeva, Himani}, issn = {1096-0325}, journal = {Theoretical Population Biology}, pages = {129--137}, publisher = {Elsevier}, title = {{Limits to selection on standing variation in an asexual population}}, doi = {10.1016/j.tpb.2024.04.001}, volume = {157}, year = {2024}, } @article{15099, abstract = {Speciation is a key evolutionary process that is not yet fully understood. Combining population genomic and ecological data from multiple diverging pairs of marine snails (Littorina) supports the search for speciation mechanisms. Placing pairs on a one-dimensional speciation continuum, from undifferentiated populations to species, obscured the complexity of speciation. Adding multiple axes helped to describe either speciation routes or reproductive isolation in the snails. Divergent ecological selection repeatedly generated barriers between ecotypes, but appeared less important in completing speciation while genetic incompatibilities played a key role. Chromosomal inversions contributed to genomic barriers, but with variable impact. A multidimensional (hypercube) approach supported framing of questions and identification of knowledge gaps and can be useful to understand speciation in many other systems.}, author = {Johannesson, Kerstin and Faria, Rui and Le Moan, Alan and Rafajlović, Marina and Westram, Anja M and Butlin, Roger K. and Stankowski, Sean}, issn = {1362-4555}, journal = {Trends in Genetics}, number = {4}, pages = {337--351}, publisher = {Elsevier}, title = {{Diverse pathways to speciation revealed by marine snails}}, doi = {10.1016/j.tig.2024.01.002}, volume = {40}, year = {2024}, } @article{18949, abstract = {Speciation research—the scientific field focused on understanding the origin and diversity of species—has a long and complex history. While relevant to one another, the specific goals and activities of speciation researchers are highly diverse, and scattered across a collection of different perspectives. Thus, our understanding of speciation will benefit from efforts to bridge scientific findings and the diverse people who do the work. In this paper, we outline two ways of integrating speciation research: (i) scientific integration, through the bringing together of ideas, data, and approaches; and (ii) social integration, by creating ways for a diversity of researchers to participate in the scientific process. We then discuss five challenges to integration: (i) the multidisciplinary nature of speciation research, (ii) the complex language of speciation; (iii) a bias toward certain study systems; (iv) the challenges of working across scales; and (v) inconsistent measures and reporting standards. We provide practical steps that individuals and groups can take to help overcome these challenges, and argue that integration is a team effort in which we all have a role to play.}, author = {Stankowski, Sean and Cutter, Asher D and Satokangas, Ina and Lerch, Brian A and Rolland, Jonathan and Smadja, Carole M and Segami Marzal, J Carolina and Cooney, Christopher R and Feulner, Philine G D and Domingos, Fabricius Maia Chaves Bicalho and North, Henry L and Yamaguchi, Ryo and Butlin, Roger K and Wolf, Jochen B W and Coughlan, Jenn and Heidbreder, Patrick and Hernández-Gutiérrez, Rebeca and Barnard-Kubow, Karen B and Peede, David and Rancilhac, Loïs and Salvador, Rodrigo Brincalepe and Thompson, Ken A and Stacy, Elizabeth A and Moyle, Leonie C and Garlovsky, Martin D and Maulana, Arif and Kantelinen, Annina and Cacho, N Ivalú and Schneemann, Hilde and Domínguez, Marisol and Dopman, Erik B and Lohse, Konrad and Rometsch, Sina J and Comeault, Aaron A and Merrill, Richard M and Scordato, Elizabeth S C and Singhal, Sonal and Pärssinen, Varpu and Lackey, Alycia C R and Kumar, Sanghamitra and Meier, Joana I and Barton, Nicholas H and Fraisse, Christelle and Ravinet, Mark and Kulmuni, Jonna}, issn = {2752-938X}, journal = {Evolutionary Journal of the Linnean Society}, number = {1}, publisher = {Oxford University Press}, title = {{Toward the integration of speciation research}}, doi = {10.1093/evolinnean/kzae001}, volume = {3}, year = {2024}, } @article{18908, abstract = {Chromosomal rearrangements can lead to the coupling of reproductive barriers, but whether and how they contribute to the completion of speciation remains unclear. Marine snails of the genus Littorina repeatedly form hybrid zones between populations segregating for multiple inversion arrangements, providing opportunities to study their barrier effects. Here, we analyzed 2 adjacent transects across hybrid zones between 2 ecotypes of Littorina fabalis (“large” and “dwarf”) adapted to different wave exposure conditions on a Swedish island. Applying whole-genome sequencing, we found 12 putative inversions on 9 of 17 chromosomes. Nine of the putative inversions reached near differential fixation between the 2 ecotypes, and all were in strong linkage disequilibrium. These inversions cover 20% of the genome and carry 93% of divergent single nucleotide polymorphisms (SNPs). Bimodal hybrid zones in both transects indicated that the 2 ecotypes of Littorina fabalis maintain their genetic and phenotypic integrity following contact. The bimodality reflects the strong coupling between inversion clines and the extension of the barrier effect across the whole genome. Demographic inference suggests that coupling arose during a period of allopatry and has been maintained for > 1,000 generations after secondary contact. Overall, this study shows that the coupling of multiple chromosomal inversions contributes to strong reproductive isolation. Notably, 2 of the putative inversions overlap with inverted genomic regions associated with ecotype differences in a closely related species (Littorina saxatilis), suggesting the same regions, with similar structural variants, repeatedly contribute to ecotype evolution in distinct species.}, author = {Le Moan, Alan and Stankowski, Sean and Rafajlović, Marina and Ortega-Martinez, Olga and Faria, Rui and Butlin, Roger K and Johannesson, Kerstin}, issn = {2056-3744}, journal = {Evolution Letters}, number = {4}, pages = {575--586}, publisher = {Oxford University Press}, title = {{Coupling of twelve putative chromosomal inversions maintains a strong barrier to gene flow between snail ecotypes}}, doi = {10.1093/evlett/qrae014}, volume = {8}, year = {2024}, }