plaintop table [figure]subcapbesideposition = top 11institutetext:  Computer
Science and Engineering, The Ohio State University, Columbus, OH 43210, USA
11email<EMAIL_ADDRESS>22institutetext: Machine Learning Department, NEC
Labs, Princeton, NJ 08540, USA
22email<EMAIL_ADDRESS>33institutetext: Digital Technologies
Research Centre, National Research Council Canada, Ontario, Canada
44institutetext: Department of Medicine, Baylor College of Medicine, Houston,
TX 77030, USA 55institutetext: NEC Oncolmmunity AS, Oslo Cancer Cluster,
Innovation Park, Ullernchausséen 64, 0379, Oslo, Norway 66institutetext:
Biomedical Informatics, The Ohio State University, Columbus, OH 43210, USA
77institutetext: Translational Data Analytics Institute, The Ohio State
University, Columbus, OH 43210, USA

# T-Cell Receptor Optimization with Reinforcement Learning and Mutation
Polices for Precision Immunotherapy

Ziqi Chen 11 Martin Renqiang Min${}^{(\text{{\char 0\relax}})}$ 22 Hongyu Guo
33 Chao Cheng 44 Trevor Clancy 55 Xia Ning ${}^{(\text{{\char 0\relax}})}$
116677

###### Abstract

T cells monitor the health status of cells by identifying foreign peptides
displayed on their surface. T-cell receptors (TCRs), which are protein
complexes found on the surface of T cells, are able to bind to these peptides.
This process is known as TCR recognition and constitutes a key step for immune
response. Optimizing TCR sequences for TCR recognition represents a
fundamental step towards the development of personalized treatments to trigger
immune responses killing cancerous or virus-infected cells. In this paper, we
formulated the search for these optimized TCRs as a reinforcement learning
($\mathop{\mathtt{RL}}\limits$) problem, and presented a framework
$\mathop{\mathtt{TCRPPO}}\limits$ with a mutation policy using proximal policy
optimization. $\mathop{\mathtt{TCRPPO}}\limits$ mutates TCRs into effective
ones that can recognize given peptides. $\mathop{\mathtt{TCRPPO}}\limits$
leverages a reward function that combines the likelihoods of mutated sequences
being valid TCRs measured by a new scoring function based on deep
autoencoders, with the probabilities of mutated sequences recognizing peptides
from a peptide-TCR interaction predictor. We compared
$\mathop{\mathtt{TCRPPO}}\limits$ with multiple baseline methods and
demonstrated that $\mathop{\mathtt{TCRPPO}}\limits$ significantly outperforms
all the baseline methods to generate positive binding and valid TCRs. These
results demonstrate the potential of $\mathop{\mathtt{TCRPPO}}\limits$ for
both precision immunotherapy and peptide-recognizing TCR motif discovery.

###### Keywords:

T-cell Receptor Immunotherapy Reinforcement Learning Biological Sequence
Design

##  1 Introduction

Immunotherapy is a fundamental treatment for human diseases, which uses a
person’s immune system to fight diseases [35, 10, 36]. In the immune system,
immune response is triggered by cytotoxic T cells which are activated by the
engagement of the T cell receptors (TCRs) with immunogenic peptides presented
by Major Histocompatibility Complex (MHC) proteins on the surface of infected
or cancerous cells. The recognition of these foreign peptides is determined by
the interactions between the peptides and TCRs on the surface of T cells. This
process is known as TCR recognition and constitutes a key step for immune
response [9, 12]. Adoptive T cell immunotherapy (ACT), which has been a
promising cancer treatment, genetically modifies the autologous T cells taken
from patients in laboratory experiments, after which the modified T cells are
infused into patients’ bodies to fight cancer. As one type of ACT therapies,
TCR T cell (TCR-T) therapy directly modifies the TCRs of T cells to increase
the binding affinities, which makes it possible to recognize and kill tumor
cells effectively [27]. TCR is a heterodimeric protein with an $\alpha$ chain
and a $\beta$ chain. Each chain has three loops as complementary determining
regions (CDR): CDR1, CDR2 and CDR3. CDR1 and CDR2 are primarily responsible
for interactions with MHC, and CDR3 interacts with peptides [26]. The CDR3 of
the $\beta$ chain has a higher degree of variations and is therefore arguably
mainly responsible for the recognition of foreign peptides [20]. In this
paper, we focused on the optimization of the CDR3 sequence of $\beta$ chain in
TCRs to enhance their binding affinities against peptide antigens, and we
conducted the optimization through novel reinforcement learning. The success
of our approach will have the potential to guide TCR-T therapy design. For the
sake of simplicity, when we refer to TCRs in the rest of the paper, we mean
the CDR3 of $\beta$ chain in TCRs.

Despite the significant promise of TCR-T therapy, optimizing TCRs for
therapeutic purposes remains a time-consuming process, which typically
requires exhaustive screening for high-affinity TCRs, either _in vitro_ or _in
silico_. To accelerate this process, computational methods have been developed
recently to predict peptide-TCR interactions [33], leveraging the experimental
peptide-TCR binding data [30, 34] and TCR sequences [6]. However, these
peptide-TCR binding prediction tools cannot immediately direct the rational
design of new high-affinity TCRs. Existing computational methods for
biological sequence design include search-based methods [3], generative
methods [19, 16], optimization-based methods [14] and reinforcement learning
($\mathop{\mathtt{RL}}\limits$)-based methods [2, 31]. However, all these
methods generate sequences without considering additional conditions such as
peptides, and thus cannot optimize TCRs tailored to recognizing different
peptides. In addition, these methods do not consider the validity of generated
sequences, which is important for TCR optimization as valid TCRs should follow
specific characteristics [18].

In this paper, we presented a new reinforcement-learning
($\mathop{\mathtt{RL}}\limits$) framework based on proximal policy
optimization (PPO) [29], referred to as $\mathop{\mathtt{TCRPPO}}\limits$
111The code is available at https://github.com/ninglab/TCRPPO, to
computationally optimize TCRs through a mutation policy. In particular,
$\mathop{\mathtt{TCRPPO}}\limits$ learns a joint policy to optimize TCRs
customized for any given peptides. In $\mathop{\mathtt{TCRPPO}}\limits$, we
designed a new reward function that measures both the likelihoods of the
mutated sequences being valid TCRs, and the probabilities of the TCRs
recognizing peptides. To measure TCR validity, we developed a TCR auto-
encoder, referred to as $\mathop{\mathtt{TCR\text{-}AE}}$, and utilized
reconstruction errors from $\mathop{\mathtt{TCR\text{-}AE}}$ and also its
latent space distributions, quantified by a Gaussian Mixture Model, to
calculate novel validity scores. To measure peptide recognition, we leveraged
a state-of-the-art peptide-TCR binding predictor
$\mathop{\mathtt{ERGO}}\limits$ [33] to predict peptide-TCR binding. Please
note that $\mathop{\mathtt{TCRPPO}}\limits$ is a flexible framework, as
$\mathop{\mathtt{ERGO}}\limits$ can be replaced by any other binding
predictors [5, 37]. In addition, we designed a novel buffering mechanism,
referred to as $\mathop{\mathtt{Buf\text{-}Opt}}\limits$, to revise TCRs that
are difficult to optimize. We conducted extensive experiments using 7 million
TCRs from $\mathop{\mathtt{TCRdb}}\limits$ [6], 10 peptides from
$\mathop{\mathtt{McPAS}}\limits$ [34] and 15 peptides from
$\mathop{\mathtt{VDJDB}}\limits$ [30]. Our experimental results demonstrated
that $\mathop{\mathtt{TCRPPO}}\limits$ can substantially outperform the best
baselines with best improvement of 45.04% and 52.89% in terms of generating
qualified TCRs with high validity scores and high recognition probabilities,
over $\mathop{\mathtt{McPAS}}\limits$ and $\mathop{\mathtt{VDJDB}}\limits$
peptides, respectively. Figure 1 presents the overall architecture of
$\mathop{\mathtt{TCRPPO}}\limits$.

##  2 Related Work

Existing methods developed for biological sequence design include search-based
methods, deep generative methods, optimization-based methods and
$\mathop{\mathtt{RL}}\limits$-based methods. Among search-based methods, the
classical evolutionary search [3] uses an evolution strategy to randomly
mutate the sequences and select desired ones in an iterative way. Among
generative methods, Killoran _et al._ [19] optimized the latent embeddings of
DNA sequences learned from a variational autoencoder towards better
properties. Gupta _et al._ [16] used generative adversarial networks (GANs) to
generate DNA sequences and selected the generated ones with desired properties
to further optimize GANs. Among optimization-based methods, Gonzalez _et al._
[14] used a Gaussian process model to emulate the production rates of a
certain protein across different gene designs in living cells, and then
optimized the gene designs to improve the production rates using Bayesian
optimization. Both the above generative methods and optimization methods aim
at optimizing the biological sequences without any additional conditions, As a
consequence, these methods are not applicable to our TCR optimization problem.
In our problem, the optimization of TCRs must be tailored to given peptides,
because TCRs binding to different peptides have different characteristics.

Despite the success of $\mathop{\mathtt{RL}}\limits$ on many applications,
there remains limited work of applying $\mathop{\mathtt{RL}}\limits$ to
biological sequence design. Angermueller _et al._ [2] developed a model-based
$\mathop{\mathtt{RL}}\limits$ method for biological sequence design using PPO
to improve the sample efficiency, where the policy is trained over a simulator
model learned to approximate the reward function. Skwark _et al._ [31] then
leveraged a $\mathop{\mathtt{RL}}\limits$ method based on PPO to discover a
potential Covid-19 cure. Their method aims at identifying the variants of
human angiotensin-converting enzyme (ACE2) protein sequence that have higher
binding affinities against the SARS-CoV-2 spike protein than the original ACE2
protein. Our $\mathop{\mathtt{TCRPPO}}\limits$ also applies PPO with a
mutation policy to optimize TCR sequences. However,
$\mathop{\mathtt{TCRPPO}}\limits$ is fundamentally different from previous
methods in three aspects. First, $\mathop{\mathtt{TCRPPO}}\limits$ learns a
joint policy to optimize the TCRs customized for any given peptides. In
addition, $\mathop{\mathtt{TCRPPO}}\limits$ employs a comprehensive reward
function to simultaneously optimize the validity and the recognition
probability of the TCRs against the peptides.
$\mathop{\mathtt{TCRPPO}}\limits$ also leverages a buffering mechanism to
generalize the optimization capability of $\mathop{\mathtt{TCRPPO}}\limits$ to
TCRs that are hard to optimize, or peptides with fewer positive binding TCRs.

##  3 Methods

Figure 1: Model Architecture of $\mathop{\mathtt{TCRPPO}}\limits$ Figure 2:
Data Flow for $\mathop{\mathtt{TCRPPO}}\limits$ and
$\mathop{\mathtt{TCR\text{-}AE}}$ training and testing

###  3.1 Problem Definition

In this paper, the recognition ability of a TCR sequence against the given
peptides is measured by a recognition probability, denoted as
$\mathop{s_{r}}$. The likelihood of a sequence being a valid TCR is measured
by a score, denoted as $\mathop{s_{v}}\limits$. A _qualified_ TCR is defined
as a sequence with $\mbox{$\mathop{s_{r}}$}>\sigma_{\text{r}}$ and
$\mbox{$\mathop{s_{v}}\limits$}>\sigma_{c}$, where $\sigma_{r}$ and
$\sigma_{c}$ are pre-defined thresholds ($\sigma_{r}$=0.9 and
$\sigma_{c}$=1.2577, as discussed in Appendix A.2 and A.4.4, respectively).
The goal of $\mathop{\mathtt{TCRPPO}}\limits$ is to mutate the existing TCR
sequences that have low recognition probability against the given peptide,
into qualified ones. A peptide $\mathop{p}$ or a TCR sequence $\mathop{c}$ is
represented as a sequence of its amino acids
$\langle\mbox{$\mathop{o}$}_{1},\mbox{$\mathop{o}$}_{2},\cdots,\mbox{$\mathop{o}$}_{i},\cdots,\mbox{$\mathop{o}$}_{l}\rangle$,
where $\mbox{$\mathop{o}$}_{i}$ is one of the 20 types of natural amino acids
at the position $i$ in the sequence, and $l$ is the sequence length. We
formulated the TCR mutation process as a Markov Decision Process (MDP)
$M=\\{\mbox{$\mathcal{S}$},\mbox{$\mathcal{A}$},P,\mathcal{R}\\}$ containing
the following components:

  * •

$\mathcal{S}$: the state space, in which each state
$\mbox{$\mathop{s}\limits$}\in\mbox{$\mathcal{S}$}$ is a tuple of a potential
TCR sequence $\mathop{c}$ and a peptide $\mathop{p}$, that is,
$\mbox{$\mathop{s}\limits$}=(\mbox{$\mathop{c}$},\mbox{$\mathop{p}$})$.
Subscript $t$ ($t=0,\cdots,T$) is used to index step of $\mathop{s}\limits$,
that is,
$\mbox{$\mathop{s}\limits$}_{t}=(\mbox{$\mathop{c}$}_{t},\mbox{$\mathop{p}$})$.
Please note that $\mbox{$\mathop{c}$}_{t}$ may not be a valid TCR. A state
$\mbox{$\mathop{s}\limits$}_{t}$ is a terminal state, denoted as
$\mbox{$\mathop{s}\limits$}_{T}$, if it contains a qualified
$\mbox{$\mathop{c}$}_{t}$, or $t$ reaches the maximum step limit $T$. Please
also note that $\mathop{p}$ will be sampled at
$\mbox{$\mathop{s}\limits$}_{0}$ and will not change over time $t$,

  * •

$\mathcal{A}$: the action space, in which each action
$\mbox{$\mathbf{a}$}\in\mbox{$\mathcal{A}$}$ is a tuple of a mutation site $i$
and a mutant amino acid $\mathop{o}$, that is,
$\mbox{$\mathbf{a}$}=(i,\mbox{$\mathop{o}$})$. Thus, the action will mutate
the amino acid at position $i$ of a sequence $\mathop{c}$ =
$\langle\mbox{$\mathop{o}$}_{1},\mbox{$\mathop{o}$}_{2},\cdots,\mbox{$\mathop{o}$}_{i},\cdots,\mbox{$\mathop{o}$}_{l}\rangle$
into another amino acid $\mathop{o}$. Note that $\mathop{o}$ has to be
different from $\mbox{$\mathop{o}$}_{i}$ in $\mathop{c}$.

  * •

$\mathcal{P}$: the state transition probabilities, in which
$\mbox{$\mathcal{P}$}(\mbox{$\mathop{s}\limits$}_{t+1}|\mbox{$\mathop{s}\limits$}_{t},\mbox{$\mathbf{a}$}_{t})$
specifies the probability of next state $\mbox{$\mathop{s}\limits$}_{t+1}$ at
time $t+1$ from state $\mbox{$\mathop{s}\limits$}_{t}$ at time $t$ with the
action $\mbox{$\mathbf{a}$}_{t}$. In our problem, the transition to
$\mbox{$\mathop{s}\limits$}_{t+1}$ is deterministic, that is
$\mbox{$\mathcal{P}$}(\mbox{$\mathop{s}\limits$}_{t+1}|\mbox{$\mathop{s}\limits$}_{t},\mbox{$\mathbf{a}$}_{t})=1$.

  * •

