十三 发自 凹非寺 量子位 报道 | 公众号 QbitAI
新冠疫情全球流行，疫苗研制成为当务之急。
mRNA作为一种全新的疫苗类型，能够快速大规模生产， 因此成为科学家们攻克的主阵地之一。
新冠疫情爆发后，RNA设计领域世界知名专家、斯坦福大学生物化学系Rhiju Das教授关注到疫苗研发存在的一个非常棘手的问题：
找到一个既具有稳定二级结构，而且还有效的mRNA疫苗。
有多难？
首先是稳定性，mRNA疫苗“脆弱”到在保存、运输过程中，就有可能因为降解而失效。
然后是有效性，需要找一个mRNA序列，能够翻译成特定的蛋白质(抗原)。
单是满足这两个条件，若是采用遍历的方式去寻找，那就需要查看10632个mRNA序列！
这是什么概念？用一台超级计算机来处理，即便一秒钟能计算一个新冠RNA序列的二级结构，哪怕是从宇宙诞生到现在(130-140亿年)，连“潜在”mRNA序列的亿万分之一都没算到。
仅靠科研人员的力量是远远不够的，那就“全民参赛”吧！
于是乎，Rhiju Das教授便找到了百度，使用百度此前开源的LinearFold算法，搭建一个疫苗设计公开赛，让全民参与进来，以游戏的形式，边玩边找这个mRNA。
但正如刚才提到的，搜索空间是异常庞大，难道就没有办法在相对节省人力的情况下，就能够设计出满足条件的mRNA疫苗序列呢？
这个可以有。
现在，(可能)“拯救世界”的新算法，LinearDesign，来了！
LinearDesign：最快16分钟完成mRNA疫苗序列设计
其实，回顾近二十年的历史，随着全球化和城市化的深入发展，全球疫情爆发周期越来越短——从2002年的SARS，到2012的MERS，再到现如今的新冠病毒。
面对一次又一次的冠状病毒的侵袭，快速研制出特定疫苗成为了解决问题的一种途径。
那么，在mRNA疫苗如此庞大的搜索空间面前，LinearDesign又能起到什么作用？
针对新冠病毒的mRNA疫苗序列，通常是以自然界存在的新冠刺突蛋白对应的mRNA段为基础，经过一些改动后作为备选序列。
但是这样的序列其二级结构通常是不够稳定的。如下图(A)展示的是新冠病毒刺突蛋白对应的mRNA二级结构，其能量为-967.8 kcal/mol。
△图A
这一能量衡量了mRNA二级结构的稳定性，能量越低（越负）表明越稳定。
mRNA由多个核苷酸（共四种，分别是A、U、C、G）串联而成，蛋白质由多个氨基酸（共21种）串联而成。每三个核苷酸（称为一个密码子）翻译成一个蛋白质。显而易见，三个核苷酸共有4的三次方共64种组合，那么必然有多个密码子对应一个氨基酸，也就是说有很多mRNA序列都可以翻译成同一个蛋白质（抗原）序列。具体来说，新冠病毒刺突蛋白（抗原）共有1273个氨基酸，能翻译成刺突蛋白的mRNA序列有10的632次方之多。如下图所示：
在保持翻译成的蛋白质不变的前提下，还可以选择其他的序列作为mRNA疫苗序列。下图(B)展示了从1万个随机序列中选取的能量最低的序列，能量为-1149.8 kcal/mol。
△图B
这一序列能量比Wildtype低一些，但是也并不是能量最低的序列。
那么能量最低的序列什么样子，其能量可以低到多少？有请LinearDesign算法来回答这个问题。
下图(C)便是LinearDesign设计出来的序列二级结构，其能量为-2477.7 kcal/mol，比A、B低一倍还多。
△图C
它的二级结构非常紧密，几乎所有的碱基都形成了碱基对。而碱基对越多，通常能量越低，结构越稳定。
从上面对比图可以看出，在新冠病毒的刺突蛋白序列上的计算机模拟实验表明，LinearDesign算法可以设计出比Wildtype序列稳定得多的结构，而且设计时间只需要1个半小时。
如果采用线性时间近似，所需时间可以进一步缩短到16分钟， 而相比于最稳定序列，线性近似算法设计出的序列与其能量仅相差0.6%。
上图对比了刺突蛋白的野生型mRNA、随机生成的mRNA序列、以及LinearDesign设计序列的稳定性和蛋白质表达水平。图中横坐标是衡量稳定性的参数MFE，越低越好；纵坐标是衡量蛋白质表达水平的参数CAI，越高越好，所以处于左上方的序列既稳定又能翻译更多蛋白质（抗原）。
野生型和随机生成的序列都集中在右下方，而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”。
除此之外，研究人员还在此基础上，对算法做了如下扩展：
- 借用LinearFold思想，进一步将计算复杂度从三次方复杂度降低到线性，大幅度缩短设计mRNA序列所需要的时间；
- 从提供一个最优的mRNA序列，到可以提供前k个次优的mRNA序列作为备选。疫苗公司可以在这些备选中选出最适合生产的疫苗序列；
- 同时优化二级结构稳定性和蛋白质表达效率，设计出稳定性好、蛋白质表达效率高的mRNA疫苗序列。
CoV-Seq：数据、工具都呈上，大家一起来抗疫
解决了寻找稳定、有效mRNA之后，对于科学家来说其实还存在一个困扰。
为了了解新冠病毒的进化和各个基因的功能，科学家们需要从不同年龄段、性别、种族和疾病阶段的患者身上收集SARS-CoV-2基因组并进行全基因组测序。
然而，公共存储库每天都在迅速发布基因组序列，每周有成千上万的新序列。
那么，问题就来了：
- 为了跟上最新发展，科学家需要经常下载并重新整理新的数据集，这可能会花费大量时间和精力。
- 另一方面，对于生物信息学知识有限的科学家可能会发现，当他们拿到新序列时，很难快速有效的进行分析。
- 而且，目前没有可以自动注释SARS-CoV-2基因和基因突变的软件。
因此，百度开发了CoV-Seq分析平台来解决上述问题。
CoV-Seq由几个组件组成。
数据分析工具，该工具接受FASTA格式的序列并生成VCF格式的突变数据。工具会自动过滤低质量的序列并删除重复的序列，执行序列比对，调用并注释遗传变异。
Web界面，无需任何编程即可快速分析自定义序列，包括交互式基因组可视化以及可供下载的分析结果。
独立脚本，以允许在本地计算机上进行高吞吐量的处理。
CoV-Seq分析平台的论文已经上线：
进击的计算生物学硬实力
百度研究院开展RNA二级结构领域的研究，其实是在2018年刚刚开始。
但就是在这短短的2年时间里，百度研究院RNA团队，除了此次的LinearDesign外，还推出了LinearFold、LinearPartition，研究成果相继被计算生物学领域顶级会议ISMB接收，引起业内的关注。
这也足以体现百度在生物计算研究领域的技术实力。
正所谓能力越大，责任越大。面对突如其来的疫情，百度于1月份对外免费开放了可以大大提升新冠RNA二级结构分析速度的LinearFold服务，引起了全世界科研机关、防疫机构和生物医学公司的广泛关注，多家机构联系百度，提出了建立后续合作的意向。
现如今，在此基础上，百度再次发力，提出的LinearDesign能够大大减少寻找mRNA疫苗序列的搜索空间，还提供了CoV-Seq这样方便的工具平台，让研究人员能够加速科研的进展。
不仅如此，这样的技术、工具组合，还大大降低了上手的门槛。
那么，就快快加入“全民抗疫”这场战斗中，在LinearDesign的基础上从更多维度继续优化mRNA疫苗序列。说不定找到最优mRNA疫苗序列的，就会是你。
拯救人类的重任，就交给你啦。
传送门
LinearDesign 论文地址：https://arxiv.org/abs/2004.10177
LinearDesign 网站链接：http://rna.baidu.com/
CoV-Seq论文地址：
https://www.biorxiv.org/content/10.1101/2020.05.01.071050v1
CoV-Seq网站链接：http://covseq.baidu.com/
作者系网易新闻·网易号“各有态度”签约作者
— 完 —
