@article{9526, abstract = {DNA methylation and histone H1 mediate transcriptional silencing of genes and transposable elements, but how they interact is unclear. In plants and animals with mosaic genomic methylation, functionally mysterious methylation is also common within constitutively active housekeeping genes. Here, we show that H1 is enriched in methylated sequences, including genes, of Arabidopsis thaliana, yet this enrichment is independent of DNA methylation. Loss of H1 disperses heterochromatin, globally alters nucleosome organization, and activates H1-bound genes, but only weakly de-represses transposable elements. However, H1 loss strongly activates transposable elements hypomethylated through mutation of DNA methyltransferase MET1. Hypomethylation of genes also activates antisense transcription, which is modestly enhanced by H1 loss. Our results demonstrate that H1 and DNA methylation jointly maintain transcriptional homeostasis by silencing transposable elements and aberrant intragenic transcripts. Such functionality plausibly explains why DNA methylation, a well-known mutagen, has been maintained within coding sequences of crucial plant and animal genes.}, author = {Choi, Jaemyung and Lyons, David B. and Kim, M. Yvonne and Moore, Jonathan D. and Zilberman, Daniel}, issn = {1097-4164}, journal = {Molecular Cell}, number = {2}, pages = {310--323.e7}, publisher = {Elsevier}, title = {{DNA methylation and histone H1 jointly repress transposable elements and aberrant intragenic transcripts}}, doi = {10.1016/j.molcel.2019.10.011}, volume = {77}, year = {2020}, } @article{9573, abstract = {It is a classical fact that for any ε>0, a random permutation of length n=(1+ε)k2/4 typically contains a monotone subsequence of length k. As a far-reaching generalization, Alon conjectured that a random permutation of this same length n is typically k-universal, meaning that it simultaneously contains every pattern of length k. He also made the simple observation that for n=O(k2logk), a random length-n permutation is typically k-universal. We make the first significant progress towards Alon's conjecture by showing that n=2000k2loglogk suffices.}, author = {He, Xiaoyu and Kwan, Matthew Alan}, issn = {1469-2120}, journal = {Bulletin of the London Mathematical Society}, number = {3}, pages = {515--529}, publisher = {Wiley}, title = {{Universality of random permutations}}, doi = {10.1112/blms.12345}, volume = {52}, year = {2020}, } @article{9576, abstract = {In 1989, Rota made the following conjecture. Given n bases B1,…,Bn in an n-dimensional vector space V⁠, one can always find n disjoint bases of V⁠, each containing exactly one element from each Bi (we call such bases transversal bases). Rota’s basis conjecture remains wide open despite its apparent simplicity and the efforts of many researchers (e.g., the conjecture was recently the subject of the collaborative “Polymath” project). In this paper we prove that one can always find (1/2−o(1))n disjoint transversal bases, improving on the previous best bound of Ω(n/logn)⁠. Our results also apply to the more general setting of matroids.}, author = {Bucić, Matija and Kwan, Matthew Alan and Pokrovskiy, Alexey and Sudakov, Benny}, issn = {1687-0247}, journal = {International Mathematics Research Notices}, number = {21}, pages = {8007--8026}, publisher = {Oxford University Press}, title = {{Halfway to Rota’s basis conjecture}}, doi = {10.1093/imrn/rnaa004}, volume = {2020}, year = {2020}, } @article{9577, abstract = {An n-vertex graph is called C-Ramsey if it has no clique or independent set of size Clogn⁠. All known constructions of Ramsey graphs involve randomness in an essential way, and there is an ongoing line of research towards showing that in fact all Ramsey graphs must obey certain “richness” properties characteristic of random graphs. Motivated by an old problem of Erd̋s and McKay, recently Narayanan, Sahasrabudhe, and Tomon conjectured that for any fixed C, every n-vertex C-Ramsey graph induces subgraphs of Θ(n2) different sizes. In this paper we prove this conjecture.}, author = {Kwan, Matthew Alan and Sudakov, Benny}, issn = {1687-0247}, journal = {International Mathematics Research Notices}, number = {6}, pages = {1621–1638}, publisher = {Oxford University Press}, title = {{Ramsey graphs induce subgraphs of quadratically many sizes}}, doi = {10.1093/imrn/rny064}, volume = {2020}, year = {2020}, } @article{9578, abstract = {How long a monotone path can one always find in any edge-ordering of the complete graph Kn? This appealing question was first asked by Chvátal and Komlós in 1971, and has since attracted the attention of many researchers, inspiring a variety of related problems. The prevailing conjecture is that one can always find a monotone path of linear length, but until now the best known lower bound was n2/3-o(1). In this paper we almost close this gap, proving that any edge-ordering of the complete graph contains a monotone path of length n1-o(1).}, author = {Bucić, Matija and Kwan, Matthew Alan and Pokrovskiy, Alexey and Sudakov, Benny and Tran, Tuan and Wagner, Adam Zsolt}, issn = {1565-8511}, journal = {Israel Journal of Mathematics}, number = {2}, pages = {663--685}, publisher = {Springer}, title = {{Nearly-linear monotone paths in edge-ordered graphs}}, doi = {10.1007/s11856-020-2035-7}, volume = {238}, year = {2020}, } @article{9581, abstract = {We show that for any 𝑛 divisible by 3, almost all order- 𝑛 Steiner triple systems have a perfect matching (also known as a parallel class or resolution class). In fact, we prove a general upper bound on the number of perfect matchings in a Steiner triple system and show that almost all Steiner triple systems essentially attain this maximum. We accomplish this via a general theorem comparing a uniformly random Steiner triple system to the outcome of the triangle removal process, which we hope will be useful for other problems. Our methods can also be adapted to other types of designs; for example, we sketch a proof of the theorem that almost all Latin squares have transversals.}, author = {Kwan, Matthew Alan}, issn = {1460-244X}, journal = {Proceedings of the London Mathematical Society}, number = {6}, pages = {1468--1495}, publisher = {Wiley}, title = {{Almost all Steiner triple systems have perfect matchings}}, doi = {10.1112/plms.12373}, volume = {121}, year = {2020}, } @article{9582, abstract = {The problem of finding dense induced bipartite subgraphs in H-free graphs has a long history, and was posed 30 years ago by Erdős, Faudree, Pach and Spencer. In this paper, we obtain several results in this direction. First we prove that any H-free graph with minimum degree at least d contains an induced bipartite subgraph of minimum degree at least cH log d/log log d, thus nearly confirming one and proving another conjecture of Esperet, Kang and Thomassé. Complementing this result, we further obtain optimal bounds for this problem in the case of dense triangle-free graphs, and we also answer a question of Erdœs, Janson, Łuczak and Spencer.}, author = {Kwan, Matthew Alan and Letzter, Shoham and Sudakov, Benny and Tran, Tuan}, issn = {1439-6912}, journal = {Combinatorica}, number = {2}, pages = {283--305}, publisher = {Springer}, title = {{Dense induced bipartite subgraphs in triangle-free graphs}}, doi = {10.1007/s00493-019-4086-0}, volume = {40}, year = {2020}, } @article{9583, abstract = {We show that for any n divisible by 3, almost all order-n Steiner triple systems admit a decomposition of almost all their triples into disjoint perfect matchings (that is, almost all Steiner triple systems are almost resolvable).}, author = {Ferber, Asaf and Kwan, Matthew Alan}, issn = {2050-5094}, journal = {Forum of Mathematics}, publisher = {Cambridge University Press}, title = {{Almost all Steiner triple systems are almost resolvable}}, doi = {10.1017/fms.2020.29}, volume = {8}, year = {2020}, } @article{9630, abstract = {Various kinds of data are routinely represented as discrete probability distributions. Examples include text documents summarized by histograms of word occurrences and images represented as histograms of oriented gradients. Viewing a discrete probability distribution as a point in the standard simplex of the appropriate dimension, we can understand collections of such objects in geometric and topological terms. Importantly, instead of using the standard Euclidean distance, we look into dissimilarity measures with information-theoretic justification, and we develop the theory needed for applying topological data analysis in this setting. In doing so, we emphasize constructions that enable the usage of existing computational topology software in this context.}, author = {Edelsbrunner, Herbert and Virk, Ziga and Wagner, Hubert}, issn = {1920-180X}, journal = {Journal of Computational Geometry}, number = {2}, pages = {162--182}, publisher = {Carleton University}, title = {{Topological data analysis in information space}}, doi = {10.20382/jocg.v11i2a7}, volume = {11}, year = {2020}, } @inproceedings{9631, abstract = {The ability to leverage large-scale hardware parallelism has been one of the key enablers of the accelerated recent progress in machine learning. Consequently, there has been considerable effort invested into developing efficient parallel variants of classic machine learning algorithms. However, despite the wealth of knowledge on parallelization, some classic machine learning algorithms often prove hard to parallelize efficiently while maintaining convergence. In this paper, we focus on efficient parallel algorithms for the key machine learning task of inference on graphical models, in particular on the fundamental belief propagation algorithm. We address the challenge of efficiently parallelizing this classic paradigm by showing how to leverage scalable relaxed schedulers in this context. We present an extensive empirical study, showing that our approach outperforms previous parallel belief propagation implementations both in terms of scalability and in terms of wall-clock convergence time, on a range of practical applications.}, author = {Aksenov, Vitaly and Alistarh, Dan-Adrian and Korhonen, Janne}, isbn = {9781713829546}, issn = {1049-5258}, location = {Vancouver, Canada}, pages = {22361--22372}, publisher = {Neural Information Processing Systems Foundation}, title = {{Scalable belief propagation via relaxed scheduling}}, volume = {33}, year = {2020}, } @inproceedings{9632, abstract = {Second-order information, in the form of Hessian- or Inverse-Hessian-vector products, is a fundamental tool for solving optimization problems. Recently, there has been significant interest in utilizing this information in the context of deep neural networks; however, relatively little is known about the quality of existing approximations in this context. Our work examines this question, identifies issues with existing approaches, and proposes a method called WoodFisher to compute a faithful and efficient estimate of the inverse Hessian. Our main application is to neural network compression, where we build on the classic Optimal Brain Damage/Surgeon framework. We demonstrate that WoodFisher significantly outperforms popular state-of-the-art methods for oneshot pruning. Further, even when iterative, gradual pruning is allowed, our method results in a gain in test accuracy over the state-of-the-art approaches, for standard image classification datasets such as ImageNet ILSVRC. We examine how our method can be extended to take into account first-order information, as well as illustrate its ability to automatically set layer-wise pruning thresholds and perform compression in the limited-data regime. The code is available at the following link, https://github.com/IST-DASLab/WoodFisher.}, author = {Singh, Sidak Pal and Alistarh, Dan-Adrian}, isbn = {9781713829546}, issn = {1049-5258}, location = {Vancouver, Canada}, pages = {18098--18109}, publisher = {Neural Information Processing Systems Foundation}, title = {{WoodFisher: Efficient second-order approximation for neural network compression}}, volume = {33}, year = {2020}, } @article{9658, abstract = {Macroscopic models of nucleation provide powerful tools for understanding activated phase transition processes. These models do not provide atomistic insights and can thus sometimes lack material-specific descriptions. Here, we provide a comprehensive framework for constructing a continuum picture from an atomistic simulation of homogeneous nucleation. We use this framework to determine the equilibrium shape of the solid nucleus that forms inside bulk liquid for a Lennard-Jones potential. From this shape, we then extract the anisotropy of the solid-liquid interfacial free energy, by performing a reverse Wulff construction in the space of spherical harmonic expansions. We find that the shape of the nucleus is nearly spherical and that its anisotropy can be perfectly described using classical models.}, author = {Cheng, Bingqing and Ceriotti, Michele and Tribello, Gareth A.}, issn = {1089-7690}, journal = {The Journal of Chemical Physics}, number = {4}, publisher = {AIP Publishing}, title = {{Classical nucleation theory predicts the shape of the nucleus in homogeneous solidification}}, doi = {10.1063/1.5134461}, volume = {152}, year = {2020}, } @article{9664, abstract = {Equilibrium molecular dynamics simulations, in combination with the Green-Kubo (GK) method, have been extensively used to compute the thermal conductivity of liquids. However, the GK method relies on an ambiguous definition of the microscopic heat flux, which depends on how one chooses to distribute energies over atoms. This ambiguity makes it problematic to employ the GK method for systems with nonpairwise interactions. In this work, we show that the hydrodynamic description of thermally driven density fluctuations can be used to obtain the thermal conductivity of a bulk fluid unambiguously, thereby bypassing the need to define the heat flux. We verify that, for a model fluid with only pairwise interactions, our method yields estimates of thermal conductivity consistent with the GK approach. We apply our approach to compute the thermal conductivity of a nonpairwise additive water model at supercritical conditions, and of a liquid hydrogen system described by a machine-learning interatomic potential, at 33 GPa and 2000 K.}, author = {Cheng, Bingqing and Frenkel, Daan}, issn = {1079-7114}, journal = {Physical Review Letters}, number = {13}, publisher = {American Physical Society}, title = {{Computing the heat conductivity of fluids from density fluctuations}}, doi = {10.1103/physrevlett.125.130602}, volume = {125}, year = {2020}, } @article{9666, abstract = {Predicting phase stabilities of crystal polymorphs is central to computational materials science and chemistry. Such predictions are challenging because they first require searching for potential energy minima and then performing arduous free-energy calculations to account for entropic effects at finite temperatures. Here, we develop a framework that facilitates such predictions by exploiting all the information obtained from random searches of crystal structures. This framework combines automated clustering, classification and visualisation of crystal structures with machine-learning estimation of their enthalpy and entropy. We demonstrate the framework on the technologically important system of TiO2, which has many polymorphs, without relying on prior knowledge of known phases. We find a number of new phases and predict the phase diagram and metastabilities of crystal polymorphs at 1600 K, benchmarking the results against full free-energy calculations.}, author = {Reinhardt, Aleks and Pickard, Chris J. and Cheng, Bingqing}, issn = {1463-9084}, journal = {Physical Chemistry Chemical Physics}, number = {22}, pages = {12697--12705}, publisher = {Royal Society of Chemistry}, title = {{Predicting the phase diagram of titanium dioxide with random search and pattern recognition}}, doi = {10.1039/d0cp02513e}, volume = {22}, year = {2020}, } @article{9671, abstract = {Water molecules can arrange into a liquid with complex hydrogen-bond networks and at least 17 experimentally confirmed ice phases with enormous structural diversity. It remains a puzzle how or whether this multitude of arrangements in different phases of water are related. Here we investigate the structural similarities between liquid water and a comprehensive set of 54 ice phases in simulations, by directly comparing their local environments using general atomic descriptors, and also by demonstrating that a machine-learning potential trained on liquid water alone can predict the densities, lattice energies, and vibrational properties of the ices. The finding that the local environments characterising the different ice phases are found in water sheds light on the phase behavior of water, and rationalizes the transferability of water models between different phases.}, author = {Monserrat, Bartomeu and Brandenburg, Jan Gerit and Engel, Edgar A. and Cheng, Bingqing}, issn = {2041-1723}, journal = {Nature Communications}, number = {1}, publisher = {Springer Nature}, title = {{Liquid water contains the building blocks of diverse ice phases}}, doi = {10.1038/s41467-020-19606-y}, volume = {11}, year = {2020}, } @article{9675, abstract = {The visualization of data is indispensable in scientific research, from the early stages when human insight forms to the final step of communicating results. In computational physics, chemistry and materials science, it can be as simple as making a scatter plot or as straightforward as looking through the snapshots of atomic positions manually. However, as a result of the "big data" revolution, these conventional approaches are often inadequate. The widespread adoption of high-throughput computation for materials discovery and the associated community-wide repositories have given rise to data sets that contain an enormous number of compounds and atomic configurations. A typical data set contains thousands to millions of atomic structures, along with a diverse range of properties such as formation energies, band gaps, or bioactivities.It would thus be desirable to have a data-driven and automated framework for visualizing and analyzing such structural data sets. The key idea is to construct a low-dimensional representation of the data, which facilitates navigation, reveals underlying patterns, and helps to identify data points with unusual attributes. Such data-intensive maps, often employing machine learning methods, are appearing more and more frequently in the literature. However, to the wider community, it is not always transparent how these maps are made and how they should be interpreted. Furthermore, while these maps undoubtedly serve a decorative purpose in academic publications, it is not always apparent what extra information can be garnered from reading or making them.This Account attempts to answer such questions. We start with a concise summary of the theory of representing chemical environments, followed by the introduction of a simple yet practical conceptual approach for generating structure maps in a generic and automated manner. Such analysis and mapping is made nearly effortless by employing the newly developed software tool ASAP. To showcase the applicability to a wide variety of systems in chemistry and materials science, we provide several illustrative examples, including crystalline and amorphous materials, interfaces, and organic molecules. In these examples, the maps not only help to sift through large data sets but also reveal hidden patterns that could be easily missed using conventional analyses.The explosion in the amount of computed information in chemistry and materials science has made visualization into a science in itself. Not only have we benefited from exploiting these visualization methods in previous works, we also believe that the automated mapping of data sets will in turn stimulate further creativity and exploration, as well as ultimately feed back into future advances in the respective fields.}, author = {Cheng, Bingqing and Griffiths, Ryan-Rhys and Wengert, Simon and Kunkel, Christian and Stenczel, Tamas and Zhu, Bonan and Deringer, Volker L. and Bernstein, Noam and Margraf, Johannes T. and Reuter, Karsten and Csanyi, Gabor}, issn = {1520-4898}, journal = {Accounts of Chemical Research}, number = {9}, pages = {1981--1991}, publisher = {American Chemical Society}, title = {{Mapping materials and molecules}}, doi = {10.1021/acs.accounts.0c00403}, volume = {53}, year = {2020}, } @article{9685, abstract = {Hydrogen, the simplest and most abundant element in the Universe, develops a remarkably complex behaviour upon compression^1. Since Wigner predicted the dissociation and metallization of solid hydrogen at megabar pressures almost a century ago^2, several efforts have been made to explain the many unusual properties of dense hydrogen, including a rich and poorly understood solid polymorphism^1,3-5, an anomalous melting line6 and the possible transition to a superconducting state^7. Experiments at such extreme conditions are challenging and often lead to hard-to-interpret and controversial observations, whereas theoretical investigations are constrained by the huge computational cost of sufficiently accurate quantum mechanical calculations. Here we present a theoretical study of the phase diagram of dense hydrogen that uses machine learning to 'learn' potential-energy surfaces and interatomic forces from reference calculations and then predict them at low computational cost, overcoming length- and timescale limitations. We reproduce both the re-entrant melting behaviour and the polymorphism of the solid phase. Simulations using our machine-learning-based potentials provide evidence for a continuous molecular-to-atomic transition in the liquid, with no first-order transition observed above the melting line. This suggests a smooth transition between insulating and metallic layers in giant gas planets, and reconciles existing discrepancies between experiments as a manifestation of supercritical behaviour.}, author = {Cheng, Bingqing and Mazzola, Guglielmo and Pickard, Chris J. and Ceriotti, Michele}, issn = {1476-4687}, journal = {Nature}, number = {7824}, pages = {217--220}, publisher = {Springer Nature}, title = {{Evidence for supercritical behaviour of high-pressure liquid hydrogen}}, doi = {10.1038/s41586-020-2677-y}, volume = {585}, year = {2020}, } @unpublished{9699, abstract = {We investigate the structural similarities between liquid water and 53 ices, including 20 known crystalline phases. We base such similarity comparison on the local environments that consist of atoms within a certain cutoff radius of a central atom. We reveal that liquid water explores the local environments of the diverse ice phases, by directly comparing the environments in these phases using general atomic descriptors, and also by demonstrating that a machine-learning potential trained on liquid water alone can predict the densities, the lattice energies, and vibrational properties of the ices. The finding that the local environments characterising the different ice phases are found in water sheds light on water phase behaviors, and rationalizes the transferability of water models between different phases.}, author = {Monserrat, Bartomeu and Brandenburg, Jan Gerit and Engel, Edgar A. and Cheng, Bingqing}, booktitle = {arXiv}, title = {{Extracting ice phases from liquid water: Why a machine-learning water model generalizes so well}}, doi = {10.48550/arXiv.2006.13316}, year = {2020}, } @misc{9706, abstract = {Additional file 2: Supplementary Tables. The association of pre-adjusted protein levels with biological and technical covariates. Protein levels were adjusted for age, sex, array plate and four genetic principal components (population structure) prior to analyses. Significant associations are emboldened. (Table S1). pQTLs associated with inflammatory biomarker levels from Bayesian penalised regression model (Posterior Inclusion Probability > 95%). (Table S2). All pQTLs associated with inflammatory biomarker levels from ordinary least squares regression model (P < 7.14 × 10− 10). (Table S3). Summary of lambda values relating to ordinary least squares GWAS and EWAS performed on inflammatory protein levels (n = 70) in Lothian Birth Cohort 1936 study. (Table S4). Conditionally significant pQTLs associated with inflammatory biomarker levels from ordinary least squares regression model (P < 7.14 × 10− 10). (Table S5). Comparison of variance explained by ordinary least squares and Bayesian penalised regression models for concordantly identified SNPs. (Table S6). Estimate of heritability for blood protein levels as well as proportion of variance explained attributable to different prior mixtures. (Table S7). Comparison of heritability estimates from Ahsan et al. (maximum likelihood) and Hillary et al. (Bayesian penalised regression). (Table S8). List of concordant SNPs identified by linear model and Bayesian penalised regression and whether they have been previously identified as eQTLs. (Table S9). Bayesian tests of colocalisation for cis pQTLs and cis eQTLs. (Table S10). Sherlock algorithm: Genes whose expression are putatively associated with circulating inflammatory proteins that harbour pQTLs. (Table S11). CpGs associated with inflammatory protein biomarkers as identified by Bayesian model (Bayesian model; Posterior Inclusion Probability > 95%). (Table S12). CpGs associated with inflammatory protein biomarkers as identified by linear model (limma) at P < 5.14 × 10− 10. (Table S13). CpGs associated with inflammatory protein biomarkers as identified by mixed linear model (OSCA) at P < 5.14 × 10− 10. (Table S14). Estimate of variance explained for blood protein levels by DNA methylation as well as proportion of explained attributable to different prior mixtures - BayesR+. (Table S15). Comparison of variance in protein levels explained by genome-wide DNA methylation data by mixed linear model (OSCA) and Bayesian penalised regression model (BayesR+). (Table S16). Variance in circulating inflammatory protein biomarker levels explained by common genetic and methylation data (joint and conditional estimates from BayesR+). Ordered by combined variance explained by genetic and epigenetic data - smallest to largest. Significant results from t-tests comparing distributions for variance explained by methylation or genetics alone versus combined estimate are emboldened. (Table S17). Genetic and epigenetic factors identified by BayesR+ when conditioning on all SNPs and CpGs together. (Table S18). Mendelian Randomisation analyses to assess whether proteins with concordantly identified genetic signals are causally associated with Alzheimer’s disease risk. (Table S19).}, author = {Hillary, Robert F. and Trejo-Banos, Daniel and Kousathanas, Athanasios and McCartney, Daniel L. and Harris, Sarah E. and Stevenson, Anna J. and Patxot, Marion and Ojavee, Sven Erik and Zhang, Qian and Liewald, David C. and Ritchie, Craig W. and Evans, Kathryn L. and Tucker-Drob, Elliot M. and Wray, Naomi R. and McRae, Allan F. and Visscher, Peter M. and Deary, Ian J. and Robinson, Matthew Richard and Marioni, Riccardo E. }, publisher = {Springer Nature}, title = {{Additional file 2 of multi-method genome- and epigenome-wide studies of inflammatory protein levels in healthy older adults}}, doi = {10.6084/m9.figshare.12629697.v1}, year = {2020}, } @misc{9708, abstract = {This research data supports 'Hard antinodal gap revealed by quantum oscillations in the pseudogap regime of underdoped high-Tc superconductors'. A Readme file for plotting each figure is provided.}, author = {Hartstein, Mate and Hsu, Yu-Te and Modic, Kimberly A and Porras, Juan and Loew, Toshinao and Le Tacon, Matthieu and Zuo, Huakun and Wang, Jinhua and Zhu, Zengwei and Chan, Mun and McDonald, Ross and Lonzarich, Gilbert and Keimer, Bernhard and Sebastian, Suchitra and Harrison, Neil}, publisher = {Apollo - University of Cambridge}, title = {{Accompanying dataset for 'Hard antinodal gap revealed by quantum oscillations in the pseudogap regime of underdoped high-Tc superconductors'}}, doi = {10.17863/cam.50169}, year = {2020}, }