$\mathcal{R}$: the reward function at a state. In
$\mathop{\mathtt{TCRPPO}}\limits$, all the intermediate rewards at states
$\mbox{$\mathop{s}\limits$}_{t}$ ($t=0,\cdots,T-1$) are 0; only the final
reward at $\mbox{$\mathop{s}\limits$}_{T}$ is used to guide the optimization.

###  3.2 Mutation Policy Network

$\mathop{\mathtt{TCRPPO}}\limits$ mutates one amino acid in a sequence
$\mathop{c}$ at a step to modify $\mathop{c}$ into a qualified TCR.
Specifically, at the initial step $t=0$, a peptide $\mathop{p}$ is sampled as
the target, and a valid TCR $\mbox{$\mathop{c}$}_{0}$ is sampled to initialize
$\mbox{$\mathop{s}\limits$}_{0}=(\mbox{$\mathop{c}$}_{0},\mbox{$\mathop{p}$})$;
at a state
$\mbox{$\mathop{s}\limits$}_{t}=(\mbox{$\mathop{c}$}_{t},\mbox{$\mathop{p}$})$
($t>0$), the mutation policy network of $\mathop{\mathtt{TCRPPO}}\limits$
predicts an action $\mbox{$\mathbf{a}$}_{t}$ that mutates one amino acid of
$\mbox{$\mathop{c}$}_{t}$ to modify it into $\mbox{$\mathop{c}$}_{t+1}$ that
is more likely to lead to a final, qualified TCR bound to $\mathop{p}$.
$\mathop{\mathtt{TCRPPO}}\limits$ encodes the TCRs and peptides in a
distributed embedding space. It then learns a mapping between the embedding
space and the mutation policy, as discussed below.

####  3.2.1 Encoding of Amino Acids

Following the idea in Chen _et al._ [7], we represented each amino acid
$\mathop{o}$ by concatenating three vectors: 1) $\mbox{$\mathbf{o}$}^{b}$, the
corresponding row of $\mathop{o}$ in the BLOSUM matrix, 2)
$\mbox{$\mathbf{o}$}^{o}$, the one-hot encoding of $\mathop{o}$, and 3)
$\mbox{$\mathbf{o}$}^{d}$, the learnable embedding, that is, $\mathop{o}$ is
encoded as
$\mbox{$\mathbf{o}$}=\mbox{$\mathbf{o}$}^{b}\oplus\mbox{$\mathbf{o}$}^{o}\oplus\mbox{$\mathbf{o}$}^{d}$,
where $\oplus$ represents the concatenation operation. We used such a mixture
of encoding methods to enrich the representations of amino acids within
$\mathop{c}$ and $\mathop{p}$.

####  3.2.2 Embedding of States

We embedded
$\mbox{$\mathop{s}\limits$}_{t}=(\mbox{$\mathop{c}$}_{t},\mbox{$\mathop{p}$})$
via embedding its associated sequences $\mbox{$\mathop{c}$}_{t}$ and
$\mathop{p}$. For each amino acid $\mbox{$\mathop{o}$}_{i,t}$ in
$\mbox{$\mathop{c}$}_{t}$, we embedded $\mbox{$\mathop{o}$}_{i,t}$ and its
context information in $\mbox{$\mathop{c}$}_{t}$ into a hidden vector
$\mbox{$\mathbf{h}$}_{i,t}$ using a one-layer bidirectional LSTM [15] as
below,

$\displaystyle\overrightarrow{\mbox{$\mathbf{h}$}}_{i,t},\overrightarrow{\mbox{$\mathbf{c}$}}_{i,t}$
$\displaystyle=\\!\\!\text{LSTM}(\mbox{$\mathbf{o}$}_{i,t},\overrightarrow{\mbox{$\mathbf{h}$}}_{i-1,t},\overrightarrow{\mbox{$\mathbf{c}$}}_{i-1,t};\overrightarrow{W});$
(1)
$\displaystyle\overleftarrow{\mbox{$\mathbf{h}$}}_{i,t},\overleftarrow{\mbox{$\mathbf{c}$}}_{i,t}$
$\displaystyle=\\!\\!\text{LSTM}(\mbox{$\mathbf{o}$}_{i,t},\overleftarrow{\mbox{$\mathbf{h}$}}_{i+1,t},\overleftarrow{\mbox{$\mathbf{c}$}}_{i+1,t};\overleftarrow{W});$
$\displaystyle\mbox{$\mathbf{h}$}_{i,t}$
$\displaystyle=\\!\\!\overrightarrow{\mbox{$\mathbf{h}$}}_{i,t}\oplus\overleftarrow{\mbox{$\mathbf{h}$}}_{i,t}$

where $\overrightarrow{\mbox{$\mathbf{h}$}}_{i,t}$ and
$\overleftarrow{\mbox{$\mathbf{h}$}}_{i,t}$ are the hidden state vectors of
the $i$-th amino acid in $\mbox{$\mathop{c}$}_{t}$;
$\overrightarrow{\mbox{$\mathbf{c}$}}_{i,t}$ and
$\overleftarrow{\mbox{$\mathbf{c}$}}_{i,t}$ are the memory cell states of
$i$-th amino acid; $\overrightarrow{W}$ and $\overleftarrow{W}$ are the
learnable parameters of the two LSTM directions, respectively; and
$\overrightarrow{\mbox{$\mathbf{h}$}}_{0,t}$,$\overleftarrow{\mbox{$\mathbf{h}$}}_{l_{c},t}$,
$\overrightarrow{\mbox{$\mathbf{c}$}}_{0,t}$ and
$\overleftarrow{\mbox{$\mathbf{c}$}}_{l_{c},t}$ ($l_{c}$ is the length of
$\mbox{$\mathop{c}$}_{t}$) are initialized with random vectors. With the
embeddings of all the amino acids, we defined the embedding of
$\mbox{$\mathop{c}$}_{t}$ as the concatenation of hidden vectors at the two
ends, that is,
$\mbox{$\mathbf{h}$}_{t}=\overrightarrow{\mbox{$\mathbf{h}$}}_{l_{c},t}\oplus\overleftarrow{\mbox{$\mathbf{h}$}}_{0,t}$.
We embedded a peptide sequence into a hidden vector
$\mbox{$\mathbf{h}$}^{\scriptsize{\mbox{$\mathop{p}$}}}$ using another
bidirectional LSTM in the same way.

####  3.2.3 Action Prediction

To predict the action $\mbox{$\mathbf{a}$}_{t}=(i,\mbox{$\mathop{o}$})$ at
time $t$, $\mathop{\mathtt{TCRPPO}}\limits$ needs to make two predictions: 1)
the position $i$ of current $\mbox{$\mathop{c}$}_{t}$ where
$\mbox{$\mathbf{a}$}_{t}$ needs to occur; 2) the new amino acid $\mathop{o}$
that $\mbox{$\mathbf{a}$}_{t}$ needs to place with at position $i$. To measure
“how likely" the position $i$ in $\mbox{$\mathop{c}$}_{t}$ is the action site,
$\mathop{\mathtt{TCRPPO}}\limits$ uses the following network:

$f(i)=\mathbf{w}^{\mathsf{T}}(\text{ReLU}(W_{1}\mbox{$\mathbf{h}$}_{i,t}+W_{2}\mbox{$\mathbf{h}$}^{\scriptsize{\mbox{$\mathop{p}$}}}))/(\sum\nolimits_{j=1}^{l_{c}}\mathbf{w}^{\mathsf{T}}(\text{ReLU}(W_{1}\mbox{$\mathbf{h}$}_{j,t}+W_{2}\mbox{$\mathbf{h}$}^{\scriptsize{\mbox{$\mathop{p}$}}}))),$
(2)

where $\mbox{$\mathbf{h}$}_{i,t}$ is the latent vector of
$\mbox{$\mathop{o}$}_{i,t}$ in $\mbox{$\mathop{c}$}_{t}$ (Equation 1);
$\mbox{$\mathbf{h}$}^{\scriptsize{\mbox{$\mathop{p}$}}}$ is the latent vector
of $\mathop{p}$; $\mathbf{w}$/$W_{j}$ ($j$=1,2) are the learnable
vector/matrices. Thus, $\mathop{\mathtt{TCRPPO}}\limits$ measures the
probability of position $i$ being the action site by looking at its context
encoded in $\mbox{$\mathbf{h}$}_{i,t}$ and the peptide $\mathop{p}$. The
predicted position $i$ is sampled from the probability distribution from
Equation 2 to ensure necessary exploration.

Given the predicted position $i$, $\mathop{\mathtt{TCRPPO}}\limits$ needs to
predict the new amino acid that should replace $\mbox{$\mathop{o}$}_{i}$ in
$\mbox{$\mathop{c}$}_{t}$. $\mathop{\mathtt{TCRPPO}}\limits$ calculates the
probability of each amino acid type being the new replacement as follows:

$\vspace{-2pt}g(\mbox{$\mathop{o}$})=\text{softmax}(U_{1}\times\text{ReLU}(U_{2}\mbox{$\mathbf{h}$}_{i,t}+U_{3}\mbox{$\mathbf{h}$}^{\scriptsize{\mbox{$\mathop{p}$}}})),$
(3)

where $U_{j}$ ($j$=1,2,3) are the learnable matrices; $\text{softmax}(\cdot)$
converts a 20-dimensional vector into probabilities over the 20 amino acid
types. The replacement amino acid type is then determined by sampling from the
distribution, excluding the original type of $\mbox{$\mathop{o}$}_{i,t}$.

###  3.3 Potential TCR Validity Measurement

Leveraging the literature [40, 1], we designed a novel scoring function to
quantitatively measure the likelihood of a given sequence $\mathop{c}$ being a
valid TCR (i.e., to calculate $\mathop{s_{v}}\limits$), which will be part of
the reward of $\mathop{\mathtt{TCRPPO}}\limits$. Specifically, we trained a
novel auto-encoder model, denoted as $\mathop{\mathtt{TCR\text{-}AE}}$, from
only valid TCRs. We used the reconstruction accuracy of a sequence in
$\mathop{\mathtt{TCR\text{-}AE}}$ to measure its TCR validity. The intuition
is that since $\mathop{\mathtt{TCR\text{-}AE}}$ is trained from only valid
TCRs, its encoding-decoding process will obey the “rules" of true TCR
sequences, and thus, a non-TCR sequence could not be well reproduced from
$\mathop{\mathtt{TCR\text{-}AE}}$. However, it is still possible that a non-
TCR sequence can receive a high reconstruction accuracy from
$\mathop{\mathtt{TCR\text{-}AE}}$, if $\mathop{\mathtt{TCR\text{-}AE}}$ learns
some generic patterns shared by TCRs and non-TCRs and fails to detect
irregularities, or $\mathop{\mathtt{TCR\text{-}AE}}$ has high model complexity
[22, 40]. To mitigate this, we additionally evaluated the latent space within
$\mathop{\mathtt{TCR\text{-}AE}}$ using a Gaussian Mixture Model
($\mathop{\mathtt{GMM}}\limits$), hypothesizing that non-TCRs would deviate
from the dense regions of TCRs in the latent space.

####  3.3.1 $\mathop{\mathtt{TCR\text{-}AE}}$

Figure 1 presents the auto-encoder $\mathop{\mathtt{TCR\text{-}AE}}$.
$\mathop{\mathtt{TCR\text{-}AE}}$ uses a bidirectional LSTM to encode an input
sequence $\mathop{c}$ into $\mbox{$\mathbf{h}$}^{\prime}$ by concatenating the
last hidden vectors from the two LSTM directions (similarly as in Equation 1).
Please note that this bidirectional LSTM is independent of the mutation policy
network in $\mathop{\mathtt{TCRPPO}}\limits$. $\mbox{$\mathbf{h}$}^{\prime}$
is then mapped into a latent embedding $\mbox{$\mathbf{z}$}^{\prime}$ as
follows,

$\mbox{$\mathbf{z}$}^{\prime}=W^{z}\mbox{$\mathbf{h}$}^{\prime},\vspace{-5pt}$
(4)

which will be decoded back to a sequence $\hat{\mbox{$\mathop{c}$}}$ via a
decoder. The decoder has a single-directional LSTM that decodes
$\mbox{$\mathbf{z}$}^{\prime}$ by generating one amino acid at a time as
follows,

$\mbox{$\mathbf{h}$}^{\prime}_{i},\mbox{$\mathbf{c}$}^{\prime}_{i}=\text{LSTM}(\hat{\mbox{$\mathbf{o}$}}_{{i-1}},\mbox{$\mathbf{h}$}^{\prime}_{i-1},\mbox{$\mathbf{c}$}^{\prime}_{i-1};W^{\prime});\
\
\hat{o}_{i}=\text{softmax}(U^{\prime}\times\text{ReLU}(U^{\prime}_{1}\mbox{$\mathbf{h}$}^{\prime}_{i}+U^{\prime}_{2}\mbox{$\mathbf{z}$}^{\prime})),\vspace{-5pt}$
(5)

where $\hat{\mbox{$\mathbf{o}$}}_{{i-1}}$ is the encoding of the amino acid
$\hat{o}_{i-1}$ that is decoded from step $i-1$; $W^{\prime}$ is the
parameter. The LSTM starts with a zero vector
$\mbox{$\mathbf{o}$}_{0}=\mathbf{0}$ and
$\mbox{$\mathbf{h}$}_{0}=W^{h}\mbox{$\mathbf{z}$}^{\prime}$. The decoder
infers the next amino acid by looking at the previously decoded amino acids
encoded in $\mbox{$\mathbf{h}$}^{\prime}_{i}$ and the entire prospective
sequence encoded in $\mbox{$\mathbf{z}$}^{\prime}$.

Please note that $\mathop{\mathtt{TCR\text{-}AE}}$ is trained from TCRs,
independently of $\mathop{\mathtt{TCRPPO}}\limits$ and in an end-to-end
fashion. Teacher forcing [39] is applied during training to feed the ground
truth amino acids as inputs to predict the next amino acid, and thus cross
entropy loss is applied on each amino acid to optimize
$\mathop{\mathtt{TCR\text{-}AE}}$. As a stand-alone module,
$\mathop{\mathtt{TCR\text{-}AE}}$ is used to calculate the score
$\mathop{s_{v}}\limits$. The input sequence $\mathop{c}$ to
$\mathop{\mathtt{TCR\text{-}AE}}$ is encoded using only BLOSUM matrix as we
found empirically that BLOSUM encoding can lead to a good reconstruction
performance and a fast convergence compared to other combinations of encoding
methods.

####  3.3.2 Reconstruction-based score

With a well-trained $\mathop{\mathtt{TCR\text{-}AE}}$, we calculated the
reconstruction-based TCR validity score of a sequence $\mathop{c}$ as follows,

$\mbox{$\mathop{r_{r}}$}(\mbox{$\mathop{c}$})=1-{\mathtt{lev}(\mbox{$\mathop{c}$},\mbox{$\mathop{\mathtt{TCR\text{-}AE}}$}(\mbox{$\mathop{c}$}))}/{l_{\scriptsize{\mbox{$\mathop{c}$}}}}\vspace{-5pt}$
(6)

