尽管mRNA疫苗已用于COVID-19的预防，但仍然面临不稳定和易降解的风险，这是mRNA疫苗存储、配送、效价等面临的重要障碍。先前的研究已表明，，再加上选择优化的密码子，可改善蛋白表达。因此，原则上mRNA的设计算法必须优化二级结构稳定性和密码子的使用。然而，由于同义密码子的存在，使得mRNA设计的工作量非常庞大，例如靶向SARS-CoV-2 Spike蛋白的mRNA就有~10^632种方案，这就带来了难以克服的计算挑战。利用计算语言中类似的概念，我们提供了一种简单且意想不到的解决办法：寻找最佳的mRNA序列类似于在发音相似的备选句子中识别最可能的句子。利用我们的算法（LinearDesign）设计Spike蛋白的mRNA仅需11分钟，并且同时优化稳定性和密码子的使用。在针对COVID-19 和 水痘带状疱疹病毒（varicella-zoster virus）mRNA疫苗，与密码子优化的基准算法相比，LinearDesign大幅度提高了mRNA的半衰期和蛋白的表达，显著增加了抗体的滴度（体内实验中增加了128倍）。该结果揭示了mRNA设计算法还有很大的改进空间，促进了对原本触不可及的高效且稳定的mRNA设计的探索。我们的工作为mRNA疫苗乃至mRNA药物（如单克隆抗体和抗癌药物）的研发带来了“及时雨”（timely tool）。

　　mRNA疫苗因其可批量生产、安全性和有效性而被认为是预防包括COVID-19在内的可行方法。然而，mRNA分子在化学上不稳定且容易降解，导致蛋白质表达不足，进而降低免疫原性和成药性。这种不稳定性也成为疫苗储存和分发中的主要障碍，mRNA疫苗需要使用冷链，这也就限制了其在发展中国家的使用。因此，人们迫切希望获得一种具有增强稳定性的mRNA分子，可能会具有更高的效力和良好的临床疗效。

　　虽然化学稳定性很难建模，但之前的研究已经确定了它与次级结构的相关性，这通过热力学折叠稳定性进行量化；改善这种结构稳定性，结合最佳密码子使用，可以增加蛋白质表达。因此，一个合理的mRNA设计算法必须优化两个因素，即结构稳定性和密码子使用，以增强蛋白质表达。

　　然而，由于搜索空间（search space）呈指数级增长，mRNA（仅考虑编码区）设计问题非常具有挑战性。每个氨基酸由一个三联密码子编码，即三个相邻的核苷酸，但由于遗传密码的冗余性（20个氨基酸对应64个密码子），大多数氨基酸具有多个密码子。这种组合导致候选序列数量极大，难以处理。例如，SARS-CoV-2的刺突蛋白（Spike protein）由1,273个氨基酸组成，可以由约2.4×10^632个mRNA序列编码（图1a）。这带来了无法逾越的计算挑战，并排除了枚举的可能性，因为对于刺突蛋白来说，枚举需要花费10617亿年的时间（图1b）。另一方面，传统的mRNA设计方法，密码子优化（11, 12）仅优化密码子使用，但几乎不会改善稳定性，忽略了高稳定性mRNA存在的巨大空间。优化GC含量具有类似的效果，因为它与脊椎动物中的密码子使用相关（13）。因此，大多数高稳定性mRNA的设计仍然是未知的。

　　在这里，我们提供了一个简单的算法，LinearDesign，通过意外地将这个具有挑战性的问题归约为计算语言学中经典概念“格子解析”（6）（图1c）来解决。我们展示了在众多类似的备选方案中找到最佳mRNA类似于在众多类似声音的备选句子中找到最有可能的句子。更具体地说，我们使用确定有限状态自动机（deterministic finite-state Automaton, DFA）来构建mRNA设计空间，类似于“词格（word lattice）”（6），它紧凑地编码了指数级的候选mRNA。然后，我们使用格子解析来找到DFA中最稳定的mRNA，或在加权DFA中找到稳定性和密码子最优性之间的最佳平衡。这种结合自然语言的方法使得我们开发了一个高效的算法，可以将计算量控制在mRNA序列长度的平方级。从这个意义上说，我们的工作将庞大的搜索空间转变为一种福音（设计自由），而不是一个障碍。

