TY - CONF AB - Determining the degree of inherent parallelism in classical sequential algorithms and leveraging it for fast parallel execution is a key topic in parallel computing, and detailed analyses are known for a wide range of classical algorithms. In this paper, we perform the first such analysis for the fundamental Union-Find problem, in which we are given a graph as a sequence of edges, and must maintain its connectivity structure under edge additions. We prove that classic sequential algorithms for this problem are well-parallelizable under reasonable assumptions, addressing a conjecture by [Blelloch, 2017]. More precisely, we show via a new potential argument that, under uniform random edge ordering, parallel union-find operations are unlikely to interfere: T concurrent threads processing the graph in parallel will encounter memory contention O(T2 · log |V| · log |E|) times in expectation, where |E| and |V| are the number of edges and nodes in the graph, respectively. We leverage this result to design a new parallel Union-Find algorithm that is both internally deterministic, i.e., its results are guaranteed to match those of a sequential execution, but also work-efficient and scalable, as long as the number of threads T is O(|E|1 over 3 - ε), for an arbitrarily small constant ε > 0, which holds for most large real-world graphs. We present lower bounds which show that our analysis is close to optimal, and experimental results suggesting that the performance cost of internal determinism is limited. AU - Fedorov, Alexander AU - Hashemi, Diba AU - Nadiradze, Giorgi AU - Alistarh, Dan-Adrian ID - 13262 SN - 9781450395458 T2 - Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures TI - Provably-efficient and internally-deterministic parallel Union-Find ER - TY - JOUR AB - Understanding population divergence that eventually leads to speciation is essential for evolutionary biology. High species diversity in the sea was regarded as a paradox when strict allopatry was considered necessary for most speciation events because geographical barriers seemed largely absent in the sea, and many marine species have high dispersal capacities. Combining genome-wide data with demographic modelling to infer the demographic history of divergence has introduced new ways to address this classical issue. These models assume an ancestral population that splits into two subpopulations diverging according to different scenarios that allow tests for periods of gene flow. Models can also test for heterogeneities in population sizes and migration rates along the genome to account, respectively, for background selection and selection against introgressed ancestry. To investigate how barriers to gene flow arise in the sea, we compiled studies modelling the demographic history of divergence in marine organisms and extracted preferred demographic scenarios together with estimates of demographic parameters. These studies show that geographical barriers to gene flow do exist in the sea but that divergence can also occur without strict isolation. Heterogeneity of gene flow was detected in most population pairs suggesting the predominance of semipermeable barriers during divergence. We found a weak positive relationship between the fraction of the genome experiencing reduced gene flow and levels of genome-wide differentiation. Furthermore, we found that the upper bound of the ‘grey zone of speciation’ for our dataset extended beyond that found before, implying that gene flow between diverging taxa is possible at higher levels of divergence than previously thought. Finally, we list recommendations for further strengthening the use of demographic modelling in speciation research. These include a more balanced representation of taxa, more consistent and comprehensive modelling, clear reporting of results and simulation studies to rule out nonbiological explanations for general results. AU - De Jode, Aurélien AU - Le Moan, Alan AU - Johannesson, Kerstin AU - Faria, Rui AU - Stankowski, Sean AU - Westram, Anja M AU - Butlin, Roger K. AU - Rafajlović, Marina AU - Fraisse, Christelle ID - 11479 IS - 2 JF - Evolutionary Applications TI - Ten years of demographic modelling of divergence and speciation in the sea VL - 16 ER - TY - JOUR AB - In this article, we develop two independent and new approaches to model epidemic spread in a network. Contrary to the most studied models, those developed here allow for contacts with different probabilities of transmitting the disease (transmissibilities). We then examine each of these models using some mean field type approximations. The first model looks at the late-stage effects of an epidemic outbreak and allows for the computation of the probability that a given vertex was infected. This computation is based on a mean field approximation and only depends on the number of contacts and their transmissibilities. This approach shares many similarities with percolation models in networks. The second model we develop is a dynamic model which we analyze using a mean field approximation which highly reduces the dimensionality of the system. In particular, the original system which individually analyses each vertex of the network is reduced to one with as many equations as different transmissibilities. Perhaps the greatest contribution of this article is the observation that, in both these models, the existence and size of an epidemic outbreak are linked to the properties of a matrix which we call the R-matrix. This is a generalization of the basic reproduction number which more precisely characterizes the main routes of infection. AU - Gómez, Arturo AU - Oliveira, Goncalo ID - 12329 JF - Scientific Reports TI - New approaches to epidemic modeling on networks VL - 13 ER - TY - JOUR AB - We determine an asymptotic formula for the number of integral points of bounded height on a blow-up of P3 outside certain planes using universal torsors. AU - Wilsch, Florian Alexander ID - 9034 IS - 8 JF - International Mathematics Research Notices SN - 1073-7928 TI - Integral points of bounded height on a log Fano threefold VL - 2023 ER - TY - JOUR AB - Hosts can carry many viruses in their bodies, but not all of them cause disease. We studied ants as a social host to determine both their overall viral repertoire and the subset of actively infecting viruses across natural populations of three subfamilies: the Argentine ant (Linepithema humile, Dolichoderinae), the invasive garden ant (Lasius neglectus, Formicinae) and the red ant (Myrmica rubra, Myrmicinae). We used a dual sequencing strategy to reconstruct complete virus genomes by RNA-seq and to simultaneously determine the small interfering RNAs (siRNAs) by small RNA sequencing (sRNA-seq), which constitute the host antiviral RNAi immune response. This approach led to the discovery of 41 novel viruses in ants and revealed a host ant-specific RNAi response (21 vs. 22 nt siRNAs) in the different ant species. The efficiency of the RNAi response (sRNA/RNA read count ratio) depended on the virus and the respective ant species, but not its population. Overall, we found the highest virus abundance and diversity per population in Li. humile, followed by La. neglectus and M. rubra. Argentine ants also shared a high proportion of viruses between populations, whilst overlap was nearly absent in M. rubra. Only one of the 59 viruses was found to infect two of the ant species as hosts, revealing high host-specificity in active infections. In contrast, six viruses actively infected one ant species, but were found as contaminants only in the others. Disentangling spillover of disease-causing infection from non-infecting contamination across species is providing relevant information for disease ecology and ecosystem management. AU - Viljakainen, Lumi AU - Fürst, Matthias AU - Grasse, Anna V AU - Jurvansuu, Jaana AU - Oh, Jinook AU - Tolonen, Lassi AU - Eder, Thomas AU - Rattei, Thomas AU - Cremer, Sylvia ID - 12469 JF - Frontiers in Microbiology TI - Antiviral immune response reveals host-specific virus infections in natural ant populations VL - 14 ER - TY - JOUR AB - We present criteria for establishing a triangulation of a manifold. Given a manifold M, a simplicial complex A, and a map H from the underlying space of A to M, our criteria are presented in local coordinate charts for M, and ensure that H is a homeomorphism. These criteria do not require a differentiable structure, or even an explicit metric on M. No Delaunay property of A is assumed. The result provides a triangulation guarantee for algorithms that construct a simplicial complex by working in local coordinate patches. Because the criteria are easily verified in such a setting, they are expected to be of general use. AU - Boissonnat, Jean-Daniel AU - Dyer, Ramsay AU - Ghosh, Arijit AU - Wintraecken, Mathijs ID - 12287 JF - Discrete & Computational Geometry KW - Computational Theory and Mathematics KW - Discrete Mathematics and Combinatorics KW - Geometry and Topology KW - Theoretical Computer Science SN - 0179-5376 TI - Local criteria for triangulating general manifolds VL - 69 ER - TY - JOUR AB - It may come as a surprise that a phenomenon as ubiquitous and prominent as the transition from laminar to turbulent flow has resisted combined efforts by physicists, engineers and mathematicians, and remained unresolved for almost one and a half centuries. In recent years, various studies have proposed analogies to directed percolation, a well-known universality class in statistical mechanics, which describes a non-equilibrium phase transition from a fluctuating active phase into an absorbing state. It is this unlikely relation between the multiscale, high-dimensional dynamics that signify the transition process in virtually all flows of practical relevance, and the arguably most basic non-equilibrium phase transition, that so far has mainly been the subject of model studies, which I review in this Perspective. AU - Hof, Björn ID - 12165 JF - Nature Reviews Physics KW - General Physics and Astronomy TI - Directed percolation and the transition to turbulence VL - 5 ER - TY - JOUR AB - The actin cytoskeleton plays a key role in cell migration and cellular morphodynamics in most eukaryotes. The ability of the actin cytoskeleton to assemble and disassemble in a spatiotemporally controlled manner allows it to form higher-order structures, which can generate forces required for a cell to explore and navigate through its environment. It is regulated not only via a complex synergistic and competitive interplay between actin-binding proteins (ABP), but also by filament biochemistry and filament geometry. The lack of structural insights into how geometry and ABPs regulate the actin cytoskeleton limits our understanding of the molecular mechanisms that define actin cytoskeleton remodeling and, in turn, impact emerging cell migration characteristics. With the advent of cryo-electron microscopy (cryo-EM) and advanced computational methods, it is now possible to define these molecular mechanisms involving actin and its interactors at both atomic and ultra-structural levels in vitro and in cellulo. In this review, we will provide an overview of the available cryo-EM methods, applicable to further our understanding of the actin cytoskeleton, specifically in the context of cell migration. We will discuss how these methods have been employed to elucidate ABP- and geometry-defined regulatory mechanisms in initiating, maintaining, and disassembling cellular actin networks in migratory protrusions. AU - Fäßler, Florian AU - Javoor, Manjunath AU - Schur, Florian KM ID - 12421 IS - 1 JF - Biochemical Society Transactions KW - Biochemistry SN - 0300-5127 TI - Deciphering the molecular mechanisms of actin cytoskeleton regulation in cell migration using cryo-EM VL - 51 ER - TY - JOUR AB - Data-driven dimensionality reduction methods such as proper orthogonal decomposition and dynamic mode decomposition have proven to be useful for exploring complex phenomena within fluid dynamics and beyond. A well-known challenge for these techniques is posed by the continuous symmetries, e.g. translations and rotations, of the system under consideration, as drifts in the data dominate the modal expansions without providing an insight into the dynamics of the problem. In the present study, we address this issue for fluid flows in rectangular channels by formulating a continuous symmetry reduction method that eliminates the translations in the streamwise and spanwise directions simultaneously. We demonstrate our method by computing the symmetry-reduced dynamic mode decomposition (SRDMD) of sliding windows of data obtained from the transitional plane-Couette and turbulent plane-Poiseuille flow simulations. In the former setting, SRDMD captures the dynamics in the vicinity of the invariant solutions with translation symmetries, i.e. travelling waves and relative periodic orbits, whereas in the latter, our calculations reveal episodes of turbulent time evolution that can be approximated by a low-dimensional linear expansion. AU - Marensi, Elena AU - Yalniz, Gökhan AU - Hof, Björn AU - Budanur, Nazmi B ID - 12105 JF - Journal of Fluid Mechanics SN - 0022-1120 TI - Symmetry-reduced dynamic mode decomposition of near-wall turbulence VL - 954 ER - TY - JOUR AB - The concept of a “speciation continuum” has gained popularity in recent decades. It emphasizes speciation as a continuous process that may be studied by comparing contemporary population pairs that show differing levels of divergence. In their recent perspective article in Evolution, Stankowski and Ravinet provided a valuable service by formally defining the speciation continuum as a continuum of reproductive isolation, based on opinions gathered from a survey of speciation researchers. While we agree that the speciation continuum has been a useful concept to advance the understanding of the speciation process, some intrinsic limitations exist. Here, we advocate for a multivariate extension, the speciation hypercube, first proposed by Dieckmann et al. in 2004, but rarely used since. We extend the idea of the speciation cube and suggest it has strong conceptual and practical advantages over a one-dimensional model. We illustrate how the speciation hypercube can be used to visualize and compare different speciation trajectories, providing new insights into the processes and mechanisms of speciation. A key strength of the speciation hypercube is that it provides a unifying framework for speciation research, as it allows questions from apparently disparate subfields to be addressed in a single conceptual model. AU - Bolnick, Daniel I. AU - Hund, Amanda K. AU - Nosil, Patrik AU - Peng, Foen AU - Ravinet, Mark AU - Stankowski, Sean AU - Subramanian, Swapna AU - Wolf, Jochen B.W. AU - Yukilevich, Roman ID - 12514 IS - 1 JF - Evolution: International journal of organic evolution TI - A multivariate view of the speciation continuum VL - 77 ER -