Model-based reinforcement learning for biological sequence design
Authors: Christof Angermueller
David Dohan
David Belanger
Ramya Deshpande
Kevin Murphy
Lucy Colwell
Venue:  (2020)
Keywords: reinforcement learning
blackbox optimization
molecule design

Abstract: The ability to design biological structures such as DNA or proteins would have considerable medical and industrial impact. Doing so presents a challenging black-box optimization problem characterized by the large-batch, low round setting due to the need for labor-intensive wet lab evaluations. In response, we propose using reinforcement learning (RL) based on proximal-policy optimization (PPO) for biological sequence design. RL provides a flexible framework for optimization generative sequence models to achieve specific criteria, such as diversity among the high-quality sequences discovered. We propose a model-based variant of PPO, DyNA-PPO, to improve sample efficiency, where the policy for a new round is trained offline using a simulator fit on functional measurements from prior rounds. To accommodate the growing number of observations across rounds, the simulator model is automatically selected at each round from a pool of diverse models of varying capacity.  On the tasks of designing DNA transcription factor binding sites, designing antimicrobial proteins, and optimizing the energy of Ising models based on protein structure, we find that DyNA-PPO performs significantly better than existing methods in settings in which modeling is feasible, while still not performing worse in situations in which a reliable model cannot be learned.

Published as a conference paper at ICLR 2020
MODEL-BASED REMNEORCEMENT LEARNING FOR BIO- LOGICAL SEQUENCE DESIGN
Christof Angermueller
David Dohan
Google Research
Google Research
[ddohan]@googlle, com
David Belanger
Ramya Deshpande
Google Research
Caltech
ttbellaager/@gooole..co
{rdeshpan) eaaltechhhaaccccccccccom edu
Kevin Murphy
Lucy Colwell
Google Research
Google Research
(kpmurphy) wooggy...ooogee.oooooooooo com
University of Cambridge
{1 co we 11 @@goog eegpogle.com com com
ABSTRACT
The ability to design biological structures such as DNA or proteins would have considerable medical and industrial impact. Doing so presents challenging black-box optimization problem characterized by the large-batch, low round set- ting due to the need for labor-intensive wet lab evaluations. response, we pro- pose using reinforcement learning (RL) based on proximal-policy optimization (PPO) for biological sequence design. RL provides flexible framework for opti- mization generative sequence models to achieve specific criteria, such diversity among the high-quality sequences discovered. We propose model-based vari- ant of PPO. DyNA PPO, improve sample efficiency, where the policy for a new round is trained offline using a simulator fit on functional measurements from prior rounds. To accommodate the growing number of observations across rounds, the simulator model automatically selected at each round from a pool of diverse models of varying capacity. On the tasks of designing DNA transcription factor binding sites, designing antimicrobial proteins, and optimizing the energy of Ising models based on protein structure, we find that DyNA PPO performs significantly better than existing methods in settings in which modeling is feasible, while still not performing worse in situations in which a reliable model cannot learned.
INTRODUCTION
Driven by real-world obstacles in health and disease requiring new drugs, treatments, and assays, the goal of biological sequence design identify new discrete sequences x which optimize some functional property f(x). This is a difficult black-box
oracle, typically experimentally--easue optimization problem over combinatorially large search space which function evaluation relies on slow and expensive wet-lab experiments. The setting induces unusual constraints in black-box optimization and reinforcement learning: large synchronous batches with few rounds total.
The current gold standard for biomolecular design is directed evolution, which was recently rec- ognized with a Nobel prize (Arnold) 1998) and form of randomized local search. Despite its impact, directed evolution is sample inefficient and relies greedy hillclimbing to the optimal quences. Recent work has demonstrated that machine-learning-gune guided optimization (Section 3) can find better sequences faster.
Work done intern Google.

---

