PaperlayerView exact revision on arXiv

Source-linked AI summary

OLGA: fast computation of generation probabilities of B- and T-cell receptor amino acid sequences and motifs

Zachary Sethna, Yuval Elhanati, Curtis G. Callan, Aleksandra M. Walczak, Thierry Mora

arXiv:1807.04425v2q-bio.GN

TL;DR

Generation probabilities are difficult to compute at the amino-acid level because many nucleotide sequences can encode the same receptor sequence. OLGA uses dynamic programming to calculate probabilities for CDR3 amino acid sequences and motifs, with or without V/J restriction, and its results agree closely with Monte Carlo estimates while operating much faster. The tool is applied to repertoire and epitope-specific receptor data, including analyses relevant to vaccine design.

  • Problem

    Amino-acid receptor generation probabilities are important because receptor function depends on protein sequence, but brute-force summation over synonymous nucleotide sequences is computationally intractable.

  • Method

    OLGA uses dynamic programming to calculate CDR3 amino acid sequence and motif generation probabilities, with or without V/J restriction, across supported B- and T-cell receptor loci.

  • Results

    OLGA agrees closely with Monte Carlo estimates and computes 10^6 mouse TRB amino acid sequence probabilities at 47 seqs/CPU/sec, versus 4313 CPU hours for Monte Carlo.

  • Takeaways & Limitations

    OLGA can estimate baseline receptor frequencies and repertoire fractions for disease-associated epitopes, supporting analyses of public repertoires, reactive T-cell clusters, and vaccine design.

Abstract

from arXiv · show

Motivation: High-throughput sequencing of large immune repertoires has enabled the development of methods to predict the probability of generation by V(D)J recombination of T- and B-cell receptors of any specific nucleotide sequence. These generation probabilities are very non-homogeneous, ranging over 20 orders of magnitude in real repertoires. Since the function of a receptor really depends on its protein sequence, it is important to be able to predict this probability of generation at the amino acid level. However, brute-force summation over all the nucleotide sequences with the correct amino acid translation is computationally intractable. The purpose of this paper is to present a solution to this problem. Results: We use dynamic programming to construct an efficient and flexible algorithm, called OLGA (Optimized Likelihood estimate of immunoGlobulin Amino-acid sequences), for calculating the probability of generating a given CDR3 amino acid sequence or motif, with or without V/J restriction, as a result of V(D)J recombination in B or T cells. We apply it to databases of epitope-specific T-cell receptors to evaluate the probability that a typical human subject will possess T cells responsive to specific disease-associated epitopes. The model prediction shows an excellent agreement with published data. We suggest that OLGA may be a useful tool to guide vaccine design. Availability: Source code is available at https://github.com/zsethna/OLGA

I. INTRODUCTION

BCRs and TCRs arise through stochastic V(D)J recombination, making nucleotide-sequence generation probabilities definable but amino-acid probabilities difficult to compute. OLGA addresses this challenge while supporting sequence and motif analysis relevant to immune-repertoire studies.

  • Repertoire applications: Repertoire sequencing identifies clusters of similar receptor amino acid sequences and responsive motifs, motivating efficient probability calculations for these patterns.Such data are used across healthy repertoires, disease cohorts, and antigen-response experiments.
  • Recombination model: BCR and TCR generation combines germline template selection with random nucleotide deletions and insertions at junctions.These events define the generative model and its possible recombination outcomes.
  • Generation probabilities: A nucleotide sequence’s generation probability sums the probabilities of all recombination events that can produce it.The same nucleotide sequence may be generated by multiple specific events.
  • Amino-acid probabilities: An amino acid sequence’s generation probability requires summing over all nucleotide sequences that translate into it.Codon degeneracy makes this amino-acid-level calculation impractical by brute force.
  • Generalized sequence classes: The framework generalizes beyond standard amino-acid translation to arbitrary codon classes, including groups defined by chemical properties or position-dependent rules.This supports motif-like constraints and other amino-acid groupings.

B. Dynamic programming computation of the generation probability of amino acid sequences

