新冠疫情全球流行，疫苗研制成为当务之急。

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疫苗序列的，就会是你。

拯救人类的重任，就交给你啦。

（转载）

以上是网络信息转载，信息真实性自行斟酌。