Published as a conference paper at ICLR 2020
Reinforcement learning (RL) provides flexible framework for black-box optimization that can har- ness modern deep generative sequence models. This paper proposes a simple method for improving the sample efficiency of policy gradient methods such PPO (Schulman et al.] 2017) for black-box
optimization by using surrogate models that are trained online to approximate f(z). Our method updates the policy's parameters using sequences x: generated by the eurrent policy To (x)). but evalu- ated using a learned surrogate f((x), instead of the true, but unknown, oracle reward function f(r). We learn the parameters of the reward model, w, simultaneously with the parameters of the policy. This is similar to other model-based RL methods, but simpler, since in the context of sequence opti- mization, the transition model is deterministic and known. Initially the learned reward model, (x)x), is unreliable, so rely entirely on f'x:) to assess sequences and update the policy. This allows graceful fallback PPO when the model not effective. Over time, the reward model becomes more reliable and can be used cheap surrogate, similar to Bayesian optimization meth- ods (Shahriari et al., 2015). We show empirically that cross-validation an effective heuristic for assessing the model quality, which is simpler than the inference required by Bayesian optimization.
We rigorously evaluate our method on three in-silico sequence design tasks that draw on experi- mental data to construct functions f()) characteristic of real-world design problems: optimizing binding affinity of DNA sequences of length 8 (search space size 4*); optimizing anti-microbial peptide sequences (search space size 2030), and optimizing binary sequences where [(x) is defined by the energy of an Ising model for protein structure (search space size 2050). These do not rely on wet lab experiments, and thus allow for large-scale benchmarking across range of methods. We show that our DyNA PPO method achieves higher cumulative reward for a given budget (measured terms of number of calls f(x)) than existing methods, such standard PPO, various forms of the cross-entropy method, Bayesian optimization, and evolutionary search.
In summary, our contributions are as follows:
We provide a model-based RI. algorthm, DyNA PPO, and demonstrate its effectiveness in performing sample efficient batched black-box function optimization.
We address model bias by quantifying the reliability and automatically selecting models of appropriate complexity via cross- cross-validation.
We propose a visitation-basee exploration bonus and show that it is more effective than entropy-regulariiztion in identifying multiple local optima.
We present optimization task for benchmarking methods for biological sequence design based on protein energy Ising models.
2 METHODS
Let f(x) be the function that we want to optimize and x E VT a sequence of length T over a
vocabulary V such as DNA nucleotides (VV = 4) or amino acids (V) 20). We assume N experimental rounds and that B sequences can be measured per round. Let D, = {(x, f(x)) be the data acquired in round n with |D,] B. For simplicity, we assume that the sequence length T is constant, but our approach based on generating sequences autoregressively easily generalizes to length sequences.
2.1 MARKOV DECISION PROCESS
We formulate the design of single sequence x as a Markov decision process M = A, with state space S, action space A, transition function p. and reward function r. The state space S = Ut= is the set of all possible sequence prefixes and A corresponds to the vocabulary V. A sequence is generated left to right. At time step f, the state 5, = ..,..., corresponds to the t last tokens and the action E A to the next token. The transition function p(st + 1(s²) s,a, is deterministic and corresponds to appending a, to st- The reward r(st, a₂) is zero except at the last step T, where it corresponds to the functional measurement f(sr-1). For generating variable- sequences, we extend the vocabulary by a special -ndoo--eeueenc token and terminate sequence generation when this token is selected.
2

---

Published as a conference paper at ICLR 2020
Algorithm DyNA PPO
1: Input: Number of experiment rounds N
2: Input: Number of model- based training rounds
3: Input: Set of candidate models S = [f')
4: Input: Minimum model score r for model-based training
5: Input: Policy with initial parameters 0
6: for n = .. do
7:
Collect samples Dr, = fx; f(x)] using policy me
8:
Train policy me on D,,
9:
Fit candidate models f' E S on Ui=1 D; and compute their score by cross-validation Select the subset of models S" with score 2
10:
S' o then
12:
for m = 1, 2, M..M do
13:
Sample a batch of sequences x from Te and observe the reward f"(x) 189 Eres (x)
14:
Update on (x))
15:
end for
end
17:
end for
2.2 POLICY OPTIMIZATION
We train a policy no(a)(s)) optimize the expected sum of rewards:
E[R(s1a)1s0 0] ΣΣ
Tu(at (s))r(s at).
(I)
St Ge
We use proximal policy optimization (PPO) with KL trust-region constraint (Schulman et al. which we have found more stable and sample efficient than REINFORCE (Williams) 1992). We have also considered off-policy deep Q-learning (DQN) (Mnih et al. 2015). and categorical dis- tributional deep Q-learning (CatDQN) (Bellemare et al. 2017), which are in principle more sample- efficient than on-policy learning using PPO since they reuse samples multiple times. However, they performed worse than PPO in our experiments (Appendix C. We implement algorithms using the TF-Agents RL library (Guadarrama et al. 2018).
2017
We employ autoregressive models with one fully-connected layer as policy and value networks since they are faster to train and outperformed recurrent networks in experiments. At time step the network takes as input the W last characters B..w...,0K a--1 that are one-hot encoded, where the context window size W is hyper-parameter. To provide the network with information about the current position of the context window, it also receives the time step I, which is embedded using a sinusoidal positional encoding (Vaswani et al. 2017). and concatenated with the one-hot characters. The policy network outputs a distribution Ty (a (t)) over next the token ag. The value network V (st,, which approximates the expected future reward for being in state 8t, used baseline to reduce the variance of stochastic estimates of equation]
(Schulman et al. 2017
2.3 MODEL-BASED POLICY OPTIMIZATION
Model-based RL learns model of the environment that is used simulator to provide additional pseudo-obserrations. While model-free RL has been successful in domains where interaction with the environment is cheap, such as those where the environment defined by a software program, its high sample complexity may be unrealistic for biological sequence design. In model-based RL, the MDP M = (S, A. p.r) is approximated by a model M' (S, A. p', r') with the same state space S and action space A as M (Sutton & Barto 2018 Ch. 8). Since the transition function is deterministic in our case, only the reward function r r(st, az) needs to be approximated by r' r'(s,, at). Since r(sr, (rr) is non-zero at the last step T and then corresponds to fxx with = 8T-1, the problem reduces to approximating fxx). This can be done by supervised regression by fitting a regressor (zxx on the data Unic=nDD collected far. We then use the resulting model to collect additional observations fx))) and update the policy in a simulation phase, instead of only using observations (x, ff (2)) from the the true environment, which expensive to collect. We call our method DyNA PPO since it is similar to the DYNA architecture (Sutton) (199T); Peng et al. (2018) and since can be used for DNA sequence design.
3

---

Published as a conference paper at ICLR 2020
Model-based RL provides the promise of improved sample efficiency when the model is accurate, but it can reduce performance if insufficient data are available for training a trustworthy model. In this case, the policy is prone to exploit regions where the model is inaccurate (Janner et al. 2019). To reap the benefit of model-based RI. when the model is accurate and avoid reduced performance when is not, (i) automatically select the model from of candidate models of varying complexity, (ii) only use the selected model if it is accurate, and iii) stop model-based training as soon the the model uncertainty increases by certain threshold. After each round of experiment, we fit set of candidate models on all available data to estimate (ax) via supervised regression. We quantify the aceuracy of each candidate model by the R² score, which we estimate by five-fold cross-vass volss-valiattoon. See Appendix G for discussion of different data splitting strategies to select models using cross- validation. If the R2 score of all candidate model is below a pre-specified threshold т, we do not perform model-base training in that round. Otherwise, we build an ensemble model that includes all models with a score greater or equal than т, and use the average prediction as reward for training the policy. We considered all problems (see Figure 14 By ignoring the model if it is inaccurate, we aim to prevent the policy from exploiting deficiencies of the model (Janner et al. 2019).
tunable appereerraeete, were we found 0.5 to be optimal for
We perform up to M model-based optimization rounds (see Algorithm 1 and stop as soon as the model uncertainty increased by certain factor relative to the model uncertainty at the first round (m = 1). This is motivated by our observation that the model uncertainty is strongly correlated with the unknown model error, and prevents from training the policy with inaccurate model predictions (see Figure 12 13 on.
as soon as the model starts to explore regions on which the model was not trained
For models, we consider nearest neighbor regression, Bayesian ridge regression, random forests, gradient boosting trees, Gaussian processes, and ensemble of deep neural networks. Within each model family, we additionally use cross- valsdaaniittionn for tuning poper-pprameters, such as the number of trees, tree depth, kernels and kernel parameters, or the number of hidden layers and units (see Appendix A.7 for details). By testing and optimizing the hyper-parameter of different models automatically. the model capacity can dynamically increase as data becomes available.
In Bayesian optimization, non-parametric models such as Gaussian processes are popular regres- sors, and they also automatically grow model capacity as more data arrives (Shahriari et al. 2015). However, with Bayesian optimization there is no opportunity ignore the regressor entirely if is unreliable. Furthermore, Bayesian optimization relies on performing (approximate) Bayesian infer- ence, which in practice is sensitive to the choice of hyper-parameter (Snoek et al. 2012).
Overall, our method combines the positive attributes of both generative and discriminative ap- proaches to sequence design. Our experiments do not compare to prior work model-based RL., since these methods primarily focus on estimating a dynamics model for state transitions.
2.4 DIVERSITY-PROMOTIN REWARD FUNCTION
Learning policies to generate diverse sequences is important because of several reasons. In many ap- plications, fax is an in-vitro (taking place outside living organism) surrogate for in-vivo taking place inside a living organism) functional measurement that is even more expensive to evaluate than f(x). The in-vivo measurement may depend on properties that are correlated with f(x) and others that are not captured at all in-vitro, such as off-target effects or toxicity. To improve the chance that sequence satisfying the ultimate in-vivo criteria found, it is therefore desirable for the optimiza- tion procedure to discover diverse set of candidate optima. Here, diversity is downstream metric, for which training the policy To (z) to maximize equation I will not necessarily yield good perfor- mance. For example, a high-quality policy can learn to always generate the same sequence with a high value of f()), and will therefore result in zero diversity. An additional reason that diversity matters is that it yields good exploration strategy, even for scenarios where optimizing equation is sufficient. Finally, use of strategies that reward high-diversity policies can reduce the policies' tendency to generate exact duplicates.
To increase sequence diversity, we employ a simple exploration reward bonus based on the den- sity of proposed sequences, similar to existing exploration techniques based state visitation fre- quency (Bellemare et al. 20166). Specifically, we define the final reward as Pr = f(x)-Xx x-dens, where dens, (z) E N the weighted number of sequences that have been proposed in previous
4

---

Published as a conference paper at ICLR 2020
rounds with distance of less than away from z, where the weight decays linearly with the dis- tance. This reward penalizes proposing similar sequences multiple times, where the strength of the penalty is controlled by A. As a result, the policy learns not to generate related sequences and hence explores the search space more effectively. We used the edit distance as distance metric and tuned the distance radius e, where setting e > 0 improved exploration Figure II). We also considered an alternative penalty based on the nearest neighbor distance of the proposed sequence to past sequences, which we found be less effective (see Figure 9).
high-dimensional problems (see
3 RELATED WORK
Recently, machine learning approaches have been shown to be effective in optimizing real-world DNA and protein sequences (Wang et al. 2019 Chhibbar & Joshi] 2019 de Jongh et al., (2019 Liu et al. 2019| (ample et al.) 2019 Wu al. 2019). Existing methods for biological sequence design fall into three broad categories: evolutionary search, optimization using discriminative models (e.g.
Bayesian optimization), and optimization using generative models (e.g. the cross entropy method).
Evolutionary approaches perform direct local search in the space of sequences. They include the aforementioned directed evolution and derivatives with application-specife mutation and recombi- nation steps. Evolutionary approaches are appealing since they are simple and can easily incorporate human intuition into the design process, but generally suffer from low sample efficiency.
Optimization methods based on discriminative models alternate between two steps: (i) using the data that have been collected so far to fit regressor f'(x) to approximate fax), and (ii) using (x)
to define an acquisition function that is optimized to select the next batch of sequences. Recently, such an approach was used to optimize the binding affinity of IgG antibodies (Liu et al.) 2019). where a neural network ensemble tion is a non-trivial combinatorial optimization problem. Liu et al. (2019) employed activation maximization, where gradient-based based optimization is performed on continuous relaxation of the discrete search space. However, this requires (x) to be differentiable and optimization of a con- tinuous relaxation is vulnerable to leaving the data manifold (ef. deep dream (Mordvintsev et al.,
used for f'(z). In general. optimizing the acquisition func-
2.15).
Bayesian optimization defines an acquisition function such as the expected improvement (Mockus et al. 2014) based on the uncertainty of (xx), which enables balancing exploration and exploita- tion (overview provided in (hahhiarii al. (2015)) Gaussian processes (GPs) are commonly used for Bayesian black-box optimization since they provide calibrated uncertainty estimates. Unfortunately, GPs are hard to scale to large, high-dimensional datasets and are sensitive to the choice of hyper- parameters. In response, recent work has performed continuous black-box optimization in the latent space of deep generative model (Gómez-Bombare et al., 2018).. However, this approach requires pre-trained model such as a variational autoencoder to obtain the latent embeddings. Our model- based reinforcement learning approach is similar to these approaches in that we train a reinforcement learning policy to optimize a model (xx) However, our policy is also trained directly on observa- tions of fxx) and is able to resort to model-free training by automatically identifying if the model f'(x:) is too inaccurate to be used as surrogate of [(x))- Janner et al. (2019) investigated conditions in which an estimate of model generalization (their analysis uses validation accuracy) could justify model usage in such model-based policy optimization settings. Hashimoto al. (2018) proposed using a cascade of classifiers, one per round, to guide sampling progressively better candidates.
Optimization methods based on generative models seek learn distribution (x(x)) parameterized by 0 that maximizes the expected value of f(x):: [zx [=x)). We note that this is the same form as variational optimization objectives. which allow the use of parameter-space evolutionary strategies (Staines & Barber 2013). Wierstra et al.] [2014; [Salimans et al. 2017). Variants of the cross entropy method (De Boer et al. 20055 Brookes et al. (019a) optimize 6, by alternating two 2005kBrrooks
steps: (i) sampling x ~ po(x)) (2)) and evaluating f(x), and (ii) updating 0 to maximize this expecta- tion. Methods differ in how step (ii) is performed. For example, hillclimb-MLE (Neil et al. 2018) performs maximum-likelihen
training on the top k sequences from step (i). Similarly, Feedback GAN (FBGAN) uses samples whose target function value f(x) exceeds a fixed threshold for train- ing generative adversarial network (Gupta & Zou, 2018). Design by Adaptive Sampling (DbAs) performs weighted MLE of variational autoencoders (Kingma & Welling, 2014), where a sample's weight corresponds the probability that f(x) is greater than quantile cutoff under an noise
5

---

Published as a conference paper at ICLR 2020
model (Brookes & Listgarten 2018). In Brookes et al. (2019b), pe(x)) is further restricted to stay close to a prior distribution over sequences.
An alternative approach for optimizing the above expectation is RL. While RL has been used for generating natural text (Bahdanau et al. 2016), small molecules (Zhou et al.) 2019), and RNA se- quences that fold into particular structure (Runge al. 2018), are not aware of applications of RL to optimizing DNA and protein sequences.
DyNA PPO is related existing work model-based RL for sample efficient control (Deisenroth & Rasmussen 2011 Kurutach et al., 2018 Peng et al. 2018 Kaiser et al. 2019) Janner et al. 2019), with the key difference that the state transition function is known and the reward function is unknown in our work, whereas most existing model-bate based RL approaches seek to model the state-transition function and consider the reward function as known.
Prior work on sequence generation incorporates non-differentiable rewards, like BLEU in machine translation, via weighted maximum likelihood (MLE). Norouzi al. (2016) introduce reward aug- mented MLE, while Bahdannu et al. (2016) fine tune an MLE-pretraing
model using actor-critiy methods. Reinforcement learning has also been applied to solving combinatorial optimization prob-
lems (Bello et al. 2016 Bengio et al. 2018 Dai et al.) 2017 Kool et al. 2018). In this setting sample complexity is less important because evaluating
(x] only involves a fast software program.
Recent work has proposed generative models of protein structures (Sabban & Markovsky 2019) or generative models of amino acids conditional on protein structure (Ingraham et al. 2019). Such methods are outside of the scope of this paper's experiments, since they could only be used in experimental settings where protein structures, which are expensive to measure, are available.
Finally, DNA and protein design differs from small molecule design Griffftts & Hernández- 2017| Kusner et al.] [2017] Bombbellll et al. 2018 Jin et al., 2018;; Sanchez- Samchez-Lengeling & Aspuru-Guziky 2018 Korovina al. 2019) in the following points: (i) the number of sequences measured in parallel in the lab is typically higher (hundred or thousands vs. dozens) due to the maturity of DNA synthesis and sequencing technology. (ii) the search space
set of sequences instead of molecular graphs, which require specialized network architectures for both discriminative and generative models, and (iii) molecules must be optimized subject to the constraint that there is set of reactions to synthesize them, whereas practically all DNA or protein sequences are synthesiz- able.
4 EXPERIMENTS
In the next three sections, compare DyNA PPO to existing methods on three in-silico optimiza- tion problems that we designed in collaboration with life scientists to faithfully simulate the behavior of real wet-lab experiments, which would be cost prohibitive for comprehensive methodological evaluation. Along the way, we present ablation experiments to help to better understand the behavior of DyNA PPO.
We compare the performance of model-free policy optimization (PPO) and model-based optimiza- tion (DyNA PPO) with the following methods that discussed in Section Further details for each method can be found in Appendix A
RegEvolution: Local search based regularized evolution (Real al. 2019). which has performed well on other black-box optimization tasks and can be seen as an instance of directed evolution.
DbAs: Cross-entropy optimization using variational autoencoders (Brookes Listgarten 2018).
FBGAN: Cross entropy optimization using generative adversarial networks (Gupta & Zou 2018).
Bayesopt GP: Bayesian optimization using Gaussian process regressor and activation maximization as acquisition function solver.
Bayesopt ENN Bayesian optimization using an ensemble of neural network regressors and activation maximization acquisition function solver.

