More Like this

1. Low-Latency Graph Streaming using Compressed Purely-Functional Trees

   Dhulipala, Laxman; Blelloch, Guy; Shun, Julian (June 2019, Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI))

   There has been a growing interest in the graph-streaming setting where a continuous stream of graph updates is mixed with graph queries. In principle, purely-functional trees are an ideal fit for this setting as they enable safe parallelism, lightweight snapshots, and strict serializability for queries. However, directly using them for graph processing leads to significant space overhead and poor cache locality. This paper presents C-trees, a compressed purely-functional search tree data structure that significantly improves on the space usage and locality of purely-functional trees. We design theoretically-efficient and practical algorithms for performing batch updates to C-trees, and also show that we can store massive dynamic real-world graphs using only a few bytes per edge, thereby achieving space usage close to that of the best static graph processing frameworks. To study the applicability of our data structure, we designed Aspen, a graph-streaming framework that extends the interface of Ligra with operations for updating graphs. We show that Aspen is faster than two state-of-the-art graph-streaming systems, Stinger and LLAMA, while requiring less memory, and is competitive in performance with the state-of-the-art static graph frameworks, Galois, GAP, and Ligra+. With Aspen, we are able to efficiently process the largest publicly-available graph with over two hundred billion edges in the graph-streaming setting using a single commodity multicore server with 1TB of memory. 

   more » « less
2. Learning Hyperbolic Embedding for Phylogenetic Tree Placement and Updates

   https://doi.org/10.3390/biology11091256  

   Jiang, Yueyu; Tabaghi, Puoya; Mirarab, Siavash (September 2022, Biology)

   Phylogenetic placement, used widely in ecological analyses, seeks to add a new species to an existing tree. A deep learning approach was previously proposed to estimate the distance between query and backbone species by building a map from gene sequences to a high-dimensional space that preserves species tree distances. They then use a distance-based placement method to place the queries on that species tree. In this paper, we examine the appropriate geometry for faithfully representing tree distances while embedding gene sequences. Theory predicts that hyperbolic spaces should provide a drastic reduction in distance distortion compared to the conventional Euclidean space. Nevertheless, hyperbolic embedding imposes its own unique challenges related to arithmetic operations, exponentially-growing functions, and limited bit precision, and we address these challenges. Our results confirm that hyperbolic embeddings have substantially lower distance errors than Euclidean space. However, these better-estimated distances do not always lead to better phylogenetic placement. We then show that the deep learning framework can be used not just to place on a backbone tree but to update it to obtain a fully resolved tree. With our hyperbolic embedding framework, species trees can be updated remarkably accurately with only a handful of genes. 

   more » « less
3. High-throughput continuous evolution of compact Cas9 variants targeting single-nucleotide-pyrimidine PAMs

   https://doi.org/10.1038/s41587-022-01410-2  

   Huang, Tony P.; Heins, Zachary J.; Miller, Shannon M.; Wong, Brandon G.; Balivada, Pallavi A.; Wang, Tina; Khalil, Ahmad S.; Liu, David R. (January 2023, Nature Biotechnology)

   Abstract Despite the availability of Cas9 variants with varied protospacer-adjacent motif (PAM) compatibilities, some genomic loci—especially those with pyrimidine-rich PAM sequences—remain inaccessible by high-activity Cas9 proteins. Moreover, broadening PAM sequence compatibility through engineering can increase off-target activity. With directed evolution, we generated four Cas9 variants that together enable targeting of most pyrimidine-rich PAM sequences in the human genome. Using phage-assisted noncontinuous evolution and eVOLVER-supported phage-assisted continuous evolution, we evolved Nme2Cas9, a compact Cas9 variant, into variants that recognize single-nucleotide pyrimidine-PAM sequences. We developed a general selection strategy that requires functional editing with fully specified target protospacers and PAMs. We applied this selection to evolve high-activity variants eNme2-T.1, eNme2-T.2, eNme2-C and eNme2-C.NR. Variants eNme2-T.1 and eNme2-T.2 offer access to N₄TN PAM sequences with comparable editing efficiencies as existing variants, while eNme2-C and eNme2-C.NR offer less restrictive PAM requirements, comparable or higher activity in a variety of human cell types and lower off-target activity at N₄CN PAM sequences. 

   more » « less
4. Flexibility in PAM recognition expands DNA targeting in xCas9

   https://doi.org/10.7554/eLife.102538  

   Hossain, Kazi A; Nierzwicki, Lukasz; Orozco, Modesto; Czub, Jacek; Palermo, Giulia (February 2025, eLife)

   xCas9 is an evolved variant of the CRISPR-Cas9 genome editing system, engineered to improve specificity and reduce undesired off-target effects. How xCas9 expands the DNA targeting capability of Cas9 by recognising a series of alternative protospacer adjacent motif (PAM) sequences while ignoring others is unknown. Here, we elucidate the molecular mechanism underlying xCas9’s expanded PAM recognition and provide critical insights for expanding DNA targeting. We demonstrate that while wild-type Cas9 enforces stringent guanine selection through the rigidity of its interacting arginine dyad, xCas9 introduces flexibility in R1335, enabling selective recognition of specific PAM sequences. This increased flexibility confers a pronounced entropic preference, which also improves recognition of the canonical TGG PAM. Furthermore, xCas9 enhances DNA binding to alternative PAM sequences during the early evolution cycles, while favouring binding to the canonical PAM in the final evolution cycle. This dual functionality highlights how xCas9 broadens PAM recognition and underscores the importance of fine-tuning the flexibility of the PAM-interacting cleft as a key strategy for expanding the DNA targeting potential of CRISPR-Cas systems. These findings deepen our understanding of DNA recognition in xCas9 and may apply to other CRISPR-Cas systems with similar PAM recognition requirements. 

   more » « less
5. Bolt: Fast Inference for Random Forests

   https://doi.org/10.1145/3528535.3531519  

   Romero, Eduardo; Stewart, Christopher; Li, Angela; Hale, Kyle; Morris, Nathaniel (October 2022, Proceedings of the 23rd ACM/IFIP International Middleware Conference)

   Random forests use ensembles of decision trees to boost accuracy for machine learning tasks. However, large ensembles slow down inference on platforms that process each tree in an ensemble individually. We present Bolt, a platform that restructures whole random forests, not just individual trees, to speed up inference. Conceptually, Bolt maps every path in each tree to a lookup table which, if cache were large enough, would allow inference with just one memory access. When the size of the lookup table exceeds cache capacity, Bolt employs a novel combination of lossless compression, parameter selection, and bloom filters to shrink the table while preserving fast inference. We compared inference speed in Bolt to three state-of-the-art platforms: Python Scikit-Learn, Ranger, and Forest Packing. We evaluated these platforms using datasets with vision, natural language processing and categorical applications. We observed that on ensembles of shallow decision trees Bolt can run 2-14X faster than competing platforms and that Bolt's speedups persist as the number of decision trees in an ensemble increases. 

   more » « less