where $\mbox{$\mathop{\mathtt{TCR\text{-}AE}}$}(\mbox{$\mathop{c}$})$
represents the reconstructed sequence of $\mathop{c}$ from
$\mathop{\mathtt{TCR\text{-}AE}}$; $\mathtt{lev}(.)$ is the Levenshtein
distance, an edit-distance-based metric, between $\mathop{c}$ and
$\mbox{$\mathop{\mathtt{TCR\text{-}AE}}$}(\mbox{$\mathop{c}$})$;
$l_{\scriptsize{\mbox{$\mathop{c}$}}}$ is the length of $\mathop{c}$. Higher
$\mbox{$\mathop{r_{r}}$}(\mbox{$\mathop{c}$})$ indicates higher probability of
$\mathop{c}$ being a valid TCR. Please note that when
$\mathop{\mathtt{TCR\text{-}AE}}$ is used in testing, the length of the
reconstructed sequence might not be the same as the input $\mathop{c}$,
because $\mathop{\mathtt{TCR\text{-}AE}}$ could fail to accurately predict the
end of the sequence, leading to either too short or too long reconstructed
sequences. Therefore, we normalized the Levenshtein distance using the length
of input sequence $l_{\scriptsize{\mbox{$\mathop{c}$}}}$ similarly to Snover
_et al._ [32]. Please note that $\mbox{$\mathop{r_{r}}$}(\mbox{$\mathop{c}$})$
could be negative when the distance is greater than the sequence length. The
negative values will not affect the use of the scores (i.e., negative
$\mbox{$\mathop{r_{r}}$}(\mbox{$\mathop{c}$})$ indicates very different
$\mbox{$\mathop{\mathtt{TCR\text{-}AE}}$}(\mbox{$\mathop{c}$})$ and
$\mathop{c}$).

####  3.3.3 Density Estimation-based Score

To better distinguish valid TCRs from invalid ones,
$\mathop{\mathtt{TCRPPO}}\limits$ also conducts a density estimation over the
latent space of $\mbox{$\mathbf{z}$}^{\prime}$ (Equation 4) using
$\mathop{\mathtt{GMM}}\limits$. For a given sequence $\mathop{c}$,
$\mathop{\mathtt{TCRPPO}}\limits$ calculates the likelihood score of
$\mathop{c}$ falling within the Gaussian mixture region of training TCRs as
follows,

$\mbox{$\mathop{r_{d}}$}(\mbox{$\mathop{c}$})=\exp(1+\frac{\log
P(\mbox{$\mathbf{z}$}^{\prime})}{\tau})\vspace{-5pt}$ (7)

where $\log P(\mbox{$\mathbf{z}$}^{\prime})$ is the log-likelihood of the
latent embedding $\mbox{$\mathbf{z}$}^{\prime}$; $\tau$ is a constant used to
rescale the log-likelihood value ($\tau=10$). We carefully selected the
parameter $\tau$ such that 90% of TCRs can have
$\mbox{$\mathop{r_{d}}$}(\mbox{$\mathop{c}$})$ above $0.5$. As we do not have
invalid TCRs, we cannot use classification-based scaling methods such as Platt
scaling [23] to calibrate the log likelihood values to probabilities.

####  3.3.4 TCR Validity Scoring

Combining the reconstruction-based scoring and density estimation-based
scoring, we developed a new scoring method to measure TCR validity as follows:

$\mbox{$\mathop{s_{v}}\limits$}(\mbox{$\mathop{c}$})=r_{r}(\mbox{$\mathop{c}$})+r_{d}(\mbox{$\mathop{c}$}).\vspace{-5pt}$
(8)

This method is used to evaluate if a sequence is likely to be a valid TCR and
is used in the reward function.

###  3.4 $\mathop{\mathtt{TCRPPO}}\limits$ Learning

####  3.4.1 Final Reward

We defined the final reward for $\mathop{\mathtt{TCRPPO}}\limits$ based on
$\mathop{s_{r}}$ and $\mathop{s_{v}}\limits$ scores as follows,

$\mbox{$\mathcal{R}$}(\mbox{$\mathop{c}$}_{T},\mbox{$\mathop{p}$})=\mbox{$\mathop{s_{r}}$}(\mbox{$\mathop{c}$}_{T},\mbox{$\mathop{p}$})+\alpha\min(0,\mbox{$\mathop{s_{v}}\limits$}(\mbox{$\mathop{c}$}_{T})-\mbox{$\mathop{\sigma_{c}}\limits$})\vspace{-5pt}$
(9)

where $\mbox{$\mathop{s_{r}}$}(\mbox{$\mathop{c}$}_{T},\mbox{$\mathop{p}$})$
is the predicted recognition probability by $\mathop{\mathtt{ERGO}}\limits$,
$\mathop{\sigma_{c}}\limits$ is a threshold that $\mbox{$\mathop{c}$}_{T}$ is
very likely to be a valid TCR; and $\alpha$ is the hyperparameter used to
control the tradeoff between $\mathop{s_{r}}$ and $\mathop{s_{v}}\limits$
($\alpha=0.5$).

####  3.4.2 Policy Learning

We adopted the proximal policy optimization (PPO) [29] to optimize the policy
network as discussed in Section 3.2. The objective function of PPO is defined
as follows:

$\displaystyle\max\nolimits_{\boldsymbol{\Theta}}L^{\text{CLIP}}(\boldsymbol{\Theta})$
$\displaystyle=\hat{\mathbb{E}}_{t}[\min(r_{t}(\boldsymbol{\Theta})\hat{A}_{t},\text{clip}(r_{t}(\boldsymbol{\Theta}),1-\epsilon,1+\epsilon)\hat{A}_{t})],$
(10) $\displaystyle\ \text{where}\
r_{t}(\boldsymbol{\Theta})=\frac{\pi_{{\boldsymbol{\Theta}}}(a_{t}|s_{t})}{\pi_{{\boldsymbol{\Theta}_{\text{old}}}}(a_{t}|s_{t})},$

where $\boldsymbol{\Theta}$ is the set of learnable parameters of the policy
network and $r_{t}(\boldsymbol{\Theta})$ is the probability ratio between the
action under current policy $\pi_{{{\boldsymbol{\Theta}}}}$ and the action
under previous policy $\pi_{{\boldsymbol{\Theta}_{\text{old}}}}$. Here,
$r_{t}(\boldsymbol{\Theta})$ is clipped to avoid moving $r_{t}$ outside of the
interval $[1-\epsilon,1+\epsilon]$. $\hat{A}_{t}$ is the advantage at timestep
$t$ computed with the generalized advantage estimator [28], measuring how much
better a selected action is than others on average:

$\hat{A}_{t}=\delta_{t}+(\gamma\lambda)\delta_{t+1}+...+(\gamma\lambda)^{T-t+1}\delta_{T-1},$
(11)

where $\gamma\in(0,1)$ is the discount factor determining the importance of
future rewards; $\delta_{t}=r_{t}+\gamma V(s_{t+1})-V(s_{t})$ is the temporal
difference error in which $V(s_{t})$ is a value function; $\lambda\in(0,1)$ is
a parameter used to balance the bias and variance of $V(s_{t})$. Here,
$V(\cdot)$ uses a multi-layer perceptron (MLP) to predict the future return of
current state $s_{t}$ from the peptide embedding
$\mbox{$\mathbf{h}$}^{\scriptsize{\mbox{$\mathop{p}$}}}$ and the TCR embedding
$\mbox{$\mathbf{h}$}_{t}$. The objective function of $V(\cdot)$ is as follows:

$\min\nolimits_{\boldsymbol{\Theta}}L^{V}(\boldsymbol{\Theta})=\hat{\mathbb{E}}_{t}[(V(\mbox{$\mathbf{h}$}_{t},\mbox{$\mathbf{h}$}^{\scriptsize{\mbox{$\mathop{p}$}}})-\hat{R}_{t})^{2}],$
(12)

where $\hat{R}_{t}=\sum_{i=t+1}^{T}\gamma^{i-t}r_{i}$ is the rewards-to-go.
Because we only used the final rewards, that is $r_{i}=0\text{ if }i\neq T$,
we calculated $\hat{R}_{t}$ with $\hat{R}_{t}=\gamma^{T-t}r_{\scriptsize{T}}$.
We also added the entropy regularization loss $H(\boldsymbol{\Theta})$, a
popular strategy used for policy gradient methods [21, 29], to encourage the
exploration of the policy. The final objective function of
$\mathop{\mathtt{TCRPPO}}\limits$ is defined as below,

$\min\nolimits_{\boldsymbol{\Theta}}L(\boldsymbol{\Theta})=-L^{\text{CLIP}}(\boldsymbol{\Theta})+\alpha_{1}L^{V}(\boldsymbol{\Theta})-\alpha_{2}H(\boldsymbol{\Theta}),\vspace{-5pt}$
(13)

where $\alpha_{1}$ and $\alpha_{2}$ are two hyperparameters controlling the
tradeoff among the PPO objective, the value function and the entropy
regularization term.

####  3.4.3 Reward-Informed Buffering and Re-optimization

$\mathop{\mathtt{TCRPPO}}\limits$ implements a novel buffering and re-
optimizing mechanism, denoted as $\mathop{\mathtt{Buf\text{-}Opt}}\limits$, to
deal with TCRs that are difficult to optimize, and to generalize its
optimization capacity to more, diverse TCRs. To optimize TCRs, various number
of mutations will be applied to get the binding TCRs. For TCRs requiring more
mutations, it could be more difficult for $\mathop{\mathtt{TCRPPO}}\limits$ to
optimize; and thus re-optimizing these TCRs enables
$\mathop{\mathtt{TCRPPO}}\limits$ to explore more actions for the optimization
of difficult TCRs, instead of being overwhelmed by relatively simple cases.
This mechanism includes a buffer, which memorizes the TCRs that cannot be
optimized to qualify. These hard sequences and the corresponding peptides will
be sampled from the buffer again following the probability distribution below,
to be further optimized by $\mathop{\mathtt{TCRPPO}}\limits$,

$\vspace{-5pt}S(\mbox{$\mathop{c}$},\mbox{$\mathop{p}$})=\xi^{(1-\scriptsize{\mbox{$\mathcal{R}$}(\mbox{$\mathop{c}$}_{T},\mbox{$\mathop{p}$})})}/\Sigma.$
(14)

In Equation 14, $S$ measures how difficult to optimize $\mathop{c}$ against
$\mathop{p}$ based on its final reward
$\mbox{$\mathcal{R}$}(\mbox{$\mathop{c}$}_{T},\mbox{$\mathop{p}$})$ in the
previous optimization, $\xi$ is hyper-parameter ($\xi=5$ in our experiments),
and $\Sigma$ converts $S(\mbox{$\mathop{c}$},\mbox{$\mathop{p}$})$ as a
probability. It is expected that by doing the sampling and re-optimization,
$\mathop{\mathtt{TCRPPO}}\limits$ is better trained to learn from hard
sequences, and also the hard sequences have the opportunity to be better
optimized by $\mathop{\mathtt{TCRPPO}}\limits$. In case a hard sequence still
cannot be optimized to qualify, it will have 50% chance of being allocated
back to the buffer. In case the buffer is full (size 2,000 in our
experiments), the sequences earliest allocated in the buffer will be removed.
We referred to the $\mathop{\mathtt{TCRPPO}}\limits$ with
$\mathop{\mathtt{Buf\text{-}Opt}}\limits$ as
$\mathop{\mathtt{TCRPPO}\text{+}\mathtt{b}}\limits$.

##  4 Experimental Settings

###  4.1 Datasets

We selected peptides and TCR sequences for the training and testing of
$\mathop{\mathtt{TCRPPO}}\limits$ and $\mathop{\mathtt{TCR\text{-}AE}}$.
Figure 2 summaries the peptides and TCRs used in our experiments.

####  4.1.1 Peptides

To test $\mathop{\mathtt{TCRPPO}}\limits$, we first identified a set of
peptides that $\mathop{\mathtt{TCRPPO}}\limits$ needs to optimize TCR
sequences for. We aimed at selecting the peptides which are very likely to
have reliable peptide-TCR binding predictions, such that their binding
predictions can serve to test $\mathop{\mathtt{TCRPPO}}\limits$’s optimized
TCRs against the respective peptides. We identified such peptides from two
databases: $\mathop{\mathtt{McPAS}}\limits$ [34] and
$\mathop{\mathtt{VDJDB}}\limits$ [30], which have experimentally validated
TCR-peptide binding pairs. We applied the autoencoder-based
$\mathop{\mathtt{ERGO}}\limits$ models [33] on
$\mathop{\mathtt{McPAS}}\limits$ and $\mathop{\mathtt{VDJDB}}\limits$
($\mathop{\mathtt{McPAS}}\limits$ and $\mathop{\mathtt{VDJDB}}\limits$ have
pre-specified training and testing sets for each peptide), and selected the
peptides which have AUC values above 0.9 on their respective testing sets.
This resulted in 10 peptides selected from $\mathop{\mathtt{McPAS}}\limits$,
denoted as
$\mathop{\mathcal{P}_{\scriptsize{\mbox{$\mathop{\mathtt{McPAS}}\limits$}}}}\limits$,
and 15 peptides selected from $\mathop{\mathtt{VDJDB}}\limits$, denoted as
$\mathop{\mathcal{P}_{\scriptsize{\mbox{$\mathop{\mathtt{VDJDB}}\limits$}}}}\limits$,
with lengths ranging from 8 to 21, as presented in Appendix Table A.1.
Additional discussion on peptides is available in Appendix A.1.

####  4.1.2 TCR sequences

We then selected TCR sequences that $\mathop{\mathtt{TCRPPO}}\limits$ needs to
optimize against each of the peptides selected as above. We selected such
sequences from the $\mathop{\mathtt{TCRdb}}\limits$ database [6], which
contains 277 million human TCR sequences, each with a TCR-$\beta$ sequence.
Here, we used $\mathop{\mathtt{TCRdb}}\limits$, not
$\mathop{\mathtt{McPAS}}\limits$ or $\mathop{\mathtt{VDJDB}}\limits$, because
$\mathop{\mathtt{TCRdb}}\limits$’s sequences are valid TCRs and have no
information on their binding affinities with the selected peptides. Therefore,
these valid TCRs can be used to train $\mathop{\mathtt{TCR\text{-}AE}}$ to
calculate $\mathop{s_{v}}\limits$. Meanwhile, since
$\mathop{\mathtt{TCRdb}}\limits$ is much larger than
$\mathop{\mathtt{McPAS}}\limits$ (4,528 TCRs) and
$\mathop{\mathtt{VDJDB}}\limits$ (50,049 TCRs), it is very likely that the
$\mathop{s_{v}}\limits$ calculated from the $\mathop{\mathtt{TCR\text{-}AE}}$,
which is trained over $\mathop{\mathtt{TCRdb}}\limits$ data, will be
independent of the $\mathop{s_{r}}$ calculated from
$\mathop{\mathtt{ERGO}}\limits$, which is trained on
$\mathop{\mathtt{McPAS}}\limits$ or $\mathop{\mathtt{VDJDB}}\limits$, avoiding
possible correlation between $\mathop{s_{v}}\limits$ and $\mathop{s_{r}}$ as
in the reward (Equation 9).