　　与密码子优化基准相比，我们设计的COVID-19和水痘带状疱疹病毒（VZV）mRNA疫苗在体外化学稳定性、细胞内蛋白质表达和体内免疫原性方面均有显著改善。特别是，COVID-19疫苗相比基准（benchmark）能够实现高达128倍的抗体反应。这一令人惊讶的结果揭示了mRNA设计的巨大潜力，并使得这些先前难以实现但高度稳定且高效的设计得以被探索。因为LinearDesign可以优化编码所有治疗蛋白质的mRNA，包括单克隆抗体（7）和抗癌药物（8）的mRNA，因此，我们的工作不仅为mRNA疫苗提供了及时和有前景的工具，也为已经显示出具有改变医疗保健的巨大潜力的mRNA治疗提供了工具（14）。

　　先前的工作（5）为mRNA设计建立了两个主要目标，即稳定性和密码子最优性，这两者协同作用以增加蛋白质表达。为了优化稳定性，在给定蛋白质序列的情况下，我们的目标是找到在所有可能编码该蛋白质的mRNA序列中具有最低最小自由能变化（MFE）的mRNA序列。换句话说，对于每个候选mRNA序列，我们使用标准的RNA折叠能量模型（15, 16）筛选MFE能量最低的mRNA序列。因此这是双重最小化的问题（扩展数据图1a）。然而，利用这种朴素的方法将花费数十亿年的时间，因此我们需要一种高效的算法，而不是枚举法。

　　接下来，我们旨在共同优化mRNA的稳定性和密码子最优性。后者通常通过密码子适应性指数（Codon Adaptation Index, CAI）（17）来衡量，CAI被定义为mRNA中每个密码子相对适应性的几何平均值。由于CAI的取值范围在0和1之间，但MFE通常与mRNA序列长度成正比，我们将CAI的对数乘以mRNA中的密码子数，并使用一个超参数lambda来平衡MFE和CAI（lambda = 0表示仅考虑MFE）。综合目标函数为MFE - lambdap log CAI

　　接下来，我们使用从自然语言中借鉴的两个概念来描述解决这两个优化问题的方法：确定有限状态自动机（DFA，格子）和格子解析。

　　设计空间表示：DFA（格子）受计算语言学中对歧义的“词格”表示（扩展数据图2a）启发，我们使用类似的格子或更正式地说，确定有限状态自动机（DFA）来表示每个氨基酸的密码子选择（图2a和扩展数据图1c；有关正式定义，请参阅方法 §1.2）。在为蛋白质序列中的每个氨基酸构建一个密码子DFA后，我们将它们连接成一个单一的mRNA DFA，在起始状态和终止状态之间的每条路径代表一个可能的编码该蛋白质的mRNA序列（图2b和扩展数据图1d）。

　　目标1（稳定性）：格子解析已知RNA折叠等同于自然语言解析，其中随机上下文无关语法（SCFG）可以表示折叠能量模型（18）（扩展数据图1e-f）。但是对于mRNA设计来说，难点在于：如何将所有的mRNA序列一起在DFA中进行折叠？我们借鉴了“格子解析”（19, 6）的思想，该方法将单个序列解析推广到同时处理格子中的所有句子以找到最有可能的句子（图1c和扩展数据图2）。类似地，我们使用格子解析同时折叠mRNA DFA中的所有序列，以找到最稳定的序列（图2b和扩展数据图1g-h）。值得注意的是，格子解析也是动态规划的一种实例，但搜索空间更大，而单个序列的折叠可以看作是一个单链DFA的格子解析特例。这个过程也可以解释为SCFG-DFA的交集（扩展数据图1a），其中SCFG用于稳定性评分，而DFA则划定了候选集。该算法的运行时间与mRNA序列的长度呈立方关系（方法 §1.3），但在实际应用中，两者仅呈二次方关系（图3a）。

