Population-Based Black-Box Optimization for Biological Sequence Design

1. Introduction

• Sequence design is challenging because the discrete search space is exponentially large, wet-lab evaluations are costly, and downstream screening benefits from diverse high-quality candidates.Modern experiments can evaluate hundreds to thousands of sequences in parallel, and in-silico problems can support ML-method development without wet-lab trials.Source: §1 · p. 1
• Existing methods are sensitive to hyperparameters, can excel on some problems but fail on others, and often waste batch capacity on similar sequences.Figure 1 illustrates an inverted baseline-method ranking on the seemingly similar PdbIsing and PfamHMM problems.Source: §1 · p. 1, Figure 1 · p. 2
• P3BO samples sequences from a portfolio of algorithms, allocating each algorithm’s budget according to the quality of its prior proposals and sharing acquired samples across algorithms.Its heterogeneous population combines global model-based optimizers using discriminative and generative models with evolutionary strategies; Adaptive-P3BO further tunes member hyperparameters through evolutionary search.Source: §1 · pp. 1–2
• Across over 100 batched problems, P3BO and Adaptive-P3BO are more robust, generate more diverse batches, and find distinct optima faster than any single population method; Adaptive-P3BO also improves on P3BO and recovers from poor initial populations.The evaluation uses in-silico optimization problems.Source: §1 · p. 2
• The paper introduces in-silico design problems for benchmarking and identifies poor generalization across similar problem classes and suboptimal use of large wet-lab batch sizes as shortcomings of existing methods.P3BO is presented as a framework for discrete batched black-box optimization that ensembles algorithms to hedge against brittleness and improve diverse sequence discovery.Source: §1 · p. 2

2. Problem Setting and Motivation

• Sequence design maximizes an objective f over batches of sequences, with batch size B and only a limited number T of evaluation rounds.Sequences are length-L strings over a finite vocabulary V; variable-length sequences are padded with an end-of-sequence token.Source: §2 · p. 2

2.1. Algorithm Requirements

• Algorithms expose fit(X, Y) and propose() interfaces, and fitting must use data from other algorithms, excluding on-policy RL methods.An algorithm instance is a method class with a specific hyper-parameter configuration.Source: §2.1 · p. 2

2.2. Robustness of Black-Box Optimizers

• P3BO performs at least as well as the best algorithm in its population and often exceeds it, while existing methods reverse rank across PDBIsing and PfamHMM.MBO performs well and DbAs-VAE struggles on PDBIsing; their relative performance reverses on PfamHMM. Figure 2 shows P3BO allocating batch fractions by past proposal quality, with Adaptive-P3BO also adapting algorithm hyper-parameters by evolutionary search.Source: §2.2 · pp. 2–3, Figure 2 · p. 3

3. Population-Based Optimization for Batched Sequence Design

• P3BO combines heterogeneous optimization algorithms to propose sequence batches, sharing observations so their distinct exploration strategies can benefit one another.Source: §3 · p. 3

3.1. Method Summary

• Each round, P3BO samples algorithms categorically to propose a batch of unique sequences, evaluates it, updates sampling probabilities, and refits every algorithm on accumulated data.The fitting step is algorithm-specific and may involve time-consuming model fitting.Source: §3.1 · p. 3

3.2. Selecting from a Population of Algorithms

• Sampling favors algorithms with better past sequences, using exponentially decayed rewards to favor consistent improvement; experiments define reward as improvement over the best value from prior rounds.Because algorithms share observations, sequence qualities are correlated. The decay rate balances past and present gains, while the softmax temperature controls exploration–exploitation; the authors suggest novelty search as a future alternative reward.Source: §3.1 · p. 3, §3.2 · pp. 3–4

3.3. Adaptive Population-Based Optimization

• Adaptive P3BO addresses performance ceilings from suboptimal in-population hyperparameters by evolving them online through survivor selection, tournament-selected parents, crossover, and mutation.When parent algorithms have incompatible hyperparameters, one parent is chosen randomly; mutation resamples values from a prior or scales them.Source: §3.3 · p. 4

ML for Sequence Design

• Generative sequence-design methods maximize expected objective value by training a parameterized distribution on high-reward sequences, a process viewed as cross-entropy optimization (De Boer et al., 2005; Neil et al., 2018; Brookes & Listgarten, 2018; Gupta & Zou, 2018; Brookes et al., 2019).The next batch is sampled from the updated distribution.Source: §4 · p. 4
• Model-based optimization uses a discriminative surrogate to approximate the objective and an acquisition function to propose sequences (Hashimoto et al., 2018; Wang et al., 2019; Yang et al., 2019; de Jongh et al., 2019; Liu et al., 2019; Sample et al., 2019; Wu et al., 2019b; Biswas et al., 2020).Surrogates are cheaper to evaluate than wet-lab objectives, and their structure or gradients can guide acquisition optimization; methods vary in surrogate, acquisition, and acquisition optimizer, including expected improvement.Source: §4 · pp. 4–5
• Angermueller et al. (2020) proposed a hybrid sequence-design approach that updates a generative policy with model-based RL when its surrogate is accurate and model-free RL otherwise.Source: §4 · p. 5

