skip to main content

Title: How a well-adapting immune system remembers
An adaptive agent predicting the future state of an environment must weigh trust in new observations against prior experiences. In this light, we propose a view of the adaptive immune system as a dynamic Bayesian machinery that updates its memory repertoire by balancing evidence from new pathogen encounters against past experience of infection to predict and prepare for future threats. This framework links the observed initial rapid increase of the memory pool early in life followed by a midlife plateau to the ease of learning salient features of sparse environments. We also derive a modulated memory pool update rule in agreement with current vaccine-response experiments. Our results suggest that pathogenic environments are sparse and that memory repertoires significantly decrease infection costs, even with moderate sampling. The predicted optimal update scheme maps onto commonly considered competitive dynamics for antigen receptors.  more » « less
Award ID(s):
Author(s) / Creator(s):
; ; ;
Date Published:
Journal Name:
Proceedings of the National Academy of Sciences
Page Range / eLocation ID:
8815 to 8823
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract Background

    CRISPR-Cas (clustered regularly interspaced short palindromic repeats—CRISPR-associated proteins) systems are adaptive immune systems commonly found in prokaryotes that provide sequence-specific defense against invading mobile genetic elements (MGEs). The memory of these immunological encounters are stored in CRISPR arrays, where spacer sequences record the identity and history of past invaders. Analyzing such CRISPR arrays provide insights into the dynamics of CRISPR-Cas systems and the adaptation of their host bacteria to rapidly changing environments such as the human gut.


    In this study, we utilized 601 publicly availableBacteroides fragilisgenome isolates from 12 healthy individuals, 6 of which include longitudinal observations, and 222 availableB. fragilisreference genomes to update the understanding ofB. fragilisCRISPR-Cas dynamics and their differential activities. Analysis of longitudinal genomic data showed that some CRISPR array structures remained relatively stable over time whereas others involved radical spacer acquisition during some periods, and diverse CRISPR arrays (associated with multiple isolates) co-existed in the same individuals with some persisted over time. Furthermore, features of CRISPR adaptation, evolution, and microdynamics were highlighted through an analysis of host-MGE network, such as modules of multiple MGEs and hosts, reflecting complex interactions betweenB. fragilisand its invaders mediated through the CRISPR-Cas systems.


    We made available of all annotated CRISPR-Cas systems and their target MGEs, and their interaction network as a web resource at We anticipate it will become an important resource for studying ofB. fragilis, its CRISPR-Cas systems, and its interaction with mobile genetic elements providing insights into evolutionary dynamics that may shape the species virulence and lead to its pathogenicity.

    more » « less
  2. We provide the first sub-linear space and sub-linear regret algorithm for online learning with expert advice (against an oblivious adversary), addressing an open question raised recently by Srinivas, Woodruff, Xu and Zhou (STOC 2022). We also demonstrate a separation between oblivious and (strong) adaptive adversaries by proving a linear memory lower bound of any sub-linear regret algorithm against an adaptive adversary. Our algorithm is based on a novel pool selection procedure that bypasses the traditional wisdom of leader selection for online learning, and a generic reduction that transforms any weakly sub-linear regret o(T) algorithm to T1-α regret algorithm, which may be of independent interest. Our lower bound utilizes the connection of no-regret learning and equilibrium computation in zero-sum games, leading to a proof of a strong lower bound against an adaptive adversary. 
    more » « less
  3. Animals encounter many novel and unpredictable challenges when moving into new areas including pathogen exposure. Because effective immune defenses against such threats can be costly, plastic immune responses could be particularly advantageous, as such defenses can be engaged only when context warrants activation. DNA methylation is a key regulator of plasticity via its effects on gene expression. In vertebrates, DNA methylation occurs exclusively at CpG dinucleotides, and typically, high DNA methylation decreases gene expression, particularly when it occurs in promoters. The CpG content of gene regulatory regions may therefore represent one form of epigenetic potential (EP), a genomic means to capacitate gene expression and hence adaptive phenotypic plasticity. Non-native populations of house sparrows (Passer domesticus) - one of the world's most cosmopolitan species – have high EP in the promoter of a key microbial surveillance gene, Toll-like receptor 4 (TLR4), compared to native populations. We previously hypothesized that high EP may enable sparrows to balance the costs and benefits of inflammatory immune responses well, a trait critical to success in novel environments. In the present study, we found support for this hypothesis: house sparrows with high EP in TLR4 promoter were better able to resist a pathogenic Salmonella enterica infection than sparrows with low EP. These results support the idea that high EP contributes to invasion and perhaps adaptation in novel environments, but the mechanistic details whereby these organismal effects arise remain obscure.

    more » « less
  4. We study the fully dynamic All-Pairs Shortest Paths (APSP) problem in undirected edge-weighted graphs. Given an n-vertex graph G with non-negative edge lengths, that undergoes an online sequence of edge insertions and deletions, the goal is to support approximate distance queries and shortest-path queries. We provide a deterministic algorithm for this problem, that, for a given precision parameter є, achieves approximation factor (loglogn)2O(1/є3), and has amortized update time O(nєlogL) per operation, where L is the ratio of longest to shortest edge length. Query time for distance-query is O(2O(1/є)· logn· loglogL), and query time for shortest-path query is O(|E(P)|+2O(1/є)· logn· loglogL), where P is the path that the algorithm returns. To the best of our knowledge, even allowing any o(n)-approximation factor, no adaptive-update algorithms with better than Θ(m) amortized update time and better than Θ(n) query time were known prior to this work. We also note that our guarantees are stronger than the best current guarantees for APSP in decremental graphs in the adaptive-adversary setting. In order to obtain these results, we consider an intermediate problem, called Recursive Dynamic Neighborhood Cover (RecDynNC), that was formally introduced in [Chuzhoy, STOC ’21]. At a high level, given an undirected edge-weighted graph G undergoing an online sequence of edge deletions, together with a distance parameter D, the goal is to maintain a sparse D-neighborhood cover of G, with some additional technical requirements. Our main technical contribution is twofolds. First, we provide a black-box reduction from APSP in fully dynamic graphs to the RecDynNC problem. Second, we provide a new deterministic algorithm for the RecDynNC problem, that, for a given precision parameter є, achieves approximation factor (loglogm)2O(1/є2), with total update time O(m1+є), where m is the total number of edges ever present in G. This improves the previous algorithm of [Chuzhoy, STOC ’21], that achieved approximation factor (logm)2O(1/є) with similar total update time. Combining these two results immediately leads to the deterministic algorithm for fully-dynamic APSP with the guarantees stated above. 
    more » « less
  5. Abstract

    In recent years, tissue‐resident memory T cells (TRM) have attracted significant attention in the field of vaccine development. Distinct from central and effector memory T cells, TRMcells take up residence in home tissues such as the lung or urogenital tract and are ideally positioned to respond quickly to pathogen encounter. TRMare found to play a role in the immune response against many globally important infectious diseases for which new or improved vaccines are needed, including influenza and tuberculosis. It is also increasingly clear that TRMplay a pivotal role in cancer immunity. Thus, vaccines that can generate this memory T cell population are highly desirable. The field of immunoengineering—that is, the application of engineering principles to study the immune system and design new and improved therapies that harness or modulate immune responses—is ideally poised to provide solutions to this need for next‐generation TRMvaccines. This review covers recent developments in vaccine technologies for generating TRMand protecting against infection and cancer, including viral vectors, virus‐like particles, and synthetic and natural biomaterials. In addition, it offers critical insights on the future of engineering vaccines for tissue‐resident memory T cells.

    more » « less