标准动态规划与懒惰动态规划.doc

《标准动态规划与懒惰动态规划.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、本科生学年论文（设计）题目：比对算法论文学院生命科学学院学科门类理学专业生物信息学号姓名岳海川指导教师刘建国2015年7月19日标准动态规划与懒惰动态规划岳海川生物信息一、标准动态规划StandardDPA是生物信息学中最流行的解决方法，其基本思想可简述为：使用迭代方法计算出两个序列的相似分值，存于一个得分矩阵中；根据这个得分矩阵，回溯寻找最优的比对序列。标准动态规划算法求解过程是从两个比对序列前端开始，逐步推进，直到两个序列的末端。标准动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新

2、、排序、装载等问题，用标准动态规划方法比用其它方法求解更为方便。虽然标准动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用标准动态规划方法方便地求解。标准动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不像搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。标准动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题

3、方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。标准动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态

4、规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。标准动态规划的基本模型如下：(1)确定问题的决策对象。(2)对决策过程划分阶段。(3)对各阶段确定状态变量。(4)根据状态变量确定费

5、用函数和目标函数。(5)建立各阶段状态变量的转移过程，确定状态转移方程。状态转移方程的一般形式：一般形式：U：状态；X：策略　　顺推：f[Uk]=opt{f[Uk-1]+L[Uk-1,Xk-1]}其中，L[Uk-1,Xk-1]：状态Uk-1通过策略Xk-1到达状态Uk的费用初始f[U1]；结果：f[Un]。倒推：　　f[Uk]=opt{f[Uk+1]+L[Uk,Xk]}　　L[Uk,Xk]：状态Uk通过策略Xk到达状态Uk+1的费用　　初始f[Un]；结果：f(U1)序列A=acgtacgtacgtB=acatacttgtact经StandardDPA比对结果

6、如图：标准动态规划算法的优点：因其准确性高而得到广泛应用，适用于字符数量不大的序列，易于理解。缺点：时间和空间复杂度为O(n2),而在实际的生物信息处理中,进行比对的生物序列通常有上万个以上的字符,因此标准动态规划方法不是很实用。二、懒惰动态规划LazyDPA是动态规划算法的一个特例，懒惰的评价是在编程中动态规划算法编辑距离问题快速运行的描述。其基本思路：从问题的某一个初始解出发逐步逼近给定的目标，以最快的速度求得更好的解，直到到达最后目标，不能继续进行下，算法停止。这其中的每一步，都是得到的一个当前最优解，传递到下一步，从而保证每一步都是选择当前最优的情况，

7、最后得到结果。每步只考虑一个数据，这个数据满足局部最优条件。编辑距离的问题是找到点突变，DAB，以编辑一个给定的一个字符串到另一个指定的字符串乙所需的最低人数。一个点突变是下列之一：改变一个字母，插入一个字母，或者删除一个字母。分子生物学中有时人们还希望找到一组最小突变来编辑B的问题，在重要的分子中，生物学用于相似度比较线性大分子。它也出现在拼写校正，文件比较等“计算”的问题。它是密切相关的时间最长的共序列问题。有一个大型的工作机构，在计算和生物文献算法，命令式语言，为编辑距离问题及其亲属。Thispaperdiscussessolvingtheedit-di

8、stanceprobleminalaz