Population-Based Optimization

• P3BO is a high-level ensemble that combines heterogeneous algorithm families, unlike low-level ensembles of instances from one algorithm class.Prior non-batched ensembles include multi-strategy methods, portfolio algorithms, and hyper-heuristics.Source: §4 · p. 5
• Adaptive operator selection assigns credit from past rewards and selects algorithms accordingly, but unlike weighted-majority bandits, each action affects other algorithms’ later rewards (Maturana et al., 2009; Fialho et al., 2010; Li et al., 2013; Wu et al., 2019a; Littlestone et al., 1989).Credit strategies include average reward, relative reward improvement, and sum of ranks.Source: §4 · p. 5
• Evolutionary reinforcement learning combines homogeneous agents in non-batched continuous parameter-space optimization (Pourchot & Sigaud, 2018; Khadka & Tumer, 2018), while PBT optimizes network weights and hyperparameters on static training data (Jaderberg et al., 2017).AlphaStar applies PBT to evolve agents in multi-agent RL.Source: §4 · p. 5

5. In-Silico Benchmarking Problems

• The suite includes exhaustive small-space measurements, regressors trained on experimental data, random-weight neural networks, and statistical protein-evolution models.The problems also vary in search-space size, the number of initial samples, and sensitivity to shifts, insertions, and deletions.Source: §5 · p. 5
• DNA benchmarks maximize measured length-8 transcription-factor binding, predicted length-10 binding (Le et al., 2018), or predicted expression from length-50 5’UTRs.TfBind8 uses exhaustive measured binding scores; TfBind10 uses predicted relative affinities for two targets, and UTR uses a CNN expression predictor.Source: §5 · p. 5
• RandomMLP/RandomRNN tasks maximize scalar outputs of randomly initialized fully connected or recurrent neural networks, following Brookes & Listgarten (2018).Source: §5 · p. 5
• Protein benchmarks optimize PfamHMM likelihood, ProteinDistance embedding similarity, and PDBIsing energy.PfamHMM likelihoods are based on curated seed sequences and a random initial subset below the 50th percentile (El-Gebali et al., 2018; Finn et al., 2011). ProteinDistance uses cosine similarity to Pfam-family representatives (Bileschi et al., 2019); PDBIsing maximizes structure-parameterized Ising energy with extra emphasis on long-range interactions (Angermueller et al., 2020; Berman et al., 2003).Source: §5 · pp. 5–6
• P3BO and Adaptive-P3BO outperform or are comparable to all other baselines in area-under-Max-reward-curve rankings across the optimization problems.Table 1 reports mean ranks over instances per problem; higher is better.Source: Table 1 · p. 6

6.1. Baseline Optimization Methods

• The population comprised N = 15 constituent algorithms: SMW, MBO with varied regressors, acquisition functions and mutation rates, DbAs with varied generative models and quantile thresholds, and Evolution with varied mutation and crossover probabilities.SMW proposes all single-mutation neighbors of the best sequence each round (Wu et al., 2019b); Evolution selects top k sequences, recombines, and mutates them (unter Rudolph, 1958; Brindle, 1980).Source: §6.2 · pp. 6–7, §6.1 · p. 6

6.2. Population-Based Optimization

• P3BO samples its 15 constituent algorithms according to prior sequence quality, with at least one member per class and at most four MBO instances.Its population includes variants of SMW, MBO, DbAs, and Evolution; Adaptive-P3BO additionally evolves population members online.Source: §6.2 · pp. 6–7

6.3. Evaluation of Sample-Efficiency and Robustness

• Across 105 optimization problems, P3BO and Adaptive-P3BO are systematically more sample-efficient than any baseline; adaptation further improves performance in most problem classes.P3BO matches or outperforms its best ensemble member, and no non-population method performs best across all problems.Source: Figure 4 · p. 7, §6.3 · p. 7
• Sample efficiency is measured by cumulative maximum reward against samples proposed and summarized by area under the curve; experiments use 20 random seeds.The study compares mean optimization trajectories across problem classes.Source: §6.3 · p. 7

6.5. Ablation Experiments

• Adaptive-P3BO increases sampling from the high-performing DbAs-VAE class and expands its population instances from 4 to 11 in the illustrated PfamHMM task.The same behavior was observed on other optimization problems.Source: Figure 5 · p. 8, §6.5 · p. 9

6.4. Evaluation of Diversity