---

Published as a conference paper at ICLR 2020
Random: Guessing sequences uniformly at random.
We quantify optimization performance by the cumulative maximum reward f(x:) for sequences pro- posed up to a given round, and we use the area under the cumulative maximum reward curve to summarize one optimization trajectory tion 2.4) in terms of the mean pairwise hamming distance between the sequences proposed at each round. For problems with known optima, we also report the fraction of global optima found. We replicate experiments with 50 random seeds.
single number. We quantify sequence diversity (Sec-
4.1
OPTIMIZATION OF PROTEIN CONTACT ISING MODELS
2.7
Jetbnw
1.4
1.3
4000
6000
8000
10000
LAM8
LAGH
1ERU
1120
2033
Number Samples
Figure 1: Comparison of methods on optimizing the energy of protein contact Ising models. Left: the cu- mulative maximum reward depending on the number of rounds for one selected protein target (1A3N). Right: the mean cumulative maximum relative to Random for alternative protein targets. Since f(x) can be well- approximated by model trained few examples, model-hased training (DyNA PPO) results in clear im- provement over model-fi free training (PPO).
0.9
Cumuisave moximum
166
-44
32
rounds
rounds
rounds
0.6
26
rounds
rounds
24
rounds
1000
2000
3000
samples
4000
5000
6000
7000 9000 10000 Number samples
Figure 2: Analysis of the performance of DyNA PPO on the Ising model. Left: Performance of DyNA PPO depending the number of inner policy optimization rounds using the surrogate model. Using 0 rounds corresponds PPO training. Since the surrogate model sufficiently accurate, it is useful perform many inner loop optimization rounds before querying f(x) again. Right: R² the surrogate model. Since always above the threshold for model-based training (0.5; dashed line). it is always used for training.
We first consider synthetic black-box optimization problems based on the 3D structure of naturally- occurring proteins. Ising models fit on sets of evolutionary-related protein sequences have been shown to be accurate predictors for proteins' 3D structure (Shakhnovich & Gutin 1993 Weigt et al.) 2009 Marks al., 2011 [Sutkowska et al. 2012). We consider the inverse problem: given a protein, scek to find the amino acid sequence that minimizes the energy of the Ising model parameterized by its structure. Optimizers are given a budget of rounds with batch size 1000 and we consider sequences of length 50 (search space size 20) The functional form of the energy function given in Appendix B.I
On the left of Figure I we consider the optimization trajectory for representative protein and the right we compare the best fx) found for each method across range of proteins. We find that DyNA PPO considerably outperforms the other methods. We expect that this is because this synthetic

---

