The inverse protein folding problem, designing a discrete amino acid sequence that spontaneously folds into a predefined macroscopic structure, remains a phenomenally demanding combinatorial challenge central to synthetic drug discovery. While algorithms like SA offer a baseline approach for navigating dense biomolecular energy landscapes, applying SA heuristics to large sequences is inherently frustrated by exponentially large search spaces and deep local energy minima. This study proposes a scalable sequence design architecture, Topological Spatial Chunking Simulated Annealing, based on a localized, exact-solving heuristic embedded within a global simulated-annealing wrapper. To fundamentally circumvent exponential scaling walls, we deploy a dynamic solver that segments the global molecular target into shallow, k-variable algorithmic windows. Crucially, rather than partitioning natively by sequential 1D chronology, we introduce topological spatial chunking, which dynamically groups discrete variables based on Euclidean spatial proximity to preserve critical non-local thermodynamic correlations. The spatially localized sub-problems are solved deterministically via exact enumeration, while the global traversal is securely regulated by an exterior simulated annealing governor augmented by dynamic reheating and continuous elitism caching. We comprehensively benchmarked this classical architecture on the standard HP biophysical lattice against targeted 20-merA, 25-mer, 50-mer, and 64-mer geometries. Most notably, when evaluating the computationally exhaustive 50-mer and 64-mer topologies, the framework successfully bypassed widely accepted heuristic boundaries. By leveraging deterministic exact solving to vault classical energy traps, the system algorithmically resolved a novel, ultra-dense sequence-packing configuration for the 50-mer, defining a new theoretical global optimum.
Figures & tables
Fig. 1: Process flowchart of the hybrid Topological Spatial Chunking Simulated Annealing (TSC-SA) architecture. The framework mitigates localized biological trapping sequences via the interaction of topologically exact-solving extractions, heavily regulated by a macro-temperature cooling schedule, active elitism caching, and induced parameter heating shocks.
Fig. 2: Optimized conformation of the 20-merA sequence with energy as -180.
Fig. 3: Energy convergence trajectory for the 20-merA sequence, comparing TSC-SA against baseline Simulated Annealing.
Fig. 4: Optimized 25-mer spatial topology with energy as -160.
Fig. 5: Energy convergence trajectory for the 25-mer sequence, comparing TSC-SA against baseline Simulated Annealing.
Fig. 9: Energy convergence trajectory for the 64-mer sequence, comparing the TSC-SA architecture against the baseline Simulated Annealing.
Target
Length ( N )
Budget ( NH )
Baseline SA Energy
TSC-SA Energy
Contacts
20-merA
20
10
-120.00
-180.00
9
25-mer
25
9
-120.00
-160.00
8
50-mer
50
24
-360.00
-440.00
22
64-mer
64
42
-700.00
-840.00
42
TABLE I: Comparative performance metrics across multiple protein topologies. The TSC-SA architecture consistently identifies deeper energy minima and more H-H contacts compared to the baseline Simulated Annealing.
Metric
from Istrail benchmark
TSC-SA
Improvement
Hydrophobic Count ( NH )
24
24
-
HH Contacts
21
22
+1
PH Contacts
2
3
+1
PP Contacts
9
7
-2
HH Energy ( EHH )
-48.30
-50.60
-2.30
Total System Energy ( Etotal )
-50.30
-53.60
-3.30
TABLE II: Comparative metrics for the 50-mer Protein Inverse Design.
Protein-protein interactions underpin nearly all biological processes. Yet, designing proteins with desired interactions remains challenging due to the structural complexity governing molecular recognition. This study views protein design as a search optimization problem over a combinatorial sequence space under expensive structural evaluation. Toward this goal, we introduce a novel tree-based search framework, ProteoCraft, that employs approximate structural gradients from diffusion-based structure predictors as effective proposal policies to specify where the search should explore. Complete no-gradient inference of folding models separately assigns values to the resulting sequences, determining what is good. ProteoCraft allocates this verification budget through a coarse-to-fine paradigm: multi-site edits first explore distinct sequence basins, then verified promising states undergo strict single-site refinement. Across fourteen de novo binder-design settings spanning eight target proteins, five immune-relevant TCR-facing targets, and four localized CDR redesign tasks, ProteoCraft improves design quality and high-confidence yield. These improvements persist under independent AF2-IG and Rosetta-based interface evaluation. Prospective experimental validation further yielded an 82.9% binding hit rate for PD-L1 miniproteins, with a best measured KD of 0.879 nM, and confirmed binding of designed IFNAR2 VHH. Our code is available at https://github.com/smiles724/ProteoCraft_v1.
Fang Wu, Hongbin Lin, Bingchen Duan +24
Stanford University · HKUST (Guangzhou) · Amazon +10
We introduce RosettaSearch, an inference-time multi-objective optimization approach for backbone conditioned protein sequence design. We use large language models (LLMs) as a generative optimizer within a search algorithm capable of controlled exploration and exploitation, using rewards computed from RosettaFold3, a structure prediction model, under a strict computational budget. In a large-scale evaluation, we apply RosettaSearch to 400 suboptimal sequences generated by LigandMPNN (a state-of-the-art model trained for protein sequence design), recovering high-fidelity designs that LigandMPNN's single-pass decoding fails to produce. RosettaSearch's designs show improvements in structural fidelity metrics ranging between 18% to 68%, translating to a 2.5x improvement in design success rate. We observe that these gains in success rate are robust when RosettaSearch-designed sequences are evaluated with an independent structure prediction oracle (Chai-1) and generalize across two distinct LLM families (o4-mini and Gemini-3), with performance scaling consistently with reasoning capability. We further demonstrate that RosettaSearch improves the sequence fidelity of ProteinMPNN designs for de novo backbones from the Dayhoff atlas, showing that the approach generalizes beyond native protein structures to computationally generated backbones. We also demonstrate a multi-modal extension of RosettaSearch with vision-language models, where images of predicted protein structures are used as feedback to incorporate structural context to guide protein sequence generation. To our knowledge, this is the first large-scale demonstration that LLMs can serve as effective generative optimizers for backbone-conditioned protein sequence design, yielding systematic gains without any model retraining.
Meghana Kshirsagar, Allen Nie, Ching-An Cheng +5
AI for Good, Microsoft Redmond · Google DeepMind · Google Research +3
Designing novel proteins with desired characteristics remains a significant challenge due to the large sequence space and the complexity of sequence-function relationships. Efficient exploration of this space to identify sequences that meet specific design criteria is crucial for advancing therapeutics and biotechnology. Here, we present BoGA (Bayesian Optimization Genetic Algorithm), a framework that combines evolutionary search with Bayesian optimization to efficiently navigate the sequence space. By integrating a genetic algorithm as a stochastic proposal generator within a surrogate modeling loop, BoGA prioritizes candidates based on prior evaluations and surrogate model predictions, enabling data-efficient optimization. We demonstrate the utility of BoGA through benchmarking on sequence and structure design tasks, followed by its application in designing peptide binders against pneumolysin, a key virulence factor of Streptococcus pneumoniae. BoGA accelerates the discovery of high-confidence binders, demonstrating the potential for efficient protein design across diverse objectives. The algorithm is implemented within the BoPep suite and is available under an MIT license at GitHub.
Erik Hartman, Di Tang, Johan Malmström
Division of Infection Medicine, Faculty of Medicine, Lund University, Sweden