新冠病毒全球累计确诊已超过400万人，疫苗是终结疫情的关键胜负手。在所有正在研发的疫苗路径中，研发速度更快、更具潜力的mRNA疫苗作为一种新兴技术受到了国内外的重点关注。但同时，mRNA疫苗由于稳定性不足容易在保存、运输中降解，也成为制约疫苗大规模推广和使用最亟待解决的问题。

现在，这个困扰世界顶级疫苗公司和学界的生物学难题有望通过AI解决！5月13日，百度研究院重磅推出全球首个mRNA疫苗基因序列设计算法LinearDesign。该算法能够在理论上设计出结构最稳定、蛋白质表达效率最高的mRNA序列，而这只需要90分钟。如果进一步应用线性时间近似算法，时间更可以缩短到16分钟！

美国罗彻斯特大学生物化学与生理系教授Dr. David H. Mathews 表示：“LinearDesign的优势在于速度！它能够快速提供一系列的优良序列，研究者可以进一步通过实验来测试其稳定性是否足以充当疫苗。”

事实上，从能够转译同一种蛋白质的众多同源序列中找到二级结构足够稳定、密码子足够优化的mRNA序列挑战难度是相当巨大的。以新冠病毒为例，它的刺突蛋白（抗原）共有1273氨基酸，能翻译成刺突蛋白的mRNA序列有10的632次方之多！

遍历所有可能？这显然难以完成。

假设一台超级计算机能做到一秒钟计算一个mRNA结构，那么从宇宙形成开始计算到现在，计算140亿年，连mRNA序列所有可能的亿万分之一都无法算完！

要找出最优的mRNA，科学家们的传统做法是随机改变序列，再看看是否有益。当前，科学界也在寻找解决问题的不同策略，比如，卡耐基梅隆大学和斯坦福大学联合百度合作开发的平台Eterna，就旨在在通过解谜的方式吸引全球玩家共同设计安全稳定的mRNA。Eterna平台所使用的，正是今年1月底百度开放的LinearFold算法作为其结构分析引擎。 

LinearFold是十分成功的实验性项目，它将生物学上的难题成功转化为形式语言理论和计算机语言学上的经典问题。在LinearFold的启发之下，百度研究院的研究团队想到了不只是结构分析，而可以进一步运用计算机科学来设计出更稳定、蛋白质表达水平更高的mRNA序列。由此，LinearDesign应运而生。

针对多达10的632次方mRNA序列，LinearDesign采用了动态规划算法来缩小搜索空间。我们知道直到AlphaGo出来之前，AI一直都无法战胜人类棋手，主要原因就是围棋的搜索空间太大了， 有3的19x19次方个状态，约合10的172次方。可以看到，mRNA序列设计问题的搜索空间远远大于下围棋的搜索空间。

而LinearDesign的动态规划算法首先用确定有限状态自动机（DFA）来表达氨基酸和蛋白质，这样不同位置上密码子的选择就可以抽象为计算理论中常用的DFA图。如下图，分别把三种氨基酸（A: methionine, B: valine, C: serine）以及终止密码子（D）抽象为DFA图。

在此基础上，将氨基酸的DFA串联起来，即可得到一段蛋白质序列的DFA图。如下图是示例序列“methionineleucine stop” 的DFA图。

接下来，我们需要通过DFA来找出二级结构最稳定的mRNA序列。在这里，百度研究院借用了通常用于计算机语言学的常见工具，也就是随机上下文无关文法（SCFG），用于指代RNA折叠。RNA二级结构可以通过SCFG构建语法树来表示。

mRNA疫苗序列设计优化问题实际上是将单个RNA序列的二级结构计算（RNAfolding）推广到多个RNA序列。在用DFA抽象表示多个RNA序列后，研究人员通过取DFA与SCFG的交集，来从多个mRNA序列中找到具有最稳定二级结构的序列。

从上图的新冠病毒突刺蛋白实验结果可以看出，对比最左侧图A自然界存在抗体所对应的mRNA序列，右边人工智能设计的二级结构非常紧密。其中的全局最优序列图C，设计时间只需要1.6小时！而如果进一步应用线性时间近似算法，如图B其设计时间将缩短到16分钟。这项技术同样适用于所有mRNA疫苗设计。

疫苗研发是一项耗时耗力的全世界性难题，运用人工智能，计算机科学技术疫苗研发正在不断加速。目前，百度研究院已将LinearDesign网站免费开放，同时相关论文已发布于arXiv，全球研究机构及疫苗研发企业均可使用。百度已与中国疾病预防控制中心病毒病预防控制所签署战略合作协议，后续也将使用百度LinearDesign算法设计的mRNA疫苗序列进行体外实验，验证疫苗的稳定性和蛋白质表达效率。相信在全球研究者的共同努力下，疫苗研发进度将不断提速！