OLGA computes amino-acid CDR3 generation probabilities by decomposing recombination into segment weights and recursively combining them with dynamic programming. The method tracks codon-boundary nucleotide information while avoiding explicit enumeration of compatible nucleotide sequences.

  • Dynamic-programming decomposition: OLGA sums over segment boundaries, germline templates, and nucleotide choices consistent with the amino acid sequence.The five contiguous segments are V, N1, D, N2, and J, with four boundary positions.
  • Segment weights: Cumulated weights represent V completion, VD and DJ insertions, D segments conditioned on D choice, and J segments conditioned on D choice.The D-conditioned J weights account for dependence between D and J germline choices.
  • Codon-aware state tracking: Codon-aware vectors and matrices retain nucleotide identity at incomplete codon boundaries and contract over nucleotide states during multiplication.At positions divisible by three, the corresponding weights become scalars; other positions retain four-nucleotide information.
  • Restrictions and motifs: The algorithm restricts germline-segment sums to selected genes when V/J restriction is requested.The same compatibility calculations support particular germline genes and incomplete-codon motif matching.
  • Computational complexity: 4 × 4 recursive matrix multiplications reduce insertion calculations to O(L^2) operations instead of exponential brute-force enumeration.The complete generation-probability procedure also has O(L^2) computational complexity.

III. RESULTS

OLGA’s amino-acid generation-probability calculations agree with Monte Carlo estimates while requiring far less computation than sampling or exhaustive nucleotide enumeration. The evaluation uses receptor sequences from human and mouse immune-repertoire models.

  • Method validation: Monte Carlo estimates and OLGA calculations agree for mouse TRB up to Poisson noise in the sampling estimate.The comparison used 5 × 10^11 recombination events and more than 98% of sampled sequences were generated at least twice.
  • Method validation: 4.82 × 10−7 bits is the Kullback-Leibler divergence between the Monte Carlo and OLGA distributions.This provides a formal measure of their agreement for the mouse TRB validation.
  • Performance comparison: 47 seqs/CPU/sec is OLGA’s rate for computing generation probabilities for 10^6 mouse TRB amino acid sequences.The calculation took 6 CPU hours, compared with 4313 CPU hours for Monte Carlo estimation.
  • Performance comparison: Each mouse validation amino acid sequence corresponds on average to 1.84 billion nucleotide sequences, making exhaustive nucleotide enumeration computationally expensive.The comparison highlights the combinatorial burden of translating amino-acid queries into nucleotide-level calculations.
  • Probability distributions: The reported probability distributions compare recombination-generation probabilities across nucleotide, amino-acid, and broader sequence contexts for sampled productive sequences.The distributions are summarized using entropies in bits, with dotted lines indicating distribution means after the stated conversion factor.

C. Distribution of generation probabilities and diversity

OLGA characterizes amino-acid generation probabilities across receptor loci and epitope-specific repertoires, revealing broad diversity and substantial cross-species overlap. It also sums sequence probabilities to estimate repertoire fractions specific to disease-associated epitopes.

  • Distribution of generation probabilities and diversity: Generation probabilities span up to 20 orders of magnitude, and amino-acid coarse-graining shifts the distribution relative to nucleotide and recombination-event probabilities.The paper compares P aa_gen with P nt_gen and P rec_gen across human and mouse TRB, human TRA, and human IGH.
  • Cross-species generation probabilities: 72.6% of human CDR3s can theoretically be produced by mice, while 100% of mouse CDR3s can be produced by humans.Cross-species generation probabilities are lower than within-species probabilities but remain correlated.
  • Epitope-specific repertoire fractions: OLGA estimates an epitope-specific repertoire fraction by summing P aa_gen across known reactive TRB sequences.The approach is applied to epitope-specific TCR sequences from VDJdb.
  • Epitope-specific repertoire fractions: 10^-7 to 10^-4 of the repertoire is specific to the hepatitis C and influenza A epitopes analyzed, a fraction considered large enough for many reactive cells in naive repertoires.Figure 4 reports results for 4 hepatitis C epitopes and 5 influenza A epitopes.
  • Epitope-specific generation probabilities: Epitope-specific TRB generation-probability distributions are similar to healthy-background distributions across viral and pathogen-associated datasets.The result indicates no strong correlation between CDR3 generation probability and response to a particular disease epitope.

F. Model accurately predicts the frequencies of sequences and of groups of specific sequences

