序列百度推出LinearDesign，全球首个mRNA疫苗不稳定性解决方案，仅需16分钟( 二 )
那么能量最低的序列什么样子 ， 其能量可以低到多少？有请LinearDesign算法来回答这个问题 。
下图(C)便是LinearDesign设计出来的序列二级结构 ， 其能量为-2477.7 kcal/mol ， 比A、B低一倍还多 。 
图片
△图C
它的二级结构非常紧密 ， 几乎所有的碱基都形成了碱基对 。 而碱基对越多 ， 通常能量越低 ， 结构越稳定 。
从上面对比图可以看出 ， 在新冠病毒的刺突蛋白序列上的计算机模拟实验表明 ， LinearDesign算法可以设计出比Wildtype序列稳定得多的结构 ， 而且设计时间只需要1个半小时 。
如果采用线性时间近似 ， 所需时间可以进一步缩短到16分钟 ，而相比于最稳定序列 ， 线性近似算法设计出的序列与其能量仅相差0.6% 。 
图片
图片
上图对比了刺突蛋白的野生型mRNA、随机生成的mRNA序列、以及LinearDesign设计序列的稳定性和蛋白质表达水平 。 图中横坐标是衡量稳定性的参数MFE ， 越低越好；纵坐标是衡量蛋白质表达水平的参数CAI ， 越高越好 ， 所以处于左上方的序列既稳定又能翻译更多蛋白质（抗原） 。
【序列百度推出LinearDesign ， 全球首个mRNA疫苗不稳定性解决方案 ， 仅需16分钟】野生型和随机生成的序列都集中在右下方 ， 而LinearDesign设计的序列在左上方 。 其中最左侧的点是LinearDesign设计出的最稳定的序列 ， 其MFE为-2477.7 kcal/mol. 而随着调整lambda值（一个平衡MFE和CAI的超参数） ， 可得到一条淡蓝色的曲线 ， 这个曲线就是所有满足条件的mRNA 序列中最优序列上界 。 粉色的曲线是近似算法设计出的序列 ， 可以看到它和精确算法找出的序列（淡蓝色曲线）非常接近 ， 但设计时间大大缩短 。
更重要的是 ， LinearDesign不仅有助于解决当下的新冠病毒问题 ， 更是适用于所有的mRNA疫苗 。
那么 ， LinearDesign到底是如何做到这点的呢？
LinearDesign原理：降低搜索空间至多项式级
主要面临的问题 ， 就是如何解决如此庞大的搜索空间 。
LinearDesign通过动态规划算法 ， 来将这一问题的搜索空间从指数级降低到多项式级 。
具体来说 ， 首先用确定有限状态自动机（DFA）来表达氨基酸和蛋白质 ， 这样不同位置上密码子的选择就可以抽象为计算理论中常用的DFA图 。
如下图 ， 分别把三种氨基酸（A: methionine, B: valine, C: serine）以及终止密码子（D）抽象为DFA图 。 
图片
在此基础上 ， 将氨基酸的DFA串联起来 ， 即可得到一段蛋白质序列的DFA图 。 如下图是示例序列“methionineleucine stop” 的DFA图 。 
图片
在有了DFA图后 ， 要通过DFA找出二级结构最稳定的mRNA序列 。
这里借用了计算语言学中常用的一个工具 ， 随机上下文无关语法（SCFG） 。 RNA二级结构可以通过SCFG构建语法树来表示 。
mRNA疫苗序列设计优化问题实际上是将单个RNA序列的二级结构计算（RNAfolding）推广到多个RNA序列 。
在用DFA抽象表示多个RNA序列后 ， 研究人员通过取DFA与SCFG的交集 ， 来从多个mRNA序列中找到具有最稳定二级结构的序列 。
下图给出了一个具体的例子 ， 通过DFA和SCFG相交 ， 生成出序列“methionine leucine stop”最优的mRNA序列为“AUGCUGUGA” 。 
图片
除此之外 ， 研究人员还在此基础上 ， 对算法做了如下扩展：
推荐阅读
- |荷兰企业推出全新半导体技术，并承诺对华投资！中国光刻机获突破
- AutoR智驾|电力不够持久？以色列推出动态无线充电网络 充电效率90％
- AutoR智驾|电力不够持久？以色列推出动态无线充电网络，一夜铺设一公里、充电效率90%
- |真奢侈品！LV旗下恒宝将推出“ Big Bang e”的新型智能手表
- 新功能|新Pixel独家更新推出，优化电池续航力、时钟也有了新功能
- 英寸|HMD在印度推出43英寸诺基亚智能电视
- 投放OKKI 推出谷歌投放解决方案，小满科技助力B2B出海企业高效推广
- 快手|快手联合多家机构推出“野生动植物保护影像评选计划”
- 新智元|B站上线！DeepMind加UCL强强联手推出深度学习与强化学习进阶课程（附视频）
- 国货腾讯携手吴晓波推出中国首部大型品牌经济纪录片《新国货》