Search for: All records

The prediction of stable crystal structures is an important part of designing solid-state crystalline materials with desired properties. Recent advances in structural feature representations and generative neural networks promise the ability to efficiently create new stable structures to use for inverse design and to search for materials with tailored functionalities. 

Many deployments of differential privacy in industry are in the local model, where each party releases its private information via a differentially private randomizer. We study triangle counting in the noninteractive and interactive local model with edge differential privacy (that, intuitively, requires that the outputs of the algorithm on graphs that differ in one edge be indistinguishable). In this model, each party’s local view consists of the adjacency list of one vertex. In the noninteractive model, we prove that additive Ω(n^2) error is necessary, where n is the number of nodes. This lower bound is our main technical contribution. It uses a reconstruction attack with a new class of linear queries and a novel mix-and-match strategy of running the local randomizers with different completions of their adjacency lists. It matches the additive error of the algorithm based on Randomized Response, proposed by Imola, Murakami and Chaudhuri (USENIX2021) and analyzed by Imola, Murakami and Chaudhuri (CCS2022) for constant ε. We use a different postprocessing of Randomized Response and provide tight bounds on the variance of the resulting algorithm. In the interactive setting, we prove a lower bound of Ω(n3/2) on the additive error. Previously, no hardness results were known for interactive, edge-private algorithms in the local model, except for those that follow trivially from the results for the central model. Our work significantly improves on the state of the art in differentially private graph analysis in the local model. 

Abstract Gut microbiomes, such as the microbial community that colonizes the rumen, have vast catabolic potential and play a vital role in host health and nutrition. By expanding our understanding of metabolic pathways in these ecosystems, we will garner foundational information for manipulating microbiome structure and function to influence host physiology. Currently, our knowledge of metabolic pathways relies heavily on inferences derived from metagenomics or culturing bacteria in vitro. However, novel approaches targeting specific cell physiologies can illuminate the functional potential encoded within microbial (meta)genomes to provide accurate assessments of metabolic abilities. Using fluorescently labeled polysaccharides, we visualized carbohydrate metabolism performed by single bacterial cells in a complex rumen sample, enabling a rapid assessment of their metabolic phenotype. Specifically, we identified bovine-adapted strains of Bacteroides thetaiotaomicron that metabolized yeast mannan in the rumen microbiome ex vivo and discerned the mechanistic differences between two distinct carbohydrate foraging behaviors, referred to as “medium grower” and “high grower.” Using comparative whole-genome sequencing, RNA-seq, and carbohydrate-active enzyme fingerprinting, we could elucidate the strain-level variability in carbohydrate utilization systems of the two foraging behaviors to help predict individual strategies of nutrient acquisition. Here, we present a multi-faceted study using complimentary next-generation physiology and “omics” approaches to characterize microbial adaptation to a prebiotic in the rumen ecosystem. 

Abstract Protamine proteins dramatically condense DNA in sperm to almost crystalline packing levels. Here, we measure the first step in the in vitro pathway, the folding of DNA into a single loop. Current models for DNA loop formation are one-step, all-or-nothing models with a looped state and an unlooped state. However, when we use a Tethered Particle Motion (TPM) assay to measure the dynamic, real-time looping of DNA by protamine, we observe the presence of multiple folded states that are long-lived (∼100 s) and reversible. In addition, we measure folding on DNA molecules that are too short to form loops. This suggests that protamine is using a multi-step process to loop the DNA rather than a one-step process. To visualize the DNA structures, we used an Atomic Force Microscopy (AFM) assay. We see that some folded DNA molecules are loops with a ∼10-nm radius and some of the folded molecules are partial loops—c-shapes or s-shapes—that have a radius of curvature of ∼10 nm. Further analysis of these structures suggest that protamine is bending the DNA to achieve this curvature rather than increasing the flexibility of the DNA. We therefore conclude that protamine loops DNA in multiple steps, bending it into a loop.