OLGA’s sequence probabilities agree with observed repertoire frequencies and support group-level analyses of epitope-specific sequences and motifs. Its motif calculations also show high generation probabilities for invariant T-cell receptor chains.

  • Sequence-frequency prediction: Observed presence frequencies of VDJdb CDR3 sequences were compared with OLGA probabilities across 648 individuals after excluding read counts.The analysis used presence or absence per individual to reduce effects of clonal expansion and PCR amplification bias.
  • Sequence-frequency prediction: Agreement between measured and predicted frequencies was excellent for individual sequences and for epitope-specific repertoire subsets.The group-level comparison covered epitopes associated with 6 viruses.
  • Motif probabilities: OLGA computes motif probabilities using multiple amino-acid choices and applies this capability to epitope-specific and invariant T-cell motifs.The motif examples include TRA and TRB VJ-CDR3 combinations for Epstein-Barr virus and influenza epitopes, plus invariant-cell TRA motifs.
  • Motif probabilities: The relatively high probabilities of iNKT- and MAIT-associated TRA motifs imply frequent generation in primary repertoires shared across individuals.The motifs were assembled from sequences reported by Gherardin et al.

IV. DISCUSSION

The discussion presents OLGA as a fast framework for baseline generation probabilities, repertoire outlier detection, and epitope-focused analyses. It identifies potential applications in vaccine and therapy design while emphasizing that repertoire presence also depends on chain pairing and selection.

  • IV. DISCUSSION: Dynamic programming lets OLGA process approximately 50 sequences per second on a single CPU while computing CDR3 sequence and motif probabilities.The current implementation covers four loci and can incorporate additional loci or species through compatible recombination models.
  • IV. DISCUSSION: The method evaluates single-chain generation probabilities, while whole-TCR probabilities can be obtained by multiplying paired-chain probabilities when chain pairing is close to independent.The paper notes that α and β recombination probabilities and function-dependent selection also affect TCR presence.
  • IV. DISCUSSION: OLGA can establish baseline receptor frequencies, identify outlying repertoire sequences, and quantify the origin of public repertoires through convergent recombination.The discussion also proposes focusing vaccine and therapy design on clonotypes likely to occur across individuals.
  • IV. DISCUSSION: Epitope-specific TCRs in the analyzed database did not differ in generation probability from random healthy-donor TCRs, although viral epitopes varied in repertoire coverage.The authors suggest that epitopes targeting more frequently generated receptors could have broader vaccine success.

Appendix A: Additional matrix definitions for VDJ algorithm

The VDJ dynamic program is expressed as matrix products over nucleotide positions, with matrices representing templated genes and non-templated insertions while tracking codon alignment.

  • Algorithm structure: The algorithm summarizes VDJ generation by summing matrix products over positions x1, x2, x3, and x4.The matrices are multiplied iteratively to account for the recombination model.
  • Indexing conventions: Nucleotide positions are mapped to amino-acid indices and codon positions from both sequence directions.xj = 3(ij −1) + uj, where ij identifies the codon and uj its position within that codon; u∗j tracks position from the right.
  • Insertion segments: Non-templated N1 and N2 insertions are represented by products of transfer matrices with dimensions determined by codon alignment.These transfer matrices sum Markov insertion-model contributions over nucleotides and all codons consistent with the amino acid sequence.
  • Insertion segments: The N2 insertion contribution handles cases where the relevant nucleotide positions lie in the same or different amino-acid codons.Separate forms are specified for i4 > i3 and i3 = i4.

e. J (D)x4

The J-segment contribution is encoded as a matrix whose size depends on the codon position at the segment boundary and whose sequence is defined relative to a conserved residue.

  • J-segment contribution: The J germline sequence sJ is read 5′ to 3′, with lJ measuring its length up to a conserved residue, generally F or W.The indexing conventions for the sequence partition are illustrated in Fig. S1.

Appendix B: VJ recombination

