TY - JOUR AB - The circadian clock orchestrates global changes in transcriptional regulation on a daily basis via the bHLH-PAS transcription factor CLOCK:BMAL1. Pathways driven by other bHLH-PAS transcription factors have a homologous repressor that modulates activity on a tissue-specific basis, but none have been identified for CLOCK:BMAL1. We show here that the cancer/testis antigen PASD1 fulfills this role to suppress circadian rhythms. PASD1 is evolutionarily related to CLOCK and interacts with the CLOCK:BMAL1 complex to repress transcriptional activation. Expression of PASD1 is restricted to germline tissues in healthy individuals but can be induced in cells of somatic origin upon oncogenic transformation. Reducing PASD1 in human cancer cells significantly increases the amplitude of transcriptional oscillations to generate more robust circadian rhythms. Our results describe a function for a germline-specific protein in regulation of the circadian clock and provide a molecular link from oncogenic transformation to suppression of circadian rhythms. AU - Michael, Alicia Kathleen AU - Harvey, Stacy L. AU - Sammons, Patrick J. AU - Anderson, Amanda P. AU - Kopalle, Hema M. AU - Banham, Alison H. AU - Partch, Carrie L. ID - 15160 IS - 5 JF - Molecular Cell KW - Cell Biology KW - Molecular Biology SN - 1097-2765 TI - Cancer/Testis antigen PASD1 silences the circadian clock VL - 58 ER - TY - JOUR AB - It is widely recognized that BMAL1 is an essential subunit of the primary transcription factor that drives rhythmic circadian transcription in the nucleus. In a surprising turn, Lipton et al. now show that BMAL1 rhythmically interacts with translational machinery in the cytosol to stimulate protein synthesis in response to mTOR signaling. AU - Michael, Alicia Kathleen AU - Asimgil, Hande AU - Partch, Carrie L. ID - 15159 IS - 9 JF - Trends in Biochemical Sciences KW - Molecular Biology KW - Biochemistry SN - 0968-0004 TI - Cytosolic BMAL1 moonlights as a translation factor VL - 40 ER - TY - JOUR AB - The emergence of drug resistant pathogens is a serious public health problem. It is a long-standing goal to predict rates of resistance evolution and design optimal treatment strategies accordingly. To this end, it is crucial to reveal the underlying causes of drug-specific differences in the evolutionary dynamics leading to resistance. However, it remains largely unknown why the rates of resistance evolution via spontaneous mutations and the diversity of mutational paths vary substantially between drugs. Here we comprehensively quantify the distribution of fitness effects (DFE) of mutations, a key determinant of evolutionary dynamics, in the presence of eight antibiotics representing the main modes of action. Using precise high-throughput fitness measurements for genome-wide Escherichia coli gene deletion strains, we find that the width of the DFE varies dramatically between antibiotics and, contrary to conventional wisdom, for some drugs the DFE width is lower than in the absence of stress. We show that this previously underappreciated divergence in DFE width among antibiotics is largely caused by their distinct drug-specific dose-response characteristics. Unlike the DFE, the magnitude of the changes in tolerated drug concentration resulting from genome-wide mutations is similar for most drugs but exceptionally small for the antibiotic nitrofurantoin, i.e., mutations generally have considerably smaller resistance effects for nitrofurantoin than for other drugs. A population genetics model predicts that resistance evolution for drugs with this property is severely limited and confined to reproducible mutational paths. We tested this prediction in laboratory evolution experiments using the “morbidostat”, a device for evolving bacteria in well-controlled drug environments. Nitrofurantoin resistance indeed evolved extremely slowly via reproducible mutations—an almost paradoxical behavior since this drug causes DNA damage and increases the mutation rate. Overall, we identified novel quantitative characteristics of the evolutionary landscape that provide the conceptual foundation for predicting the dynamics of drug resistance evolution. AU - Chevereau, Guillaume AU - Dravecka, Marta AU - Batur, Tugce AU - Guvenek, Aysegul AU - Ayhan, Dilay AU - Toprak, Erdal AU - Bollenbach, Mark Tobias ID - 1619 IS - 11 JF - PLoS Biology TI - Quantifying the determinants of evolutionary dynamics leading to drug resistance VL - 13 ER - TY - JOUR AB - Protein oligomers have been implicated as toxic agents in a wide range of amyloid-related diseases. However, it has remained unsolved whether the oligomers are a necessary step in the formation of amyloid fibrils or just a dangerous byproduct. Analogously, it has not been resolved if the amyloid nucleation process is a classical one-step nucleation process or a two-step process involving prenucleation clusters. We use coarse-grained computer simulations to study the effect of nonspecific attractions between peptides on the primary nucleation process underlying amyloid fibrillization. We find that, for peptides that do not attract, the classical one-step nucleation mechanism is possible but only at nonphysiologically high peptide concentrations. At low peptide concentrations, which mimic the physiologically relevant regime, attractive interpeptide interactions are essential for fibril formation. Nucleation then inevitably takes place through a two-step mechanism involving prefibrillar oligomers. We show that oligomers not only help peptides meet each other but also, create an environment that facilitates the conversion of monomers into the β-sheet–rich form characteristic of fibrils. Nucleation typically does not proceed through the most prevalent oligomers but through an oligomer size that is only observed in rare fluctuations, which is why such aggregates might be hard to capture experimentally. Finally, we find that the nucleation of amyloid fibrils cannot be described by classical nucleation theory: in the two-step mechanism, the critical nucleus size increases with increases in both concentration and interpeptide interactions, which is in direct contrast with predictions from classical nucleation theory. AU - Šarić, Anđela AU - Chebaro, Yassmine C. AU - Knowles, Tuomas P. J. AU - Frenkel, Daan ID - 10382 IS - 50 JF - Proceedings of the National Academy of Sciences KW - multidisciplinary SN - 0027-8424 TI - Crucial role of nonspecific interactions in amyloid nucleation VL - 111 ER - TY - JOUR AB - We use numerical simulations to compute the equation of state of a suspension of spherical self-propelled nanoparticles in two and three dimensions. We study in detail the effect of excluded volume interactions and confinement as a function of the system's temperature, concentration, and strength of the propulsion. We find a striking nonmonotonic dependence of the pressure on the temperature and provide simple scaling arguments to predict and explain the occurrence of such anomalous behavior. We explicitly show how our results have important implications for the effective forces on passive components suspended in a bath of active particles. AU - Mallory, S. A. AU - Šarić, Anđela AU - Valeriani, C. AU - Cacciuto, A. ID - 10383 IS - 5 JF - Physical Review E SN - 1539-3755 TI - Anomalous thermomechanical properties of a self-propelled colloidal fluid VL - 89 ER - TY - JOUR AB - Diffraction-unlimited far-field super-resolution fluorescence (nanoscopy) methods typically rely on transiently transferring fluorophores between two states, whereby this transfer is usually laid out as a switch. However, depending on whether this is induced in a spatially controlled manner using a pattern of light (coordinate-targeted) or stochastically on a single-molecule basis, specific requirements on the fluorophores are imposed. Therefore, the fluorophores are usually utilized just for one class of methods only. In this study we demonstrate that the reversibly switchable fluorescent protein Dreiklang enables live-cell recordings in both spatially controlled and stochastic modes. We show that the Dreiklang chromophore entails three different light-induced switching mechanisms, namely a reversible photochemical one, off-switching by stimulated emission, and a reversible transfer to a long-lived dark state from the S1 state, all of which can be utilized to overcome the diffraction barrier. We also find that for the single-molecule- based stochastic GSDIM approach (ground-state depletion followed by individual molecule return), Dreiklang provides a larger number of on-off localization events as compared to its progenitor Citrine. Altogether, Dreiklang is a versatile probe for essentially all popular forms of live-cell fluorescence nanoscopy. AU - Jensen, Nickels AU - Danzl, Johann G AU - Willig, Katrin AU - Lavoie Cardinal, Flavie AU - Brakemann, Tanja AU - Hell, Stefan AU - Jakobs, Stefan ID - 1058 IS - 4 JF - ChemPhysChem TI - Coordinate-targeted and coordinate-stochastic super-resolution microscopy with the reversibly switchable fluorescent protein dreiklang VL - 15 ER - TY - JOUR AB - In the last several decades, developmental biology has clarified the molecular mechanisms of embryogenesis and organogenesis. In particular, it has demonstrated that the “tool-kit genes” essential for regulating developmental processes are not only highly conserved among species, but are also used as systems at various times and places in an organism to control distinct developmental events. Therefore, mutations in many of these tool-kit genes may cause congenital diseases involving morphological abnormalities. This link between genes and abnormal morphological phenotypes underscores the importance of understanding how cells behave and contribute to morphogenesis as a result of gene function. Recent improvements in live imaging and in quantitative analyses of cellular dynamics will advance our understanding of the cellular pathogenesis of congenital diseases associated with aberrant morphologies. In these studies, it is critical to select an appropriate model organism for the particular phenomenon of interest. AU - Hashimoto, Masakazu AU - Morita, Hitoshi AU - Ueno, Naoto ID - 10815 IS - 1 JF - Congenital Anomalies KW - Developmental Biology KW - Embryology KW - General Medicine KW - Pediatrics KW - Perinatology KW - and Child Health SN - 0914-3505 TI - Molecular and cellular mechanisms of development underlying congenital diseases VL - 54 ER - TY - BOOK AB - Auxin is an important signaling compound in plants and vital for plant development and growth. The present book, Auxin and its Role in Plant Development, provides the reader with detailed and comprehensive insight into the functioning of the molecule on the whole and specifically in plant development. In the first part, the functioning, metabolism and signaling pathways of auxin in plants are explained, the second part depicts the specific role of auxin in plant development and the third part describes the interaction and functioning of the signaling compound upon stimuli of the environment. Each chapter is written by international experts in the respective field and designed for scientists and researchers in plant biology, plant development and cell biology to summarize the recent progress in understanding the role of auxin and suggest future perspectives for auxin research. ED - Zažímalová, Eva ED - Petrášek, Jan ED - Benková, Eva ID - 10811 SN - 9783709115251 TI - Auxin and Its Role in Plant Development ER - TY - CONF AB - We revisit the parameterized model checking problem for token-passing systems and specifications in indexed CTL  ∗ \X. Emerson and Namjoshi (1995, 2003) have shown that parameterized model checking of indexed CTL  ∗ \X in uni-directional token rings can be reduced to checking rings up to some cutoff size. Clarke et al. (2004) have shown a similar result for general topologies and indexed LTL \X, provided processes cannot choose the directions for sending or receiving the token. We unify and substantially extend these results by systematically exploring fragments of indexed CTL  ∗ \X with respect to general topologies. For each fragment we establish whether a cutoff exists, and for some concrete topologies, such as rings, cliques and stars, we infer small cutoffs. Finally, we show that the problem becomes undecidable, and thus no cutoffs exist, if processes are allowed to choose the directions in which they send or from which they receive the token. AU - Aminof, Benjamin AU - Jacobs, Swen AU - Khalimov, Ayrat AU - Rubin, Sasha ID - 10884 SN - 0302-9743 T2 - Verification, Model Checking, and Abstract Interpretation TI - Parameterized model checking of token-passing systems VL - 8318 ER - TY - CHAP AB - Saddle periodic orbits are an essential and stable part of the topological skeleton of a 3D vector field. Nevertheless, there is currently no efficient algorithm to robustly extract these features. In this chapter, we present a novel technique to extract saddle periodic orbits. Exploiting the analytic properties of such an orbit, we propose a scalar measure based on the finite-time Lyapunov exponent (FTLE) that indicates its presence. Using persistent homology, we can then extract the robust cycles of this field. These cycles thereby represent the saddle periodic orbits of the given vector field. We discuss the different existing FTLE approximation schemes regarding their applicability to this specific problem and propose an adapted version of FTLE called Normalized Velocity Separation. Finally, we evaluate our method using simple analytic vector field data. AU - Kasten, Jens AU - Reininghaus, Jan AU - Reich, Wieland AU - Scheuermann, Gerik ED - Bremer, Peer-Timo ED - Hotz, Ingrid ED - Pascucci, Valerio ED - Peikert, Ronald ID - 10893 SN - 1612-3786 T2 - Topological Methods in Data Analysis and Visualization III TI - Toward the extraction of saddle periodic orbits VL - 1 ER - TY - JOUR AB - The spindle assembly checkpoint prevents separation of sister chromatids until each kinetochore is attached to the mitotic spindle. Rodriguez-Bravo et al. report that the nuclear pore complex scaffolds spindle assembly checkpoint signaling in interphase, providing a store of inhibitory signals that limits the speed of the subsequent mitosis. AU - Buchwalter, Abigail AU - HETZER, Martin W ID - 11080 IS - 5 JF - Cell KW - General Biochemistry KW - Genetics and Molecular Biology SN - 0092-8674 TI - Nuclear pores set the speed limit for mitosis VL - 156 ER - TY - JOUR AB - The nuclear pore complex (NPC) plays a critical role in gene expression by mediating import of transcription regulators into the nucleus and export of RNA transcripts to the cytoplasm. Emerging evidence suggests that in addition to mediating transport, a subset of nucleoporins (Nups) engage in transcriptional activation and elongation at genomic loci that are not associated with NPCs. The underlying mechanism and regulation of Nup mobility on and off nuclear pores remain unclear. Here we show that Nup50 is a mobile Nup with a pronounced presence both at the NPC and in the nucleoplasm that can move between these different localizations. Strikingly, the dynamic behavior of Nup50 in both locations is dependent on active transcription by RNA polymerase II and requires the N-terminal half of the protein, which contains importin α– and Nup153-binding domains. However, Nup50 dynamics are independent of importin α, Nup153, and Nup98, even though the latter two proteins also exhibit transcription-dependent mobility. Of interest, depletion of Nup50 from C2C12 myoblasts does not affect cell proliferation but inhibits differentiation into myotubes. Taken together, our results suggest a transport-independent role for Nup50 in chromatin biology that occurs away from the NPC. AU - Buchwalter, Abigail L. AU - Liang, Yun AU - HETZER, Martin W ID - 11082 IS - 16 JF - Molecular Biology of the Cell KW - Cell Biology KW - Molecular Biology SN - 1059-1524 TI - Nup50 is required for cell differentiation and exhibits transcription-dependent dynamics VL - 25 ER - TY - JOUR AB - In eukaryotic cells the nuclear genome is enclosed by the nuclear envelope (NE). In metazoans, the NE breaks down in mitosis and it has been assumed that the physical barrier separating nucleoplasm and cytoplasm remains intact during the rest of the cell cycle and cell differentiation. However, recent studies suggest that nonmitotic NE remodeling plays a critical role in development, virus infection, laminopathies, and cancer. Although the mechanisms underlying these NE restructuring events are currently being defined, one common theme is activation of protein kinase C family members in the interphase nucleus to disrupt the nuclear lamina, demonstrating the importance of the lamina in maintaining nuclear integrity. AU - Hatch, Emily AU - HETZER, Martin W ID - 11081 IS - 2 JF - Journal of Cell Biology KW - Cell Biology SN - 1540-8140 TI - Breaching the nuclear envelope in development and disease VL - 205 ER - TY - JOUR AB - Candidate galaxies at redshifts of z ∼ 10 are now being found in extremely deep surveys, probing very small areas. As a consequence, candidates are very faint, making spectroscopic confirmation practically impossible. In order to overcome such limitations, we have undertaken the CF-HiZELS survey, which is a large-area, medium-depth near-infrared narrow-band survey targeted at z = 8.8 Lyman α (Lyα) emitters (LAEs) and covering 10 deg2 in part of the SSA22 field with the Canada–France–Hawaii Telescope (CFHT). We surveyed a comoving volume of 4.7 × 106 Mpc3 to a Lyα luminosity limit of 6.3 × 1043舁erg舁s−1. We look for Lyα candidates by applying the following criteria: (i) clear emission-line source, (ii) no optical detections (ugriz from CFHTLS), (iii) no visible detection in the optical stack (ugriz > 27), (iv) visually checked reliable NBJ and J detections and (v) J − K ≤ 0. We compute photometric redshifts and remove a significant amount of dusty lower redshift line-emitters at z ∼ 1.4 or 2.2. A total of 13 Lyα candidates were found, of which two are marked as strong candidates, but the majority have very weak constraints on their spectral energy distributions. Using follow-up observations with SINFONI/VLT, we are able to exclude the most robust candidates as LAEs. We put a strong constraint on the Lyα luminosity function at z ∼ 9 and make realistic predictions for ongoing and future surveys. Our results show that surveys for the highest redshift LAEs are susceptible of multiple contaminations and that spectroscopic follow-up is absolutely necessary. AU - Matthee, Jorryt J AU - Sobral, David AU - Swinbank, A. M. AU - Smail, Ian AU - Best, P. N. AU - Kim, Jae-Woo AU - Franx, Marijn AU - Milvang-Jensen, Bo AU - Fynbo, Johan ID - 11583 IS - 3 JF - Monthly Notices of the Royal Astronomical Society KW - Space and Planetary Science KW - Astronomy and Astrophysics KW - galaxies: evolution KW - galaxies: high-redshift KW - cosmology: observations KW - dark ages KW - reionization KW - first stars SN - 0035-8711 TI - A 10 deg2 Lyman α survey at z=8.8 with spectroscopic follow-up: Strong constraints on the luminosity function and implications for other surveys VL - 440 ER - TY - JOUR AB - We have observed a sample of typical z ∼ 1 star-forming galaxies, selected from the HiZELS survey, with the new K-band Multi-Object Spectrograph (KMOS) near-infrared, multi-integral field unit instrument on the Very Large Telescope (VLT), in order to obtain their dynamics and metallicity gradients. The majority of our galaxies have a metallicity gradient consistent with being flat or negative (i.e. higher metallicity cores than outskirts). Intriguingly, we find a trend between metallicity gradient and specific star formation rate (sSFR), such that galaxies with a high sSFR tend to have relatively metal poor centres, a result which is strengthened when combined with data sets from the literature. This result appears to explain the discrepancies reported between different high-redshift studies and varying claims for evolution. From a galaxy evolution perspective, the trend we see would mean that a galaxy's sSFR is governed by the amount of metal-poor gas that can be funnelled into its core, triggered either by merging or through efficient accretion. In fact, merging may play a significant role as it is the starburst galaxies at all epochs, which have the more positive metallicity gradients. Our results may help to explain the origin of the fundamental metallicity relation, in which galaxies at a fixed mass are observed to have lower metallicities at higher star formation rates, especially if the metallicity is measured in an aperture encompassing only the central regions of the galaxy. Finally, we note that this study demonstrates the power of KMOS as an efficient instrument for large-scale resolved galaxy surveys. AU - Stott, John P. AU - Sobral, David AU - Swinbank, A. M. AU - Smail, Ian AU - Bower, Richard AU - Best, Philip N. AU - Sharples, Ray M. AU - Geach, James E. AU - Matthee, Jorryt J ID - 11582 IS - 3 JF - Monthly Notices of the Royal Astronomical Society KW - Space and Planetary Science KW - Astronomy and Astrophysics KW - galaxies: abundances KW - galaxies: evolution KW - galaxies: kinematics and dynamics SN - 0035-8711 TI - A relationship between specific star formation rate and metallicity gradient within z ∼ 1 galaxies from KMOS-HiZELS VL - 443 ER - TY - JOUR AB - We report on the magnetic properties of a hot-pressed FeSb 2 sample. We find a significant increase in the magnetic susceptibility in our sample when compared with the values previously reported for the polycrystalline sample. The pronounced Curie tail at low temperature corresponds to 0.2% of Fe 2+ impurities per mole. In the intrinsic conductivity region, the susceptibility due to free carriers shows thermally activated behavior and is consistent with the data reported for single crystal FeSb 2 . Based on our data and analysis, while the enhanced magnetic susceptibility in our sample comes mainly from a small amount of unreacted Fe, the contribution from the enhanced carrier density due to lattice and strain defects arising from the ball milling process is also significant. Existence of an unreacted Fe phase is evidenced by small coercivity values of ~100 observed at 50 and 300 K. AU - Pokharel, Mani AU - Zhao, Huaizhou AU - Modic, Kimberly A AU - Ren, Zhifeng AU - Opeil, Cyril ID - 11750 IS - 5 JF - IEEE Transactions on Magnetics SN - 0018-9464 TI - Magnetic properties of hot-pressed FeSb2 VL - 50 ER - TY - CONF AB - We study a weighted online bipartite matching problem: G(V 1, V 2, E) is a weighted bipartite graph where V 1 is known beforehand and the vertices of V 2 arrive online. The goal is to match vertices of V 2 as they arrive to vertices in V 1, so as to maximize the sum of weights of edges in the matching. If assignments to V 1 cannot be changed, no bounded competitive ratio is achievable. We study the weighted online matching problem with free disposal, where vertices in V 1 can be assigned multiple times, but only get credit for the maximum weight edge assigned to them over the course of the algorithm. For this problem, the greedy algorithm is 0.5-competitive and determining whether a better competitive ratio is achievable is a well known open problem. We identify an interesting special case where the edge weights are decomposable as the product of two factors, one corresponding to each end point of the edge. This is analogous to the well studied related machines model in the scheduling literature, although the objective functions are different. For this case of decomposable edge weights, we design a 0.5664 competitive randomized algorithm in complete bipartite graphs. We show that such instances with decomposable weights are non-trivial by establishing upper bounds of 0.618 for deterministic and 0.8 for randomized algorithms. A tight competitive ratio of 1 − 1/e ≈ 0.632 was known previously for both the 0-1 case as well as the case where edge weights depend on the offline vertices only, but for these cases, reassignments cannot change the quality of the solution. Beating 0.5 for weighted matching where reassignments are necessary has been a significant challenge. We thus give the first online algorithm with competitive ratio strictly better than 0.5 for a non-trivial case of weighted matching with free disposal. AU - Charikar, Moses AU - Henzinger, Monika H AU - Nguyễn, Huy L. ID - 11789 SN - 0302-9743 T2 - 22nd Annual European Symposium on Algorithms TI - Online bipartite matching with decomposable weights VL - 8737 ER - TY - CONF AB - Assume a seller wants to sell a digital product in a social network where a buyer’s valuation of the item has positive network externalities from her neighbors that already have the item. The goal of the seller is to maximize his revenue. Previous work on this problem [7] studies the case where clients are offered the item in sequence and have to pay personalized prices. This is highly infeasible in large scale networks such as the Facebook graph: (1) Offering items to the clients one after the other consumes a large amount of time, and (2) price-discrimination of clients could appear unfair to them and result in negative client reaction or could conflict with legal requirements. We study a setting dealing with these issues. Specifically, the item is offered in parallel to multiple clients at the same time and at the same price. This is called a round. We show that with O(logn) rounds, where n is the number of clients, a constant factor of the revenue with price discrimination can be achieved and that this is not possible with o(logn) rounds. Moreover we show that it is APX-hard to maximize the revenue and we give constant factor approximation algorithms for various further settings of limited price discrimination. AU - Cigler, Luděk AU - Dvořák, Wolfgang AU - Henzinger, Monika H AU - Starnberger, Martin ID - 11790 SN - 0302-9743 T2 - 10th International Conference of Web and Internet Economics TI - Limiting price discrimination when selling products with positive network externalities VL - 8877 ER - TY - JOUR AB - While the penetration of objects into granular media is well-studied, there is little understanding of how objects settle in gravities, geff, different from that of Earth - a scenario potentially relevant to the geomorphology of planets and asteroids and also to their exploration using man-made devices. By conducting experiments in an accelerating frame, we explore geff ranging from 0.4 g to 1.2 g. Surprisingly, we find that the rest depth is independent of geff and also that the time required for the object to come to rest scales like geff-1/2. With discrete element modeling simulations, we reproduce the experimental results and extend the range of geff to objects as small as asteroids and as large as Jupiter. Our results shed light on the initial stage of sedimentation into dry granular media across a range of celestial bodies and also have implications for the design of man-made, extraterrestrial vehicles and structures. Key Points The settling depth in granular media is independent of gravity The settling time scales like g-1/2 Layering driven by granular sedimentation should be similar. AU - Altshuler, Ernesto AU - Torres, H AU - González_Pita, A AU - Sánchez, Colina G AU - Pérez Penichet, Carlos AU - Waitukaitis, Scott R AU - Hidalgo, Rauól ID - 118 IS - 9 JF - Geophysical Research Letters TI - Settling into dry granular media in different gravities VL - 41 ER - TY - CONF AB - The decremental single-source shortest paths (SSSP) problem concerns maintaining the distances between a given source node s to every node in an n-node m-edge graph G undergoing edge deletions. While its static counterpart can be easily solved in near-linear time, this decremental problem is much more challenging even in the undirected unweighted case. In this case, the classic O(mn) total update time of Even and Shiloach (JACM 1981) has been the fastest known algorithm for three decades. With the loss of a (1 + ε)-approximation factor, the running time was recently improved to O(n 2+o(1) ) by Bernstein and Roditty (SODA 2011), and more recently to O(n 1.8+o(1) + m 1+o(1) ) by Henzinger, Krinninger, and Nanongkai (SODA 2014). In this paper, we finally bring the running time of this case down to near-linear: We give a (1 + ε)-approximation algorithm with O(m 1+o(1) ) total update time, thus obtaining near-linear time. Moreover, we obtain O(m 1+o(1) log W) time for the weighted case, where the edge weights are integers from 1 to W. The only prior work on weighted graphs in o(mn log W) time is the O(mn 0.986 log W)-time algorithm by Henzinger, Krinninger, and Nanongkai (STOC 2014) which works for the general weighted directed case. In contrast to the previous results which rely on maintaining a sparse emulator, our algorithm relies on maintaining a so-called sparse (d, ε)-hop set introduced by Cohen (JACM 2000) in the PRAM literature. A (d, ε)-hop set of a graph G = (V, E) is a set E' of weighted edges such that the distance between any pair of nodes in G can be (1 + ε)-approximated by their d-hop distance (given by a path containing at most d edges) on G'=(V, E∪E'). Our algorithm can maintain an (n o(1) , ε)-hop set of near-linear size in near-linear time under edge deletions. It is the first of its kind to the best of our knowledge. To maintain the distances on this hop set, we develop a monotone bounded-hop Even-Shiloach tree. It results from extending and combining the monotone Even-Shiloach tree of Henzinger, Krinninger, and Nanongkai (FOCS 2013) with the bounded-hop SSSP technique of Bernstein (STOC 2013). These two new tools might be of independent interest. AU - Henzinger, Monika H AU - Krinninger, Sebastian AU - Nanongkai, Danupon ID - 11855 SN - 0272-5428 T2 - 55th Annual Symposium on Foundations of Computer Science TI - Decremental single-source shortest paths on undirected graphs in near-linear total update time ER -