百度LinearFold是什么？百度Linear Fold算法介绍

百度LinearFold是什么?

LinearFold算法可以将本次新型冠状病毒的全基因组二次结构预测从55分钟缩短到27秒，提高120分钟的速度，节省了2个数级的等待时间.接下来，小编将介绍如何使用百度棋盘算法

如果有需要RNA结构预测算法和技术支持的科学研究部门、防疫部门等，可以联系百度研究院这个项目的专用邮箱抵抗瘟疫，众志成城，中国在行动!

LinearFold 算法介绍

传统上，RNA二级结构预测采用自底向上的动态规划(DP)，是一种三次方时间复杂度的算法，也就是说，如果序列长度翻一倍的话，就要付出 8 倍的计算时间，这对于 RNA 病毒基因组这样的超长序列(例如艾滋病毒有约1万个碱基，埃博拉病毒有约2万个碱基)需要很长的等待时间。LinearFold创造性的将传统算法中自底向上的动态规划改为从左到右的方式，并利用”beam pruning“的思想，只保留分数较高的中间状态，从而大大减小了搜索空间。

LinearFold能够在线性时间内预测RNA二级结构，在长序列RNA上的预测速度远远大于传统算法。下图比较了传统算法与LinearFold算法的运行时间、所需内存：

同时LinearFold在预测精度上相比传统算法也有提升。尤其对于长序列RNA二级结构(如16S和23S rRNA二级结构)和长碱基对(相距500+ nt)预测上，LinearFold预测精度有显著地提升。下图比较了传统算法与LinearFold算法的预测精度