• P3BO and Adaptive-P3BO maintain diverse batches and find diverse high-reward sequences, locating more TfBind8 optima than MBO.They find sequences across nearly all clusters identified by baseline methods.Source: Figure 7 · p. 8, §6.4 · p. 8, Figure 6 · p. 8

6.5. Ablation Experiments

• Data sharing lets weaker algorithms learn from stronger ones, while Adaptive-P3BO recovers faster than P3BO from a poorly initialized population.Ablations also examine sensitivity to scoring function, softmax temperature, population size, and batch size.Source: §6.5 · p. 9

7. Conclusion

• Across extensive novel in-silico benchmarks, standard ML sequence-design approaches lack robustness, while P3BO’s algorithm ensemble improves sample-efficiency, robustness, and discovery of diverse optima.P3BO is motivated by biological sequence design but is also applicable to non-biological black-box optimization problems.Source: §7 · p. 9
• Online adaptation of the algorithm population in Adaptive-P3BO further improves performance.Source: §7 · p. 9
• Efficient selection of the initial algorithm population and transfer learning across optimization problems remain crucial open questions.Source: §7 · p. 9

A. In-Silico Design problems

• RandomMLP and RandomRNN use sequence lengths of 20 or 40, PfamHMM and ProteinDistance range from 50 to 100, and only PfamHMM provides 500 initial samples.All other problems do not provide initial samples.Source: Table 1 · p. 12
• Instances vary the protein target for PDBIsing, PfamHMM, and TfBind, or the neural-network architecture and weight-initialization seed for RandomMLP and RandomRNN.Table 1 reports the number of instances per problem alongside optimization rounds, batch size, vocabulary size, sequence length, and initial-sample count.Source: A. In-Silico Design problems · p. 12, Table 1 · p. 12

A.1. TfBind

• TfBind defines 12 optimization problems that maximize transcription-factor binding affinity for length-8 DNA sequences.The targets include CRX, NR1H4, HOXD13, GFI1B, FOXC1, PAX4, POU6F2, and SIX6 variants.Source: §A.1 · p. 12
• TfBind10 uses length-10 sequences and the experimentally characterized transcription factors Cbf1 and Pho4 (Le et al., 2018).It differs from TfBind8 in sequence length and available transcription factors.Source: §A.1 · p. 12

A.2. Random Neural Network

• Random Neural Network tasks optimize a randomly initialized network’s scalar output over 10 rounds with batches of 100 sequences.Instances vary sequence length (20 or 40), vocabulary size (4 or 20), random seed (0 or 13), and network architecture.Source: §A.2 · p. 12
• RandomMLP varies convolutional and fully connected layers, while RandomRNN varies the number of LSTM layers.RandomMLP uses either no convolution or one 128-unit convolution with kernel width 13 and stride 1, and either one 128-unit or three 128-, 256-, and 512-unit fully connected layers; RandomRNN uses one, two, or three LSTM layers with 128, 256, and 512 hidden units respectively.Source: §A.2 · p. 12

A.3. PfamHMM

• PfamHMM optimization uses fixed-length sequences set to the median length of unaligned domains in each family’s Pfam-full alignment.Its initial dataset samples 500 sequences with HMM likelihood below the 50th percentile from family sequences of that length.Source: §A.3 · pp. 12–13
• The PfamHMM experiments use families with relatively short sequences; longer sequences with only a subset of positions optimized are left for future work.Source: §A.3 · p. 13

A.4. ProteinDistance

• ProteinDistance seeks sequences with high embedding-space cosine similarity to target sequences chosen from Pfam HMM seed sequences.Embeddings come from a Pfam-family classifier network whose protein features have been shown useful for few-shot learning (Bileschi et al., 2019); the task uses the same Pfam families as PfamHMM.Source: §A.4 · p. 13

A.5. PDBIsingModel

• PDBIsingModel defines 10 protein optimization problems using structural contacts and residue-coupling scores, with local terms based on the true PDB sequence.Contacts are Cα atom pairs separated by less than 8 Angstroms; the coupling block uses global contacting-residue co-occurrence probabilities, and local scores use log Blosum substitution probabilities (Berman et al., 2003).Source: §A.5 · p. 13

B.1. Model-Based Optimization

• MBO averages regressors with cross-validated explained variance ≥0.4 and uses posterior mean acquisition optimized by evolutionary search to select top-scoring unique, novel sequences.Regressor hyper-parameters are selected by randomized search; acquisition search runs for 500 rounds with batch size 25. Posterior mean performed as well as or better than UCB, expected improvement, or probability of improvement.Source: §B.1 · p. 13

B.2. Latent-Space Model-Based Optimization

• Latent-space optimization jointly trains a VAE and reward regressor, then retrains an ensemble regressor and applies cross-entropy search with prior-likelihood reweighting to limit drift from training data.This extends encoder-decoder optimization to multiple rounds using observed sequence-reward pairs; the prior is a diagonal multivariate Gaussian fit to VAE and regressor training data (Brookes et al., 2019).Source: §B.2 · pp. 13–14