Published as a conference paper at ICLR 2020
reward landscape be well-described by model fit using few examples, which also explains the good performance of Bayesian optimization. On the left of Figure 2 we vary the number of inner-loop policy optimization rounds with observations from the model-based environment, where using 0 rounds corresponds to performing standard PPO. Since the surrogate model is of sufficient accuracy already the beginning (right plot), performing more inner policy optimization rounds increases performance and enables DyNA PPO to generate high-quality sequences using very few evaluations of (x).
4.2
OPTIMIZATION OF TRANSCRIPTION FACTOR BINDING SITES
DyNA PPO
PPD
Bayesopt.co GP
DbΛs
RegEvolution
FBGN
Random
0.7
0.6
Cumulative maximum
Fraction of optima found
0.5
0.7
0.4
0.6
0.3
0.5
0.2
0.4
0.1
0.3
0.0
200
400
600
800
1000
Number samples
Number samples
Figure 3: Comparison of methods on optimization transcription factor binding sites. Left: maximum cumulative reward f(z) as function of samples. Right: fraction of local optima found. DyNA PPO optimizes [(x) faster finds more optima than PPO and baseline methods. Results are shown for one representative transcription factor target (SIX6 REF R1).
DyNA PPO
PPO
BO-GP
DbAs
RegEvol
FBGAN
Random
Cumulative maximum
6.4
5.8
5.0
3.7
3.7
2.2
I.3
Fraction optima found
6.8
5.6
5.4
3.3
3,3
2.5
1.0
Mean hamming distance
5.6
5.4
4.0
2.5
1.0
2.5
7.0
Table I: Mean rank of methods across transcription factor binding targets. Mean rank of methods across 41 hold-out transcription factor targets. Ranks were computed within each target using the average of metrics across optimization rounds, and then averaged across target. The higher the rank the better. 7 is the maximum rank. DyNA PPO outperforms the other methods on both optimization of /' (z) and its ability to identify multiple well-separated local optima.
Transcription factors are protein sequences that bind to DNA sequences and regulate their activ- ity. [Barrera al. (2016) measured the binding affinity of numerous transcription factors against all possible length-8 8 DNA sequences (V 4). The resulting dataset defines 158 different discrete opti- mization tasks, where the goal of each task is to find DNA sequence of length eight that maximizes the affinity towards one of the transcription factors. It is well suited for in-silico benchmarking since () it is exhaustive and thereby does not require estimating missing fxx and (ii) the distinct local optima of all tasks are known and can be used to quantify exploration (see Appendix B for details).
The optimization methods are given budget of 10 rounds with batch size of B 100 sequences. The search space size is 48, We use one task (CRX REF R1) for optimizing the hyper-paranee paraaetaraeeters of all methods, and test performance on 41 heterogeneous hold-out tasks.
Figure plots the performance of methods on single representative binding target (SIX REF R1) as a function the total number of sequences measured so far. We find that DyNA PPO and PPO outperform all other methods in terms of both the cumulative maximum f(x) found well as the fraction of local optima discovered. We also find that the diversity of proposed sequences quantified by the fraction of global optima found is high compared to other generative approaches. This shows that our method continues to explore the search space by proposing novel sequences instead of converging single sequence handful of sequences-a desired property as discussed
8

---

Published as a conference paper at ICLR 2020
0.7
Freduercy mode baood traiting
00.8
Model sc0m
0.5
0..6
0.2
0.0
500 500
200
Number
Figure 4: Analysis of the progression model-based training on transcription factor task. Left: mean Hf model score averaged across replicas as a function of the number of training samples. The horizontal dashed line indicates the minimum threshold (0.5) for model-based training. Right: the fraction of replicates that performed model-based training based on this threshold. Shows that models tend to be inaccurate in early rounds and are therefore used for model-based training. This explains the relatively small improvement of DyNA PPO over PPO in Figure
Proposed exploration bonus
Entropy regularization
0.8
0.0
Foadien ontim Deure
Prrtiinn @stima Souive
0.5
0.5
0.4
0.4
0,3
0.3
0.1
0.1
1000
1500
2000
2500
3000
1000
1500
2000
2500
3000
samples
3.0
1.0
Penalty
Entropy
Mean parrens hammih ditance
0.075'
Wean parrege Tamming disance
0.8
0.6
0.6
0.6
0.4
0.4
500
1000
1500
2000
2500
3000
500
1000
1500
2000
2500
3000
Figure 5: Comparison of the proposed exploration bonus vs. entropy regularization the transcription factor task. Left: performance with exploration bonus as a function the density penalty (Section 2.4 Right: performance of entropy regularization as a function of the regularization strength. The top row shows that PPO finds about 80% of local optima with relatively mild density penalty of X = 0.1, whereas only about 45% local optima found when using entropy regularization. The bottom shows that varying the density penalty enables control sequence diversity quantified by the mean pairwise hamming distance between sequences.
in Section 2.4 Across all tasks DyNA PPO and PPO rank highest compared with other methods (Table D.
In Figure and we analyze the effects two key design decisions of DyNA PPO: model-based train- ing and promoting exploration. We find that automated model selection automatically increases the complexity of the model, but that the models are not always accurate enough to used for model- based training. This explains the relatively small improvement of DyNA PPO PPO. We also find that the exploration bonus outlined Section 2.4 is more effective than entropy regularization in finding multiple local optima and promoting sequence diversity.

---

Published as a conference paper at ICLR 2020
4.3 OPTIMIZATION OF ANTI-MICROBIAL PEPTIDES
Next, we seek to design antimicrobial peptides (AMPs), AMPs are relatively short (8 75 amino acids) protein sequences (VV) 20 amino acids), which are promising candidates against multi- resistant pathogens due to their wide range of antimicrobial activities. We use the dataset proposed by by[Witten& & Witten (2019), which contains 6,760 unique AMP sequences and their antimicrobial ac- tivity towards multiple pathogens. We follow Witten & Witten (2019) for preprocessing the dataset and generating non-AMP sequences as negative training samples. Unlike the transcription factor binding site dataset, we do not have wet-lab experiments for every sequence in the search space. Therefore, we fit random forest classifiers to predict if sequence is antimicrobial towards a certain pathogen in the dataset (see Section B.3) and use the predicted probability as the functional mea- surement (x) to optimize. Given the high accuracy of the classifiers (cross-validated AUC 0.94 and 0.99), we expect that the reward landscape of f(x) is of realistic diffieulty. We perform 8 rounds with a batch size 250 and restrict the sequence length to at most 50 characters (search space size 2030).
DyNA PPO
PPG
Beyesopt ENN
DbAs
RegEvolution
FSGAN
Random
0.9
Mean pairwise hamming distance
Cumulstiv maximum
0.6
0.7
0.5
0.6
0.4
0.5
0.3
0.4
0.2
0.1
1250 1500 Number samples
500
750
1250 1500
Number samples
Figure 6: Comparison of methods the AMP design task. Left: Modcl-based training using DyNA PPO and model-free PPO clearly outperform the other methods terms of the maximum cumulative reward. Right: The mean pairwise hamming distance between sequences proposed at cach round, which is lower for DyNA PPO and PPO but does not converge to zero due to the density-based exploration bonus (Figure IT.
Figure 6 compares methods on C. alibicani. We find that model-based optimization using DyNA PPO enables finding high reward sequences in early rounds, though model-free PPO slightly sur- passes the performance of DyNA PPO later on. Both DyNA PPO and PPO considerably outperform the other methods in terms of the maximum [() found. The density based exploration bonus prevents PPO and DyNA PPO from generating non-unique sequences (Figure III. Stopping model- based training as soon as the model uncertainty increased by certain factor prevents DyNA PPO from converging to sub-optimal solution when performing many model-based optimization rounds (Figure 13
CONCLUSION
We have shown that RL is an attractive alternative to existing methods for designing DNA and protein sequences. We have proposed DyNA PPO, model-based extension of PPO (Schulman et al., (017) with automatic model selection that improves sample efficiency, and incorporates reward function that promotes exploration by penalizing identical sequences. By approximating an expensive wet-lab experiment with surrogate model, we perform many rounds of optimization in simulation. While this work has been focused on showing the benefit of DyNA PPO for biological sequence design, we believe that the large-batch, low-round optimization setting described here may well be of general interest, and that model- -ased RL may be applicable in other scientific and economic domain.
10

---

Published as a conference paper at ICLR 2020
REFERENCES
Frances H Arnold. Design by directed evolution. Accounts of chemical research, 315)1125-131,
1998.
Dzmitry Bahdanau, Philemon Brakel, Kelvin Xu, Anirudh Goyal, Ryan Lowe, Joelle Pineau, Aaron Courville, and Yoshua Bengio. An actor-critic algorithm for sequence prediction, 2016.
Luis A. Barrera, Anastasia Vedenko, Jesse V. Kurland, Julia M. Rogers, Stephen S. Gisselbrecht, Elizabeth J. Rossin, Jaie Woodard, Luca Mariani, Kian Hong Kock, Sachi Inukai, Trevor Sig- gers, Leila Shokri, Raluca Gordān, Nidhi Sahni, Chris Cotsapas, Tong Hao, Song Yi, Mano- lis Kellis, Mark J. Daly, Mare Vidal, David E. Hill, and Martha L. Bulyk. Survey of vari- ation in human transcription factors reveals prevalent DNA binding changes. Science, 351 (2280):1450-1433 2016. ISSN 0036-8075.
doi: 10. 10.1126/science.aadieeo 7 //science. sc www.:ieeeiiinneeag.ccoo wwwnemaag.oogoo wwnttnttttt//.cc wtt..///..oooeon///////////3 02/0///11/620/111 02//6/2201155
URL. https:
Mare G. Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos. Unifying count-based exploration and intrinsic motivation, 2016.
Mare G Bellemare, Will Dabney, and Rémi Munos. distributional perspective on reinforcement learning. In Proceedings of the 34th International Conference Machine Coarning-Volumme 70, pp. 449-458. JMLR.org, 2017.
Irwan Bello, Hieu Pham, Quoe V. Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning, 2016.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimiza- tion: a methodological tour d' d'horizon, 2018
Helen M Berman, Philip Bourne, John Westbrook, and Christine Zardecki. The protein data bank. In Protein Structure, pp. 394-410. CRC Press, 2003.
David H Brookes and Jennifer Listgarten. arXiv:1810.03714. 2018
Design by adaptive sampling. arXiv preprint
David Brookes, Akosua Busia, Clara Fannjiang, Kevin Murphy, and Jennifer Listgarten. view of estimation of distribution algorithms through the lens of expectation expectation-maximiie maximization, 2019a.
David H Brookes, Hahnbeom Park, and Jennifer Listgarten. Conditioning by adaptive sampling for robust design. arXiv preprint urXiv: 10060, 2019b.
Prabal Chhibbar and Arpit Joshi. Generating protein sequences from antibiotic resistance genes data using generative adversarial networks. arXiv preprint arXiv:1904.132444 2019.
Hanjun Dai, Elias B. Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs, 2017.
Pieter-Tjerk De Boer, Dirk P Kroese, Shie Mannor, and Reuven Rubinstein. tutorial on the cross-entropy method. Annals of operations research, 134(1):19-67, 2005.
Ronald PH de Jongh, Aalt DJ van Dijk, Mattijs K Julsing, Peter J Schaap, and Dick de Ridder. De- signing eukaryotic gene expression regulation using machine learning. Trends in biotechnology. 2019.
Mare Deisenroth and Carl E Rasmussen. Pilco: A model-basee and data-efficient approach to policy search. In Proceedings of the 28th International Conference on machine learning (ICML-11), pp. 465 201
Rafael
Jennifer N Wei, David Duvenaud, José Miguel Hernández-Lobate Benjamín Sánchez- Lengeling Dennis Sheberla, Jorge Iparlere-, Timothy D Hirzel, Ryan P. Adams, and Alán Aspuru-Guzik. Automatic chemical design using data-driven contin- uous representation of molecules. ACS central science, 4(2):268-2) 276, 2018.
Ryan-Rhys Griffiths and José Miguel Hernández- Constrained Bayesian optimization for automatic chemical design. arXiv preprint 1709:0/70000500// 2017.

---

Published as a conference paper at ICLR 2020
Sergio Guadarrama, Anoop Korattikara, Oscar Ramirez, Pablo Castro, Ethan Holly, Sam Fishman, Ke Wang, Ekaterina Gonina, Neal Wu, Chris Harris, Vincent Vanhoucke, and Eugene Brevdo. TF-Agents: A library for reinforcement learning in tensorflow. https: /ttps://github. com/ wtt.uuu...commttttoofooooooo agent.s 2018. URL http://s/sssstacccccc////ooosof/ [Online; accessed 25-June-2019).
Anvita Gupta and James Zou. Feedback gan (fbgan) for dna: novel feedback-loop architecture for optimizing protein functions. arXiv preprint arXiv:1804.0I1 2018.
Tatsunori B. Hashimoto, Steve Yadlowsky, and John C. Duchi. Derivative free optimization via
repeated classification, 2018.
John Ingraham, Vikas K Garg, Regina Barzilay, and Tommi Jaakkola. Generative models for graph- based protein design. 2019.
Michael Janner, Justin Fu, Marvin Zhang, and Sergey Levine. When to trust your model: Model- 2019.
based policy optimization. arXiv preprint
Wengong Jin, Kevin Yang. Regina Barzilay, and Tommi Jaakkola. Learning multimodal graph-to- graph translation for molecular optimization. arXiv preprint arXiv:1812.0111 010000 2018.
Lukasz Kaiser, Mohammad Babaeizadeh, Piotr Milos, Blazej Osinski, Roy H Campbell, Konrad Czechowski, Dumitru Erhan, Chelsea Finn, Piotr Kozakowski, Sergey Levine, et al. Model-based reinforcement learning for atari. arXiv preprint arXiv: 100:::99300055. 2019.
Nathan Killoran, Leo J Lee, Andrew Delong, David Duvenaud, and Brendan Frey. Generating and designing dna with deep generative models. arXiv preprint arXiv: 2017.
Diederik P. Kingma and Max Welling. Auto-encoding variational bayes. In 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014. (tL/httpp//arxi// wwtrxivv.rgr/ae.. www/abs/////ooooooroo..o/...eeaa 1312. 6114
Scott Kirkpatrick, Daniel Gelatt, and Mario Vecchi. Optimization by simulated annealing. science, 220(4598):671-688 1983.
Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In ICLR, 2018
Ksenia Korovina, Sailun Xu, Kirthevasan Kandasamy, Willie Neiswanger, Barnabas Poczos, Jeff Schneider, and Bric P Xing. ChemBO: Bayesian Optimization of Small Organic Molecules with Synthesizable Recommendations. arXiv preprint arXiv: 011./9908.11199 2019.
Thanard Kurutach, Ignasi Clavera, Yan Duan, Aviv Tamar, and Pieter Abbeel. Model-ensemble trust-region policy optimization. arXiv preprint arXiv:1802.10559, 2018
Matt Kusner, Brooks Paige, and José Miguel Hernández-Lobato Grammar variational autoen- coder. In Proceedings of the 34th International Conference on Machine Learning- -oarning-VVoluee 70, pp. 1945-1954. JMLR. org, 2017.
Ge Liu, Haoyang Zeng. Jonas Mueller, Brandon Carter, Ziheng Wang, Jonas Schilz, Geraldine Horny, Michael E Birnbaum, Stefan Ewert, and David K Gifford. Antibody complementarity determining region design using high-capacity machine learning. bioRxiv, pp. 682880, 2019.
Debora S Marks, Lucy J Colwell, Robert Sheridan, Thomas A Hopf, Andrea Pagnani, Riccardo Zecchina. and Chris Sander. Protein 3d structure computed from evolutionary sequence variation. PioS one, 6(12):228666, 2011.
Sanzo Miyazawa and Robert I. Jernigan Residue-residue potentials with favorable contact pair term and an unfavorable high packing density term, for simulation and threading. Journal of molecular biology, 256(3):623-644 1996.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529, 2015.
12

---

Published as a conference paper at ICLR 2020
J. Mockus, Vytautas Tiesis, and Antanas Zilinskas. The application of Bayesian methods for seeking the extremum. Towards Global Optimization, 2:117-129, 09 2014.
Alexander Mordvintsev, Christopher Olah, and Mike Tyka. Deepdream-a code example for visual- izing neural networks. Google Research, 2(5), 2015.
Daniel Neil, Marwin Segler, Laura Guasch, Mohamed Ahmed, Dean Plumbley, Matthew Sellwood, and Nathan Brown. Exploring deep recurrent models with reinforcement learning for molecule design. In International Conference on Learning Representations Workshop, 2018.
Mohammad Norouzi, Samy Bengio, Navdeep Jaitly, Mike Schuster, Yonghui Wu, Dale Schuurmans, et al. Reward augmented maximum likelihood for neural structured prediction. In Advances In Neural Information Processing Systems, pp. 1723-1731, 2016.
Pedregosa, G. Varoquaux, Gramfort, V. Michel, Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Couraaeeau M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning Python. Journal of Machine Learning Research, 12:2825-2830 2011.
Baolin Peng, Xiujun Li, Jianfeng Gao, Jingjing Liu, Kam-Fai Wong, and Shang-Yu Yu Su. Deep dyna-q: Integrating planning for task-completion dialogue policy learning. arXiv preprint 2018.
arXfv:1801.06116, 2018.
Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc V Le. Regularized evolution for image classifier architecture search. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4780 4789, 2019.
Frederic Runge, Danny Stoll, Stefan Falkner, and Frank Hutter. Learning to design ma, 2018.
Sari Sabban and Mikhail Markovsky. Ramanet: Computational de novo protein design using long short-term memory generative adversarial neural network. BioRxiv, pp. 671552 2019.
Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Ilya Sutskever. Evolution strategies as a scalable alternative reinforcement learning. arXiv preprint arXivv:703.. 03864, 2017.
Paul Sample, Ban Wang. David W Reid, Vlad Presnyak, lain J McFadyen, David R Morris, and Georg Seelig. Human utr design and variant effect prediction from a massively parallel transla- tion assay. Nature biotechnology. 37(7):803, 2019.
Benjamin Sanchez-Lengeling and Alán Aspuru-Guzit Inverse molecular design using machine learning: Generative models for matter engineering. Science, 36 361(6400):360-365 2018.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford. and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint vrXiv:1707.06344 2017.
Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan P Adams, and Nando De Freitas. Taking the human out of the loop: A review of Bayesian optimization. Proceedings of the IEEE, 104(1): 148-175, 2015.
Eugene Shakhnovich and AM Gutin. A new approach to the design of stable proteins. Protein Engineering, Design and Selection, 688):793-80, 1993.
Jasper Snoek, Hugo Larochelle, and Ryan P Adams. Practical bayesian optimization of machine learning algorithms. In Advances in neural information processing systems, pp. 2951-2959, 2012.
Joe Staines and David Barber. Optimization by variational bounding. In ESANN, 2013.
Joanna Sulkowska, Faruck Morcos, Martin Weigt, Terence Hwa, and José Onuchic, Genomics- aided structure prediction. Proceedings of the National Academy of Sciences, 109(26):10300- 10345, 2012.
Richard S Sutton. Dyna, an integrated architecture for learning, planning, and reacting. ACM Sigart Bulletin, 164) 1991.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
13

---

Published as a conference paper at ICLR 2020
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 59985-998,, 2017.
Ye Wang, Haochen Wang, Liyang Liu, and Xiaowo Wang. Synthetic promoter design in escherichia coli based on generative adversarial network. BioRxiv, pp. 563775, 2019.
Martin Weigt, Robert A White, Hendrik Szurmant, James A Hoch, and Terence Hwa. Identification of direct residue contacts National Academy of Sciences, 106(1):67-72, 2009.
interaction by message passing. Proceedings of the
Daan Wierstra, Tom Schaul, Tobias Glasmachers, Yi Sun, Jan Peters, and Jürgen Schmidhuber. Natural evolution strategies. The Journal of Machine Learning Research, 15(1): (5(1):949-999) 980, 2014.
Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning, Machine learning, 8(3-4))229-256, 1992.
Jacob Witten and Zack Witten. Deep learning regression model for antimicrobial peptide design.
BioRxiv, pp. 692681, 2019.
Zachary Wu, SB Jennifer Kan, Russell D Lewis, Bruce J Wittmann, and Frances H Arnold. Ma- chine learning- assisted directed protein evolution with combinatorial libraries. Proceedings of the National Academy of Sciences, 116((8):888)) 0888885228888,,, 2019.
Zhenpeng Zhou, Steven Kearne,, Li Li. Richard N Zare, and Patrick Riley. Optimization of molecules via deep reinforcement learning. Scientific reports, 9(1):10752, 2019.
14

---

Published as a conference paper at ICLR 2020
A IMPLEMENTATION DETAILS
A.1 REGULARIZED EVOLUTION
Regularized evolution variant of directed evolution that regularizes the search by keeping fixed number of individuals alive as candidates for selection (analogous to death by aging). At each round, it generates batch of child sequences by sampling from the population via tournament selection, i.. selecting the fittest out of K randomly sampled individuals. then performs crossover of the two parent sequences by copying the characters of one parent from left to right and randomly transitioning to transcribing from the other parent sequence with some crossover probability at each step. Child sequences are mutated by substituting characters independently by other characters with some substitution probability. For variable-length sequences, we also allowed insertion and deletion mutations. As hyper-parameters, we tune the tournament size, substitution-, insertion-, and celetion-probabiiie
parent sequences per child
A.2 MCMC AND SIMULATED ANNEALING
MCMC and simulated annealing (Kirkpatrick et al., 1983) resemble evolution with no crossover, and selection only occurring between an individual and its parent. Beginning with a random popula- tion, each individual evolves single chain, with neighborhood structure defined by the mutation operator described section A. We denote x and x' as a parent and child sequence, respectively. A transition x - z' is always accepted if the reward increases (f(x') f(z)). Otherwise. the transition accepted with some acceptance probability. For MCMC, the acceptance probability is (x)) while for simulated annealing is exp((f(x') (()))/T) for some temperature T. A high temperature increases the likelihood of accepting a move that decreases the reward. The next mutation on the chain begins from x if the transition rejected, and from x' otherwise. We treated the temperature T as tunable described in section A.1
in addition to the evolution hyper-parameters
A.3 FEEDBACK GAN
We follow the methodology suggested by Gupta & Zou 2018). Instead of using constant threshold for selecting positive sequences as described in the original publication, we used a quantile cutoff, which does not depend on the absolute scale of f() and performed better our experiments. As syper-parameters, we tuned the quantile cutoff, learning rate, batch size, discriminator and generator training epochs, the gradient penalty weight, the Gumble softmax temperature, and the number of latent variables of the generator.
A.4 DBAS
We follow the methodology suggested by Brookes & Listgarten 2018 As hyper-parameters, we optimized the quantile for selecting training samples, learning rate, batch size, training epochs, number of hidden units of the MLP generator and discriminator, and number of latent variables. The generative model an variational autoencoder with a multi-layer perceptron decoder. We also considered DbAs with LSTM as generative model, which performed slightly better than a VAE on the TfBind8 problem but worse on the Publsing and AMP problem (see Figure B).
A.5 BAYESIAN OPTIMIZATION
As regressors, we considered Gaussian process (GP) with RBF kernel on one-hot features, and an ensemble of ten fully-connected neural networks with one fully connected layer and 128 hidden units. We used the regressor output to compute the expected improvement or posterior mean acqui- sition function, which we maximized by gradient ascent for certain number of acquisition steps following Killoran et al. (2017). We took the resulting B unique sequences with highest acquisition function value as sequences to measure in the next round. We tuned the length scale and variance of the RBF kernel, and the learning rate, batch size, and number of training epochs of the neural net- work ensemble. We further tuned the number of gradient ascent steps for activation maximization.
15

---

Published as a conference paper at ICLR 2020
A.6 PPO AND DYNA PPO
We used the PPO implementation of the TT-Agents RL library (Guadarrama et al. 2018). After each round, trained trained the agent on the collected batch of sequences for relatively high number of steps (about 72) since it resulted in a performance mereasee compared with performing only single training step. We used the adaptive KL trust region penalty, which performed slightly better than importance ratio clipping in our experiments Schulman et al. (2017). We used policy and value network with one fully connected layer and 128 hidden units. Both networks take the current position and the W last generated characters as input, which we padded at the beginning of the sequence. We set the context window to the minimum of the total sequence length and 50, As hyper-parameters, we tuned the learning rate, number of training steps, adaptive KL target, and entropy regularization. For DyNA PPO, we also tuned the maximum number of model-based optimization rounds M (see Section 2.3
A.7 AUTOMATED MODEL SELECTION
Automatic model selection optimizes the hyper-parameters of a set of candidate models by random- ized search, and evaluates each sapee--arameter configuration by five-fold vols-vvaiiation using the R² score. To account for randomness in the R² score between models due to different cross- validation splits, we used the same split for evaluating each the models per round. We considered the following candidate models (implemented in Scikit-learn (Pedregosa et al. 201I and corre- sponding prperpparameters:
KNeighborsRegrrssoor neighbors
BayesianRidge: alpha_1, alpha lambda_1, lamdha_2
RandomFooresRRerressor mex_depth, max_features, n-estimators
ExtrrarreeRRorresso:: max depth, max features, estimators
GradientBoostinnReggrssor learning_rate, max_depth, n_estimators
GrussinnProessRRgreesoor with RBF, RationalQuadrattcc and Matern kernel
We also considered an ensemble of neural networks with two convolutional layers and one fully connected layer, and optimized the learning rate and number of training epochs.
B DATASET DETAILS
B.1 PROTHIN CONTACT ISING MODELS
Given a protein from the Protein Data Bank (Berman al. 2003 we compute the energy E(x) for sequence x (xx) Σ, (x,)) + Eig Cijo(z;,Zz)) where x; refers the character in the i-th position of sequence Cij is an indicator for whether the Ca atoms of the residues at positions and j are separated by less than Angstroms when the protein folds. d(I;, 2y) is a widely-used 'pair potential' based on co-occurence probabilities derived from the structures of real-world proteins MMiyazawa & Jernigan, 1996). The same 20 x 20 table of pair potentials is used at all positions in the sequence, and thus the difference in energy functions across proteins is dictated only by their differing contact map structure. We set the local term (x,),) to zero. In future work, would be interesting to consider non-zero local terms.
Our experiments consider a set of qualitatieely-diffeenntt proteins listed at the bottom-right of Fig- D We identify the local optima using the same procedure in Section B.2 except without accounting for reverse complements.
B.2 TRANSCRIPTION FACTOR BINDING SITE DATASET
We used the dataset described by Barrera et al. 2016), and min-max normalized binding affinities between zero and one. To reduce computational costs, only considered the first replicate (REF RI) of each wild type transcription factor in the dataset, which resulted in 41 optimization targets that used for comparing optimizers described in Section 4.2 We extracted local optima for
16

---

Published as a conference paper at ICLR 2020
each binding target as follows. First, separated sequences into forward and reverse sequences by ordering sequences lexicographically and including each sequence in the set of forward sequences unless the set already contained its reverse complement. We then chose the 100 forward sequences with the highest binding affinity and clustered them using the hamming distance metric, where we determined the number of clusters by finding the number of PCA components required to explain 95% of variance. We then used the sequences with the highest reward per cluster and their reverse complement local optima.
B.3 ANITMICROBIAL PEPTIDE DATASET
We downloaded the datase provided by Witten & Witten 2019), and followed the paper for prepro- cessing sequences and generating non AMP sequences as negative training samples. We addition- ally excluded sequences containing cysteine and sequences shorter than 15 or longer than 50 amino acids. We fit one classifier to predict if sequence is antimicrobial towards either E.coli, S.aureus, Paeruginosa, B.subtilis, which we used for hyper-parameter tuning, and second classifier for C. alibicani, which we used for hold-out evaluation. We used C. alibicani as hold-out target since its antimicrobial activity
least correlated with the activity of other pathogenes in the dataset with more than 1000 AMP sequences. We used random forest classifiers since they were more accurate validae AUC 0.99 and 0.94) than alternative models such k-nearest neighbors, Gaussian processes, or neural networks. Since sequences are variable-length, we padded them to the maxi- mum sequence length of 50 and extended the vocabulary by an additional end of sequence token. Tokens after the fist end of sequence token were ignored when evaluating f(x).
Pept des
17

