AdaLead: A simple and robust adaptive greedy search algorithm for sequence design
Authors: Sam Sinai
Richard Wang
Alexander Whatley
Stewart Slocum
Elina Locane
Eric Kelsic
Venue:  (2021)
Keywords: Black-box Optimization
Model-guided sequence design
Computational biology

Abstract: Efficient design of biological sequences will have a great impact across many industrial and healthcare domains. However, discovering improved sequences requires solving a difficult optimization problem. Traditionally, this challenge was approached by biologists through a model-free method known as “directed evolution”, the iterative process of random mutation and selection. As the ability to build models that capture the sequence-to-function map improves, such models can be used as oracles to screen sequences before running experiments. In recent years, interest in better algorithms that effectively use such oracles to outperform model-free approaches has intensified. These span from approaches based on Bayesian Optimization, to regularized generative models and adaptations of reinforcement learning. In this work, we implement an open-source Fitness Landscape EXploration Sandbox (FLEXS) environment to test and evaluate these algorithms based on their optimality, consistency, and robustness. Using FLEXS, we develop an easy-to-implement, scalable, and robust evolutionary greedy algorithm (AdaLead). Despite its simplicity, we show that AdaLead is a remarkably strong benchmark that out-competes more complex state of the art approaches in a variety of biologically motivated sequence design challenges. 

Under review as a conference paper at ICLR 2021
ADALEAD: A SIMPLE AND ROBUST ADAPTIVE GREEDY SEARCH ALGORITHM FOR SEQUENCE DESIGN
Anonymous authors Paper under double-blind review
ABSTRACT
Efficient design of biological sequences will have a great impact across many industrial and healthcare domains. However, discovering improved sequences requires solving a difficult optimization problem. Traditionally, this challenge was approached by biologists through a model-free method known as "directed evolution", the iterative process of random mutation and selection. As the abil- ity to build models that capture the sequence-tor corrccetto-ffnciiioon map improves, such models can be used oracles to screen sequences before running experiments. In recent years, interest in better algorithms that effectively use such oracles to outperform model-free approaches has intensified. These span from approaches based on Bayesian Optimization, to regularized generative models and adaptations of reinforcement learning. In this work, implement an open-source Fitness Landscape EXploration Sandbox (FLEXS) environment to test and evaluate these algorithms based on their optimality, consistency, and robustness. Using FLEXS, we develop an easy-to- -ottt-mmmeeeet,, scalable, and robust evolutionary greedy algo- rithm (edd). Despite its simplicity, we show that Adal ead is remarkably strong benchmark that out-competes more complex state of the art approaches in variety of biologically motivated sequence design challenges.
INTRODUCTION
An important problem across many domains in biology is the challenge of finding DNA, RNA, or protein sequences which perform a function of interest at a desired level. This task is challenging for two reasons: (i) the map é between sequences X {œ11
. and their biological function [u1.... Un } is non-convex and (ii) has sparse support in the space of possible sequences AL, which also grows exponentially in the length of the sequence L for alphabet A. This map otherwise known as a "fitness landscape" (de Visser et al.) 2018). Currently, the most widely used practical approach in sequence design is "directed evolution" (Arnold) 1998), where populations of biological entities are selected through an assay according to their function y, with each iteration becoming more stringent in the selection criteria. However, this model-free approach relies on evolutionary random walks through the sequence space, and most attempted optimization steps (mutations) are discarded due to their negative impact on
Recent advances in DNA sequencing and synthesis technologies allow large assays which query for specific sequences æ with up to 10s physical samples per batch (Barrera et al. (016)). This development presents opening for machine learning to contribute in building better surrogate models ø' X + y which approximate the oracle ş that maps each sequence to its true function. We may use these models ø' as proxies of c, order generate and screen sequences in silico before they are sent to synthesis (Yang et al.) 2019 Fox et al. 2007). While a large body of work has focused on building better local approximate models on already published data (Otwinowski al. 2018 Allipanhii et al. 2015) Riesselman et al. 2017 (Sinai et (017), the more recent work is being done on optimization in this setting (Biswas et al. 2018 Angermueller et al. 2020 Brookes & Listgarten 2018 Brookes et al. 2019). Although synthesizing many sequences within batch is now possible, because of the labor intensive nature the process, only a handful of iterations of learning can be performed. Hence data is often collected in serial batches b, comprising data D, (bo,.-. bbb and the problem of sequence design is generally cast as that of proposing batches so that we may find the optimal sequence a. arg max max (bx) over the course of these experiments.

---

Under review as a conference paper at ICLR 2021
In this paper, we focus attention ML-augmented exploration algorithms which use (possibly non-differentiable) surrogate models ø' to improve the process of sequence design. While the work is under an active learning setting, in which an algorithm may select samples to be labelled, with data arriving in batches b; our primary objective is black-box optimization, rather than improving the accuracy of surrogate model. We define Eg (D, of) denote an exploration algorithm with parameters 0, which relies on dataset D and surrogate model ø'. When the context is clear, we will simply use & as shorthand.
In most contexts, the sequence space is large enough that even computational evaluation is limited to very small subset of possible options. For this reason, we consider the optimization as sample- restricted, not only in the number of queries to the ground truth oracle, but also the number of queries to the surrogate model( Among other reasons, this allows us to thoroughly study the algorithms on landscapes that can be brute-forced, simulating a similar situation when the sequence space is very large compared to computation power, a very common setting.) The algorithm & may perform sequence evaluations in silico for every sequence proposed. For example, v x B samples may be evaluated by the model before samples are proposed for measurement. Ideally, & should propose strong sequences even when is small; that is, the algorithm should not need to evaluate many sequences to arrive at a strong one.
2 CONTRIBUTIONS
In this study, we make three main contributions towards improving algorithms for sequence design:
1. To build on recent progress in biological sequence design, the research community needs good benchmarks and reference algorithm implementations against which to compare new methods. We implement open-source simulation environment FLEXS that emulate complex biological landscapes and can be readily used for training and evaluating sequence design algorithms. We hope that FLEXS will help ensure meaningful and reproducible research results and accelerate the process of algorithm development for ML-guided biological sequence design.
We introduce an abstracted oracle to allow the empirical study of exploration strategies, indepen- dent of the underlying models. This helps us understand relevant properties, such robustness and consistency of the algorithms.
3. Inspired by evolutionary and Follow the Perturbed Leader approaches in combinatorial opti- mization, we propose simple model-guided greedy approach, termed Adapt-with-the-Leaan (ADALEAD). ADALEAD simple to implement and is competitive with previous state-of-the-a algorithms. We propose ADALEAD algorithms. We show that in general, simple evolutionary algorithms are strong benchmarks to compete against and should be included in future analyses of new methods.
strong, accessible baseline for testing sequence design
EVALUATION
We evaluate the algorithms on set of criteria designed to be relevant to both the biological appli- cability as well as the soundness of the algorithms considered (Purohit et al. 2018). We run the algorithms using FLEXS, where all of these algorithms and criteria evaluators are implemented.
Optimization: We let maximization be the objective. Most optimization algorithms operate under the assumption that critical information such as the best possible y" or the set of all local maxima M is unknown. While it is reasonable to assume that the best sequence is the one with the highest fitness, this is not necessarily the case in reality. For instance, we might wish to bind particular target, but binding it too strongly may be less desirable than binding it at moderate level. As measurements of this criterion, we consider the maximum = max ((x) over all sequences considered, as well as the cardinality |S], where S = {æ; d(æ,) > yr and yr is minimum threshold value. It is noteworthy that we often do not know if any solutions y > Vr exists, hence finding many solutions by an algorithm is a sign of its strength.
Robustness: A major challenge for input design in model- -uidedd algorithms is that optimizing directly on the surrogate o' can result in proposing a sequence x with large error, instead of approximating xt (e.g. if the proposed input x is far outside D). Additionally, while biological
2

---

Under review as a conference paper at ICLR 2021
models & may contain regularities that are universally shared, those regularities not known. Hence, a desired property of the algorithm is that is robust in the face of poor model.
Consistency: The algorithm & should produce better performing sequences if it has access to a higher quality model 6¹.
Additionally, we desire that the perforrifo sequences proposed by the algorithm are diverse. Because a sequence may be disqualified for reasons which are unknown during the design phase, we would like to find distinct solutions which meet the optimality criteria. However, metrics for measuring diversity can be ambiguous and we only focus on measuring diversity in a narrow sense. We measure diversity using [S]. When the ground truth model can be fully enumerated to find its local optima (peaks) by brute force (i.e. we know the maxima M), we can use the number of found maxima [M as measure of diversity, where My C M represents the maxima found by the algorithm above fitness yr-
4 RELATED WORK
Bayesian Optimization (BO). BO algorithms are designed to optimize black-box functions which are expensive to query. Importantly, these algorithms make use of the uncertainty of model estimates to negotiate exploration versus exploitation. In pioneering study, [Romero stode, et al. (2013) demonstrate the use of BO for protein engineering. Many successful attempts have followed since (e.g. Gonzalez et al. (2155) and Yang al. (2019)), however in each of these cases specifie model of the design space is assumed to shrink the search space significantly. Otherwise BO is known to perform poorly in higher dimensional space (Frazier 2018). and to our knowledge, no general purpose sequence design algorithm using BO has performed better than the models considered below. For this reason, while we implement variations of BO as benchmarks (see similar interpretations in |Belanger et al. (2019)), we do not consider these implementations as competitive standards. In our figures, we use the EI (Expected Improvement) acquisition function with an evolutionary sequence generator as our BO algorithm, and show comparisons with alternatives (on TF landscapes) in the supplement.
Generative models. Another class of algorithms approach the task of sequence design by using regularized generative models. At high level, these approaches pair a generative model G with an oracle ø', and construct a feedback loop that updates Go (and sometimes ø') to produce high-performing sequences. In Feedback- -GAN (FBGAN), Gupta & Zou (0118) pair generative adversarial network (Goodfellow et al., 2014) that is trained to predict whether sequences belong to the functional set using frozen oracle o' which filters subset of sequences at each training step. They bias the training of the generator and discriminator towards high-performing sequences. Killoran itt al. (017)) pursue the sequence optimization by regularizing an "inverted model", %8/ -'') = I; with Wasserstein GAN (Arjovsky al., 2017) which is trained produce realistic samples. In this case, both @ and the generator are trained jointly.
Brookes & Listgarten (018) propose an algorithm, Design by Adaptive Sampling (DbAS), that works by training generative model G.p. on set of sequences Xo. and generating a set of proposal sequences X ~ G.p. They then use %% to filter X for high- geghoreeformnngg sequences, retrain G.., and iterate this process until convergence. This scheme is identical to the cross-entropy method with a VAE as the generative model, important optimization scheme (Rubinstein 1999). In follow-up work, termed Conditioning by Adaptive Sampling (CbAS) (Brookes et al.] 2019). the authors aim to address the pitfall in which the oracle is biased, and gives poor estimates outside its training domain D. The authors enforce soft pessimism penalty for samples that are very distinct from those that the oracle could have possibly learned from. Specifically, they modify the paradigm so that as the generator updates its parameters & v/ while training samples in the tail of the distribution, it discounts the weight of the samples x; by Pr(e; G:p.))
Pria:|Gieo) In other words, if the generative model that
was trained on the original data was more enthusiastic about a sample than the one that has updated according to the oracle's recommendations, that sample is up- apigeeghted in the next training round (and vice versa). Notably, as the oracle is not updated during the process, there are two rounds of experiments where they maximize the potential gains from their oracle given what it already knows: a round to create the oracle, and a round to improve the generative model. While is trivial to repeat the process for multiple rounds, the process can be improved by incorporating information about how
3

