Bandit Theory and Thompson Sampling-Guided Directed Evolution for Sequence Optimization
Bandit Theory and Thompson Sampling-Guided Directed Evolution for Sequence Optimization
复制标题
DOI：
10.48550/arxiv.2206.02092
复制
发表时间：
2022-06
期刊：
影响因子：
--
通讯作者：
Hui Yuan;Chengzhuo Ni;Huazheng Wang-;Xuezhou Zhang;Le Cong;Csaba Szepesvari;Mengdi Wang
中科院分区：
文献类型：
--
作者：
Hui Yuan;Chengzhuo Ni;Huazheng Wang-;Xuezhou Zhang;Le Cong;Csaba Szepesvari;Mengdi Wang
定向进化（DE）是一种具有里程碑意义的湿实验室方法，起源于20世纪60年代，通过进化候选序列群来发现新的蛋白质设计。生物技术的最新进展使得收集高通量数据成为可能，允许使用机器学习来绘制蛋白质的序列-功能关系。人们对机器学习辅助DE加速蛋白质优化的兴趣越来越大。然而，对DE的理论理解以及机器学习在DE中的应用仍然有限。在本文中，我们将DE与bandit学习理论联系起来，并首次尝试研究DE中的遗憾最小化。我们提出了一个用于序列优化的汤普森采样引导定向进化（TS-DE）框架，其中序列到函数的映射是未知的，查询单个值受到昂贵和噪声测量的影响。TS-DE根据收集到的测量值更新函数的后验。它使用后验抽样函数估计来指导DE中的交叉重组和突变步骤。在线性模型的情况下，我们表明TS-DE具有阶为$\tilde O(d^{2}\sqrt{MT})$的贝叶斯遗憾，其中$d$为特征维数，$M$为总体大小，$T$为轮数。这个遗憾界几乎是最优的，证实了强盗学习可以证明加速DE。它可能对更一般的序列优化和进化算法有启示。
Directed Evolution (DE), a landmark wet-lab method originated in 1960s, enables discovery of novel protein designs via evolving a population of candidate sequences. Recent advances in biotechnology has made it possible to collect high-throughput data, allowing the use of machine learning to map out a protein's sequence-to-function relation. There is a growing interest in machine learning-assisted DE for accelerating protein optimization. Yet the theoretical understanding of DE, as well as the use of machine learning in DE, remains limited. In this paper, we connect DE with the bandit learning theory and make a first attempt to study regret minimization in DE. We propose a Thompson Sampling-guided Directed Evolution (TS-DE) framework for sequence optimization, where the sequence-to-function mapping is unknown and querying a single value is subject to costly and noisy measurements. TS-DE updates a posterior of the function based on collected measurements. It uses a posterior-sampled function estimate to guide the crossover recombination and mutation steps in DE. In the case of a linear model, we show that TS-DE enjoys a Bayesian regret of order $\tilde O(d^{2}\sqrt{MT})$, where $d$ is feature dimension, $M$ is population size and $T$ is number of rounds. This regret bound is nearly optimal, confirming that bandit learning can provably accelerate DE. It may have implications for more general sequence optimization and evolutionary algorithms.