---

Published as a conference paper at ICLR 2020
C COMPARISION OF RL METHODS
TF Bind
Protein Ising
AMP
0.5
19
2.7
Op TorreRDive
PD
X
CWROW
Cabqy
fumber samplec
Numbor of samples
Buntoo of oisampicy
3.0
0.8
05
0.4
Muthol RD
Mathod
Mathol
0.3
D08
D05
005
92
400
4337
B000
232
1000
1230
1590
Figure 7: Comparison of PPO against alternative RL methods. Shown are the cumulative maximum reward and pairwise hamming distance for the transcription factoring binding, protein Ising, and AMP problem (Section
DyNA PPO is built on PPO, which we have found to outperform other policy-based and value-based
RL methods practice our problems. Figure 7 we contrast the performance of PPO (Schul-
man et al. 2017). REINFORCE (Williams) 1992), deep Q-learning (DQN) (Mnih et al. 2013). and
categorical distributional deep Q-learning (CatDON) (Bellemare et al.) 2017) on all problems con- sidered in Section 4 We find that PPO has better exploration properties than REINFORCE, which
DQN and CatDQN can be explained by the sparse reward (the reward is only non-zero at the terminal state), such that the Bellman error and training loss for updating the Q network are zero in most states. We also found the performance of DQN and CatDQN to be sensitive to the choice of the epsilon greedy rate and Boltzmann temperature for trading-of off exploration and exploitation and increasing diversity.
tends converge too soon to a local optimum. The poor performance
18