---

Under review as a conference paper at ICLR 2021
many rounds it will be used for. We use DbAS and CbAS state of the art representatives in this class of regularized generative algorithms.
Reinforcement Learning (RL). RL algorithms another method used to approach this problem. As these algorithms learn to perform tasks by experience, their success often dependent on whether interactions with the environment are cheap if there is good simulator of the environment which they can practice on (Mnih et al.) 2015). However, in our setting, good simulators often do not exist, and sampling the environment directly can be very expensive. As result, recent approaches to this problem have built locally accurate simulators and used them to train an RL agent. With DyNA-PPO, Angermueller
al. (2020) achieve state-of-the results in sequence design tasks following this approach. They train policy network based on Proximal Policy Optimization (PPO) (Schulman et al. 2017) by simulating through an ensemble of models d". The models are trained on all measured data so far, and those that achieve high R² score in cross-validation are selected as part of the ensemble. Additionally, to increase the diversity of proposed sequences, they add penalty for proposing samples that are close to previously proposed samples. They compare their results against some of the methods mentioned above, as well as other RL training schemes, showing superior results. While DyNA-PPO reaches state of the art performance, major drawback of policy gradient algorithms is that they are complex to implement, and their performance is highly sensitive implementation (Engstrom et al. 2019). We DyNA-PPO as representative state of the art for all sequence design algorithms for our study.
Most recent sequence design algorithms do not use evolution-inspiree methods. Despite their lack of popularity, as we show here, they are fairly strong baselines that should be considered. Here we investigate classic algorithms like standard Wright-Fisher process, without and without models, Covariance Matrix Adaptation evolutionary strategy, (CMA-ES) (Hansen & Ostermeier 2001 and ADALEAD.
It's important to note that the focus of our study is distinet from those focused on better local approximate models (e.g. (Rao al. 2019 Riesselman al., 2017)) or semi-supervised and transfer learning approaches (e.g. (Madani et al.) 2020 Biswas et al. 2020
A
B
R²2 R22 betwesn true fitness and model estimate
aptamm
apta=a.
Optimbration on apprsainatt models
Ersemble
Exploners
0.8
o 0.75
alpha=0.0
0.6
Approsimats modds
ML
0.4
D
Obearotions
Experiments
02
duatatrnc SPRESO
ground- foandd--uuhhhhho
0.0
landscape
Distance from wt
Figure 1: A: An overview of our scheme. An expensive-to-query ground-truth oracle Φ - y/ local approximate model ø' trained on samples 'D from o; an exploration algorithm & which is the primary interest of our study (e.g. ADALEAD, DynaPPO,, ...). In our setting, the training ø' is fully supervised. B: Noise corrupted abstract models &' allow for independent study of & on landscapes where ground truth can be simulated (here an RNA landscape of size 14, binding to one target). For comparison, the R² score for ensemble of 3 CNNs trained random set of 100 sequences around the starting position is provided.
5 METHODS
In this study, we evaluate representative state of the art algorithms in addition to a simple greedy algorithm which we call Adae-- (ADALEAD) (See Algorithm []. The main advantage
4

---

Under review as a conference paper at ICLR 2021
of ADALEAD benchmark is that it is easy to implement and reproduce. The algorithm selects set of seed sequences a such that ((z) is within (1 - k) of the maximum y observed in the previous batch. These seeds are then iteratively recombined and mutated (see appendix for details) and the ones that show improvement on their seed according to d' are added to a set of candidates M. Finally, all candidates are sorted according to ø' and the top B are proposed for the next batch. We consider the recombination rate and mutation rate μ as well as the threshold K as hyperparameters, However, the algorithm fairly robust in performance for K, r 0.5. We note that recombination known to be a powerful generative method which promotes diversity and avoids local maxima (Otwinowski & LaMont 2019). Despite this, the performance gain due to recombination ADALEAD small (see supplement Fig. A2 for details).
Algorithm 1 ADALEAD
Input: model d', batch b, threshold K, virtual evaluations t
Initialize parents P 2- Ø Initialize mutants MM f- 2
Update d' with data from by
S = {ac ((xx)= 2 maxyeb, y V-(1 RT, Vo E be}
while _M| < V l6,| do
P = SUPPUEEEEE RECOMBINE(S)
for x; E P do
{I 2.k 2 = ROLLOUT(Z; x²)
M - ( (a........ xx
end for end while
Use ø' to select bi41, the top [b,] sequences from M RETURN bi+1
As ADALEAD perturbs the best (known) sequences, it is a greedy algorithm where the threshold determines the greediness. However, it is adaptive in the sense that given fixed threshold when the optimisation surface flat, many sequences will clear the (1 - k) max y filter, and therefore the algorithm encourages diversity. When the surface has a prominent peak, it will opt to climb rapidly from the best-known samples. As we will see, this yields a robust, yet surprisingly Wright-Fisher process, but faster
effective algorithm that uses the same principle of hill-climbing and more scalable to compute (as it does not require fitness based sampling), and is supported by the intuition behind Fisher's fundamental theorem (see Otwinowski & LaMont (2019) for helpful discussion). Notably, this is distinct from rank-based and quantile-based algorithms, where diversity may be compromised due to the dominance of sequences that are trivial changes to æi, and hence are more likely to remain at the same local optima. The ROLLOUT procedure mutates (with mutation rate 1/L) proposed candidates in S until ø' d'(xx..) < ø' 6'(x..o) where the number of times a candidate has been subject to mutation operation. Finally, all candidates are sorted according to d' and the top B are proposed for the next batch. We find that the rollout process has a small beneficial effect the performance of the algorithm (see supplement Fig. A4). Overall, ADALEAD takes advantage of correlation structure of biological sequences. Namely that sequences close to each other are more likely to have similar values. Since it always starts from the best known sequences, it ensures better robustness (less dependence on the model). The optimization side is greedy hill-climbing with the help of the model's foresight. We found surprising that such simple method can compete with more sophisticated state of the art approaches presented here.
speculate that
In order to focus our attention comparing the power of exploration algorithms, rather than the power of an oracle, we make use of, but do not limit ourselves to, an abstract model V., which is a noise-corrupted version of the ground truth landscape. Specifically,
&e a (1 d
where d the distance from the closest measured neighbor and E a noise parameter sampled from an exponential distribution with À equal to á operating on the closest measured neighbor" We find
An alternative approach is to let the noise he random sample from the empirical distribution of known mutants; since hehaves more stochastically in this setting, we do not evaluate the models with this approach.
5

---

Under review as a conference paper at ICLR 2021
that this setup allows to emulate the performance of trained models well, while controlling for model accuracy. We also define the null model (uall as an exponential distribution with À equal to the average measured fitness (Orr) 2010). The null model is special case of the abstract model where = 0. Importantly, this abstraction allows us to control a to investigate consistency and robustness (see supplement for additional description and Fig. IB for comparison of abstract and empirical models on RNA landscapes).
To validate the applicability of this strategy, we also use it with trainable sequence models, including a simple linear regressor, random forest regressors, Gaussian process regressors, and several neural network architectures. As we show using the abstract models, ADALEAD is consistent, and any improvement on the model is beneficial for the algorithm. Although ADALEAD is compatible with single models, we implement and recommend using it with an ensemble of models. Additionally, our implementation is adaptive: model estimates are re-weighted based on how well they predicted the labels on sequences proposed on the previous batch. Herein, we show the results from an ensemble of 3 CNN models as representative choice of the empirical models, denoted by ø". This ensemble was our strongest empirical model across different landscapes, among those mentioned above.
EXPERIMENTS
Prior to discussing the empirical experiments, two preliminaries are noteworthy. Firstly, proposing general algorithm that can optimize on arbitrary landscapes is not possible, and even local optima can take an exponential number of samples to find with hill-climbing algorithms (Wolpert et al. 1997] Kaznatcheev 2019). Nonetheless, since biological landscapes are governed by bhysio-chemica laws that may constrain and structure them in specific ways, some generalizability can be expected. Secondly, the problem of choosing suitable optimization challenges that are biologically representative requires some consideration. Biological fitness landscapes are notoriously hard model outside the locality where rich data is available (see Bank et al.] (2016) as well as Fig. A3 in the supplement). As such, models that are built on data around some natural sequence are often only representative in that context, and the model becomes pathological rapidly as the distance from the context increases. This is the motivation for Brookes al. 2019) as an improvement on Brookes & Listgarten (2018) to ensure the model ø' is not trusted outside its zone of applicability. Here, we are interested in exploring deep into the sequence space, through multiple "experimental design" rounds. Hence is highly preferable that the quality of our ground-truth simulator á remains consistent as we drift away from the starting sequence. Note that this not the case for models that are trained on empirical data such as those in Rao et al. (2019) where the model is accurate in local contexts where data is available, but the behavior outside the trust region is unknown and may be pathological.
We test our algorithms on multiple sequence design tasks. We first choose contexts in which the ground truth and the optimal solutions are known (to the evaluator). We then challenge the algorithms with more complex landscapes, in which the ground truth may be queried, but the optimal solution is unknown.
TF binding landscapes. |Barrera al. (2016) surveyed the binding affinity of more than one hundred transcription factors (T'F) to all possible DNA sequences of length 8. Since the oracle ø is entirely characterized, and biological, it a relevant benchmark for our purpose (Angermueller et al., 22220). We randomly sample five of these measured landscapes, and evaluate the performance of these algorithms on these landscapes. For each landscape, we start the process 13 random initial sequences which are then fixed. We do not pre- pre-train the algorithms on other landscapes before using them, since TF binding sites for different proteins can be correlated (e.g. high- performing sequences in some landscapes may bind many proteins well). Should pre-training be required, we impose a cost for collecting the data required. We shift the function distribution such that y/ E [0, 1). and therefore y" 1. We show the results of our optimization tasks on these landscape in Fig. 2A. All algorithms perform similarly well in terms of optimization in these landscapes, suggesting that while the task itself is biologically suitable, the landscape is rather easy to optimize on, partially due to its size.
RNA landscapes. The task of predicting RNA secondary structures has been well-studied and is relatively mature. Classic algorithms use dynamic programming to efficiently fold RNA structures. RNA landscapes are particularly suitable because they provide a relatively accurate model of bi- ological sequences that is consistent across the domain, even for landscapes of size 4 4100 and are
6

---

Under review as a conference paper at ICLR 2021
LANDSCAPE
Ø'
# PEAKS
ADALEAD
DYNAPPO
CBAS/DBAS
CMAES
5 TF BINDING
> 0.75
a ==
67.6
31.29 19.24
22.85 111.05
2.57 11.08
26.16 -10.74
5 TF BINDING
ENSEMBLE -=0 0
11.65 14.12
4.09 -4.23
1.79 11.25
10.02 =3.6
5 TF BINDING
5.02 #2.42
1.76
1.99 #1.64
2.1
5 TF BINDING
> 0.9
a=
22.6
21.87=5..2
13.33 #6,04
1.35+1.08
15.05
5 TF BINDING
ENSEMBLE a 0
9.56 +3.77
1.55 +1.9
0.79 +00.9
7.53 +3344
5 TF BINDING
3.7+
0.57 -0.88
0.9 +0.9
0.9 +1.07
5 TF RINDING
o=1
0.97=
0.53 +0.5
0.05+00.21
0.67+0.47
5 TF BINDING
ENSEMBLE a=
0.31 10.46
0.08 -0.27
0.03 10.17
0.31100.6
5 BINDING
0.21
0.02.10.11
0.06110.22
0.04 10.18
RNA14_B B1
0.75
a a=
353
12.8 +5.26
9.2
1.0
1.4 +0.5
RNA14_B B1
ENSEMBLE
3.8+
+2.55
1.0 #0.8
0.67+1.0
RNA14_B1
a=0 0
0.5+
0.3 #0.67
0,2+0.63
0
RNA14
0.9
Q=1
37
1.67
1.442.07
0.4::.255
0.4
RNA14_B B1
ENSEMBLE
1.2.
0
0.33:10.58
0.4400.54
RNA14_B B1
a= 0
0.240.42
0
0
RNA14 B1
=1
a=
3
0.410.54
0.2:10.4
RNA14 B1
ENSEMBLE
0.240.44
0
0
0
RNA14_BI
0.1+0.31
0
0
RNA14 _M42
0.75
a=1 ENSEMBLE a
33
4.8+
1.8 +0.83
0.4+0.55
0.2++0.44
RNA14 B1+2
2.611.34
0.0
0.0
0.0
RNA14 B1+2
0.3
0.1
RNA14 B1+2
0.9
9
1.4.10.89
0.4
RNA14_ B1+2
ENSEMBLE a=0
1.2 +1.0
R B1+2
0.2+0.31
4 AM224_B142
a=1 ENSEMBLE a=0
3
0.6
RNA14 B1+2
0.2+:0.44
RNA14_B142
0.1 +0.31
0
Table We compare the algorithms based on the number of optima above certain threshold yr each of them finds. The total number of optima has been computed by brute force in each landscape.
The algorithms were run with an empirical ensemble model, a perfect model (a = 1) and an uninformative model (a 0), querying the ground truth with total of 1000 sequences, and the surrogate model with ratio = 20 and at least initializations each (mean and standard deviation reported). For TF landscapes (size 4 each), we average the scores across 5 landscapes (each with 13 initiations). ADALEAD finds high-performing peaks more consistently than the other algorithms. regularly finds the global optimum in RNA binding landscape landscape of size 4-4 with 2925 local peaks in total (RNAI 14_ 14_B1). It also outperforms other algorithms in similarly sized composite landscape with two binding targets (RNA14 B1+2), with 806 peaks overall.
non-convex with many local optima (see Fig, A3). We use the ViennaRNA package to simulate binding landscapes of RNA sequences as & (Lorenz et 201I).
We test our algorithms on many RNA binding landscapes of various complexity and size (e.g. sequence length 14-100). In short, ADALEAD outperforms the other algorithms in all of the attempted landscapes. As basic ground-truth test, we optimize sequences of size 14 for binding hidden 50 nucleotide targets. We use the duplex energy of the sequence and the target as our objective y. which means that the sequence can bind the target in multiple different ways, producing many local minima. We also consider more complex landscapes with hidden targets and compute the objective y Vi9e. Due to the size of these landscapes and as with the TF binding landscapes, find out how well the algorithms explore the space. Table [ summarizes the number of local optima with function greater than y- that each algorithm finds. We define local optima in this case as sequences whose immediate neighbors all have lower y.
enumerate all 4 sequences with the oracle,
We also test RNA sequences of size 100, that bind hidden targets of size 100. In these cases do not know the actual optima in advance, hence, we estimate by computing the binding energy of the perfect complement of the target. Using this normalization, y 1. Like before, use both single
7

---

Under review as a conference paper at ICLR 2021
and double target binding objectives. Additionally, define conserved patterss in sequences which would not allow inntations,meaninn the sequence needs to preserve those positions in order to remain viable. In these cases, conserve fifth of the sequence, which results in roughly fifth of the landscape providing no gradients. This resembles the scenario for many biological objectives, where gradients are not available over large regions of the space. We refer to this challenging landscape as "Swampland" (see breakdown in Fig. Ple.e refer to section A3 for more detailed discussion. Despite using a greedy heuristic, ADALEAD outperforms the other algorithms in landscapes that
A
5 TF landscapes
C 1.
RNA L14, hidden targets
Oumulativv maxy
0.5
Cumulativv max
86
0.0
ENS 3x CNN
Adalasd DynPPO
AMAudd
Exa .00
Cldad6
DynaPmo
Gosg
Modil doen Eviieolion
DD44
02
ajpha=1
06A0
OMAR
08
B
Consistency and Robustness
Mean cumulative T1X
0.00
DreFPo
0.5
Oumuuaativ max
0.00
BEAS
0.5
AdaLard
mm
DyraPPO
ENS 3x CNN
OMAES
502
100
alpha
samples (batch size=100)
ENS 3x CNN
alpha=1
Cumulettve max
Swamplond LTN0
target R14
3rici
Swampland LINO
1 target HIA L14
3msi 00-30 proten
68-48 prolein
Figure 2: We record the cumulative maximum over all sequences generated by each algorithm when run with 10 batches of size 100, and 20. All scores on the y-axis normalized known or estimated maximum possible value. A: The cumulative maximum achieved by each algorithm on TF binding landscapes (13 initializations). using an ensemble of 3 CNNs as the oracle (Ø"). On this simple landscape, even model free evolution algorithm can optimize well. B: Consistency (performance vs. model quality a) and robustness (performance low a:) of the algorithms on 2 target RNA landscapes of L 14. C: Time evolution of the cumulative maximum landscape with sequence length 14, and hidden targets (5 initializations, a = 1). Top: Φa=1, bottom: d" ensemble of 3 CNNs. D: Comparison of overall performance for 3 landscape classes. Swampland landscapes show high variance due to the difficulty of finding good sequences starting from dead sequences. ADALFAAD, and evolutionary algorithms in general tend be strongly competitive in more complex landscapes.
RNA
are highly epistatic (include lot of local peaks). shown in Fig. A3, even the set of shortest path permutations on the landscapes between one of the starting positions and the global peak may include valleys of multiple deleterious steps. The time evolution the best sequence found at each batch, shown in Fig. 2C, suggests that some algorithms are faster to climb in the first couple of batches, but none outperform ADALEAD in the longer horizon. As we show in Fig. 2B, ADALEAD is also more robust (performs well even with uninformative model), and as consistent as all the other algorithms. The relative ranking of algorithms remains similar to the a = case when CNN ensembles used (Fig. 2C).
8

---

Under review as a conference paper at ICLR 2021
Protein design. As a final challenge also compare the performance of algorithms with multiple protein design tasks. While ground-truth simulators for protein design are much less accurate than the RNA landscapes, the larger alphabet size of ~ 20 and complexity of the landscapes are of high relevance. In this case we use PyRosetta (Chaudhury et al. 2010) as Φb. The Rosetta design objective function is a scaled estimate of the folding energy, which has been found to be an indicator of the probability that a sequence will fold to the desired structure (Kuhlman et al., 2003). We optimize for the structure of 3MSI, 66 amino acid antifreeze protein found in the ocean pout (DeLuca et al., 1998) starting from 5 sequences with 3-27 mutations from the wildtype. Here, we normalize energy scores by scaling and shifting their distribution and then applying the sigmoid function.
7 CONCLUSIONS AND FUTURE DIRECTIONS
We implement an open- source simulation environment FLEXS that can emulate complex biological landscapes and can be readily used for training and evaluating sequence design problems. We also include "'wampland" landscapes with large areas of no gradient, a biological aspect of sequence design rarely explored (see Fig A3). We also provide additional interfaces for protein design based on trained black-box oracles (e.g. (Rao al. 2019) that we don't 't study for reasons explained in the manuscript. Additionally, we proposed simple evolutionary algorithm, ADALEAD as a competitive benchmark. We demonstrate that ADALEAD is able to robustly optimize in challenging settings, and consistently performs better as model performance improves. We show that in general, simple evolutionary algorithms are strong benchmarks compete against. While we have investigated consistency and robustness for the queries to ground truth oracle, the same concepts also apply to variations in v. These would affect sample efficiency, and scalability of the algorithms. There are also other properties of interest, also mentioned in Purohit et al. (2018) (e.g. independence), which are closely connected to consistency and robustness, where the algorithm can operate with oracles with different biases and noise profiles. Additionally, in the online batch setting, for any fixed total sequences proposed, the algorithm expected to pay a performance penalty as the batch size grows. This is due to lack of model updates for the sequences proposed within each batch. Algorithms that incur lower penalties can be desirable in low-round batch setting. This is known as adaptivity. We do not evaluate these properties directly in this work, but implement tools that allow for their study within FLEXS.
We hope that FLEXS provides useful environment for future development of better sequence design algorithms, and hope that ADALEAD help discipline such efforts towards more simple approaches that are reproducible and translatable in practice.
REFERENCES
Babak Alipanahi, Andrew Delong, Matthew Weirauch, and Brendan J Frey. Predicting the sequence specificities of DNA-and RNA-binding proteins by deep learning. Nature biotechnology. 33(8):
831, 2015.
Christof Angermueller, David Dohan, David Belanger, Ramya Deshpande, Kevin Murphy, and Lucy Colwell. Model-based reinforcement learning for biological sequence design. In International Conference on Learning Representations, 2020. URL hnttps://openrev/// www.:nnutffttooooooo forum?
id=HikxbgBKvr
Martin Arjovsky, Soumith Chintala, and Léon Bottou. 17X1n: 2017.
Wasserstein gan. arXiv preprint
Frances H Arnold. Design by directed evolution. Accounts of chemical research, 3153)112--331, 1998.
Claudia Bank, Sebastian Matuszewski, Ryan T Hietpas, and Jeffrey D Jensen. On the (un) predictabil- ity of a large intragenic fitness landscape. Proceedings of the National Academy of Sciences, 113 (:9):14085-14000 2016.
Luis A Barrera, Anastasia Vedenko, Jesse V Kurland, Julia M Rogers, Stephen Gisselbrecht, Elizabeth J Rossin, Jaie Woodard, Luca Mariani, Kian Hong Kock, Sachi Inukai, et al. Survey of variation in human transcription factors reveals prevalent dna binding changes. Science, 351 (6280): 1450-14444 2016.

---

Under review as a conference paper at ICLR 2021
David Belanger, Suhani Vora, Zelda Mariet, Ramya Deshpande, David Dohan, Christof Angermueller, Kevin Murphy, Olivier Chapelle, and Lucy Colwell. Biological sequence design using batched bayesian optimization. 2019.
Surojit Biswas, Gleb Kuznetsov, Pierce Ogden, Nicholas J Conway, Ryan P Adams, and George M Church. Toward machine-guided design of proteins. bioRxiv, pp. 337154, 2018.
Surojit Biswas, Grigory Khimulya, Ethan Alley, Kevin M Esvelt, and George M Church. Low-n protein engineering with data- deep learning, bioRxiv, 2020.
David H Brookes and Jennifer Listgarten. Design by adaptive sampling. arXiv preprint 1rx1v:1810.03714, 2018.
David H Brookes, Hahnbeom Park, and Jennifer Listgarten. Conditioning by adaptive sampling for robust design. arXiv preprint arXiv: 10060, 2019.
Sidhartha Chaudhury, Sergey Lyskov, and Jeffrey J Gray. Pyrosetta: script-based interface for implementing molecular modeling algorithms using rosetta. Bioinformatics, 26(5):689-691, 2010.
J Arjan GM de Visser, Santiago F Elena, Inês Fragata, and Sebastian Matuszewski. The utility of fitness landscapes and big data for predicting evolution, 2018.
Carl DeLuca, Peter L Davies, Qilu Ye, and Zongchao Jia. The effects of steric mutations on the structure of type iii antifreeze protein and its interaction with ice. Journal of molecular biology, 275(3):515-525, 1998.
Logan Engstrom, Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Firdaus Janoos, Larry Rudolph, and Aleksander Madry. Implementation matters deep RL: A case study on PPO and TRPO. In International Conference Learning Representations, 2019.
Richard Fox, Christopher Davis, Emily C Mundorff, Lisa M Newman, Vesna Gavrilovic, Steven Ma, Loleta M Chung, Charlene Ching, Sarena Tam, Sheela Muley, al. Improving catalytic function by ProSAR-driven enzyme evolution. Nature biotechnology. 25(3):338, 2007.
Peter Frazier. A tutorial bayesian optimization. arXiv preprint arXiv:1807.028111 2018.
Javier Gonzalez, Joseph Longworth, David C James, and Neil Lawrence. Bayesian optimization for synthetic gene design. arXiv preprint
2015.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural informa- tion processing systems. pp. 2672-2680, 2014.
Sergio Guadarrama, Anoop Korattikara, Oscar Ramirez, Pablo Castro, Ethan Holly, Sam Fishman, Ke Wang, Ekaterina Gonina, Neal Wu, Ef Kokiopoulou, Luciano Shaiz, Jamie Smith, Gabor Bartok, Jesse Berent, Chris Harris, Vincent Vanhoucke, and Eugene Brevdo. TF-Agents: A library for reinforcement learning tensorflow, |tttps::/ wttp://sortt/o/co/ooo/oo/o wwwp///ggtsss/// 2018. URL http://pp///ggaaao.oooco//ooooop 2019].
aggett
[Online; accessed 25-June-
Anvita Gupta and James Zou. Feedback GAN (FBGAN) for DNA: a novel feedback-loop architecture for optimizing protein functions. arXiv preprint (tfv::/804.0060 2018.
Nikolaus Hansen and Andreas Ostermeier. Completely derandomized self-adaptation in evolution strategies. Evolutionary computation, 9(2):159-195 2001.
Artem Kaznatcheev. Computational complexity as an ultimate constraint on evolution. Genetics, 212 (1):245-265, 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 Jimmy Ba. Adam: A method for stochastic optimization, 2014.
10

---

Under review as a conference paper at ICLR 2021
Diederik P Kingma and Max Welling. arXiv:1312.61 14,6111142000 2013.
Auto-encoding variational bayes.
arXiv preprint
Brian Kuhlman, Gautam Dantas, Gregory C Ireton, Gabriele Varani, Barry L Stoddard, and David Baker. Design of novel globular protein fold with atomic-level accuracy. science, 302(5649):
1364-1368, 2003.
Ronny Lorenz, Stephan H Bernhart, Christian Höner Zu Siederdissen, Hakim Tafer, Christoph Flamm, Peter F Stadler, and Ivo Hofacker. ViennaRNA package 2.0. Algorithms for molecular biology, 6(1):26, 2011.
Ali Madani, Bryan McCann, Nikhil Naik, Nitish Shirish Keskar, Namrata Anand, Raphael R Eguchi, Po-Ssu Huang, and Richard Socher. Progen: Language modeling for protein generation. arXiv preprint ar arXiv:2004.0344 2020.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei Rusu, Joel Veness, Mare G Bellemare. Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529-35 2015.
The population genetics of beneficial mutations. Philosophical Transactions of the Royal Society B: Biological Sciences, 365((544):1 2010.
Allen Orr.
Jakub Otwinowski and Colin LaMont. Cooommationgcomettiin optimization with natural selection. arXiv, pp. arXiv-1912, 2019.
Jakub Otwinowski, David Martin McCandlish, and Joshua Plotkin. Inferring the shape of global epistasis. bioRxiv, pp. 278630, 2018.
Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning Python. Journal of Machine Learning Research, 12:2825-2830. 2011.
Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ml predictions. In Advances in Neural Information Processing Systems, pp. 9661-9670, 2018.
Roshan Rao, Nicholas Bhattacharya, Neil Thomas, Yan Duan, Xi Chen, John Canny, Pieter Abbeel, and Yun Song. Evaluating protein transfer learning with tape. In Advances in Neural Information Processing Systems, 2019.
Adam J Riesselman, John B Ingraham, and Debora S Marks. Deep generative models of genetic variation capture mutation effects. arXiv preprint arXiv:1712.06522 2017.
Philip A Romero, Andreas Krause, and Frances H Arnold. Navigating the protein fitness landscape with Gaussian processes. Proceedings of the National Academy of Sciences, 1033) 2013.
Reuven Rubinstein. The cross-entropy method for combinatorial and continuous optimization. Methodology and computing applied probability, 1(2):127-190, 1999.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint 17770:1707.06377, 2017.
Sam Sinai, Eric Kelsic, George M Church, and Martin A Nowak. Variational auto-encoding of protein sequences, arXiv preprint arXiv:1712.03346 2017.
David H Wolpert, William G Macready, et al. No free lunch theorems for optimization. IEEE transactions on evolutionary computation, 1(1):67-82. 1997.
Kevin K Yang, Zachary Wu, and Frances H Arnold. Machine-learing-guiieee directed evolution for protein engineering, Nature methods, 16(8):687-694 2019.
11

---

Under review as a conference paper at ICLR 2021
A APPENDIX
A.1 NOISE MODELS
A.1.1 NOISY ORACLE
In order to control for model accuracy, we define noise-corrupted versions of the landscape oracle
6 = a (1 11--"% a a²)c,
where d is the distance from the closest measured neighbor and E a noise parameter sampled from an exponential distribution with the rate parameter À equal to & operating on the closest measured neighbor. An alternative approach is to sample from the empirical distribution of known mutants; since e behaves more stochastically in this setting, we use the former approach, while we confirm that the results are qualitatively the same if the second approach is used.
In Fig. IB show the performance of these models between 0 and 1. We also show the predictive power of the empirical CNN ensembles, when trained on 100 random mutants with varying distances from the wild type on the same landscape. The noise-corrupted oracles allow testing for consistency and robustness in particular.
RNA14 14 B1 landscape as is varied
A.1.2 EMPIRICAL MODELS
For our sandbox, we implement suite of empirical models. We use linear regression, random forest regression from the scikit-learn library (Pedregosa et al. 2011). We also implement two neural architectures: (1) A "global epistasis" network that first collapses the input to single linear unit, and then non-linear transform through two 50 unit ReLUs, and final single linear unit (Otwinowski ctt al. 2018). (2) A convolutional neural network. We tested a variety of other architectures and sklearn models, but found these sufficient representative models. We find that the CNN is often the most accurate model. For ensembling, we use ensembles of 3 initializations of the CNN architecture. Ensembles may be run in "adaptive mode" where the model outputs averaged based on weights proportional to the R² of the model on the data generated in the previous step. While ensembles come with the additional benefit of allowing uncertainty estimation (which is useful in most of our algorithms), the performance gain of using them is often small. In the paper, we show the results for an adaptive ensemble of CNNs, which was the strongest empirical model we attempted.
A.2 ALGORIHTMS
A.2.1 BAYESIAN OPTIMIZATION
We first test classical GP-BO algorithms on TF landscapes, as they are of small enough (4 total sequences) to enumerate fully. We use a Gaussian process regressor (GPR) with default settings from the sklearn library. Furthermore, we lift the virtual screen restriction for this particular optimization method. We propose a batch of sequences as determined by an acquisition function. We use the standard EI, UCB as well as Thompson sampling (where the posterior is sampled for each sequence, and top B are selected for next round). The GPR based, enumerative approach scales poorly and cannot accommodate domains where the sequence space is much larger (e.g. RNA landscapes or protein landscapes).
As a compromise, we also implement BO-guided evolutionary algorithm, where mutants generated at random from sequences, defining a tractable action space. To generate the batch sequences in each round, we take state sequence and sample v sequences with per position mutation probability of j. Instead of GPRs, we use ensembles of the empirical models to compute uncertainty in the posterior, similar to (Belanger et al.) 2019). We evaluate the ensemble on each proposed mutant s/ and use El and UCB acquisition functions for selecting $'.0 to mutate further to K-,1- We stop adding mutations once Var(ø" (st.))) > 2 Var(ø" virtual screen limit. We collect all candidates that were generated through this process and we then use Thompson sampling based on d" to choose subset of size B our batch. After the batch is filled and the ensemble is updated, the state sequence for the next batch is chosen to be the sequence from the previous batch with the highest predicted score (Frazier 2018). As shown in Fig. A1A, the evolutionary BO is competitive with, or better than, the enumerative BO algorithms we attempted on the TF landscapes. We therefore use the evolutionary BO in the main paper.
or once we reach the
12

---

Under review as a conference paper at ICLR 2021
A
B
GP regression TF landscapes
Comparison on Evolutionary algorithms
1/4
Cumulative maxy
0.6
0.7
04
AdaLood
Ex BD
CHA-ES
04
80 Greacy
Thomsson
Modsl tro Dvdluttor
NL- NL-qadde Eveludio
Excarton-aayyd0gg
0.0
100
250
902
400
500
800
500
500
1000
Nurtbrr camp en (butch -100)
Figure A1: A: Running GP-based BO on the TF binding landscape with full enumeration of the sequence space (v oo). For comparison, we show that the evolutionary BO, used in the paper as benchmark, outperforms these methods. B: A comparison of multiple evolutionary algorithms that were run on RNA binding landscapes of length 14 and one target, with similar μ = 1/L, r 0.2.
A.2.2 ADALEAD
We performed basic parameter tuning for ADALEAD, testing recombination rates, mutation rates and threshold. For comparisons with other algorithms, we use recombination rate of 0.2 (i.e. 1/5 probability of crossover at each position), mutation rate of 1/T. where I. is the sequence size, and threshold of r 0.05. We find that presence of recombination helps the performance of the algorithm both in optimality and ability to find diverse peaks. However, both of these effects are small (see Fig. A2) and most of the benefits tend to be detrimental with noisier models. While higher mutations rates can help with exploration chose L/L accommodate the simpler models and uniformity across all algorithms (some that introduce one change at a time). The parameter begins to be effective below 0.5, but tends to be too restrictive (resulting in less than enough seeds when generating) when T < 0.05. We use 0.05 in shown experiments. Overall, ADALEAD is fairly robust to these parameters. Since ADALEAD evolutionary algorithm, we also compare its performance other evolutionary algorithms as benchmarks. Our results, shown in Fig. A1B, show that ADALEAD is roughly equivalent to model- guided Wright-Fisher process (this expected, as ADALEAD operates on the same hill-climbing principle although it is faster to compute and less memory intensive, and hence it can be scaled better). consistently outperforms model-free evolution (WF), CMA-ES, and Evolutionary BO.
present within rate < 0.3, above which the stochastic effects
A.2.3 DBAS
We implement the sampling algorithm introduced in Brookes & Listgarten (2018) with variational autoencoder (VAE) (Kingma & Welling 2013) as the generator. The encoder and decoder of the VAE both consist of three dense layers with 250 exponential linear units. There is 30% dropout layer after the first encoder and the second decoder layer as well as batch normalization after the second encoder layer. The input is a mn--hot-nncodig of sequence and the output layer has sigmoid neurons that result into a positional weight matrix as a reconstruction of the input. The latent space dimension is 2. We use the Adam optimizer (Kingma & Ba 2014). In each cycle, the DbAS algorithm starts by training the VAE on the sequences whose fitness is known and selects the top 20% as scored by the oracle. New samples are then generated by drawing from the multivariate Gaussian distribution of the latent space of the VAE. Once again, the top 20% of the generated sequences (or the ones whose fitness is above the 80th percentile of the previous batch, whichever the stricter threshold) selected and the process is repeated until convergence (which in case is defined as not having improved the top scoring sequence for 10 consecutive rounds) or the computational budget is exhausted. At that point the batch of sequences proposed in the latest iteration is returned.
13

---

Under review as a conference paper at ICLR 2021
A
Alpha=1
B
Ensemble of 3x CNNs
1.0
Selecled Racomb
Max cumulative
0.5
330
1000
425
500
600
730
complics (baoch -100)
sampless .103)
Figure A2: Effects of these hyperparameters the performance of ADALEAD, RNA landscape of length 14 and two hidden targets. ADALEAD is robust to hyperparameter choices for K, The setting used in the paper shown is in blue (r 0.2,
0.05). The same 6 with recombination is shown in red. All other hyperparameters E [0, 5] and к are shown as "alt. HP". l was set to mirror the y used for all other algorithms, and 20. A: The case where
i.e. the model has perfect information. B: When an ensemble of 3 CNNs was used.
A.2.4 CBAS
We implement the adaptive sampling algorithm proposed in Brookes et al. (2019). The parameters and the generator identical the DbAS implementation, see Section [A2.33 The difference here that, compared to DbAS cycle, where the top sequences in each cycle are selected based on the fitness predicted by the oracle, in CbAS cycle the sequences the reconstruction probability of the VAE) assigned to it by the generator trained on the ground truth data divided by the score assigned it by the generator trained on the all sequences proposed far.
weighted by the score (in this case
A.2.5 CMA-ES
We adapt the covariance matrix adaptation evolution strategy (CMA-ES) (Hansen & Ostermeier 2001] for the purpose of sequence generation. Let A be the product of the alphabet length and the sequence length. We initialize the mean value m E IR" of the search distribution to a zero vector, and the covariance matrix C pax= an identity matrix of the same dimension.
At every iteration, we propose À sequences, where À is equal to the batch size. We sample À x V sequences, where V is the virtual sereening ratio. Every sample x N(m, C) converted into one-hot representation of sequence by computing the argmax at each sequence position. A model provides a fitness value for the proposed sequence. Out of the top sequences (by fitness value) are returned to be evaluated by the oracle. Because the sampled sequences are continuous but the one-hot representations are discrete, we normalize m such that ||m||2 1 to prevent value explosion.
proposed samples, the
A.2.6 PPO
As sanity check for ensuring that DyNA-PPO implemented well, we also test proximal policy optimization (PPO) to train the policy network which selects the best action given state. The policy network is pretrained on ExV sequences, where B is the batch size and the virtual screening ratio. The remaining budget for evaluating sequences is then amortized among the remaining iterations that is, each sequence proposal step trades some of its evaluation power in order to train a stronger policy network in the beginning. In each iteration where propose sequences, we allow the agent to propose B x sequences, and take the top B sequences according to their fitnesses predicted by the model.
14

---

Under review as a conference paper at ICLR 2021
We use the TF-Agents library (Guadarrama et al. 2018 to implement the PPO algorithm. Our policy and value networks each consist of one fully collycoonecctd layer with 128 hidden units. Our results are consistent with those in Angermueller et al. (2020).
A.2.7 DYNA-PPO
We closely follow the algorithm presented in Angermueller et al. (2020). We perform 10 experiment rounds. In each experiment round, the policy network is trained on samples collected from an oracle. Fach model comprising an ensemble model is then trained on this data. The top models are retained in the ensemble, while the remaining models are removed. Initially, the ensemble model is composed of models with the same skles skleart rn architectures as in Angermueller et al. (2020) as well as several neural network architectures which we add. We compare models based on their cross- validaaiint score; top models cross a predetermined threshold (which we also set to be 0.5). We compute the cross-validation score via five-fold cross-validatio scored on the same section for each model.
The ensemble model serves approximate the oracle function. The mean prediction of all models in the ensemble is used to approximate the true fitness of a sequence. For each experiment round, we perform up to 20 virtual rounds of model-based optimization each sequence based on the outputs of this ensemble model. A model-based round is ended early if the ensemble model uncertainty (measured by standard deviation of individual model rewards) over twice high the uncertainty of the ensemble in the first model-based evaluation.
As mentioned in the main text, TRPO algorithms be sensitive implementation (Engstrom it al. 2019). To ensure that we build fair comparison, we implement variant of DyNA-PPO that uses a sequence generation process akin to evolutionary algorithms (which we call mutative), as well as one that follows closely to that of the paper (which we call constructive). In the first case, when proposing new sequence, the agent will begin a previously measured sequence and mutate individual residues until the reward (which is the fitness value of a sequence) is no longer increasing, or until the same move made twice (signalling that the agent thinks that no better action can be taken). In the constructive case in Angermueller et al. (2020), the agent will add residues onto an originally empty sequence until it reaches the desired sequence length, which is fixed beforehand. In this case, the step reward is zero until the last step is reached, in which case is the fitness value of the sequence. We find that the mutative version of the algorithm performs better than the constructive version, likely due to the rewards longer being sparse in the mutative setting.
Additionally, the DyNA- PPO algorithm as presented in Angermueller et al. (2020) trains the policy on of true fitnesses of sequences before entering the proposal loop. In our setting, all explorers allowed to make B queries to assess the true fitness of sequences, equal to the batch size of sequences proposed the end of a round. We further limit the computational queries difference with the original algorithm). No sopee-parramter tuning on held-out landscapes are done, as opposed to the original paper.
B samples (a
A.3 LANDSCAPES
A.3.1 RNA LANDSCAPES
To better clarify the structure of the RNA landscapes, and demonstrate their complexity, particularly of the Swampland fitness landscupes, we break down the components that go into them in Fig. A3. Even small landscapes of size 14 show this type of non-convexity that is seen in the figure. We pick sequences of interest: The max peak for hidden target 1, the max peak for hidden target 2, the starting position (termed wildtype), the top known sequence in the swampland landscape and the top sequence found by a model-free WF process. We then compute 30 direct (shortest mutational paths) between each pair of these sequences, and show their fitness on the landscape. It is clear that there is significant non-monotoy and permutations of order of mutations can change the shape of the trajectory. We believe that these landscapes enable appropriate challenge for sequence design algorithms, while enabling full information of ground tuuth (which can be queried quickly) and is consistent across the domain.
15

---

Under review as a conference paper at ICLR 2021
Sequence
Binding target
Top binding
Top binding
Wildtype
04
Top known
Top WF
Bindlng target 2
Proportion of maximum
0.0
1+2 Combined
Composite
Model estimate
Within training domain
Out training domain
0.
56
Pairwise (shortest path) walk
Figure A3: A tour of composite "Swampland" fitness landscape with sequence size 100 by direct walks between sequences of interest. Colored circles represent sequences significance. Each grey line is the fitness of walk from one sequence to another. Walks are defined as shortest paths between two sequences, and different walks between the same sequences represent different orders of making the same set of substitutions (30 walks shown for each pair). The x-axis shows the number steps between two sequences. The third panel shows the combined binding landscape of the first two panels (computed as /V1V2). The composite "Swampland" landscape has the same targets as the combined landscape, but is also subject to the constraint that 20/100 100 nucleotides cannot be mutated. We also train CNN 1000 mutants around the wildtype. The points underneath the plots represent the CNN's prediction of random samples from the paths. Cyan points show predictions within the
distance the training set (here of max distance 12), and black points are extrapolations outside that range. The model fits the in-domain samples with high accuracy (R²2 0.7), but often misses global structure, as be seen with the black points.
16

---

Under review as a conference paper at ICLR 2021
Batch size effects on performance (RNA L14)
B
Consistency without rollout (RNA L14)
1.0
Adalaud
099
0.9
6.7
0.8
0.7
58
0.6
Adsasdd 3-100
6.3
DynaFF
SynaPO..bei be100
0.
Figure A4: A: Effects of batch-size on ADALEAD, RNA landscape of length 14 and two hidden targets. The case where a 1, i.c. the model has perfect information. B: Ablation study for Adalead without ROLLOUT on the same landscape.
17


Reviews:
[{"review_id": "v6gj-Wtnmkh", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "The authors implement an open-source simulation environment FLEXS to emulate complex biological landscapes (TF binding landscapes) and to train and evaluate (RNA or protein) sequence design problems. ‘Swampland’ landscapes with large areas of no gradient, are also studied.\nThey also propose a simple greedy-search evolutionary algorithm, Adapt-with-the-leader (ADALEAD) that is shown to perform better than its competitors and to optimize in challenging settings. \n\nThe paper is well written and motivated and previous, relevant literature is discussed. \n\nComments: \n>> An important component of the environment and for ADALEAD is phi^prime. The paper mentions that this is fully supervised. How is one to come up with the appropriate\tphi_prime for a problem at hand. \n\n>> For the experiments, are the Ensembles always a 3-CNN model? Also, are the CNN architectures always the same?\n\n>> Can non-neural net architectures be used as ensembles? \n\n>> In the Figure 1A, it seems that the schema is iterative between the 4 layers shown by the arrows. Is this the case? If so, the iterative aspect is not mentioned clearly in the paper. \n\n>> What is EI in the Bayesian optimization subsection?", "extra_scores": {}, "extra_text": {}}, {"review_id": "aQD2wFcusP0", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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 greedy search approach for designing biological sequences in an active learning, batch setting. The algorithm is a fairly standard evolutionary algorithm which identifies the set of candidates at each iteration by adapting the best candidates from the previous iteration, and then evaluating those adaptations using a surrogate model. A set of experiments (using an evaluation sandbox also proposed by the authors for this work) suggest the proposed approach finds more high-quality solutions than competing approaches; however, especially in the experiments using the realistic/empirical surrogate model (an ensemble of 3 CNNs), the quality of the best solutions found by several approaches are statistically similar.\n\nAs promised by the authors, the proposed approach indeed appears rather straightforward to implement. Further, Table 1 does show that the proposed approach identifies more sequences which meet the specified criteria. To the best of my knowledge, the paper also places the work into context with respect to existing work.\n\nAs a non-expert approaching this paper, I find it very difficult to gauge the impact of the choice of the abstract and null models in the experiments. In particular, all of the results (and especially Table 1 and Figure 2B) suggest that the proposed approach is much better than the competition when using these models. On the other hand, when the ensemble is used as the surrogate model (e.g., Figures 2C(bottom) and 2D(left)), the performance of several methods become very similar.\n\nSince the methodological contribution of this work is rather limited (again, a pretty standard evolutionary algorithm), it is concerning to me that the strongest empirical results only arise in the settings based on these choices.\n\nConcerning the diversity of solutions found, in Table 1, it is not clear to me how meaningful the diversity measure (number of local optima with a score above the given threshold) actually is. Especially in cases where many solutions are found, it would be useful to also characterize the diversity of the sequences themselves, for example, by using BLOSUM or some other sequence similarity measure.\n\nOf course, actual wetlab validation demonstrating the superiority of the proposed approach would significantly strengthen the contribution.\n\nMinor comments\n----------------\n\nThe references are not consistently formatted.\n\nTable 1 should include some measure of variance.\n\nWhen introducing “optimization”, the authors rightly point out that, e.g., moderate binding may be preferable to stronger binding in some cases. However, they also suggest that the stronger binder has a better fitness. To me, this suggests the model for fitness is wrong and fits better with the “robustness” theme (since an accurate fitness model would have a parabola shape or some such in this example). It is also not clear to me whether any of the objective functions for the simulations capture this phenomenon.\n\nI found the description of the RNA ground truth simulation unclear.", "extra_scores": {}, "extra_text": {}}, {"review_id": "KapDfUxg_DA", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "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 addressed a critical issue on biological sequence design. It is an important task in biomedical research. The authors proposed an evaluation/simulation framework along with an evolutionary algorithm and showed the simple evolutionary algorithm \"AdaLead\" outperformed several existing methods. The paper is clearly written. \n\npros: \n1. Addressing an important issue. Sequence design and optimization are critical for many real-world problems, such as antibody optimization, etc. \n2. The authors have surveyed and tested many existing algorithms. They have also considered many settings such as DNA, RNA, and protein as well as \"swampland\" where the optimization landscape is flat. Experiments are done thoroughly.  \n3. Offered an open-sourced sandbox for model comparisons and proposed and evaluated a simple yet strong-performing evolutionary algorithm that should be used as a baseline in further works in this space.\n\ncons:\n1. First of all, although I appreciate a thorough investigation and comparison between existing methods and implementing an evolutionary algorithm as a strong baseline, it is, however, unclear to me the ML significance of this work to the ICLR community. It might be more suitable for a specific compbio venue. \n2. The authors proposed an evaluation framework where a noisy version of the oracle learned from sampling, $\\phi^{'}$, could be obtained. Although this is a valid and reasonable framework, it is not fully in line with other algorithms' assumptions. For example, DbAS and CbAS are more conservative and exploring locally by generating a new batch of sequences that are similar to the best performing one in the previous batch. This can be also a valid approach as the extrapolation might be very bad. Moreover, the authors tuned AdaLead on their proposed evaluation framework and claimed it is not sensitive to parameters, I do not see any results regarding this matter.  In short, I suspect the evaluation framework proposed here is biased towards a simple evolutionary algorithm that does not even use much information (as AdaLead outperforms other more complicated evolutionary algorithms in fig A1B). \n3. Related to 2, there is a lack of exploration to understand why AdaLead is outperforming. What could we learn from this result? \n\nminor:\n1. The authors talked about batch size issues in the paper. Could they give more details or some results on this? \n2. Some of the figure labels can be improved. There are some acronyms likely not familiar to computer scientists with little biological background left unexplained, such as \"w.t.\" in fig 1B.", "extra_scores": {}, "extra_text": {}}, {"review_id": "AAO5_cMhOR8", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "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": "The authors introduce a new algorithm AdaLead to solve the problem of efficient design of biological sequences and FLEXS, an open-source simulation environment for sequence design. \n\nThe structure of this paper is somewhat unconventional, the paper would benefit from more rigor and structure. There are 4 sections, the method section which is the section that contains the novel part (section 2) is a fairly short section (less than 2 pages). The experimental setting is crammed together with the results. So, the details of the outcome of the experiments are lost in the various implementation details. The experimental setting can be moved in a section where the authors talk about the benchmarks alone. Or perhaps in the appendix.  The authors talk about the contributions at the very end of the paper. A reader wants to know what the contributions of the paper are in the introduction section. It wasn't very clear for example that FLEXS was the main contribution of this paper until the very last section. FLEXS was barely mentioned at the beginning of the paper. \n\nThe second contribution of the paper according to the authors is the novel algorithm AdaLead. This evolutionary algorithm is poorly explained. How are the recombine and mutate operators defined for example? In addition, this algorithm seems simplistic and I'm not sure we can call this algorithm a novel contribution. The authors should make more explicit why is this evolutionary algorithm a novelty, how does that improve wrt EAs? \n\nThe authors dismiss the use of Bayesian optimization by saying that BO doesn't perform well on high-dimensional space and citing a tutorial by Frazier 2018 that says that usually BO is used on problems that have less than 20 dimensions. I'm not entirely sure why this is a problem for this work where Table 1 shows that the applications considered have a few variables only, up to 14 if I understand correctly. In addition, some BO frameworks such as SMAC (https://www.automl.org/automated-algorithm-design/algorithm-configuration/smac/)  were used on problems with more than 100 variables. \n\nThe authors compare against BO by implementing a BO algorithm based on EI and an evolutionary sequence generator. While it is not clear what this means, this is surely an uncommon BO algorithm. Why didn't the authors use one of the standard BO packages available? The experimental results are unsatisfactory without a proper BO comparison. \n\nFinally, I question the interest of the ICLR audience for this type of study. While the paper would follow in the track: \"applications in audio, speech, robotics, neuroscience, computational biology, or any other field\" I found the algorithm being a specific application of a simplistic search algorithm to the domain of sequence design. What are the lessons learned? Is there any general insight that became available from this study? The improvement wrt to SOTA is shaky. \n\nMinor remarks: \n- Figure 2 is not cited in the text. \n- CMA-ES is not introduced - even if the CMA-ES is a popular algorithm it should be properly introduced.\n- Model-free evolution in Figure 2 is not introduced. What is that algorithm about? \n- Figure 2, I'm not sure what is the y-axis in the performance plot. In these types of papers, we usually show simple regret or similar performance quantities. It seems that the y-axis is the higher the better and that 1 is the max achievable? \n- Figure 2 should give a better understanding of what the figure means and what are the methods that perform best by writing about that in the text of the paper. \n- Not clear to me why the queries to the surrogate model are sample-restricted. This is an uncommon setting in Bayesian optimization where usually the budget is restricted for the evaluation of the latent black-box function.  \n- Not entirely clear what the role of the cardinality |S| in the optimization is. Is this an optimization with unknown feasibility constraints problem formulation? \n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers the problem of (biological) sequence design and optimization. The authors made an interesting yet important case that in certain sequence design tasks, a simple evolutionary greedy algorithm could be competitive with the increasingly complex contemporary black-box optimization models.

Most reviewers appreciate the design of the open-source simulation environment in benchmarking AdaLead (and other competing algorithms) in a number of biological sequence design tasks (e.g. TF binding, RNA, and protein). However, there is a common concern that the experimental results are not fine-grained enough to explain the outperforming results of the proposed algorithm. There are also unresolved comments on missing important BO baselines in the empirical study. As a purely empirical work, these appear to be important concerns. While these results appear to be useful for the domain of biological sequence design, the reviewers are unconvinced that the proposed algorithm is significantly novel, or the results are sufficiently compelling to merit an acceptance to this venue.

Decision: Reject