B.3. Evolution; Evolution

• Evolution repeatedly selects tournament-based parents, recombines and mutates children, and retires old samples from parent selection to prevent elite domination.Crossover probability is 0.1 and mutation probability is 0.01 in the described setup; P3BO samples these probabilities from uniform intervals of 0.1–0.3 and 0.05–0.2, respectively.Source: §B.3 · p. 14, Evolution · p. 14

B.4. DbAs-VAE; DbAs-VAE

• DbAs-VAE uses a one-hidden-layer encoder-decoder with 64 units and 32 latent vectors, trained for 60 epochs, while P3BO samples VAE unit counts from 64 or 128.The setup uses learning rate 0.01, batch size 20, and quantile cutoff 0.85; P3BO samples the cutoff from 0.825–0.975 and learning rate from 0.008–0.012 on a log scale.Source: §B.4 · p. 14, DbAs-VAE · p. 14

B.5. DbAs-RNN; DbAs-RNN

• DbAs-RNN matches DbAs-VAE except for a one-layer, 128-unit LSTM generator; P3BO samples LSTM size as 64 or 128 and tunes acquisition function and regressor choices.P3BO samples the quantile cutoff from 0.9–0.975 and learning rate from 0.0005–0.012 on a log scale; acquisition choices are PosteriorMean or UCB, and regressors are Ensemble or BayesianRidge.Source: §B.5 · p. 14, DbAs-RNN · p. 14

B.6. FBGAN

• FBGAN uses a Wasserstein GAN within cross-entropy optimization and a quantile cutoff, tuning generator, discriminator, gradient-penalty, temperature, and latent-variable settings.The quantile cutoff performed better than a fixed threshold across the reported diverse problems.Source: §B.6 · p. 14

B.7. P3BO

• P3BO uses a population of 15 comprising MBO, DbAs-VAE, DbAs-RNN, Evolution, and SMW; SMW is hyper-parameter free.A smaller population above five can achieve similar performance. P3BO samples hyper-parameters for its constituent algorithm classes from specified distributions.Source: §B.7 · p. 14

• For enumerative TfBind8, the fraction of optima found counts exact matches to cluster representatives preselected at reward ≥0.9 using edit distance 3, treating forward and reverse sequences as distinct.Unlike the high-reward-cluster metric, it normalizes by the total number of clusters and uses edit distance to group similar motifs at different positions.Source: C. Diversity metrics · p. 15

D. Additional results

• P3BO finds significantly more diverse and higher-reward sequences than MBO and SMW, while DbAs-VAE and Evolution are more diverse but achieve lower reward.The comparison covers PdbIsing, ProteinDistance, TfBind8, and UTR; the figure describes P3BO as a good trade-off between reward and diversity.Source: Figure 1 · p. 16
• On UTR, Evolution’s early relative-improvement credit leads Adaptive-P3BO to sample more Evolution sequences and increase its instances from 4 to 11 after three warm-up rounds.The total population size is 15.Source: Figure 4 · p. 18
• Removing MBO lowers P3BO performance on PdbIsing, and removing best-performing DbAs-VAE lowers it on PfamHMM; sharing samples improves individual methods, including SMW after MBO finds high-reward sequences.The comparison includes P3BO with its full population and variants with one algorithm removed, as well as stand-alone and data-sharing runs.Source: Figure 5 · p. 19
• On PdbIsing, methods without sample sharing propose distinct sequences and only MBO quickly finds high-reward sequences; with sharing, methods benefit from MBO’s discoveries and propose similar sequences.The t-SNE visualization uses PDB structure 1KDQ.Source: Figure 6 · p. 20
• Adaptive-P3BO recovers from a poorly initialized algorithm population through online adaptation, producing a clear performance improvement over P3BO.Source: Figure 7 · p. 21
• Relative-improvement and rank-based reward functions perform similarly across problems; additional curves compare relative-improvement scoring with random scoring for P3BO and Adaptive-P3BO.Source: Figure 8 · p. 21, Figure 9 · p. 22
• On PfamHMM, ProteinDistance, and UTR, sampling proportional to credit scores with τ < 10 outperforms uniform sampling with τ ≥ 10; population size 15 is best on average, though smaller populations perform similarly.Using only one algorithm (N = 1) causes a clear performance decrease.Source: Figure 10 · p. 22, Figure 11 · p. 23
• P3BO is applicable across batch sizes, including non-batched optimization; additional performance curves cover RandomMLP, TfBind10, and the FBGAN and DbAs-RNN baselines.The RandomMLP and TfBind10 curves average over available targets, while the baseline curves average over instances; shaded areas show 95% bootstrap confidence intervals.Source: Figure 2 · p. 17, Figure 3 · p. 17, Figure 12 · p. 23