---

Published as a conference paper at ICLR 2020
D COMPARISON OF ADDITIONAL BASELINES
Bind
Protein Ising
AMP
0.0
g0.45
1.5
3.4
233
500
EC0
312
3000
2037
600
1560
6722
30000
237
307
752
1000
1220
1399
1799
2038
Nimber
0.
1.2
surppha
Narber Cimplen
Numser SEmpIIA
Method
Random
RegEvoluttor
MCMC
MCMC-SA
DaAs VAE
DMAs RNN
Figure 8: Comparison of additional baselines. We consider the performance of optimizers based on MCMC (Section A.2 Such methods are known to be effective optimizers when evaluating the black-box function inexpensive. and thus many iterations of sampling resource-constrained blx optimization. We find that their low sample efficiency makes them undesirable for biological sequence design. also consider DbAS with a LSTM generative model instcad of a VAE with multi-layer perceptron decoder to disentangle the choice of generative model in DbAS from the overall optimization strategy. DbAs VAE outperforms DbAs RNN on all problems except for TF bind.
be performed. The focus of experiments
19

---

Published as a conference paper at ICLR 2020
E ANALYSIS OF THE EXPLORATION BONUS
Deruty perstt
ponult
6-3
5-3
3.0
0-
0.5
1.5
8.69
0.2
6.'
6.5
6.4
1007
1300
2503
1000
3222
320
1530
3000
2500
3023
of camples
Numterrd of SaRak
Benkerr
0.9
6.8
6.09
6."
08
8.7
6.7
3.7
2.4
64
Sumber com Mi
Number of campees
Numrer camo
3.0
Ditarce
2.5
8.5"
Meat parrea hamrer
6-4
Sumber of samppee pine
Number of cample
1.0
Derdty persby
Custicee penshl
Energgy peralt
6.8
0.0
3.5
8.0
0.2
6/
6.5
1722
1300
2000 2097
322
1033
1355 2000
5250
503
1933
2000
2300
3932
Figure 9: Comparison of alternative approaches for promoting diversity. Left column: The proposed density based exploration bonus described in Section 2.4 which adds penalty the reward of sequence x that is proportional to the distance-weighted number of past sequence that are less than specified distance away from x (here edit distance one). Middle column: An alternative approach where the exploration honus of sequence is proportional to the distance to the nearest neighboring past sequence. Right column: standard entropy regularization. Shown diversity depending on the penalty strength
the cumulative maximum reward and alternative metrics for quantifying Section(..4 each exploration approach. Without exploration bonus (penalty = 0.0; red line), PPO docs not find the optimum (cumulative maximum is below 1.0) and the hamming distance and uniqueness of sequences within batch converge to zero. PPO finds the optimal solutions and continues generate diverse sequences increasing the strength of any of the three exploration approaches. The density based exploration bonus most effective in recovering all optima (second row, left plot) and enables more fine-grained control of diversity compared to distance based approach. Results are shown for target CRX REF RI of the transcription factor binding problem.
20

---

Published as a conference paper at ICLR 2020
Panubly
Punaly 0.200
Round
Round
20
10
-20
-50 -10 -20
20 20
182
Figure 10: tSNE embedding of proposed sequences with and without exploration bonus colored by the optimization round when they were proposed. Without exploration bonus (penalty 0.0), sequences cluster into few groups low diversity at different rounds. With the exploration bonus, diversity proposed sequences remain high also in later rounds. Results are shown for target CRX REF RI of the transcription factor binding problem.
2.6
0.00
2.3
0,73
Packe
730
1038
1750
252
1750
250
6.7
6.2
0.4
3.3
122
Pesils
0.4
0.00
3.0
4tep
1780
Figure 11: Analysis of basst exploration bonus on the AMP problem. The top row shows the sensitivity to the distance radius and the bottom row to the regularization strength À (Section 2.4). Diversity correlates positively with the distance radius and regularization strength. = 2 and À 0.1 provides the best trade-off hetween optimization performances (cumulative maximum reward) and diversity (mean pairwise hamming distance uniqueness). Penalizing only exact duplicates 0) is less effective maintaining high hamming distance than taking neighboring sequences into account (c > 0).
F ANALYSIS OF MODEL- MODEL-BASED BASED TRAINING
21

---

Published as a conference paper at ICLR 2020
Sid threshold = 0.5
Std threshold = 1.0
No Std threshold
0.35
9.30
0.50
2 0.30
3.2
0.20
0.35
9:30
0.20
0.20
0.35
0.50
Inner round
0.32
1sser mund
Figure 12: Analysis of model accuracy during model based training on the AMP problem. Shown are the mean absolute eтror (top row) and model uncertainty (bottom row; standard deviation) depending on the number of inner model-based optimization rounds m (X-axis; see Algorithm [ and outer optimization rounds (colors). Columns correspond different thresholds for stopping model optimization (see Section (.33 Without threshold (right column), the model error model uncertainty increase rapidly after only optimization rounds. The model uncertainty is strongly correlated with the model error (R² 0.87), and can be hence used as proxy for the unknown model error. Stopping model-based optimization as soon the the model uncertainty increases by factor of 0.5 (left column) upper-bounds the model error and prevents DyNA PPO from performing policy updates with inaccurate model predictions.
inner
0.8
0.7
2.5
0,7
6.7
E3'
1750
230
1757
300
2000
Aunberro Ginilee
Narberre camiiee
Marier CEcomase
Figure 13: Optimization performance the AMP problem depending the uncertainty threshold for stopping model-based optimization the maximum number model optimization rounds Without threshold (Inf; red line), DyNA PPO converges to a sub-optimal solution, particular when the maximum number of model-hased optimization rounds M is high. A threshold of 0.5 prevents a performance decrease due inaccuracy of the model (see Figure 12
G COMPARISON OF
SPLITTING STRATEGIES
We used the k-fold cross-validation tools scikit-learn for performing model selection. After pub- lication of the paper, we discovered that the default behavior in not shuffle the input data but to slice them into chunks based on the input ordering.
is to
When we switched to using random cross-validee validatio folds, found that the predictive accuracy of models was considerably higher than when using folds based on the data order. This led to dif- ferent models being selected, which led to slight decrease in black-box optimization performance compared to when not shuffling the input data (Figure 15).
Our data sorted in the order in which it appeared in the optimization rounds. Hence, k-fold cross-vals validation without shuffling corresponds to splitting the data approximately by rounds, which favorably selects models that generalize across rounds. This is desired since samples in the same
22

---

Published as a conference paper at ICLR 2020
TF Bind
Protein lsing
AMP
3.0
8-9
0.7
0.2
63
4.2
250
323
750
3380
1230
1500
3750 2033
samppla
Namber Siaampia
Figure 14: Sensitivity of DyNA PPO depending the choice of the minimum cross-validation masel optimization. Shown are the results for the transcription factor binding.. protein contact Ising-, and AMP problem. DyNA PPO reduces to PPO if r is above the maximum cross-validation score of models that are considered during model selection, e.g. if = 1.0. If r is too low, also inaccurate models are selected, which reduces the overall accuracy of the ensemble model and optimization performance. A cross-validation between 0.4 and 0.5 is best for all problems.
for
round tend to be correlated. It splits the data only approximately by rounds if the number of folds k not equal the number of rounds performed far.
In response, we ran experiments using true round-based split, which performed similarly to split- ting the data approximately by rounds using sklearn.mode selection. KFold KFold with shuffle=False. Based on the similar performance of these two slitting strategies, we did not change the experiments the paper.
lann
1.5
3.4
0.0
Oum 4e0e B168 mu..mmmmm
0.7
9.6
0.5
3.4
Shuffie
3.3
Figure 15: Comparison of cross-validation splitting strategies. Shown are the mean optimization trajecto- ries over 12 TfBind8 targets and 10 Protein Ising models when splitting the input data into folds with shuffling the input data (Shuffle), without shuffling the input data (NoShuffle), and splitting the input data by optimiza- tion rounds (BatchShuflle). Splitting input data approximately by rounds (NoShuffle) or exactly by rounds (BatchShuffle) results in a performance increase on Protein Ising problems compared with splitting the data randomly (Shuffle). NoShufile performs as well as BatchShuffle on TfBind8, and better than BatchShuffle and Shuffle on all Pdblsing targets.
23


Reviews:
[{"review_id": "ryxDkJqCYH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Designing new discrete sequences satisfying desirable properties is an important problem in molecular biology. This is a difficult combinatorial optimization problem because of the difficulty in optimizing over a combinatorially large space. The authors propose a RL based framework for this black box optimization problem.\n\nThe paper is well written, but I have questions about the efficacy of the method, particularly because I think some of these results are against weak baselines. For example, the authors don't compare against many better performing protein design methods (See: Ingraham et. al, GENERATIVE   MODELS   FOR   GRAPH-BASED   PROTEIN DESIGN, Sabban et. al, RamaNet: Computational De Novo Protein Design using a Long Short-Term Memory Generative Adversarial Neural Network). VAE based methods have worked well for designing sequences like SMILES strings, but the authors dismiss them claiming that they are better modelled as molecular graphs. While it could be true that molecules are better modeled as molecular graphs, it is not clear why methods that have worked well in a sequence based modeling using SMILES strings will not work for Protein Design. For AMP Design, again they compare with a weak baseline and don't compare with VAE based methods (like for example: Das et al. PepCVAE: Semi-Supervised Targeted Design of Antimicrobial Peptide Sequences)", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "rylwJMHTKH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Contribution\nThis paper apply a model-based RL algorithm, DyNA-PPO for designing biological sequences. By being model-based, this algorithm is sample efficiency compared to model-free RL algorithms. This advantage is attractive and important in the context of biological sequence design since the designed is constrained to be done in the large batch / low round settings. To further improves model efficiency, the authors reduce learning bias by quantifying the reliability and automatically selecting models of appropriate complexity via cross validation. To encourage diversity in the target distribution they also penalize the reward using a visitation-based strategy.\n\n\nClarity\nOverall, the paper is well written, well motivated and well structured. The technical content is also very clear and good.\n\n\nNovelty\nThe novelty in this work seems to be more on the applicative side (RL to optimizing DNA and protein sequences) than the method itself. I agree with the authors that most existing optimization methods are ill equipped for the large batch / low round settings and as sample efficiency becomes critically important as the number of round gets lower and their method is a good solution in such settings. \n\nThe technical novelty seems incremental as cross-validating and using a set of models under particular performance constraints does not constitutes a novel contribution. Penalizing the reward if the same sequence is seen multiple times seems decent and works well compared to the entropy regularization but it is still questionable if it is the best solution for biological sequences. Showing results when the reward is penalized using the hamming loss or the biological similarity  with previous sequences could go a long way to convince of your choice.\n\n\nExperiments:\nThe experiments are overall well presented and seems robust given the number of replicates that was made each time. \nAnalyzing the model performances across different metrics: diversity, fraction of optimals, cumulative maximum helped to  understand the method and its advantages. \n\nHowever, I would like to see other RL algorithms that were shown in the appendix for all those comparisons.\nIncluding MCMC methods in the experiments will also allow to see how RL methods compared to  the sota in bioinformatics.\nFor the Icing dataset, you mention that it is a contribution but do not provide enough details regarding it to allow further research with it.\n\nIn a real life biological setting, the data obtained at each batch will be more likely different both in term of sequences but also in term of labels. How all your method (and the others) perform with changing distribution of data from one batch to another. Ex (e.g. 0 < y batch 1 < 100, 100 <= y batch 2 < 500, etc) ?\n\nYou tried two values for R^2 in one experiment (one positive and one negative). What happens for any other positive values (e.g 0.1. 0.2, 0.3, etc) ?\n\n\nPoints of improvement\nGiven the applicative nature of the paper and the proposed method there are few small experiments that could have been done to strengthen the manuscript (see questions and comments above). \n\nPreliminary rating:\n* weak accept *", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "S1gxUQJD9B", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this work the authors propose a framework for combinatorial optimisation problems in the conditions that the measurements are expensive. The basic idea is to make an approximation of the reward function and then train the policy using the simulated environment based on the approximated reward function. The applications are shown in a set of biological tasks, which shows that the model performs well compared to the baselines. \n\nThe idea of learning the models of environment (or reward) and simulating the model to train the policy is not novel (e.g., https://arxiv.org/pdf/1903.00374.pdf). Similarly, in terms of formulating the discrete search problem as a reinforcement-learning problem, again there are similar works in the past, which are cited in the paper, but the combination of these two is novel to my knowledge; having said this the paper should discuss relevant works such as the one above. \n\nThe experiments seem convincing to me overall, however, I have the following concerns: \n\n- The performance of the model seems similar to PPO in the large state-spaces (section 4.3), which somehow is disappointing.\n\n- The performance of the model seems very sensitive to the choice of \\tau (Figure 6 right), which is set to 0.5, but it is not mentioned how this parameter is chosen (or at least I couldn’t find it) and how much the performance of the model in the other experiments is affected by the choice of this parameter.  \n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a model based proximal policy optimization reinforcement learning algorithm for designing biological sequences. The policy of for a new round is trained on data generated by a simulator. The paper presents empirical results on designing sequences for transcription factor binding sites, antimicrobial proteins, and Ising model protein structures.

Two of the reviewers are happy to accept the paper, and the third reviewer was not confident. The paper has improved significantly during the discussion period, and the authors have updated the approach as well as improved the presented results in response to comments raised by the reviewers. This is a good example of how an open review process with a long discussion period can improve the quality of accepted papers.

A new method, several nice applications, based on a combination of two ideas (simulating a model to train a policy RL method, and discrete space search as RL). This is a good addition to the ICLR literature.
Decision: Accept (Poster)