Source-linked AI summary
AdaLead: A simple and robust adaptive greedy search algorithm for sequence design
Sam Sinai, Richard Wang, Alexander Whatley, Stewart Slocum, Elina Locane, Eric D. Kelsic
TL;DR
Biological sequence design is difficult because fitness landscapes are non-convex and sparse, while experiments permit only a handful of learning iterations. The paper evaluates model-guided exploration in FLEXS and introduces AdaLead, a simple greedy algorithm. Across attempted landscapes, AdaLead outperforms other algorithms and is reported to be robust and consistent as model performance improves.
Problem
Sequence design seeks biological sequences with desired function despite non-convex, sparse fitness landscapes and limited experimental iterations.
Source: §1 · pp. 1–2Method
Results
Takeaways & Limitations
The authors conclude that simple evolutionary algorithms are strong benchmarks for sequence-design methods.
Source: §4 · p. 8In online batch settings, larger batches are expected to incur a performance penalty because proposed sequences do not receive intervening model updates.
Source: §4 · p. 9
Abstract
from arXiv · showhide
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: github.com/samsinai/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.
1 Introduction
Biological sequence design seeks sequences with desired function despite a non-convex, sparse fitness landscape and costly experimental rounds. The paper frames model-guided exploration as a black-box optimization problem and introduces AdaLead as an accessible baseline for evaluating such algorithms.
1 Introduction
- Sequence design is difficult because fitness landscapes are non-convex and sparse across a sequence space that grows exponentially with sequence length.Directed evolution selects populations through assays, but its random mutations are often discarded because they reduce function.Source: §1 · p. 1
- Model-guided design uses surrogate models to screen sequences before synthesis, but labor-intensive experiments allow only a handful of learning iterations.The task is framed as proposing serial batches to find the best sequence over the course of experiments.Source: §1 · p. 2
1.1 Related work
- The study focuses on exploration algorithms that use surrogate models, rather than improving surrogate accuracy or addressing semi-supervised and transfer-learning approaches.The exploration setting may allow sample selection with data arriving in batches.Source: §1 · p. 2, §1.1 · p. 4
1 Introduction
- AdaLead is proposed as a simple, model-guided greedy algorithm and an accessible baseline for testing sequence-design methods.The authors evaluate algorithms in FLEXS using criteria relevant to biological applicability and algorithmic soundness.Source: §1 · p. 2
- The evaluation criteria include optimization, robustness to poor models, consistency as model quality improves, and a narrowly defined measure of diversity.The paper notes that diversity metrics can be ambiguous and limits its focus to a narrow sense of diversity.Source: §1 · p. 2
1.1 Related work
- Bayesian optimization, regularized generative models, and reinforcement learning provide comparison approaches, with DbAS, CbAS, and DyNA-PPO used as representatives.The paper notes that policy-gradient methods can be complex to implement and sensitive to implementation choices.Source: §1.1 · pp. 3–4
2 Methods
AdaLead selects strong measured sequences as seeds, then mutates and recombines candidates using a surrogate model to choose the next batch. Its threshold adapts search behavior to the fitness landscape, while the paper also uses controlled abstract models and trainable sequence models to study exploration.
2 Methods
- AdaLead is an easy-to-implement, reproducible greedy algorithm that seeds from strong measured sequences, iteratively generates candidates, and proposes the surrogate-ranked top batch.Seeds fall within a threshold of the highest observed fitness; candidates are retained when the surrogate predicts improvement over their seed.Source: §2 · p. 4
- The authors model recombination and mutation rates and the threshold as hyperparameters, reporting fairly robust performance for threshold κ and recombination rate r below 0.5.They report that recombination's performance gain in AdaLead is small.Source: §2 · p. 4
- A fixed threshold makes AdaLead adaptive: flatter landscapes admit more seeds and diversity, while prominent peaks prompt faster climbing from the best-known samples.Rollouts mutate candidates until their predicted fitness falls below the starting candidate's prediction.Source: §2 · p. 4
- A noise-corrupted abstract surrogate enables controlled comparisons of exploration algorithms independently of oracle quality, with α varied to study consistency and robustness.The null model is the α = 0 special case; its predictions are sampled from an exponential distribution based on average measured fitness.Source: §2 · p. 5
- The authors also validate AdaLead with trainable sequence models, including linear, random-forest, Gaussian-process, and neural-network regressors.They recommend an ensemble; the reported representative empirical model is an ensemble of three CNNs, with estimates reweighted according to previous-batch prediction performance.Source: §2 · p. 5
3 Experiments
Across the tested RNA landscapes, ADALEAD outperformed the other algorithms, while TF binding landscapes were comparatively easy to optimize. The experiments also examine performance across model quality and sequence-design settings.
Experimental considerations
- The authors prefer ground-truth simulators that remain consistent as search moves away from the starting sequence, since empirical-data models may become pathological outside local contexts.They note that no general algorithm can optimize arbitrary landscapes, and even hill-climbing may require exponentially many samples to find local optima.Source: §3 · pp. 5–6
Experiments
- The experiments span known-optimum and more complex tasks, including TF binding, RNA binding, and protein design.The protein-design task used PyRosetta to optimize a 66-amino-acid antifreeze protein from five starting sequences.Source: §3 · pp. 6–7
TF binding landscapes
- Algorithms performed similarly well on the sampled TF binding landscapes, suggesting these landscapes were relatively easy to optimize.The experiment sampled five landscapes and used 13 fixed random initial sequences per landscape.Source: §3 · p. 6
RNA landscapes
- ADALEAD outperformed the other algorithms across attempted RNA landscapes, including highly epistatic settings with many local peaks.The tested RNA sequences ranged from length 14 to 100.Source: §3 · p. 6
- Across five landscapes with 13 initializations each, ADALEAD more consistently found high-performing peaks, regularly reaching the global optimum on RNA14_B1 and outperforming alternatives on RNA14_B1+2.RNA14_B1 has 2925 local peaks; the two-target RNA14_B1+2 landscape has 806.Source: §3 · p. 7
- Some algorithms climbed faster in the first batches, but none surpassed ADALEAD over the longer horizon; it also performed well with an uninformative model.Its relative ranking remained similar when CNN ensembles were used.Source: §3 · p. 7
4 Contributions and Future directions
The paper contributes FLEXS for sequence-design research and introduces ADALEAD as a simple evolutionary algorithm. It also identifies important properties and improvements that remain outside the study’s evaluation.
4 Contributions and Future directions
- FLEXS provides an open-source sandbox for simulating complex biological landscapes, including rarely explored Swampland landscapes with large areas of no gradient.It also provides interfaces for protein design using trained black-box oracles, which the paper does not study.Source: §4 · p. 8
- An abstracted oracle enables empirical study of exploration strategies independently of the underlying models, supporting analysis of algorithm robustness and consistency.Source: §4 · p. 8
- ADALEAD robustly optimizes challenging settings and performs better as model performance improves, making simple evolutionary algorithms strong benchmarks.The authors describe ADALEAD as competitive with current state-of-the-art methods.Source: §4 · p. 8
- The study does not directly evaluate how variation in virtual-screen size, independence, or batch adaptivity affects algorithm behavior.For a fixed total number of proposed sequences, larger batches are expected to incur a performance penalty because models are not updated within a batch.Source: §4 · p. 9
- Potential ADALEAD improvements include enriching its recombination-based generator with generative models; studied algorithms could also use information about the remaining horizon.Source: §4 · p. 9
A.1.1 Noisy oracle
The noisy-oracle setup varies model accuracy to examine algorithm consistency and robustness. The paper describes a distance-dependent noise construction and tests it on an RNA landscape.
A.1.1 Noisy oracle
- The noise construction uses distance from the closest measured neighbor and samples ε from an exponential distribution whose rate parameter is the oracle value at that neighbor.The authors report qualitatively similar results when ε is instead sampled from the empirical distribution of known mutants.Source: §A.1.1 · p. 12
- The noise-corrupted oracles support testing algorithm consistency and robustness, with performance examined as α varies on RNA14_B1.The comparison also includes empirical CNN ensembles trained on 100 random mutants at varying distances from wild type.Source: §A.1.1 · p. 12
A.1.2 Empirical models
The sandbox includes linear and neural empirical models, with an adaptive ensemble of CNNs serving as the strongest empirical model attempted in the paper.
A.1.2 Empirical models
- The empirical-model suite includes linear regression, random forests, a global-epistasis network, and a convolutional neural network.The global-epistasis network uses a linear unit, two 50-unit ReLUs, and a final linear unit.Source: §A.1.2 · p. 12
- The CNN is often the most accurate model, and an adaptive ensemble of three CNN initializations is the strongest empirical model attempted.Adaptive ensemble weights are proportional to each model’s R2 on data generated in the previous step; the gain from ensembling is often small.Source: §A.1.2 · p. 12
A.2.1 Bayesian Optimization
The appendix compares enumerative GP-based Bayesian optimization with an evolutionary alternative. The latter is used in the main paper because it scales to larger sequence spaces and is competitive with or better than the enumerative methods on TF landscapes.
A.2.1 Bayesian Optimization
- Enumerative GP-based BO uses a Gaussian-process regressor and EI, UCB, or Thompson sampling to select batches from fully enumerated TF landscapes of 48 sequences.The authors note that this approach scales poorly and cannot accommodate larger RNA or protein sequence spaces.Source: §A.2.1 · p. 12
- Evolutionary BO is competitive with or better than the enumerative BO algorithms attempted on TF landscapes, and is therefore used in the main paper.Source: §A.2.1 · p. 12
- Evolutionary BO samples mutants from a state sequence, extends candidates using EI or UCB, then selects a batch by Thompson sampling and updates the state to the top predicted sequence.Mutation probability is 1/L; candidate extension stops at a variance threshold or the virtual-screen limit.Source: §A.2.1 · p. 12
- Figure A1A compares GP-based BO with full sequence-space enumeration against evolutionary BO on a TF binding landscape.Source: Figure A1 · p. 13
A.2.2 AdaLead
ADALEAD is fairly robust to the tested hyperparameters; recombination offers small benefits, and ADALEAD is roughly equivalent to model-guided Wright–Fisher while outperforming several other evolutionary benchmarks.
A.2.2 AdaLead
- ADALEAD is roughly equivalent to model-guided Wright–Fisher, while consistently outperforming model-free evolution, CMA-ES, and Evolutionary BO.The authors note that ADALEAD follows the same hill-climbing principle as model-guided Wright–Fisher but is faster to compute and less memory intensive.Source: §A.2.2 · p. 13
- Recombination provides small gains in optimality and finding diverse peaks, with most benefit below rate 0.3.Above 0.3, stochastic effects tend to be detrimental with noisier models.Source: §A.2.2 · p. 13
- The comparison uses recombination rate 0.2, mutation rate 1/L, and threshold τ = 0.05.The authors chose mutation rate 1/L to accommodate simpler models and maintain uniformity across algorithms; thresholds below 0.05 tend to leave too few seeds.Source: §A.2.2 · p. 13
- ADALEAD is fairly robust to recombination rate, mutation rate, and threshold choices.The threshold begins to be effective below 0.5, but becomes too restrictive below 0.05.Source: §A.2.2 · p. 13
A.2.3 DbAS
This block describes implementations of comparison algorithms and the construction and properties of RNA landscapes. The landscapes include non-monotonic paths and can challenge sequence-design algorithms while retaining accessible ground truth.
A.2.3 DbAS
- DbAS trains a VAE on known-fitness sequences, repeatedly selects high-scoring sequences, and samples new sequences from the latent-space Gaussian until convergence or budget exhaustion.Each cycle selects the top 20% by oracle score; generated sequences are selected using the stricter of the top-20% cutoff and the previous batch’s 80th-percentile fitness.Source: §A.2.3 · p. 13
A.2.4 CbAS
- CbAS weights sequences by their generator reconstruction probabilities under the ground-truth-trained and proposed-sequence-trained generators.The weights use the score from the generator trained on ground-truth data divided by the score from the generator trained on all sequences proposed so far.Source: §A.2.4 · p. 14
A.2.5 CMA-ES
- CMA-ES samples λ × V continuous candidates, converts them to one-hot sequences, and returns the top λ by model fitness for oracle evaluation.The search-distribution mean is normalized to ∥m∥2 = 1 to prevent value explosion.Source: §A.2.5 · p. 14
A.2.6 PPO
- PPO is tested as a sanity check for DyNA-PPO implementation, with a pretrained policy proposing B × V sequences and selecting the top B by model fitness.The remaining evaluation budget is amortized over later iterations after policy pretraining.Source: §A.2.6 · p. 14
A.2.7 DyNA-PPO
- The mutative DyNA-PPO variant performs better than the constructive variant, likely because rewards are less sparse in the mutative setting.The mutative version starts from a measured sequence and changes residues; the constructive version adds residues to an empty sequence and receives reward only at the final step.Source: §A.2.7 · p. 15
A.3.1 RNA Landscapes
- RNA landscape walks are significantly non-monotonic, and mutation order can change their fitness trajectories.The authors present 30 shortest mutational paths between each pair of six sequences of interest and describe the landscapes as challenging while providing quickly queryable ground truth.Source: §A.3.1 · p. 15, Figure A3 · p. 16
- A CNN trained on 1,000 wildtype mutants fits in-domain samples with R2 > 0.7 but often misses global structure beyond that range.The figure distinguishes predictions within the training-distance range from extrapolations outside it.Source: §A.3.1 · p. 16