%0 Journal Article
%T rna二级结构预测中动态规划的优化和有效并行
%A 谭光明？
%A 冯圣中？
%A 孙凝晖？
%J 软件学报
%P 1501-1509
%D 2006
%X 基于最小自由能模型的方法是计算生物学中rna二级结构预测的主要方法,而计算最小自由能的动态规划算法需要o(n4)的时间,其中n是rna序列的长度.目前有两种降低时间复杂度的策略:限制二级结构中内部环的大小不超过k,得到o(n2×k2)算法;lyngso方法根据环的能量规则,不限制环的大小,在o(n3)的时间内获得近似最优解.通过使用额外的o(n)的空间,计算内部环中的冗余计算大为减少,从而在同样不限制环大小的情况下,在o(n3)的时间内能够获得最优解.然而,优化后的算法仍然非常耗时,通过有效的负载平衡方法,在机群系统上实现并行程序.实验结果表明,并行程序获得了很好的加速比.
%K 最小自由能
%K 动态规划
%K 计算冗余
%K 负载平衡
%K 加速比
%U http://www.jos.org.cn/ch/reader/view_abstract.aspx?file_no=20060703&flag=1