好吧,其实这么炸裂的名字既不动态,也无关编程技巧,只是Richard Bellman为了吓唬人而取的,hoho…
算法思想
动态规划算法是运筹学的一个分支,最早用于解决最优化决策问题,其在序列比对中有比较广泛的应用,如著名的BLAST、CLUSTALW、MFOLD、PHYLIP等都利用了其核心思想,主要包括三个部分:
递归:将一个大问题转换为多个子问题。对于序列比对来说,长度为N的两条序列大约有22N/2πN−−−−√种不同的比对方式,这在实际中几乎不可操作,而利用动态规划,将一整条序列变为一个个的碱基进行比对,从计算规模上给予了解决之道。一般性的递归公式为:
动态规划矩阵:自下而上,记录每个子问题的得分及最佳路径;
回溯:从最后一个位置S(M,N)回溯至(0,0),从而得到整条解决路径,但最佳路径可能不止一条。
对于序列比对来讲,动态规划只是从数学上给出了N2规模的计算方法,然而实际应用中可能面对百万级数量的长度不等的序列,这种时间复杂度就变得不可接受,故BLAST等算法往往是动态规划的一种快速逼近。
打分规则
动态规划虽然给出了算法,但对于序列比对来说,面临着如何评价相似性的高低、如何评价indel与mismatch的不同影响、是否考虑遗传变异等等涉及到生物学意义的问题,这就对打分规则提出了要求。
著名的BLOSUM矩阵就是基于这样一个打分公式:s(a,b)=1λlogPabfafb,其中Pab为期望的概率,fa和fb为背景概率,λ仅作为缩放因子。我们也可以根据自身的需求,参照不同的生物学假设,设定不同的打分矩阵,对序列相似性作出个性化的评价。
原文链接https://wenlongshen.github.io/2016/12/04/Dynamic-Programming/
转载本文请联系原作者获取授权,同时请注明本文来自沈文龙科学网博客。
链接地址:https://wap.sciencenet.cn/blog-543513-1026956.html?mobile=1
收藏