The VJ algorithm closely parallels the VDJ algorithm but omits the D and N2 segments and incorporates a joint V,J distribution to model TRA-chain correlation.

  • VJ model: VJ recombination lacks a D segment and an N2 insertion segment compared with VDJ recombination.The algorithm used to compute Pgen therefore has a similar structure to the VDJ procedure.
  • VJ model: A joint V,J distribution is included because a strong correlation between V and J templates is observed in the TRA chain.This correlation is incorporated directly into the VJ generative model.
  • Dynamic programming: The VJ dynamic program retains the notation conventions of the VDJ algorithm and has a similar matrix-based form.The implementation breakdown across V, N, and J contributions is schematized in Fig. S2.

a. V(J )x1

The VJ algorithm includes separate matrix contributions for templated V genes and non-templated insertions at the VJ junction.

  • V contribution: The templated V-gene contribution is represented as a distinct component of the VJ algorithm.It parallels the corresponding V contribution in the VDJ formulation.
  • VJ insertion: The VJ-junction insertion contribution Mx1x2 is defined as a product of transfer matrices using VJ-specific model parameters.It uses SVJ, PinsVJ, and p0 from a VJ recombination model.

c. J (J)x2

OLGA computes amino-acid CDR3 generation probabilities efficiently through dynamic programming, with practical runtime scaling near linearly in CDR3 length and outperforming the compared alternatives.

  • Algorithm and validation: OLGA was validated against Monte Carlo estimates, with deviations from equality consistent with expected Poisson statistics.The comparison includes one- and two-sigma curves reflecting sampling noise in the Monte Carlo estimates.
  • Algorithm and validation: OLGA’s dynamic-programming summation combines V, N1, D, N2, and J contributions while accounting for D–J dependence.The computation proceeds inward from both CDR3 ends and sums over segment positions, boundaries, and germline templates.
  • Computational performance: 184 seqs/CPU second is achieved for a VJ model after excluding J genes that contribute zero probability.For human TRA, the insertion step is repeated across J alleles, but alignment-based exclusions substantially accelerate computation.
  • Computational performance: OLGA’s runtime scales approximately linearly with CDR3 length in practice, despite an algorithmic worst-case complexity of O(L2).This behavior persists even for fully ambiguous amino-acid sequences because the model has finite insertion and D-sequence parameter ranges.
  • Computational performance: For CDR3 length 4, OLGA processes 122 seqs/CPU second versus 0.33 seqs/CPU second for IGoR amino-acid evaluation by nucleotide enumeration.The number of nucleotide sequences encoding an amino-acid sequence grows exponentially with length, creating a severe IGoR bottleneck.
  • Computational performance: Monte Carlo estimation scales as 1/Pgen and can be noisy or miss sequences, whereas OLGA remains faster for plausible dataset sizes.The estimated Monte Carlo crossing points correspond to unrealistic numbers of sequences under the stated noise tolerance.

Appendix E: Generation probability distributions from RNA-derived repertoires

OLGA’s generation-probability distributions are broadly robust across RNA-derived repertoires and sample sizes, while revealing species- and protocol-dependent differences. Cross-species evaluations show strongly reduced probabilities under the other species’ model, and pathogen-response distributions remain similar to background repertoires.

  • RNA-derived repertoires: Two of three RNA-derived TRB repertoires closely match DNA-based generation-probability distributions.The glioblastoma repertoire shows a systematic shift toward more frequent low-generation-probability sequences, whose biological significance is unresolved.
  • Cross-species Pgen: Human and mouse TRB sequences generally receive substantially lower Pgen values under the other species’ model.The asymmetry is strongest for human sequences evaluated with the mouse model, where 27.4% have Pgen = 0.
  • Cross-species Pgen: Cross-species Pgen differences are primarily associated with distinct insertion profiles and, consequently, CDR3 length distributions.Despite these differences, the analyses suggest that some CDR3 sharing between mouse and human repertoires can arise by chance.
  • RNA-derived repertoires: Smaller RNA-derived samples mainly increase noise while preserving generation-probability distribution shape.Multiple samples from the Sims et al. study are statistically consistent with the largest samples despite greater variability.
  • Pathogen-response repertoires: Pathogen-responsive T-cell sequences have Pgen distributions indistinguishable from peripheral-blood background distributions within statistical noise.Becattini et al.’s controlled stimulation experiment further supports the conclusion that pathogen-response activity is uncorrelated with Pgen.
Loading 1807.04425v2…