　　目标2（密码子最优性）：带权重的格子解析我们将确定有限状态自动机（DFA）扩展为带权重的确定有限状态自动机（WDFAs），以便在边权重中集成密码子最优性。由于我们的联合优化公式将CAI因子分解为每个密码子c的相对适应性w(c)，我们在每个密码子DFA中设置边权重，使得密码子c的路径成本为-log w(c)，这可以解释为与最优密码子的“偏差量”。然后，在带权重的mRNA DFA中，每条起始-终止路径的成本是对应mRNA中每个密码子c的-log w(c)的总和，这与其-log CAI成正比（图2d）。现在，格子解析同时使用随机语法（用于稳定性）和带权重的DFA（用于密码子使用），并解决具有优化保证的联合优化问题，可以将其视为SCFG和WDFA之间的加权交集（20）（扩展数据图1b；方法 §1.4）。

　　DFA的表现能力我们的DFA框架非常通用，可以表示替代的遗传密码、修饰核苷酸和编码约束因素。详细信息请参见方法 §1.7，扩展数据图3和补充图5。

　　线性时间近似法对于长序列，精确的设计算法可能仍然很慢。此外，由于mRNA设计中涉及许多除稳定性和密码子使用之外的因素，次优设计可能也值得在湿实验中进行探索。因此，受先前工作LinearFold（21）的启发，我们开发了一种近似搜索版本，使用波束搜索在线性时间内运行，每一步只保留最有前景的b个项目（b是波束大小）。

　　相关工作之前的两项研究也通过动态规划解决了“最稳定的mRNA设计”问题（我们的目标1），但是利用Zuker算法的专门扩展（22, 23）无法兼具密码子最优性（目标2）。相比之下，我们建立了mRNA设计与计算语言学中的格子解析之间的联系，这也是我们工作最具创新性的贡献。这种联系使得我们能够使用更简单、更通用的算法，可以同时优化密码子使用，并利用一个新颖的目标函数将CAI因子分解到个别密码子上。我们还通过体内验证了这些算法设计的mRNA，结果显示两个mRNA疫苗的效果具有显著的改善（图4-5）。详细信息请参见方法 §1.1和§1.8。

　　图3a展示了LinearDesign对UniProt蛋白质的运行时间。LinearDesign通过两个优化目标的组合进行展示，即仅MFE（目标1）与MFE+CAI（目标1和2），以及两种搜索模式，即精确搜索与波束搜索（波束大小b=500）。经验证，由于DFA表示和格子解析的便利性，LinearDesign在实际应用中对mRNA序列长度n呈二次方扩展（n

　　对于偏好GC的密码子的mRNA（例如人类），传统的密码子优化方法确实可以提高稳定性，但仅略有改善（图3b-c），因为其优化方向（粉色箭头）在很大程度上与稳定性优化方向（蓝色箭头）几乎正交。相比之下，我们的LinearDesign可以直接优化稳定性并找到最稳定的mRNA序列。在COVID Spike蛋白和VZV gE蛋白中，最低的MFE值（l=0）比最优CAI（l=¥）的MFE值低1.8倍。此外，我们的最稳定设计主要具有双链二级结构（图3d），据预测这种结构更不容易降解（5）。通过l在0到¥范围内变化，LinearDesign计算了mRNA设计空间的可行性界限（最优边界）（图3b-c中的蓝色曲线]中的l）。此外，当密码子偏好偏向AU富集密码子（如酵母）时，密码子优化实际上会导致稳定性的降低。

　　对于COVID-19 Spike蛋白质，本研究使用了八条mRNA序列。其中七条序列（序列A-G）是使用LinearDesign算法设计的次优分子（使用波束搜索(21, 25)）。它们广泛分布在低MFE设计空间中（图4a中MFE £ 1,400 kcal/mol的区域），这是传统密码子优化算法无法达到的。为了更好地理解MFE和CAI参数的生物学影响，我们设计了这些mRNA序。