We selected all the TCRs with lengths below 27
($\mathop{\mathtt{ERGO}}\limits$ can only predict sequences of length 27 or
shorter) from $\mathop{\mathtt{TCRdb}}\limits$, resulting in 7,331,105 unique
TCR-$\beta$ sequences. Figure A.1 presents the distribution of lengths of TCRs
in $\mathop{\mathtt{TCRdb}}\limits$. As shown in Figure A.1, the most common
length of TCRs is 15. Additional discussion on the length of TCRs is available
in Appendix A.1. Among these selected sequences, we sampled 50K sequences,
denoted as the validation set $\mathop{\mathcal{S}_{v}}\limits$, to test and
validate $\mathop{s_{v}}\limits$; within these 50K sequences, we again sampled
1K sequences, denoted as the testing set $\mathop{\mathcal{S}_{tst}}\limits$,
to test $\mathop{\mathtt{TCRPPO}}\limits$ performance once it is well trained.
The remaining selected sequences (i.e., not in the validation set), denoted as
the training set $\mathop{\mathcal{S}_{trn}}\limits$, are used to train
$\mathop{\mathtt{TCRPPO}}\limits$; they are also used to train
$\mathop{\mathtt{TCR\text{-}AE}}$.

###  4.2 Experimental Setup

For all the selected peptides from a same database (i.e., 10 peptides from
$\mathop{\mathtt{McPAS}}\limits$, 15 peptides from
$\mathop{\mathtt{VDJDB}}\limits$), we trained one
$\mathop{\mathtt{TCRPPO}}\limits$ agent, which optimizes the training
sequences (i.e., 7,281,105 TCRs in Figure 2) to be qualified against one of
the selected peptides. The $\mathop{\mathtt{ERGO}}\limits$ model trained on
the corresponding database (the same $\mathop{\mathtt{ERGO}}\limits$ model
also used to select the peptides from the database as in Section 4.1) will be
used to test recognition probabilities $\mathop{s_{r}}$ for the
$\mathop{\mathtt{TCRPPO}}\limits$ agent. Please note that as in Springer _et
al._ [33], one $\mathop{\mathtt{ERGO}}\limits$ model is trained for all the
peptides in each database (i.e., one $\mathop{\mathtt{ERGO}}\limits$ predicts
TCR-peptide binding for multiple peptides). Thus, the
$\mathop{\mathtt{ERGO}}\limits$ model is suitable to test $\mathop{s_{r}}$ for
multiple peptides in our setting. Also note that we trained one
$\mathop{\mathtt{TCRPPO}}\limits$ agent corresponding to each database,
because peptides and TCRs in these two databases are very different,
demonstrated by the inferior performance of an $\mathop{\mathtt{ERGO}}\limits$
trained over the two databases together, and discussed in Springer _et al._
[33].

$\mathop{\mathtt{TCRPPO}}\limits$ mutates each sequence up to 8 steps (i.e.,
T=8). In $\mathop{\mathtt{TCRPPO}}\limits$ training, an initial TCR sequence
(i.e., $\mbox{$\mathop{c}$}_{0}$ in $\mbox{$\mathop{s}\limits$}_{0}$) is
randomly sampled from $\mathop{\mathcal{S}_{trn}}\limits$, and will be mutated
in the following states; a peptide $\mathop{p}$ is randomly sampled at
$\mbox{$\mathop{s}\limits$}_{0}$, and remains the same in the following states
(i.e.,
$\mbox{$\mathop{s}\limits$}_{t}=(\mbox{$\mathop{c}$}_{t},\mbox{$\mathop{p}$})$).
Once a $\mathop{\mathtt{TCRPPO}}\limits$ is well trained from
$\mathop{\mathcal{S}_{trn}}\limits$, it will be tested on
$\mathop{\mathcal{S}_{tst}}\limits$. We set the dimensions of the hidden
layers (e.g., hidden layers of action prediction networks) as 256, and the
dimensions of latent embeddings (e.g.,
$\mbox{$\mathbf{h}$}^{\scriptsize{\mbox{$\mathop{p}$}}}$,
$\mbox{$\mathbf{h}$}_{t}$) as 128 (i.e., half of the hidden dimensions). Other
hyper-parameters and the details of hyper-parameter selection of the TCR
mutation environment, the policy network and the $\mathop{\mathtt{RL}}\limits$
agent are available in Appendix A.2.

Table 1: Overall Performance Comparison

Dataset | Method | $\mathop{\mathtt{q\%}}\limits$ | $\mathop{\mathtt{edist}}$ |  $\mathop{\overline{\mbox{$\mathop{s_{v}}\limits$}}}\limits$ ($\mathop{\mathcal{C}_{q}}\limits$) |  $\mathop{\overline{\mbox{$\mathop{s_{v}}\limits$}}}\limits$ ($\mathop{\mathcal{C}_{v}}\limits$) |  $\mathop{\overline{\mbox{$\mathop{s_{r}}$}}}\limits$ ($\mathop{\mathcal{C}_{q}}\limits$) |  $\mathop{\overline{\mbox{$\mathop{s_{r}}$}}}\limits$ ($\mathop{\mathcal{C}_{v}}\limits$) | $\mathop{\mathtt{v\%}}\limits$ | $\mathop{\\#\mbox{$\mathcal{R}$}}$
---|---|---|---|---|---|---|---|---|---
$\mathop{\mathcal{P}_{\scriptsize{\mbox{$\mathop{\mathtt{McPAS}}\limits$}}}}\limits$ | $\mathop{\mathtt{RS}}\limits$ | 0.05 | $\pm$ | 0.12 |  | - |  | 1.46 | $\pm$ | 0.16 | 1.73 | $\pm$ | 0.17 | 0.95 | $\pm$ | 0.01 | 0.05 | $\pm$ | 0.00 | 95.22 | $\pm$ | 0.45 | 1
$\mathop{\mathtt{MCTS}}\limits$ | 0.01 | $\pm$ | 0.03 |  | - |  | 1.38 | $\pm$ | 0.00 | 1.34 | $\pm$ | 0.03 | 0.93 | $\pm$ | 0.00 | 0.09 | $\pm$ | 0.09 | 0.59 | $\pm$ | 0.28 | 200
$\mathop{\mathtt{BP\text{-}VAE}}\limits$ | 0.04 | $\pm$ | 0.09 |  | - |  | 1.31 | $\pm$ | 0.02 | 1.34 | $\pm$ | 0.02 | 0.95 | $\pm$ | 0.02 | 0.09 | $\pm$ | 0.04 | 6.86 | $\pm$ | 2.52 | 7
$\mathop{\mathtt{RM}}\limits$ (n=5) | 1.27 | $\pm$ | 2.09 | 2.88 | $\pm$ | 1.50 | 1.49 | $\pm$ | 0.07 | 1.54 | $\pm$ | 0.02 | 0.93 | $\pm$ | 0.02 | 0.18 | $\pm$ | 0.09 | 99.36 | $\pm$ | 0.21 | 39
$\mathop{\mathtt{RM}}\limits$ (n=10) | 2.15 | $\pm$ | 3.86 | 3.04 | $\pm$ | 1.48 | 1.50 | $\pm$ | 0.11 | 1.52 | $\pm$ | 0.02 | 0.93 | $\pm$ | 0.02 | 0.26 | $\pm$ | 0.11 | 99.84 | $\pm$ | 0.12 | 77
$\mathop{\mathtt{Greedy}}\limits$ | 20.58 | $\pm$ | 17.85 | 5.10 | $\pm$ | 1.09 | 1.46 | $\pm$ | 0.03 | 1.44 | $\pm$ | 0.02 | 0.93 | $\pm$ | 0.01 | 0.62 | $\pm$ | 0.12 | 99.98 | $\pm$ | 0.04 | 74
$\mathop{\mathtt{Genetic}}\limits$ | 25.18 | $\pm$ | 21.28 | 5.16 | $\pm$ | 1.05 | 1.46 | $\pm$ | 0.03 | 1.46 | $\pm$ | 0.02 | 0.93 | $\pm$ | 0.01 | 0.69 | $\pm$ | 0.12 | 100.00 | $\pm$ | 0.00 | 166
$\mathop{\mathtt{TCRPPO}}\limits$ | 25.89 | $\pm$ | 29.60 | 5.15 | $\pm$ | 2.02 | 1.55 | $\pm$ | 0.19 | 1.51 | $\pm$ | 0.17 | 0.97 | $\pm$ | 0.03 | 0.76 | $\pm$ | 0.27 | 65.23 | $\pm$ | 12.47 | 7
$\mathop{\mathtt{TCRPPO}\text{+}\mathtt{b}}\limits$ | 36.52 | $\pm$ | 30.25 | 5.37 | $\pm$ | 1.81 | 1.55 | $\pm$ | 0.17 | 1.53 | $\pm$ | 0.17 | 0.96 | $\pm$ | 0.03 | 0.83 | $\pm$ | 0.21 | 75.83 | $\pm$ | 9.46 | 7
$\mathop{\mathcal{P}_{\scriptsize{\mbox{$\mathop{\mathtt{VDJDB}}\limits$}}}}\limits$ | $\mathop{\mathtt{RS}}\limits$ | 0.08 | $\pm$ | 0.10 |  | - |  | 1.58 | $\pm$ | 0.20 | 1.73 | $\pm$ | 0.28 | 0.94 | $\pm$ | 0.02 | 0.03 | $\pm$ | 0.03 | 95.02 | $\pm$ | 0.46 | 1
$\mathop{\mathtt{MCTS}}\limits$ | 0.00 | $\pm$ | 0.00 |  | - |  | 0.00 | $\pm$ | 0.00 | 1.35 | $\pm$ | 0.03 | 0.00 | $\pm$ | 0.00 | 0.05 | $\pm$ | 0.06 | 0.46 | $\pm$ | 0.09 | 200
$\mathop{\mathtt{BP\text{-}VAE}}\limits$ | 0.08 | $\pm$ | 0.12 |  | - |  | 1.33 | $\pm$ | 0.03 | 1.35 | $\pm$ | 0.01 | 0.95 | $\pm$ | 0.03 | 0.05 | $\pm$ | 0.03 | 18.46 | $\pm$ | 5.13 | 9
$\mathop{\mathtt{RM}}\limits$ (n=5) | 2.15 | $\pm$ | 1.82 | 2.84 | $\pm$ | 1.47 | 1.48 | $\pm$ | 0.09 | 1.55 | $\pm$ | 0.01 | 0.94 | $\pm$ | 0.02 | 0.16 | $\pm$ | 0.06 | 99.33 | $\pm$ | 0.21 | 39
$\mathop{\mathtt{RM}}\limits$ (n=10) | 4.41 | $\pm$ | 3.72 | 3.03 | $\pm$ | 1.52 | 1.48 | $\pm$ | 0.07 | 1.52 | $\pm$ | 0.02 | 0.94 | $\pm$ | 0.01 | 0.24 | $\pm$ | 0.08 | 99.86 | $\pm$ | 0.08 | 77
$\mathop{\mathtt{Greedy}}\limits$ | 31.81 | $\pm$ | 17.09 | 5.01 | $\pm$ | 1.12 | 1.47 | $\pm$ | 0.03 | 1.44 | $\pm$ | 0.02 | 0.93 | $\pm$ | 0.01 | 0.64 | $\pm$ | 0.09 | 99.96 | $\pm$ | 0.06 | 71
$\mathop{\mathtt{Genetic}}\limits$ | 38.57 | $\pm$ | 20.57 | 5.07 | $\pm$ | 1.07 | 1.48 | $\pm$ | 0.03 | 1.47 | $\pm$ | 0.02 | 0.94 | $\pm$ | 0.01 | 0.72 | $\pm$ | 0.09 | 100.00 | $\pm$ | 0.00 | 156
$\mathop{\mathtt{TCRPPO}}\limits$ | 45.82 | $\pm$ | 21.59 | 5.34 | $\pm$ | 1.58 | 1.51 | $\pm$ | 0.19 | 1.51 | $\pm$ | 0.19 | 0.96 | $\pm$ | 0.02 | 0.87 | $\pm$ | 0.18 | 69.99 | $\pm$ | 11.74 | 7
$\mathop{\mathtt{TCRPPO}\text{+}\mathtt{b}}\limits$ | 58.97 | $\pm$ | 29.11 | 5.20 | $\pm$ | 1.69 | 1.65 | $\pm$ | 0.20 | 1.63 | $\pm$ | 0.19 | 0.97 | $\pm$ | 0.02 | 0.89 | $\pm$ | 0.17 | 82.41 | $\pm$ | 5.54 | 6

  * •

Columns represent: $\mathop{\mathtt{q\%}}\limits$: the percentage of qualified
TCR sequences; $\mathop{\mathtt{edist}}$: the edit distance between the
original TCR sequences and the mutated qualified TCR sequences;
$\mbox{$\mathop{\overline{\mbox{$\mathop{s_{v}}\limits$}}}\limits$}(\mbox{$\mathop{\mathcal{C}_{q}}\limits$})$/$\mbox{$\mathop{\overline{\mbox{$\mathop{s_{v}}\limits$}}}\limits$}(\mbox{$\mathop{\mathcal{C}_{v}}\limits$})$:
the average $\mathop{s_{v}}\limits$ scores over the TCRs in set
$\mathop{\mathcal{C}_{q}}\limits$/$\mathop{\mathcal{C}_{v}}\limits$;
$\mbox{$\mathop{\overline{\mbox{$\mathop{s_{r}}$}}}\limits$}(\mbox{$\mathop{\mathcal{C}_{q}}\limits$})$/$\mbox{$\mathop{\overline{\mbox{$\mathop{s_{r}}$}}}\limits$}(\mbox{$\mathop{\mathcal{C}_{v}}\limits$})$:
the average $\mathop{s_{r}}$ probabilities over the TCRs in set
$\mathop{\mathcal{C}_{q}}\limits$/$\mathop{\mathcal{C}_{v}}\limits$;
$\mathop{\mathtt{v\%}}\limits$: the percentage of valid TCR sequences.
$\mathop{\\#\mbox{$\mathcal{R}$}}$: the average number of calls to calculate
$\mathcal{R}$ functions. Values $x\pm y$ represent mean $x$ and standard
deviation $y$. “-”: not applicable. The “$n$" value in
$\mathop{\mathtt{RM}}\limits$ indicates that $\mathop{\mathtt{RM}}\limits$ is
done $n$ times over each sequence.

###  4.3 Baseline Methods

We compared the $\mathop{\mathtt{TCRPPO}}\limits$ method and
$\mathop{\mathtt{TCRPPO}\text{+}\mathtt{b}}\limits$ with multiple baseline
methods of two primary categories: 1) generative methods that generate a new
TCR in its entirety, and 2) mutation-based methods that optimize TCRs via
mutating amino acids of existing TCRs. For generative methods, we used two
baseline methods including Monte Carlo tree search
($\mathop{\mathtt{MCTS}}\limits$) [8] and a variational autoencoder with
backpropagation ($\mathop{\mathtt{BP\text{-}VAE}}\limits$) [13]. For mutation-
based methods, we used three baseline methods to mutate each TCR sequence up
to 8 steps and stop the mutation once a qualified TCR is generated, including
random mutation ($\mathop{\mathtt{RM}}\limits$), greedy mutation
($\mathop{\mathtt{Greedy}}\limits$) and genetic mutation
($\mathop{\mathtt{Genetic}}\limits$) [38]. In addition, we used a random
selection method ($\mathop{\mathtt{RS}}\limits$) as another baseline to
randomly sample a TCR from $\mathop{\mathtt{TCRdb}}\limits$, which helps
quantify the space of valid TCRs. More details about baseline methods are
available in Appendix A.3.

