rna二级结构预测中动态规划的优化和有效并行

基于最小自由能模型的方法是计算生物学中rna二级结构预测的主要方法,而计算最小自由能的动态规划算法需要o(n4)的时间,其中n是rna序列的长度.目前有两种降低时间复杂度的策略:限制二级结构中内部环的大小不超过k,得到o(n2×k2)算法;lyngso方法根据环的能量规则,不限制环的大小,在o(n3)的时间内获得近似最优解.通过使用额外的o(n)的空间,计算内部环中的冗余计算大为减少,从而在同样不限制环大小的情况下,在o(n3)的时间内能够获得最优解.然而,优化后的算法仍然非常耗时,通过有效的负载平衡方法,在机群系统上实现并行程序.实验结果表明,并行程序获得了很好的加速比.