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

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

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

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

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

5、态转移方程的一般形式： 一般形式： U：状态； X：策略顺推：fUk=optfUk-1+LUk-1,Xk-1 其中， LUk-1,Xk-1： 状态Uk-1通过策略Xk-1到达状态Uk 的费用 初始fU1；结果：fUn。 倒推：fUk=optfUk+1+LUk,XkLUk,Xk： 状态Uk通过策略Xk到达状态Uk+1 的费用初始fUn；结果：f(U1)序列 A = acgtacgtacgt B = acatacttgtact经Standard DPA比对结果如图：标准动态规划算法的优点：因其准确性高而得到广泛应用，适用于字符数量不大的序列，易于理解。缺点：时间和空间复杂度为O(n2),而在实际的

6、生物信息处理中,进行比对的生物序列通常有上万个以上的字符,因此标准动态规划方法不是很实用。二、懒惰动态规划 Lazy DPA是动态规划算法的一个特例，懒惰的评价是在编程中动态规划算法编辑距离问题快速运行的描述。其基本思路：从问题的某一个初始解出发逐步逼近给定的目标，以最快的速度求得更好的解，直到到达最后目标，不能继续进行下，算法停止。这其中的每一步，都是得到的一个当前最优解，传递到下一步，从而保证每一步都是选择当前最优的情况，最后得到结果。每步只考虑一个数据，这个数据满足局部最优条件。编辑距离的问题是找到点突变，D A B，以编辑一个给定的一个字符串到另一个指定的字符串乙所需的最低人数。 一个

7、点突变是下列之一： 改变一个字母， 插入一个字母，或者删除一个字母。分子生物学中有时人们还希望找到一组最小突变来编辑B的问题，在重要的分子中，生物学用于相似度比较线性大分子。 它也出现在拼写校正，文件比较等“计算”的问题。 它是密切相关的时间最长的共序列问题。 有一个大型的工作机构，在计算和生物文献算法，命令式语言，为编辑距离问题及其亲属。 This paper discusses solving the edit-distance problem in a lazy functional language$Peyt.本文讨论了一个懒功能语言求解编辑距离的问题。 It begins with

8、a simple but inefficient algorithm.它从一个简单但低效的算法。 其中有O（| A | * | B |）的时间和空间 - 复杂性。 A simple modification of this second algorithm and an obvious observation lead to an O(|A|*(1+D A B) algorithm.本次算法的简单修改和明显的观察导致O（| A | *（1 + DAB）算法。 This is fast for the important special case of similar strings.这是快速进

9、行的相似字符串的重要的特殊情况。 It exploits lazy-evaluation to gain its speed.它利用懒惰的评价来获得它的速度。 It is as simple as the basic DPA but, thanks to lazy-evaluation, effectively implements an eager or greedy strategy$Mill$Myer which requires added complication when written in an imperative language.这很简单，只要基本DPA但是，由于懒惰评估

10、，有效地实现了一个渴望或贪婪策略这需要更加复杂的时候写的命令式语言。 This may give hope to the less energetic among us: being lazy can be fast.这可能给我们中间能量较低以希望：懒惰可快。 A = acgtacgtacgtB = acatacttgtact B = acatacttgtactA = acgtac gtacgt A = acgtac gtacgt | | | | | | | |B = acatacttgtac t B = acatacttgtac t | | | | | | | | delete | | 删除

11、 | | | | | insert*2 | 插入* 2 | | change变化DAB = 4 DAB = 4序列A = acgtacgtacgtB = acatacttgtact B = acatacttgtact经Lazy DPA比对结果如图：定字符串A和B，以自然的方式，开始计算的DAB是比较它们的第一个字母.（等效地，一开始可以与最后一个字母来制备。）如果它们相等，没有突变是必需在这里，所以编辑距离的字符串的其余部分，As= TL A和Bs = TL B，计算。 If they are not equal a mutation is required and there are three possibilities: (i) hd A can be changed into hd B and As edited into Bs, (ii) hd A can be deleted and As edited into B, or (iii) hd B can be inserted and A edited into Bs.如果它们是不相等的，有三种可能性：（）A可以改变为B，As编辑成B（）A可以被删除，并且As编辑成B，或（iii） B可以用插入，且编辑成Bs。 The least costly alternative is chosen.成本最低的替代选