###  4.4 Evaluation Metrics

We evaluated all the methods using six metrics including: (1) qualification
rate $\mathop{\mathtt{q\%}}\limits$, which measures the percentage of
qualified TCRs (Section 3.1) among all the output TCRs; (2) edit distance
between $\mbox{$\mathop{c}$}_{0}$ and $\mbox{$\mathop{c}$}_{T}$
($\mathop{\mathtt{edist}}$), which measures sequence difference between
$\mbox{$\mathop{c}$}_{0}$ and qualified $\mbox{$\mathop{c}$}_{T}$; (3) average
TCR validity score $\mathop{\overline{\mbox{$\mathop{s_{v}}\limits$}}}\limits$
over valid TCRs or over qualified TCRs; (4) average recognition probability
$\mathop{\overline{\mbox{$\mathop{s_{r}}$}}}\limits$ over valid TCRs or over
qualified TCRs; (5) validity rate $\mathop{\mathtt{v\%}}\limits$, which
measures the percentage of valid TCRs (Section 3.1) among all the output TCRs;
(6) average number of calls to $\mathcal{R}$ calculation
($\mathop{\\#\mbox{$\mathcal{R}$}}$) (Equation 9) over all the generated TCRs,
which estimates the efficiency of methods. We calculated the metrics over two
different sets of output TCRs: (1) the set of valid TCRs
$\mathop{\mathcal{C}_{v}}\limits$:
$\mbox{$\mathop{\mathcal{C}_{v}}\limits$}=\\{\mbox{$\mathop{c}$}|\mbox{$\mathop{s_{v}}\limits$}(\mbox{$\mathop{c}$})>\mbox{$\mathop{\sigma_{c}}\limits$}\\}$;
(2) the set of qualified TCRs $\mathop{\mathcal{C}_{q}}\limits$:
${\mbox{$\mathop{\mathcal{C}_{q}}\limits$}}=\\{\mbox{$\mathop{c}$}|\mbox{$\mathop{s_{r}}$}(\mbox{$\mathop{c}$})>\mbox{$\mathop{\sigma_{c}}\limits$},\mbox{$\mathop{c}$}\in\mbox{$\mathop{\mathcal{C}_{v}}\limits$}\\}$.

##  5 Experimental Results

###  5.1 Comparison on TCR Optimization Methods

####  5.1.1 Overall Comparison

Table 1 presents the overall comparison among all the methods over
$\mathop{\mathcal{P}_{\scriptsize{\mbox{$\mathop{\mathtt{McPAS}}\limits$}}}}\limits$
and
$\mathop{\mathcal{P}_{\scriptsize{\mbox{$\mathop{\mathtt{VDJDB}}\limits$}}}}\limits$.
In
$\mathop{\mathcal{P}_{\scriptsize{\mbox{$\mathop{\mathtt{McPAS}}\limits$}}}}\limits$,
$\mathop{\mathtt{TCRPPO}}\limits$ methods achieve overall the best
performance: in terms of $\mathop{\mathtt{q\%}}\limits$,
$\mathop{\mathtt{TCRPPO}}\limits$ achieves $25.89\\!\pm\\!29.60\%$, which
slightly outperforms the best $\mathop{\mathtt{q\%}}\limits$ from the baseline
method $\mathop{\mathtt{Genetic}}\limits$ ($25.18\\!\pm\\!21.28\%$).
$\mathop{\mathtt{TCRPPO}\text{+}\mathtt{b}}\limits$ achieves the best
$\mathop{\mathtt{q\%}}\limits$ at $36.52\\!\pm\\!30.25\%$ among all the
methods, which is 45.04% better than the best from the baseline methods
($25.18\\!\pm\\!21.28\%$ from $\mathop{\mathtt{Genetic}}\limits$).
$\mathop{\mathtt{TCRPPO}\text{+}\mathtt{b}}\limits$ achieves so with a few
$\mathcal{R}$ calls ($\mathop{\\#\mbox{$\mathcal{R}$}}$ =7). In
$\mathop{\mathcal{P}_{\scriptsize{\mbox{$\mathop{\mathtt{VDJDB}}\limits$}}}}\limits$,
$\mathop{\mathtt{TCRPPO}}\limits$ methods also achieve overall the best
performance: in terms of $\mathop{\mathtt{q\%}}\limits$,
$\mathop{\mathtt{TCRPPO}}\limits$ and
$\mathop{\mathtt{TCRPPO}\text{+}\mathtt{b}}\limits$ outperform the best
baseline $\mathop{\mathtt{Genetic}}\limits$ by 18.80% and 52.89%.

Among the qualified TCRs ($\mathop{\mathcal{C}_{q}}\limits$) for
$\mathop{\mathcal{P}_{\scriptsize{\mbox{$\mathop{\mathtt{McPAS}}\limits$}}}}\limits$,
$\mathop{\mathtt{TCRPPO}}\limits$and
$\mathop{\mathtt{TCRPPO}\text{+}\mathtt{b}}\limits$ methods achieve the
highest $\mathop{\overline{\mbox{$\mathop{s_{v}}\limits$}}}\limits$ values on
average ($1.55\\!\pm\\!0.19$ for $\mathop{\mathtt{TCRPPO}}\limits$;
$1.55\\!\pm\\!0.17$ for $\mathop{\mathtt{TCRPPO}\text{+}\mathtt{b}}\limits$),
with above 6% improvement from those of $\mathop{\mathtt{Genetic}}\limits$,
which achieves the best $\mathop{\mathtt{q\%}}\limits$ among all the baseline
methods. Note that qualified TCRs must have $\mathop{s_{v}}\limits$ above
$\mathop{\sigma_{c}}\limits$, which is set as 1.2577 as discussed in Appendix
A.4.4. The significant high $\mathop{s_{v}}\limits$ values from
$\mathop{\mathtt{TCRPPO}}\limits$ methods demonstrate that
$\mathop{\mathtt{TCRPPO}}\limits$ is able to generate qualified TCRs that are
highly likely to be valid TCRs. In terms of $\mathop{s_{r}}$ among qualified
TCRs, $\mathop{\mathtt{TCRPPO}}\limits$ methods have
$\mbox{$\mathop{\overline{\mbox{$\mathop{s_{r}}$}}}\limits$}(\mbox{$\mathop{\mathcal{C}_{q}}\limits$})$
value $0.97\\!\pm\\!0.03$, above the $\mathop{\sigma_{r}}\limits$. Note that
$\mbox{$\mathop{\sigma_{r}}\limits$}=0.9$, a very high threshold for
$\mathop{s_{r}}$ to determine TCR-peptide binding, is actually a very tough
constraint. The fact that $\mathop{\mathtt{TCRPPO}}\limits$ methods can
survive this constraint with substantially high $\mathop{\mathtt{q\%}}\limits$
and highly likely valid TCRs as results demonstrates the strong capability of
$\mathop{\mathtt{TCRPPO}}\limits$ methods. In addition,
$\mathop{\mathtt{TCRPPO}}\limits$ methods need a few number of calls to
calculate $\mathcal{R}$ (i.e., 7 for $\mathop{\mathtt{TCRPPO}}\limits$,
compared to 166 for $\mathop{\mathtt{Genetic}}\limits$), indicating that
$\mathop{\mathtt{TCRPPO}}\limits$ is very efficient in identifying qualified
TCRs. In
$\mathop{\mathcal{P}_{\scriptsize{\mbox{$\mathop{\mathtt{VDJDB}}\limits$}}}}\limits$,
we observed very similar trends as those in
$\mathop{\mathcal{P}_{\scriptsize{\mbox{$\mathop{\mathtt{McPAS}}\limits$}}}}\limits$.

Among all the baseline methods, $\mathop{\mathtt{RS}}\limits$ randomly selects
a valid TCR from $\mathop{\mathtt{TCRdb}}\limits$, given that some TCRs in
$\mathop{\mathtt{TCRdb}}\limits$ may already qualify. Thus, it is a naive
baseline for all the other methods. It has $\mathop{\mathtt{v\%}}\limits$
around 95%, corresponding to how our $\mathop{s_{v}}\limits$ threshold
$\mathop{\sigma_{c}}\limits$ is identified (by 95 percentile true positive
rate) as discussed in Appendix A.4.4. On average, among all valid TCRs, about
0.05% ($\mathop{\mathtt{q\%}}\limits$ in $\mathop{\mathtt{RS}}\limits$) TCRs
are qualified TCRs. $\mathop{\mathtt{RM}}\limits$,
$\mathop{\mathtt{Greedy}}\limits$, $\mathop{\mathtt{Genetic}}\limits$ and
$\mathop{\mathtt{TCRPPO}}\limits$ methods substantially outperform this
baseline method.

####  5.1.2 Comparison among Mutation-based Methods

$\mathop{\mathtt{RM}}\limits$, $\mathop{\mathtt{Greedy}}\limits$,
$\mathop{\mathtt{Genetic}}\limits$, $\mathop{\mathtt{TCRPPO}}\limits$ and
$\mathop{\mathtt{TCRPPO}\text{+}\mathtt{b}}\limits$ are mutation-based
methods: they start from a valid TCR from $\mathop{\mathtt{TCRdb}}\limits$,
and optimize the TCR by mutating its amino acids. Among all the mutation-based
methods, $\mathop{\mathtt{TCRPPO}}\limits$ and
$\mathop{\mathtt{TCRPPO}\text{+}\mathtt{b}}\limits$ outperform others as
discussed above. Below we only focused on
$\mathop{\mathcal{P}_{\scriptsize{\mbox{$\mathop{\mathtt{McPAS}}\limits$}}}}\limits$,
as similar trends exist on
$\mathop{\mathcal{P}_{\scriptsize{\mbox{$\mathop{\mathtt{VDJDB}}\limits$}}}}\limits$.

In
$\mathop{\mathcal{P}_{\scriptsize{\mbox{$\mathop{\mathtt{McPAS}}\limits$}}}}\limits$,
$\mathop{\mathtt{RM}}\limits$ underperforms all the other mutation-based
methods: it has $\mathop{\mathtt{q\%}}\limits$ below 3% on average, but has
very high $\mathop{\mathtt{v\%}}\limits$ (close to 100%).
$\mathop{\mathtt{RM}}\limits$ uses $\mathcal{R}$ to select randomly mutated
sequences, which decomposes to its $\mathop{s_{v}}\limits$ and its
$\mathop{s_{r}}$ components. $\mathop{\mathtt{RM}}\limits$ starts from valid
TCRs with high $\mathop{s_{v}}\limits$ already, but low $\mathop{s_{r}}$ in
general. During random mutation, $\mathop{s_{r}}$ cannot be easily improved as
no knowledge or informed guidance is used to direct the mutation towards
better $\mathop{s_{r}}$. Therefore, the $\mathop{s_{v}}\limits$ component in
$\mathcal{R}$ will dominate, leading to that the final selected, best mutated
sequence tends to have high $\mathop{s_{v}}\limits$ to satisfy high
$\mathcal{R}$. Such best mutated sequence tends to occur after only a few
random mutations, since as shown in Appendix A.4.4, random mutations can
quickly decrease $\mathop{s_{v}}\limits$ values. Thus, the qualified sequences
produced from $\mathop{\mathtt{RM}}\limits$ tend to be more similar to the
initial TCRs ($\mathop{\mathtt{edist}}$ is small, around 3; high
$\mathop{\mathtt{v\%}}\limits$ as $99.36\\!\pm\\!0.21\%$), their
$\mathop{s_{v}}\limits$ values are high (close to 1.5; highest among all
mutation-based methods) but $\mathop{\mathtt{q\%}}\limits$ is low due to
hardly improved $\mathop{s_{r}}$ values.

In
$\mathop{\mathcal{P}_{\scriptsize{\mbox{$\mathop{\mathtt{McPAS}}\limits$}}}}\limits$,
$\mathop{\mathtt{Greedy}}\limits$ has a better $\mathop{\mathtt{q\%}}\limits$
($20.58\\!\pm\\!17.85\%$) than $\mathop{\mathtt{RM}}\limits$ and also a high
$\mathop{\mathtt{v\%}}\limits$ ($99.98\\!\pm\\!0.04\%$).
$\mathop{\mathtt{Greedy}}\limits$ leverages a greedy strategy to select the
random mutation that gives the best $\mathcal{R}$ at the current step. Thus,
it leverages some guidance on $\mathop{s_{r}}$ improvement based on
$\mathcal{R}$, and can improve $\mathop{s_{r}}$ values compared to
$\mathop{\mathtt{RM}}\limits$. As in Table 1, it has better
$\mbox{$\mathop{s_{r}}$}(\mbox{$\mathop{\mathcal{C}_{v}}\limits$})$ value
($0.62\\!\pm\\!0.12$) for valid TCRs. Meanwhile,
$\mathop{\mathtt{Greedy}}\limits$ explores a large sequence space, allowing
its to identify more valid TCRs, leading to high
$\mathop{\mathtt{v\%}}\limits$ ($99.98\\!\pm\\!0.04$), high
$\mathop{\mathtt{q\%}}\limits$ ($20.58\\!\pm\\!17.85$; also due to better
$\mathop{s_{r}}$ improvement) but more diverse results
($\mbox{$\mathop{\mathtt{edist}}$}=5.10\\!\pm\\!1.09$) than
$\mathop{\mathtt{RM}}\limits$.

$\mathop{\mathtt{Genetic}}\limits$ is the second best mutation-based method on
$\mathop{\mathcal{P}_{\scriptsize{\mbox{$\mathop{\mathtt{McPAS}}\limits$}}}}\limits$,
after $\mathop{\mathtt{TCRPPO}}\limits$ methods.
$\mathop{\mathtt{Genetic}}\limits$ explores a sequence space even larger than
that in $\mathop{\mathtt{Greedy}}\limits$, and uses $\mathcal{R}$ to guide
next mutations also in a greedy way. Thus, it enjoys the opportunity to reach
more, potentially qualified TCRs, demonstrated by high
$\mathop{\mathtt{edist}}$ ($5.16\\!\pm\\!1.05$) indicating diverse sequences,
and thus achieves a better $\mathop{\mathtt{q\%}}\limits$
($25.18\\!\pm\\!21.28\%$) than $\mathop{\mathtt{Greedy}}\limits$, even better
than that of $\mathop{\mathtt{TCRPPO}}\limits$, and a high
$\mathop{\mathtt{v\%}}\limits$ ($100.00\pm 0.00\%$), at a significant cost of
many more calls to calculate $\mathcal{R}$. Even though, it still
significantly underperforms
$\mathop{\mathtt{TCRPPO}\text{+}\mathtt{b}}\limits$ in terms of
$\mathop{\mathtt{q\%}}\limits$ and qualities of qualified TCRs as discussed
earlier.

####  5.1.3 Comparison between Mutation-based Methods and Generation-based
Methods

Overall, mutation-based methods substantially outperform generation-based
methods. For example, in terms of $\mathop{\mathtt{q\%}}\limits$, mutation-
based methods (excluding random mutation $\mathop{\mathtt{RM}}\limits$) has an
average $\mathop{\mathtt{q\%}}\limits$ $22.88\%$ in
$\mathop{\mathcal{P}_{\scriptsize{\mbox{$\mathop{\mathtt{McPAS}}\limits$}}}}\limits$,
compared to $0.03\%$ of the generation-based methods
($\mathop{\mathtt{MCTS}}\limits$ and
$\mathop{\mathtt{BP\text{-}VAE}}\limits$). In addition to the superior
performance, mutation-based methods have strong biological relevance that make
them very suitable and practical for TCR-T based precision immunotherapy, in
which they can be readily employed to optimize existing TCRs found in
patient’s TCR repertoire. However, any promising TCRs generated from
generation-based methods have to be either synthesized, which could be both
very costly and technically challenging, or mutated from existing TCRs that
are similar to the generated TCRs in their amino acids. Detailed discussions
on generation-based methods are available in Appendix A.4.1.

###  5.2 Evaluation on Optimized TCR Sequences

[] []

Figure 3: Optimized TCR patterns for $\mathop{\mathtt{McPAS}}\limits$ peptides
(A); TCR distances (B).

Figure 3A presents the entropy of amino acid distributions at each sequence
position among the length-15 TCRs for each
$\mathop{\mathcal{P}_{\scriptsize{\mbox{$\mathop{\mathtt{McPAS}}\limits$}}}}\limits$
peptide. Here the TCRs are optimized by $\mathop{\mathtt{TCRPPO}}\limits$ with
respect to the $\mathop{\mathtt{McPAS}}\limits$ peptides. Figure 3A clearly
shows some common patterns among all the optimized TCRs. For example, the
first three positions and last four positions tend to have high conservation.
TCRs for some peptides (e.g., “SSPPMFRV", “ASNENMETM", and “RFYKTLRAEQASQ")
have high variations at internal regions. Similar patterns are also observed
among the binding TCRs for other peptides in $\mathop{\mathtt{VDJDB}}\limits$
222https://vdjdb.cdr3.net/motif.

Figure 3B presents the difference between qualified TCRs optimized by
$\mathop{\mathtt{TCRPPO}}\limits$ and existing TCRs. It presents the
distribution of Hamming distances between qualified TCRs (length 15) for
peptide “RFYKTLRAEQASQ” and their most similar (in terms of Hamming distance)
TCRs that are known to bind to this peptide in
$\mathop{\mathtt{McPAS}}\limits$; and the distribution of Hamming distances
between qualified TCRs for this peptide and their most similar TCRs in
$\mathop{\mathtt{TCRdb}}\limits$. This figure demonstrates that the qualified
TCRs by $\mathop{\mathtt{TCRPPO}}\limits$ are actually different from known
binding TCRs, but there are TCRs similar to them existing in
$\mathop{\mathtt{TCRdb}}\limits$. This can be meaningful for precision
immunotherapy, as $\mathop{\mathtt{TCRPPO}}\limits$ can produce diverse TCR
candidates that are different from known TCRs, leading to a novel sequence
space; meanwhile, these TCR candidates actually have similar human TCRs
available for further medical evaluation and investigation purposes.

Additional analyses are available in Appendix A.4, such as the overview of
amino acid distributions of TCRs, the patterns for binding TCRs and the
comparison on TCR detection. Specifically, we found that
$\mathop{\mathtt{TCRPPO}}\limits$ can successfully learn the patterns of TCRs
(Appendix A.4.2); we also found that $\mathop{\mathtt{TCRPPO}}\limits$ can
identify the specific binding patterns which are more conserved than the real
binding patterns (Appendix A.4.3). We also found that our
$\mathop{s_{v}}\limits$ scoring method successfully distinguishes TCRs from
non-TCRs in Appendix A.4.4.

##  6 Conclusions and Outlook

In this paper, we presented a reinforcement learning framework to optimize
TCRs for more effective TCR recognition, which has the potential to guide TCR
engineering therapy. Our experimental results in comparison with generation-
based methods and mutation-based methods on optimizing TCRs demonstrate that
$\mathop{\mathtt{TCRPPO}}\limits$ outperforms the baseline methods. Our
analysis on the TCRs generated by $\mathop{\mathtt{TCRPPO}}\limits$
demonstrates that $\mathop{\mathtt{TCRPPO}}\limits$ can successfully learn the
conservation patterns of TCRs. Our experiments on the comparison between the
generated TCRs and existing TCRs demonstrate that
$\mathop{\mathtt{TCRPPO}}\limits$ can generate TCRs similar to existing human
TCRs, which can be used for further medical evaluation and investigation. Our
results in TCR detection comparison show that the $\mathop{s_{v}}\limits$
score in our framework can very effectively detect non-TCR sequences. Our
analysis on the distribution of $\mathop{s_{v}}\limits$ scores over mutations
demonstrates that $\mathop{\mathtt{TCRPPO}}\limits$ mutates sequences along
the trajectories not far away from valid TCRs.

Our proposed $\mathop{\mathtt{TCRPPO}}\limits$ is a modular and flexible
framework. Thus, the $\mathop{\mathtt{TCR\text{-}AE}}$ and
$\mathop{\mathtt{ERGO}}\limits$ scoring functions in the reward design can be
replaced with other predictors trained on large-scale data when available.
Also, $\mathop{\mathtt{TCRPPO}}\limits$ can be further improved from the
following perspectives. First, the recognition probabilities of TCRs
considered in our paper are based on a peptide-TCR binding predictor (i.e.,
$\mathop{\mathtt{ERGO}}\limits$) rather than experimental validation.
Therefore, testing the generated qualified TCR candidates in a wet-lab will be
needed ultimately to validate the interactions between TCRs and peptides.
Moreover, when the predicted recognition probabilities are not sufficiently
accurate, $\mathop{\mathtt{TCRPPO}}\limits$ learned from unreliable rewards
could be inaccurate, resulting in generating TCRs that could not recognize the
given peptide. Thus, it could be an interesting and challenging future work to
incorporate the reliabilities of predictions in the reward function of
$\mathop{\mathtt{TCRPPO}}\limits$, so that the effect of unreliable
recognition probabilities can be alleviated. Finally,
$\mathop{\mathtt{TCRPPO}}\limits$ only considers the CDR3 of $\beta$ chain in
TCRs, while other regions of TCRs, though not contributing most to
interactions between TCRs and peptides, are not considered. In this sense,
incorporating other regions of TCRs (e.g., CDR3 of alpha chains) could be an
interesting future work.

## References

  * [1] Abati, D., Porrello, A., Calderara, S., Cucchiara, R.: Latent space autoregression for novelty detection. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) (June 2019)
  * [2] Angermüller, C., Dohan, D., Belanger, D., Deshpande, R., Murphy, K., Colwell, L.: Model-based reinforcement learning for biological sequence design. In: 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020 (2020)
  * [3] Arnold, F.H.: Design by directed evolution. Accounts of Chemical Research 31(3), 125–131 (feb 1998)
  * [4] Auer, P., Cesa-Bianchi, N., Fischer, P.: Machine Learning 47(2/3), 235–256 (2002)
  * [5] Cai, M., Bang, S., Zhang, P., Lee, H.: ATM-TCR: TCR-epitope binding affinity prediction using a multi-head self-attention model. Frontiers in Immunology 13 (jul 2022)
  * [6] Chen, S.Y., Yue, T., Lei, Q., Guo, A.Y.: TCRdb: a comprehensive database for t-cell receptor sequences with powerful search function. Nucleic Acids Research 49(D1), D468–D474 (sep 2020)
  * [7] Chen, Z., Min, M.R., Ning, X.: Ranking-based convolutional neural network models for peptide-MHC class i binding prediction. Frontiers in Molecular Biosciences 8 (may 2021)
  * [8] Coulom, R.: Efficient selectivity and backup operators in monte-carlo tree search. In: Computers and Games, pp. 72–83. Springer Berlin Heidelberg (2007)
  * [9] Craiu, A., Akopian, T., Goldberg, A., Rock, K.L.: Two distinct proteolytic processes in the generation of a major histocompatibility complex class i-presented peptide. Proceedings of the National Academy of Sciences 94(20), 10850–10855 (sep 1997)
  * [10] Esfahani, K., Roudaia, L., Buhlaiga, N., Rincon, S.D., Papneja, N., Miller, W.: A review of cancer immunotherapy: From the past, to the present, to the future. Current Oncology 27(12), 87–97 (apr 2020)
  * [11] Freeman, J.D., Warren, R.L., Webb, J.R., Nelson, B.H., Holt, R.A.: Profiling the t-cell receptor beta-chain repertoire by massively parallel sequencing. Genome Research 19(10), 1817–1824 (jun 2009)
  * [12] Glanville, J., Huang, H., Nau, A., Hatton, O., Wagar, L.E., Rubelt, F., Ji, X., Han, A., Krams, S.M., Pettus, C., et al.: Identifying specificity groups in the t cell receptor repertoire. Nature 547(7661), 94–98 (2017)
  * [13] Gómez-Bombarelli, R., Wei, J.N., Duvenaud, D., Hernández-Lobato, J.M., Sánchez-Lengeling, B., Sheberla, D., Aguilera-Iparraguirre, J., Hirzel, T.D., Adams, R.P., Aspuru-Guzik, A.: Automatic chemical design using a data-driven continuous representation of molecules. ACS Central Science 4(2), 268–276 (jan 2018)
  * [14] González, J., Longworth, J., James, D.C., Lawrence, N.D.: Bayesian optimization for synthetic gene design (2015)
  * [15] Graves, A., Schmidhuber, J.: Framewise phoneme classification with bidirectional LSTM and other neural network architectures. Neural Networks 18(5-6), 602–610 (jul 2005)
  * [16] Gupta, A., Zou, J.: Feedback GAN for DNA optimizes protein functions. Nature Machine Intelligence 1(2), 105–111 (feb 2019)
  * [17] Hinton, G.E., Vinyals, O., Dean, J.: Distilling the knowledge in a neural network. CoRR abs/1503.02531 (2015)
  * [18] Hou, X., Wang, M., Lu, C., Xie, Q., Cui, G., Chen, J., Du, Y., Dai, Y., Diao, H.: Analysis of the repertoire features of TCR beta chain CDR3 in human by high-throughput sequencing. Cellular Physiology and Biochemistry 39(2), 651–667 (2016)
  * [19] Killoran, N., Lee, L.J., Delong, A., Duvenaud, D., Frey, B.J.: Generating and designing DNA with deep generative models. CoRR abs/1712.06148 (2017)
  * [20] La Gruta, N.L., Gras, S., Daley, S.R., Thomas, P.G., Rossjohn, J.: Understanding the drivers of mhc restriction of t cell receptors. Nature Reviews Immunology 18(7), 467–478 (2018)
  * [21] Mnih, V., Badia, A.P., Mirza, M., Graves, A., Lillicrap, T., Harley, T., Silver, D., Kavukcuoglu, K.: Asynchronous methods for deep reinforcement learning. In: Proceedings of The 33rd International Conference on Machine Learning. vol. 48, pp. 1928–1937. PMLR, New York, New York, USA (20–22 Jun 2016)
  * [22] Pang, G., Shen, C., Cao, L., Hengel, A.V.D.: Deep learning for anomaly detection: A review. ACM Comput. Surv. 54(2) (mar 2021)
  * [23] Platt, J.: Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods. Advances in large margin classifiers 10(3), 61–74 (mar 1999)
  * [24] Raffin, A., Hill, A., Gleave, A., Kanervisto, A., Ernestus, M., Dormann, N.: Stable-baselines3: Reliable reinforcement learning implementations. Journal of Machine Learning Research 22(268), 1–8 (2021)
  * [25] Ren, J., Liu, P.J., Fertig, E., Snoek, J., Poplin, R., DePristo, M.A., Dillon, J.V., Lakshminarayanan, B.: Likelihood Ratios for Out-of-Distribution Detection. Curran Associates Inc., Red Hook, NY, USA (2019)
  * [26] Rossjohn, J., Gras, S., Miles, J.J., Turner, S.J., Godfrey, D.I., McCluskey, J.: T cell antigen receptor recognition of antigen-presenting molecules. Annual review of immunology 33, 169–200 (2015)
  * [27] Sadelain, M., Rivière, I., Riddell, S.: Therapeutic t cell engineering. Nature 545(7655), 423–431 (2017)
  * [28] Schulman, J., Moritz, P., Levine, S., Jordan, M., Abbeel, P.: High-dimensional continuous control using generalized advantage estimation. In: Proceedings of the International Conference on Learning Representations (ICLR) (2016)
  * [29] Schulman, J., Wolski, F., Dhariwal, P., Radford, A., Klimov, O.: Proximal policy optimization algorithms. CoRR abs/1707.06347 (2017)
  * [30] Shugay, M., Bagaev, D.V., Zvyagin, I.V., Vroomans, R.M., Crawford, J.C., Dolton, G., et al.: VDJdb: a curated database of t-cell receptor sequences with known antigen specificity. Nucleic Acids Research 46(D1), D419–D427 (sep 2017)
  * [31] Skwark, M.J., Carranza, N.L., Pierrot, T., Phillips, J., Said, S., Laterre, A., Kerkeni, A., Sahin, U., Beguir, K.: Designing a prospective COVID-19 therapeutic with reinforcement learning. CoRR abs/2012.01736 (2020)
  * [32] Snover, M., Dorr, B., Schwartz, R., Micciulla, L., Makhoul, J.: A study of translation edit rate with targeted human annotation. In: Proceedings of the 7th Conference of the Association for Machine Translation in the Americas: Technical Papers. pp. 223–231. Cambridge, Massachusetts, USA (Aug 8-12 2006)
  * [33] Springer, I., Besser, H., Tickotsky-Moskovitz, N., Dvorkin, S., Louzoun, Y.: Prediction of specific TCR-peptide binding from large dictionaries of TCR-peptide pairs. Frontiers in Immunology 11 (aug 2020)
  * [34] Tickotsky, N., Sagiv, T., Prilusky, J., Shifrut, E., Friedman, N.: McPAS-TCR: a manually curated catalogue of pathology-associated t cell receptor sequences. Bioinformatics 33(18), 2924–2929 (may 2017)
  * [35] Verdegaal, E.M.E., de Miranda, N.F.C.C., Visser, M., Harryvan, T., van Buuren, M.M., Andersen, R.S., Hadrup, S.R., van der Minne, C.E., Schotte, R., Spits, H., Haanen, J.B.A.G., Kapiteijn, E.H.W., Schumacher, T.N., van der Burg, S.H.: Neoantigen landscape dynamics during human melanoma–t cell interactions. Nature 536(7614), 91–95 (jun 2016)
  * [36] Waldman, A.D., Fritz, J.M., Lenardo, M.J.: A guide to cancer immunotherapy: from t cell basic science to clinical practice. Nature Reviews Immunology 20(11), 651–668 (may 2020)
  * [37] Weber, A., Born, J., Martínez, M.R.: TITAN: T-cell receptor specificity prediction with bimodal attention networks. Bioinformatics 37(Supplement_1), i237–i244 (jul 2021)
  * [38] Whitley, D.: A genetic algorithm tutorial. Statistics and Computing 4(2) (jun 1994)
  * [39] Williams, R.J., Zipser, D.: A learning algorithm for continually running fully recurrent neural networks. Neural Computation 1(2), 270–280 (jun 1989)
  * [40] Zong, B., Song, Q., Min, M.R., Cheng, W., Lumezanu, C., Cho, D., Chen, H.: Deep autoencoding gaussian mixture model for unsupervised anomaly detection. In: International Conference on Learning Representations (2018)

##  A.1 Data Analyses

We listed the selected peptides from $\mathop{\mathtt{McPAS}}\limits$ and
$\mathop{\mathtt{VDJDB}}\limits$ in Table A.1. As shown in Table A.1, these
selected peptides are very different. For example, the average edit distance
between pairs of peptides in
$\mathop{\mathcal{P}_{\scriptsize{\mbox{$\mathop{\mathtt{McPAS}}\limits$}}}}\limits$
and
$\mathop{\mathcal{P}_{\scriptsize{\mbox{$\mathop{\mathtt{VDJDB}}\limits$}}}}\limits$
are 10.84 and 9.14, respectively, demonstrating the diversity of peptides
compared with the average length of peptides in
$\mathop{\mathcal{P}_{\scriptsize{\mbox{$\mathop{\mathtt{McPAS}}\limits$}}}}\limits$
and
$\mathop{\mathcal{P}_{\scriptsize{\mbox{$\mathop{\mathtt{VDJDB}}\limits$}}}}\limits$
(10.90 and 9.67). Comparing
$\mathop{\mathcal{P}_{\scriptsize{\mbox{$\mathop{\mathtt{McPAS}}\limits$}}}}\limits$
with
$\mathop{\mathcal{P}_{\scriptsize{\mbox{$\mathop{\mathtt{VDJDB}}\limits$}}}}\limits$,
we found that 6 peptides included in
$\mathop{\mathcal{P}_{\scriptsize{\mbox{$\mathop{\mathtt{McPAS}}\limits$}}}}\limits$
are also included in
$\mathop{\mathcal{P}_{\scriptsize{\mbox{$\mathop{\mathtt{VDJDB}}\limits$}}}}\limits$,
which could be due to the data overlapping between
$\mathop{\mathtt{McPAS}}\limits$ and $\mathop{\mathtt{VDJDB}}\limits$ [30].

We also listed the distribution of length of TCRs in
$\mathop{\mathtt{TCRdb}}\limits$ in Figure A.1. We found that the most common
length of TCRs is 15; and TCRs with 13, 14, 15, and 16 lengths account for
over 10% of the entire database. In this manuscript, our analyses focus on
TCRs of length 13, 14, 15 and 16.

Table A.1: Peptides in $\mathop{\mathtt{McPAS}}\limits$ and $\mathop{\mathtt{VDJDB}}\limits$ that TCRs are optimized to bind to $\mathop{\mathcal{P}_{\scriptsize{\mbox{$\mathop{\mathtt{McPAS}}\limits$}}}}\limits$ |  | $\mathop{\mathcal{P}_{\scriptsize{\mbox{$\mathop{\mathtt{VDJDB}}\limits$}}}}\limits$
---|---|---
ASNENMETM |  | ASNENMETM
ATDALMTGY |  | ATDALMTGY
HGIRNASFI |  | CTPYDINQM
HPKVSSEVHI |  | FPRPWLHGL
MEVGWYRSPFSRVVHLYRNGK |  | FRDYVDRFYKTLRAEQASQE
RFYKTLRAEQASQ |  | GTSGSPIVNR
SSLENFRAYV |  | HGIRNASFI
SSPPMFRV |  | LSLRNPILV
SSYRRPVGI |  | NAITNAKII
YSEHPTFTSQY |  | SQLLNAKYL
|  | SSLENFRAYV
|  | SSPPMFRV
|  | SSYRRPVGI
|  | STPESANL
|  | TTPESANL
Figure A.1: The distribution of length of TCRs in
$\mathop{\mathtt{TCRdb}}\limits$.

##  A.2 Parameter setup

Table A.2: Experimental Setup for $\mathop{\mathtt{TCRPPO}}\limits$ description | value
---|---
maximum steps $T$ | 8
threshold of $\mathop{s_{r}}$ | 0.9
threshold of $\mathop{s_{v}}\limits$ | 1.2577
discount factor $\gamma$ | 0.9
latent dimension of $\overrightarrow{\mbox{$\mathbf{h}$}}_{i}/\overleftarrow{\mbox{$\mathbf{h}$}}_{i}/\mbox{$\mathbf{h}$}^{p}$ | 256
hidden dimension of policy & value networks | 128
hidden layers of policy & value networks | 2
number of steps per iteration | 5,120
batch size for policy update | 64
number of epochs per iteration | 10
clip range | 0.2
learning rate | 3e-4
coefficient for value function $\alpha_{1}$ | 0.5
coefficient for entropy regularization $\alpha_{2}$ | 0.01

We listed the hyper-parameters of the TCR mutation environment, the policy
network and the $\mathop{\mathtt{RL}}\limits$ agent in Table A.2. We selected
an optimal set of hyperparameters including the discount factor, the entropy
coefficient and the maximum steps by a grid search, according to the average
rewards of the final 10 iterations. Particularly, we set the maximum steps $T$
as 8 steps, as we empirically found that it can lead to the highest average
final rewards. We set the parameter $\alpha$ as 0.5 for the tradeoff between
validity scores and recognition probabilities, as we empirically found that
different $\alpha$ values could lead to comparable results. We also
constructed a validation set by sampling 1,000 TCRs from the test set of
$\mathop{\mathtt{TCR\text{-}AE}}$; these TCRs are not included in the test set
of $\mathop{\mathtt{TCRPPO}}\limits$. We then selected the hyperparameters
including the hidden dimension of policy network and value networks and the
ratio of difficult initial state from
$\mathop{\mathtt{Buf\text{-}Opt}}\limits$ that the corresponding models
achieve the maximum qualified percentage $\mathop{\mathtt{q\%}}\limits$. Among
three options $[64,128,256]$, the optimal hidden dimensions of policy and
value networks for $\mathop{\mathtt{McPAS}}\limits$ and
$\mathop{\mathtt{VDJDB}}\limits$ are 128. We set the latent dimension of
$\overrightarrow{\mbox{$\mathbf{h}$}}_{i}/\overleftarrow{\mbox{$\mathbf{h}$}}_{i}/\mbox{$\mathbf{h}$}^{p}$
to be double of the optimal hidden dimensions, that is, 256. In terms of
encodings of amino acids, we set the dimension of learnable embeddings as 20,
which is the same with the dimensions of BLOSUM embeddings and one-hot
encodings; that is, the total dimension of amino acid encodings is 60. In
terms of ratios of difficult initial state, the optimal ratios for
$\mathop{\mathtt{McPAS}}\limits$ and $\mathop{\mathtt{VDJDB}}\limits$ are 0.2
and 0.1, respectively. We set the threshold for recognition probability
$\mathop{s_{r}}$ as 0.9, which is demonstrated as a proper threshold as it can
lead to 47.04% and 56.48% at true positive rate and 0.16% and 0.30% at false
positive rate, respectively, for selected peptides in
$\mathop{\mathtt{McPAS}}\limits$ and $\mathop{\mathtt{VDJDB}}\limits$. In the
implementation of $\mathop{\mathtt{TCRPPO}}\limits$, for each iteration, we
ran 20 environments in parallel for 256 timesteps and collect trajectories
with 5,120 timesteps in total. We trained $\mathop{\mathtt{TCRPPO}}\limits$
for 1e7 timesteps (i.e., 1954 iterations). We set all the other hyper-
parameters for the $\mathop{\mathtt{RL}}\limits$ agent as the default hyper-
parameters provided by the stable-baselines3 [24], as we found little
performance improvement from tuning these parameters. We trained the models
using a Tesla P100 GPU and a CPU on Red Hat Enterprise 7.7. It took 9-10 hours
to train a $\mathop{\mathtt{TCRPPO}}\limits$ model. With the trained model
available, on a single GPU and a single CPU core, optimizing 1,000 TCRs for a
single peptide using $\mathop{\mathtt{TCRPPO}}\limits$ takes 160.5 seconds,
which is faster than that of the state-of-the-art baseline
$\mathop{\mathtt{Genetic}}\limits$ (i.e., 207.8s).

For $\mathop{\mathtt{TCR\text{-}AE}}$, we selected an optimal set of
hyperparameters including the dimension of hidden layers and the dimension of
latent layers. According to the reconstruction accuracy on the validation set,
we set the dimension of hidden layers in $\mathop{\mathtt{TCR\text{-}AE}}$ to
be 64, and the dimension of latent layers to be 16. At each step, we randomly
sampled 256 TCR sequences from $\mathop{\mathtt{TCRdb}}\limits$, and trained
the $\mathop{\mathtt{TCR\text{-}AE}}$ for 100,000 steps. This
$\mathop{\mathtt{TCR\text{-}AE}}$ is with high reconstruction accuracy on our
validation set, which is $94.6$%, and thus can be used to provide reliable
reconstruction-based scores for TCR sequences.

##  A.3 Baseline methods

We describe the baseline methods used in the main text as follows,

  * •

$\mathop{\mathtt{MCTS}}\limits$: Monte Carlo Tree Search. Given a peptide
$\mathop{p}$, $\mathop{\mathtt{MCTS}}\limits$ generates TCR sequences by
adding one amino acid step by step until reaching the maximum length of 20
amino acids or with the recognition probability $\mathop{s_{r}}$ greater than
$\sigma_{r}$. All the generated peptides with no less than 10 amino acids will
be evaluated by $\mathop{\mathtt{ERGO}}\limits$. The approach of
$\mathop{\mathtt{MCTS}}\limits$ is described in Algorithm A.1. At each step,
the amino acid to be added is determined by the Upper Confidence Bound
algorithm (see equation in line 12 of Algorithm A.1) to balance exploration
and exploitation [4]. The hyper-parameter $c_{puct}$ is set as 0.5. For each
peptide, the number of rollout $N$ is set as 1,000, as all the methods
including $\mathop{\mathtt{TCRPPO}}\limits$ generate 1,000 TCRs for each
peptide. At the beginning of search, we initialize the sequence with “C”, as
all the TCRs in $\mathop{\mathtt{TCRdb}}\limits$ begin with “C”. We collected
all the generated TCRs during the search process, and calculated the metrics
listed in Table 1 over the 1,000 TCRs with the highest reward values for each
peptide.

  * •

$\mathop{\mathtt{BP\text{-}VAE}}\limits$: Back Propagation with the
Variational Autoencoder. In $\mathop{\mathtt{BP\text{-}VAE}}\limits$, a VAE
model is first pre-trained to convert TCR sequences of variable lengths into
continuous latent embeddings of a fixed size with a single-layer LSTM. Then, a
student model with the pre-trained VAE is employed to distill knowledge from
$\mathop{\mathtt{ERGO}}\limits$ via learning the recognition probabilities
produced by $\mathop{\mathtt{ERGO}}\limits$ from the latent embeddings [17].
Note that during this fine-tuning process, the parameters of pre-trained VAE
will also be updated. With the well-trained student model,
$\mathop{\mathtt{BP\text{-}VAE}}\limits$ can generate TCRs by optimizing the
latent embeddings of TCRs through gradient ascent to maximize the predicted
recognition probabilities from the student model. The decoded TCR sequences
with the prediction from student model greater than $\sigma_{r}$ will be
evaluated by $\mathcal{R}$ function. We fine-tuned the hyper-parameters and
set the dimension of hidden layers for VAE as 64, the dimension of latent
embeddings as 8, the batch size as 256, the initial coefficient for KL loss as
0.05 and the initial learning rate as 0.005. We increased the coefficient by
0.05 every 1e4 steps until reaching the maximum coefficient limit 0.3; we also
decreased the learning rate by 10 percent every 5,000 steps until reaching the
minimum learning rate limit 0.0001. We pre-trained the VAE model for 2e6
steps. We then fine-tune the VAE model with the student model for 50,000
steps. During the inference, we set the maximum step $t$ for gradient ascent
as 50 and the learning rate of gradient ascent as 0.05. Similar to
$\mathop{\mathtt{MCTS}}\limits$, we collected all the generated TCRs and
calculated the metrics over the 1,000 TCRs with the highest reward values for
each peptides.

  * •

$\mathop{\mathtt{RM}}\limits$: random mutation. It randomly mutates a sequence
one amino acid at a step up to 8 steps, each step leading to an intermediate
mutated sequence; it does so for each sequence $n$ times, generating 8$n$
mutated sequences. It selects the mutated sequence with the highest
$\mathcal{R}$ as the final output.

  * •

$\mathop{\mathtt{Greedy}}\limits$: greedy mutation. It randomly mutates one
amino acid of $\mbox{$\mathop{c}$}_{t}$ at step $t$, and does this 10 times,
generating 10 mutated sequences which are all one-amino-acid different from
$\mbox{$\mathop{c}$}_{t}$. It selects the one with best $\mathcal{R}$ among
the 10 sequences as the next sequence to further mutate.

  * •

$\mathop{\mathtt{Genetic}}\limits$: genetic mutation. It randomly mutates each
sequence in the population (size $n=5$) five times, each at one site,
generating five mutated sequences. Among all the mutated sequences for all the
sequences in the population, $\mathop{\mathtt{Genetic}}\limits$ selects the
top-$n$ sequences with the best $\mathcal{R}$ as the next population.

Algorithm A.1 Monte Carlo Tree Search for TCR Generation

1:$\mbox{$\mathcal{R}$}(.,\mbox{$\mathop{p}$})$, $c_{puct}$, $N$, minLen,
maxLen

2:$U=\\{\\}$

3:for $n=$ 1 to $N$ do

4: $\triangleright$ root node of search tree $T$

5: $\mbox{$\mathop{c}$}_{0}=$ “C”; $\tau^{n}=\\{\\}$

6: for $l=$ 1 to maxLen do

7: $\triangleright$ expansion

8: for each amino acid $\mathop{o}$ do

9:
$\mbox{$\mathop{c}$}_{l}^{\prime}=\mbox{$\mathop{c}$}_{l-1}+\mbox{$\mathop{o}$}$

10: if $\mbox{$\mathop{c}$}_{l}^{\prime}\notin T$ then

11: $W(\mbox{$\mathop{c}$}_{l}^{\prime})=0$;
$N(\mbox{$\mathop{c}$}_{l}^{\prime})=0$;
$P(\mbox{$\mathop{c}$}_{l}^{\prime})=0$

12: add $\mbox{$\mathop{c}$}_{l}^{\prime}$ as a child of
$\mbox{$\mathop{c}$}_{l-1}$ into $T$

13: end if

14: end for

15: $\triangleright$ selection

16: select a child $\mbox{$\mathop{c}$}_{l}$ of $\mbox{$\mathop{c}$}_{l-1}$
with the maximum value
$a_{k}=\arg\max_{a}\frac{W(\mbox{$\mathop{c}$}_{l})}{N(\mbox{$\mathop{c}$}_{l})}+c_{puct}*\sqrt{\frac{2N(\mbox{$\mathop{c}$}_{l-1})}{1+N(\mbox{$\mathop{c}$}_{l})}}$

17: if $N(\mbox{$\mathop{c}$}_{l})=$ 0 and length($\mbox{$\mathop{c}$}_{l}$)
$\geq$ minLen then

18:
$P(\mbox{$\mathop{c}$}_{l})=\mbox{$\mathcal{R}$}(\mbox{$\mathop{c}$}_{l},\mbox{$\mathop{p}$})$

19: end if

20: $N(\mbox{$\mathop{c}$}_{l})=N(\mbox{$\mathop{c}$}_{l})+1$

21: add $\mbox{$\mathop{c}$}_{l}$ into $\tau^{n}$

22: if $\mbox{$\mathop{c}$}_{l}$ is qualified then

23: break

24: end if

25: end for

26: $\triangleright$ backpropagation

27: $r^{n}=0$

28: for each $\mbox{$\mathop{c}$}_{l}$ along path $\tau^{n}$ from
$\mbox{$\mathop{c}$}_{\text{maxLen}}$ to $\mbox{$\mathop{c}$}_{0}$ do

29: if $P(\mbox{$\mathop{c}$}_{l})>r^{n}$ then

30: $r^{n}=\mbox{$\mathop{c}$}_{l}.P$

31: end if

32: $W(\mbox{$\mathop{c}$}_{l})=W(\mbox{$\mathop{c}$}_{l})+r^{n}$

33: end for

34: $\triangleright$ output

35: add $\mbox{$\mathop{c}$}_{l}$ with maximum $P(\mbox{$\mathop{c}$}_{l})$
into $U$

36:end for

37:return $U$

##  A.4 Additional Results

###  A.4.1 Discussion on Comparison among Generation-based Methods

Generation-based methods $\mathop{\mathtt{MCTS}}\limits$ and
$\mathop{\mathtt{BP\text{-}VAE}}\limits$ on average very much underperform
mutation-based methods. Both $\mathop{\mathtt{MCTS}}\limits$ and
$\mathop{\mathtt{BP\text{-}VAE}}\limits$ hardly generate any qualified TCRs
(very low $\mathop{\mathtt{q\%}}\limits$: $0.01\\!\pm\\!0.03\%$ for
$\mathop{\mathtt{MCTS}}\limits$ and $0.04\\!\pm\\!0.09\%$ for
$\mathop{\mathtt{BP\text{-}VAE}}\limits$in
$\mathop{\mathcal{P}_{\scriptsize{\mbox{$\mathop{\mathtt{McPAS}}\limits$}}}}\limits$).
$\mathop{\mathtt{MCTS}}\limits$ explores potentially the entire sequence
space, including both valid TCRs and non-TCRs. Although it uses $\mathcal{R}$
to guide the search, with substantially more calls to calculate $\mathcal{R}$
than other methods, due to the fact that valid TCRs may only occupy an extreme
small portion of the entire sequence space, it is extremely challenging for
$\mathop{\mathtt{MCTS}}\limits$ to find qualified TCRs. In
$\mathop{\mathcal{P}_{\scriptsize{\mbox{$\mathop{\mathtt{VDJDB}}\limits$}}}}\limits$,
$\mathop{\mathtt{MCTS}}\limits$ even cannot find any qualified TCR for all the
peptides within 1,000 rollouts, and thus has zero values at
$\mbox{$\mathop{\overline{\mbox{$\mathop{s_{v}}\limits$}}}\limits$}(\mbox{$\mathop{\mathcal{C}_{q}}\limits$})$
and
$\mbox{$\mathop{\overline{\mbox{$\mathop{s_{r}}$}}}\limits$}(\mbox{$\mathop{\mathcal{C}_{q}}\limits$})$.
An estimation using $\mathop{\mathtt{TCRdb}}\limits$ over all possible
length-15 sequence space results at most $\frac{1,817,721}{20^{15}}=5.55\times
10^{-12}$% TCRs being valid in the sequence space. Therefore, it is possible
that $\mathop{\mathtt{MCTS}}\limits$ ends at a region in the sequence space
with $\mathop{\mathtt{q\%}}\limits$ even worse than random selection method
$\mathop{\mathtt{RS}}\limits$.

Similarly, $\mathop{\mathtt{BP\text{-}VAE}}\limits$ also has a minimum
$\mathop{\mathtt{q\%}}\limits$ ($0.04\\!\pm\\!0.09\%$).
$\mathop{\mathtt{BP\text{-}VAE}}\limits$ encodes valid TCRs into its latent
space, and uses a predictor in the latent space, which is trained to
approximate $\mathop{\mathtt{ERGO}}\limits$, to guide the search of an optimal
latent vector. This vector could correspond to a binding TCR and then is
decoded to a TCR sequence. However, there is a phenomenon that is observed in
other VAE-based generative approaches [13]: while the latent vector is
searched under a guidance to maximize desired properties, its decoded instance
does not always have the properties or are not even valid. This phenomenon
also appears in $\mathop{\mathtt{BP\text{-}VAE}}\limits$: the decoded TCRs are
not qualified most of the times. This might be due to the propagation or
magnification of the errors from the predictor in the latent space, or the
exploration in the latent space ends at a region far away from that of valid
TCRs. However, theoretical justification behind VAE-based generative
approaches is out of the scope of this paper.

###  A.4.2 Overview of Amino Acid Distributions of TCRs

Valid TCRs, regardless of their binding affinities against any peptides, have
certain patterns [11]. For example, the first and last amino acids have to be
‘C’ and ‘F’, respectively. Figure A.2 presents the patterns among different
TCRs of length 13, 14, 15 and 16. For TCRs of length 15 (most common TCR
length), the left panel of Figure A.2 shows the enrichment of different amino
acids at different positions among peptides in
$\mathop{\mathtt{TCRdb}}\limits$. Recall that $\mathop{\mathtt{TCRdb}}\limits$
has 277 million valid human TCRs, and thus the patterns in the left panel of
Figure A.2 are very representative of the common patterns among valid TCRs.
The middle panel of Figure A.2 shows that the patterns among the TCRs that
$\mathop{\mathtt{TCRPPO}}\limits$ produces for peptides in
$\mathop{\mathtt{McPAS}}\limits$ are similar to those of TCRs in
$\mathop{\mathtt{TCRdb}}\limits$. For example, ‘G’ is one of the most frequent
amino acids on positions 6-9; the first three positions and the last four
positions of optimized TCRs have patterns highly similar to those in
$\mathop{\mathtt{TCRdb}}\limits$ TCRs. Similar observations are also for the
TCRs that $\mathop{\mathtt{TCRPPO}}\limits$ produces for peptides in
$\mathop{\mathcal{P}_{\scriptsize{\mbox{$\mathop{\mathtt{VDJDB}}\limits$}}}}\limits$
as in the right panel of Figure A.2. Please note that in
$\mathop{\mathtt{TCRPPO}}\limits$, we do not impose any rules to reserve amino
acids at the ends of sequences when generating TCRs with both high validity
and high recognition probability against given peptides; clearly,
$\mathop{\mathtt{TCRPPO}}\limits$ successfully learns the pattern. In Figure
A.2, A.2 and A.2, the same observations are for TCRs of length 13, 14 and 16
as in Figure A.2 for TCRs of length 15. For example, the first three positions
and the last three positions of generated TCRs have very similar patterns with
those in $\mathop{\mathtt{TCRdb}}\limits$ (i.e., dominated by “CAS” and
“QYF”). This indicates that $\mathop{\mathtt{TCRPPO}}\limits$ also
successfully learn the patterns for TCRs of other lengths.

[]
[]
[]
[]

Figure A.2: The distribution of amino acids at different positions for all the
TCRs in $\mathop{\mathtt{TCRdb}}\limits$ (left panel) and the generated TCRs
for
$\mathop{\mathcal{P}_{\scriptsize{\mbox{$\mathop{\mathtt{McPAS}}\limits$}}}}\limits$
(middle panel) and
$\mathop{\mathcal{P}_{\scriptsize{\mbox{$\mathop{\mathtt{VDJDB}}\limits$}}}}\limits$
(right panel) of length 13 (A), length 14 (B), length 15 (C)and length 16 (D).

###  A.4.3 Amino Acid Distributions of Binding TCRs

Figure A.3 presents the patterns among binding TCRs in
$\mathop{\mathtt{McPAS}}\limits$ dataset (left) and the generated TCRs of
different lengths for peptide “RFYKTLRAEQASQ” in
$\mathop{\mathtt{McPAS}}\limits$. Particularly, as in Figure A.3, the patterns
among binding TCRs in $\mathop{\mathtt{McPAS}}\limits$ are similar to those of
generated TCRs. For example, the most frequent amino acids at position 6 - 9
in generated TCRs (i.e., “R”, “A”, “R”, “G”) are also one of the most frequent
amino acids at corresponding positions in known binding TCRs. Similar
observations are also for generated TCRs of different lengths. This
demonstrates that $\mathop{\mathtt{TCRPPO}}\limits$ can successfully identify
the patterns of binding TCRs. In addition to the similar patterns, we also
observe the inconsistent patterns between known binding TCRs and generated
TCRs. For example, the generated TCRs are highly conserved on position 4, that
is, most fourth amino acids are “H”; this conservation pattern does not exist
in known binding TCRs. Please note that “H” also exists on position 4 among
known binding TCRs as in Figure A.3. One reason for inconsistency between
generated TCRs and known binding TCRs could be that only limited percentage of
binding TCRs are with predicted recognition probabilities greater than 0.9,
resulting in that generated TCRs are more conserved on some patterns.

Figure A.4 presents the distribution of action types produced by
$\mathop{\mathtt{TCRPPO}\text{+}\mathtt{b}}\limits$ for TCRs of length 15
binding to the peptide “RFYKTLRAEQASQ”. As shown in Figure A.4, positions 5,
7, 9 in the TCRs prefer to be Histidine (“H”), Alanine (“A”), Arginine(“R”)
and Glycine (“G”). Since Alanine and Glycine are non-polar and hydrophobic,
the hydrophobic effect tends to be strong around these positions. On the other
hand, position 4 prefer to be Histidine, which has a positive charge on its
side chain. Additionally, positions 5, 6, 8 in the TCRs prefer to be Arginine,
which is hydrophilic and has a positive charge on its side chain. This shows
that the binding pocket around these positions is more electrophilic which
favors the interaction with amino acids with positive charges.

[]
[]
[]
[]

Figure A.3: The distribution of amino acids at different positions for TCRs
binding to the peptide “RFYKTLRAEQASQ” in $\mathop{\mathtt{McPAS}}\limits$
(left panel) and generated TCRs (right panel) of length 13 (A), length 14 (B),
length 15 (C) and length 16 (D). Figure A.4: The distribution of action types
produced by $\mathop{\mathtt{TCRPPO}\text{+}\mathtt{b}}\limits$ for TCRs of
length 15 binding to the peptide “RFYKTLRAEQASQ”.

###  A.4.4 Comparison on TCR Detection

We compared our $\mathop{s_{v}}\limits$ scoring method (Equation 8) and the
likelihood ratio method [25], denoted as $\mathop{\mathtt{lr}}\limits$, on
distinguishing TCRs from non-TCRs. The likelihood ratio method is one of the
state-of-the-art methods on out-of-distribution (OOD) detection for genomic
sequences. To compare $\mathop{s_{v}}\limits$ and
$\mathop{\mathtt{lr}}\limits$, we generated 50,000 sequences for each TCR in
$\mathop{\mathcal{S}_{tst}}\limits$, with the two ends conserved to ‘C’ and
‘F’ respectively as in valid TCRs, and all the other internal amino acids
fully random. These generated, random sequences will be considered as non-
TCRs. The conserved ‘C’ and ‘F’ ends among the non-TCRs ensure that they are
not trivially separable from TCRs simply due to the ends. We compared
$\mathop{s_{v}}\limits$ and $\mathop{\mathtt{lr}}\limits$ scores to detect
TCRs from such non-TCRs, and present their distributions in Figure A.5.

[] []

Figure A.5: Distributions of $\mathop{s_{v}}\limits$ scores (A) and
$\mathop{\mathtt{lr}}\limits$ scores (B).

[] []

Figure A.6: Distributions of $\mathop{s_{v}}\limits$ scores of TCRs with
random mutations (A) and mutations from $\mathop{\mathtt{TCRPPO}}\limits$ (B);
the red lines represent the threshold value $\mathop{\sigma_{v}}\limits$.

Figure A.5A shows that TCRs and non-TCRs are well separated by their
$\mathop{s_{v}}\limits$ scores, while Figure A.5B shows a clear overlap
between TCRs and non-TCRs using their $\mathop{\mathtt{lr}}\limits$ scores.
Using the 5 percentile of $\mathop{s_{v}}\limits$ scores on TCRs,
corresponding to value 1.2577 and 95% true positive rate on TCRs, as the
decision boundary, $\mathop{s_{v}}\limits$ scoring method achieves 0.10% false
positive rate. Using the 5 percentile of $\mathop{\mathtt{lr}}\limits$ scores
on TCRs (corresponding to $-0.4459$), $\mathop{\mathtt{lr}}\limits$ has a much
higher false positive rate 8.26%. This demonstrates that
$\mathop{s_{v}}\limits$ is very effective in distinguishing TCRs. Please note
that the random sequences are not guaranteed to be true non-TCRs. However,
given the random nature of these sequences, it is highly likely that they are
not valid TCRs. In $\mathop{\mathtt{TCRPPO}}\limits$, we used 1.2577 as the
threshold to quantify if a sequence is a valid TCR (i.e.,
$\sigma_{c}=1.2577$).

Figure A.6 presents the change of $\mathop{s_{v}}\limits$ scores over
mutations. Figure A.6A shows that as TCRs have more random mutations, their
$\mathop{s_{v}}\limits$ scores decrease dramatically. This implies that the
TCR optimization via mutation is not trivial, as a random/bad mutation can
significantly decrease $\mathop{s_{v}}\limits$ score and easily lead to an
unqualified solution. However, as Figure A.6B shows, the
$\mathop{s_{v}}\limits$ scores do not decrease very dramatically during
$\mathop{\mathtt{TCRPPO}}\limits$ mutations, consistently with a good portion
of mutated sequences being valid TCRs. This demonstrates that for this non-
trivial optimization problem, $\mathop{\mathtt{TCRPPO}}\limits$ succeeds in
mutating sequences along the trajectories not far away from valid TCRs, toward
final qualified sequences.