数学建模案例SPDP基因限制性图谱重构.pdf

DNA 限制性图谱绘制 SPDP 问题的解决算法 第 1 页 共 41 页 DNADNADNADNA 限制性图谱绘制限制性图谱绘制限制性图谱绘制限制性图谱绘制 SPDPSPDPSPDPSPDP 问题的解决算法问题的解决算法问题的解决算法问题的解决算法 刘若鹏 彭博 论文摘要论文摘要 本文首先证明了该问题不存在多项式算法 最坏情况下其时间复杂度不低于 指数 进而在穷举法基础上提出了一种优化算法 该算法通过分析所有的 DNA 片 段数据 建立了 b b 表与 b c 表 利用两个表的逻辑 几何的关系对穷举二叉树进 行预测 对穷举过程进行强限制 极大优化穷举法 文中并应用计算机实践报告 与复杂度理论分析对所提出的算法进行了深入的测试与评估 对于稀疏的数据该 算法时间平均复杂度是多项式 在解决了一般 SPDP 问题后 针对带误差的 SPDP 问题 通过对误差及概率 的讨论给出了一解法 解决了含有误差的 SPDP 问题 在原有 SPDP 问题上 考虑实际需要 对 SPDP 问题进行分析 提出了改进 方法 并对于一些特殊情况进行了讨论 关键词 DNA 限制性图谱SPDP算法 DNA 限制性图谱绘制 SPDP 问题的解决算法 第 2 页 共 41 页 目录 1SPDP 问题介绍 3 1 1PDP 部分消化法 3 1 2SPDP 简化部分消化法 4 2问题分析 5 2 1SPDP 算法的目标 5 2 2SPDP 算法是指数复杂度问题 5 2 3穷举法 6 2 4对穷举法优化 6 3建立数学模型以及 SPDP 问题算法 6 3 1关于 SPDP 的两种数学模型及其穷举算法 6 3 2关于 SPDP 的一些基本定理 9 3 3利用基本定理构建 SPDP 的标准问题并确定其数据结构 13 3 4对 SPDP 算法进行进一步的优化 建立 b b 表与 b c 表 16 3 5SPDP 问题算法 24 4算法的实践与检验 25 4 1穷举算法实验 25 4 2关于 SPDP 问题算法实现中时间与空间复杂度的协调分析 26 5算法评估 27 5 1对于算法复杂度的估计 27 5 2对 SPDP 二叉树数据结构进行分析 27 5 3对于 SPDP 问题算法优化效率的分析 28 5 4SPDP 问题算法的进一步讨论 34 6测量值含有误差时对本算法的影响 35 6 1确定 b b 表和 b c 表 35 6 2算法的相应变化 39 6 3误差对问题求解的影响 39 6 4有误差计算模型的评价和讨论 40 7SPDP 方案的改进 40 7 1并行算法 40 7 2SPDP 原理改进 41 DNA 限制性图谱绘制 SPDP 问题的解决算法 第 3 页 共 41 页 1 1 1 1 SPDPSPDPSPDPSPDP 问题介绍问题介绍问题介绍问题介绍 绘制 DNA 限制性图谱 restriction mapping 是遗传生物学中的重要问题 由于 DNA 分子很长 目前的实验技术无法对其进行直接测量 所以生物学家们 需要把 DNA 分子切开 一段一段的来测量 在切开的过程中 DNA 片段在原 DNA 分子上的排列顺序丢失了 为了构造限制性图谱 可以采用不同的生化技 术获得关于图谱的间接信息 然后采取组合的方法用这些数据重构图谱 本文涉及到了两个测量 DNA 限制性图谱的方法 1 11 11 11 1 PDPPDPPDPPDP 部分消化法部分消化法部分消化法部分消化法 利用限制性位点酶可以将 DNA 分子中的限制性位点切开 假如一个 DNA 分子有 n 个限制性位点 利用不同的限制性位点酶 通过大量实验得到任两个限 制性位点 包括两个端点 的长度 共 2 22 n C个值 把利用这些数据作为第一组 数据 PDP 方法就是利用这组数据重新构建 DNA 限制性图谱 例如 2 3 4 5 2 5 9 14 16 7 12 14 9 11 7 图 1 图 1 中 A B 是 DNA 分子的两个端点 a b c 和 d 是限制性位点 通过 实验可以得到 2 3 4 5 2 5 9 14 16 7 12 14 9 11 7 再通过 来求 对应 于上图的 0 2 5 9 14 16 是一种解 1 21 21 21 2 SPDPSPDPSPDPSPDP 简化部分消化法简化部分消化法简化部分消化法简化部分消化法 鉴于目前的实验技术所限 PDP 的方法实行起来有相当的难度 所以在 PDP 的基础上得到了 SPDP 方法 SPDP 方法不需要得到任两个限制性位点的距离 DNA 限制性图谱绘制 SPDP 问题的解决算法 第 4 页 共 41 页 只要的测量任一个位点到两个端点的距离 作为第一组数据 以每段 DNA 片段 的长度作为第二组数据 重构 DNA 限制性图谱 图 2 中 a 就是我们希望重构的 DNA 图谱 b 中的前 4 对图谱为第一 组数据 它的每对的长度和都是 16 剩下的为第二组数据 含有 5 个片段的长 度 是由 a 每段都切开以后得到的 SPDP 方法就是要利用 b 中的数据通过计算重构图谱 a 的结构 DNA 限制性图谱绘制在目前的技术条件下 SPDP 是一个可行的办法 但是 SPDP 的实验数据只有不完整的片段长度 需要对这些片段长度进行数学处理才 能得到原始的 DNA 限制性图谱 本文第 3 部分中面对生物学对 SPDP 问题的求 解需要 给出了一个完整的 SPDP 问题的解法 图 2 DNA 限制性图谱绘制 SPDP 问题的解决算法 第 5 页 共 41 页 2 2 2 2 问题分析问题分析问题分析问题分析 2 12 12 12 1 SPDPSPDPSPDPSPDP 算法的目标算法的目标算法的目标算法的目标 SPDP 问题的目标是求出 DNA 限制性图谱 由于 SPDP 提供的两组数据相 对于原有的 DNA 限制性图谱已经不完整 通常情况下有多个解 比如实例二的 数据解就不是唯一的 当解不唯一的情况下 必须解出所有可能解 然后利用生 物学方法判断这些可能接中哪一个是原 DNA 限制性图谱 如果算法求出的解不 全 有可能真实的 DNA 限制性图谱没有被求出 那么对下一步的科学工作会导 致错误 所以 SPDP 算法是要求出所有符合第一组和第二组数据的全部可能解 根据生命科学的需要 DNA 测序往往是将原有的 DNA 切至几十段到几百 段 如果在 N 1000 的情况下 可以求出原有的 DNA 图谱的排序即可满足 SPDP 的基本需要 2 22 22 22 2 SPDPSPDPSPDPSPDP 算法是指数复杂度问题算法是指数复杂度问题算法是指数复杂度问题算法是指数复杂度问题 通过对多解情况下 SPDP 问题的研究 发现对存在大量解的 SPDP 数据 在 3 4 3 中给出了一个构造大量解的 SPDP 数据 表 1 为该数据解的数 量 这组数据的解至少有 3 2 n 个 解 那么对于任何一个算法求出所 有解的时间复杂性至少不低于 3 2 n 据此可以判断 SPDP 问题至 少是指数复杂度问题 对于指数复杂度问题 无法求得多项式算法 因此目标在 于寻找优秀的穷举算法 2 32 32 32 3 穷举法穷举法穷举法穷举法 穷举法可以通过两种方法实现 两种穷举法的效率分别是 NN 和 N N2 分 N解数量 596 6192 7384 8768 91536 103072 15 20 表1 超出硬件计算能力 约100000 DNA 限制性图谱绘制 SPDP 问题的解决算法 第 6 页 共 41 页 别在 3 1 1 和 3 1 2 中进行了详细讨论 2 42 42 42 4对穷举法优化对穷举法优化对穷举法优化对穷举法优化 在 N N2 穷举法的基础上 我们对算法进行了多次优化 提出了标准 SPDP 算法 详见 3 6 节 标准 SPDP 算法的核心思想是通过对第一组数据与第二组数据分析 不仅考 虑组内数据的关系 同时也分析组间的数据关系 得到对于 SPDP 解的约束 在 搜索中 利用约束 可以去掉绝大部分的不可能解 只需要在极少剩余的可能解 搜索即可得到全部 SPDP 问题的解 该思想可以通过二叉树搜索实现 3 1 2 穷 举法中搜索算法基于二叉树搜索 此时 只需把约束条件加入对于二叉树每个节 点的判断 当该节点不再符合约束条件时 对该节点的子树可以停止搜索 搜索 整树后得到全部 SPDP 的解 基于这种思想 我们提出了解决 SPDP 问题的优秀 算法 3 3 3 3 建立数学模型以及建立数学模型以及建立数学模型以及建立数学模型以及 SPDPSPDPSPDPSPDP 问题算法问题算法问题算法问题算法 3 13 13 13 1 关于关于关于关于 SPDPSPDPSPDPSPDP 的两种数学模型及其穷举算法的两种数学模型及其穷举算法的两种数学模型及其穷举算法的两种数学模型及其穷举算法 利用 SPDP 方法重构 DNA 的顺序时 已知的数据有两组 若一段 DNA 的位 点总数为 n 则第一组数据是通过对位点进行一次切割而得到的 2n 组数据 第 二组数据是切开所有的位点得到的 n 1 个片段的数据 这样就有两种穷举法可以 解决顺序重构的问题 3 1 13 1 13 1 13 1 1第一种数学模型以及其穷举算法第一种数学模型以及其穷举算法第一种数学模型以及其穷举算法第一种数学模型以及其穷举算法 第一种方法是通过对第二组数据这 n 1 个片段的顺序直接进行组合 对于每 DNA 限制性图谱绘制 SPDP 问题的解决算法 第 7 页 共 41 页 一种组合用第一组数据进行检测 看看是否符合第一组数据的要求 具体写成数 学表达如下 设 第 一 组 数 据 为 11 bb 22 bb 33 bb nn bb 第 二组数据为 1321 n cccc 其 中 i b表示 DNA 被切开后其中一段 的长度 并且 i b与 i b 是同一段基因 被切成的两段的长度 所以有 i b i b L L 为 DNA 总长度 其中 i 1 2 3 n 将第二组数据 c 进行排列后可以得到 n kkkk cccc 321 这样一组序列 而要 检验这组排列的序列是否合理就要看它是否满足第一组数据的要求 即检验对于 每个 j 1 2 3 n 1 在第一组数据中是否有一对 b 可以与和式 j kkkk cccc 321 对应 并且每组 b 只可以对应一个和式 流程图如图 3 表示 对于这种穷举法 我们很容易可以看出 要将 c 不重不漏的进行全排列 再加上 每一步的检验 其复杂度高于 n 虽然这种模型的思路最直接 但是其时间复杂 度过高 不能应用于程序的实践 3 1 23 1 23 1 23 1 2第二种数学模型以及其穷举算法第二种数学模型以及其穷举算法第二种数学模型以及其穷举算法第二种数学模型以及其穷举算法 第二种想法则是从第一组数据入手 进行一定的组合 而利用第二组数据对 第一组数据的组合进行检验 这里 我们首先要对第一组数据进行一定的处理 在第一组数据中 DNA 都是被切成两段 当 DNA 总长度 L 知道的时候 其实 只要知道每对 b 中的一个值就得到了全部的信息 现在我们将每对 b 中较小的一 个挑出来 若 i b与 i b 相等任取一个就可以 这样我们就得到了 n 个数据 再对 这 n 个数据进行升序排列 得到一个不严格递增的 b 序列 在这里不妨记作 n bbbb 321 它们满足 2 321 L bbbb n 它包含了第一组数据 的所有的信息 为了方便计算 我们不妨先对基因图谱的起点和终点做一个规定 假设从起 输出答案用 b 检验 对 c 组合 图 3 不合条件 符合条件 DNA 限制性图谱绘制 SPDP 问题的解决算法 第 8 页 共 41 页 点算起 第一个位点到起点的距离小于或者等于从终点算起第一个位点到终点的 距离 即 11 n kk cc 对于重新组织后的第一组数据 其含义为 对于某一个 i b 它表示离这段基 因起点或者终点 i b距离的位置有一个位点 则对于第二种穷举方法也就由此而得 出 对于每个 i b它有两种状态 一种是靠近起点 不妨用 0 表示 另一种是 靠近终点 不妨用 1 来表示 而当全部的 i b的状态确定后 DNA 的顺序也 就确定了 但此时要对这个顺序的合理性进行检验 即检验这个顺序是否符合第 二组数据 c 的要求 具体措施如下 将 0 状态的 i b全部挑出来按照升序排列 l ssss bbbb 3121 再将 1 状态的 i b全部挑出来按照升序排列 nlll ssss bbbb 321 记第二组数据 c 组成 的集合为 1321 n ccccC 然后检验是否满足以下条件 CCbs 1 1 前半段 112 12sss bCCbb 1223 23ssss bbCCbb 211 1 llll ssllss bbCCbb 11 1 lll sslls bbCCb 后半段 1 12 llss CCbb ll 211 1 nnnn ssnnss bbCCbb 1 1 nnln ssnnss bbCCbbL 当全部检验条件符合的时候 这组组合即为合理的顺序 从 DNA 的起点算起 在前半段的基因中 第 i 段长度为 1 ii ss bb 其中0 0 s b 而对于后半段则有 DNA 限制性图谱绘制 SPDP 问题的解决算法 第 9 页 共 41 页 相同的处理 其示意图如图 5 表示 流程图如图 4 表示 这里值得说明一下的就 是对与这个循环的结束条件 因为对 于基因的排序问题 必须要求出所有 的可能解 因此对于这个循环就必须 要把所有的可能组合全部进行一遍 以后才可以停止 即需要循环 n 2 次 分析这个模型以及它的穷举方法可以容易的发现 对 b 进行组合时的复杂度 为 n 2 而每次判定组合是否是合理的组合还需要利用查找函数 复杂度为n 2 log 所以总的复杂程度在n n 2 log2 以上 对于计算机的实现而言 指数的复杂度仍 然是非常高的 而且属于 坏 算法 但对比模型一的穷举法而言 它比 n 要 好的多 因此我们可以看到 这两组初始数据所包含的信息并不等价 显然似乎 是第一组数据包含的信息要多一些 这是因为第一组数据所给出的长度都是关于 整段基因的绝对位置 而第二组全部都是相对位置 而在问题分析中我们也有这 样的思想 这个问题并没有多项式的算法 因此 我们需要找到一种高效率的穷 举法 而从第二个模型的穷举法入手进行优化是比较合适的 3 23 23 23 2 关于关于关于关于 SPDPSPDPSPDPSPDP 的一些基本定理的一些基本定理的一些基本定理的一些基本定理 通过 3 1 的分析 我们希望能从第二个模型入手优化算法 对于第二种模型 的穷举 我们已经讨论了它必须要经过 n 2 次的循环才能结束 而 SPDP 问题有它 其中的一些特有的性质与规律 我们希望能找到这样的性质与规律来减少循环的 次数 并且将复杂的问题化约为标准的情形便于算法的实现 基于上述这种考虑 我们寻找了一些性质 并将比较重要的总结为一些基本的定理 以便后面进行算 法设计与优化 在给出定理之前 先对一些术语做一定的规定 首先规定 同侧 与 异侧 我们将整段基因分为前半段与后半段 以基因正中为分界 在第二种模型中 不合条件 符合条件 输出答案用 c 检验 组合 b 图 4 1 s b 2 s b l s b m s b 1 l s b 2 l s b 图 5 DNA 限制性图谱绘制 SPDP 问题的解决算法 第 10 页 共 41 页 ji bb与称为同侧 如果 ji bb与所表示的位点的位置在同一段中 同属于前半段或 后半段 ji bb与称为异侧 如果 ji bb与所表示的位点不在同一段中 而对于整 段基因的每个片段我们都将认为它是一个元素 那么从起点开始的第一个片段我 们称之为 首元素 而从终点开始的第一个片段我们称之为 尾元素 而包含 基因中点位置的基因片段我们称之为 中间元素 下面我们给出 SPDP 问题的一些基本定理 3 2 13 2 13 2 13 2 1定理一 首元素定理 定理一 首元素定理 定理一 首元素定理 定理一 首元素定理 在 第 二 种 模 型 中 对 于 第 二 组 数 据 n bbbb 321 满 足 2 321 L bbbb n 则 1 b为 首 元 素 片 段 的 长 度 1 1s bb 即 在 1321 n cccc 中存在 c与 1 b相等 并且从起点算起第一个基因片段的长度 就为 1 b 或者说该片段就是 c 定理一说明 定理一说明 此定理唯一的确定了首元素 节省了排列这个元素的时间 它 更重要的意义在于把问题进行标准化 3 2 23 2 23 2 23 2 2定理二 尾元素定理 定理二 尾元素定理 定理二 尾元素定理 定理二 尾元素定理 在确定了首元素之后 我们把第二组数据中的 1 b除去 把与其对应的 c除 去 在剩下的 b 与 c 中 我们寻找相等的 b 与 c 比如 ji cb 那么这个 i b就是 可能的尾元素 j c为它的对应元 即从整段基因的终点算起 第一个片段 实 际上是这段基因最后一个片段 的长度为 i b 或者说最后一段基因就是 j c 定理二说明定理二说明 此定理给出了尾元素 最后一个片段 可能的情况 与首元素 一起可以将整段基因的首尾确定下来 当尾元素的可能性超过一个是我们每次只 考虑其中一种首 尾元素的情况 然后对首 尾元素的组合进行穷举 可以看出 这个循环最多是 n 1 次 DNA 限制性图谱绘制 SPDP 问题的解决算法 第 11 页 共 41 页 3 2 33 2 33 2 33 2 3定理三 首尾排序定理 定理三 首尾排序定理 定理三 首尾排序定理 定理三 首尾排序定理 当首 尾元素确定后 若首元素长度为 1 b 尾元素长度为 s b 则 1432 s bbbb所表示的位点的位置必在同侧并且在前半段 并且它们所确定 的位点在整段基因中彼此相邻 即 1 ii bb与所确定的两个同侧位点之间没有别的 位点 其中 i 2 3 4 s 1 定理三说明 定理三说明 首先 对尾元素 s b要进行一个补充 实际问题中有可能出现 1 ss bb的情况 此时我们的脚标 s 选取两者脚表较大的一个 取 s b而不取 1 s b 而且对于 1 ss bb相等的情况 s b与 1 s b一定在异侧 表示在与中点对称的两个 位置有两个位点 而且由此观点我们还可以知道如果 1 ss bb 则必然有 11 ssss bbbb 因此 1 s b严格大于 s b 1 s b严格小于 s b 其实这个结论也非 常重要 但很直观 就不在这里做为定理 而定理三一方面可以节省 1432 s bbbb在组合中的状态选择 更主要的是当首尾元素确定后 它可以 将 SPDP 问题进行标准化 即通过首尾排序定理后 我们可以把最靠近起点的 s 1 段基因看作一个整体 因为这 s 1 段的顺序已经知道了 当作一个基因片段 它的长度为 1 s b 并且 ss bb 1 而 b 中剩下的元素都比首尾元素大 3 2 43 2 43 2 43 2 4定理四 尾元素约束定理 定理四 尾元素约束定理 定理四 尾元素约束定理 定理四 尾元素约束定理 在定理三的说明中 我们知道 b 中的元素有可能两两相等 如果 1 ss bb 我们记录 1 s b为重值代表 我们找出所有的重值的情况并记录其重值代表 l kkkk bbbb 321 其中角标满足 l kkk 21 若尾元素长度为 s b 则有约 束 1 ks bb 即 1 ks 定理四说明定理四说明 此定理是对尾元素定理的一个补充 通过这个约束限制了尾元 素的可能情况 降低计算的复杂程度 DNA 限制性图谱绘制 SPDP 问题的解决算法 第 12 页 共 41 页 3 2 53 2 53 2 53 2 5定理五 中间元素对偶定理 定理五 中间元素对偶定理 定理五 中间元素对偶定理 定理五 中间元素对偶定理 由前面的定义知道中间元素是包含中点的片段 那么此片段的两端有一端的 位置必在 n b所确定的位点 而另一段的位置若为 j b所确定的位点 那么一定有 在第二组数据 c 中有元素与 jn bb 相等 则这类 j b就为另一端点 并且若将 n b视 为从整段基因中点往两端算起的首位点 首元素 它是距离中点最近的位点 而将 j b视为中点另一侧的第一个出现的位点 那么中间元素的两端可以等效为 基因的起点和终点 n b等效为首元素 j b等效为尾元素 那么定理一到定理四 的性质在此处都将成立 这就是中间元素的两端与起点 终点的对偶性质 定理五说明 定理五说明 前四个定理实际上是从基因的两端出发并不断的向中间考察 而定理五刚好相反 是先确定最中间的情况 再想两边考察 对于定理五的应用 在 3 5 进行讨论 3 2 63 2 63 2 63 2 6定理六 相邻重值等效方法 定理六 相邻重值等效方法 定理六 相邻重值等效方法 定理六 相邻重值等效方法 若 2 ii bb与均为重值代表 即 321 iiii bbbb 那么在第二 组数据 c 中一定有两个相等的 ii bbcc 2 并且在 整段基因中 它们的位置如图 6 所 示 因此这两段基因片段的位置就 已经确定下来 因此我们可以将 A 点与 B 点接起来 C 点与 D 点接起来 这样 原来的基因长度就缩短了 2 2ii bb 在数据中除去上述几个元素 在剩余的 b 中 我 们 要 对 nii bbb 54 进 行 一 定 的 处 理 对 每 个 数 处 理 后 的 值 为 2iikk bbbb 其中 k i 4 i 5 n k b为 k b处理后的值 当如果有更多 的重值代表两两相邻 我们可以用同样的方法在一开始就把这些位置已经确定的 片段去除 等效出新的一整段基因以及它的初始数据 当最后计算出全部的结果 图 6 DNA 限制性图谱绘制 SPDP 问题的解决算法 第 13 页 共 41 页 之后再将这些已知的片段插回去 定理六说明定理六说明 此定理最重要的作用就是可以将问题进行标准化 使要解决的 问题不含有那些已经知道基因片段位置的这些特殊情况 从另一个角度看这也是 通过对数据特征的观察降低计算的复杂度 3 33 33 33 3 利用基本定理构利用基本定理构利用基本定理构利用基本定理构建建建建SPDSPDSPDSPDP P P P的标准问题并确定其数据的标准问题并确定其数据的标准问题并确定其数据的标准问题并确定其数据 结构结构结构结构 3 3 13 3 13 3 13 3 1标准化标准化标准化标准化 SPDPSPDPSPDPSPDP 问题的建立问题的建立问题的建立问题的建立 有了 3 2 中一些基本规律 定理的准备 我们就可以建立标准化的 SPDP 问 题 建立过程如下 第一步 利用定理六 相邻重值等效方法 去除由于相邻对称的位点所确定 的基因片段 调整两组数据 b 与 c 的值 第二步 利用定理一 首元素定理 确定首元素 除去 b 中的首元素元与 c 中的对应元 第三步 利用定理二 尾元素定理 与定理四 尾元素约束定理 确定尾元 素的可能值 并在计算中对每个有可能的尾元素进行循环 当确定 其中一个可能值作为尾元素时 去除 b 中的尾元素元与 c 中的对应 元 第四步 利用定理三 首尾排序定理 并将前 s 1 个片段看为等效首元素 1 s b 尾元素为 s b 这里要注意 若发现前 s 1 个片段中存在一个片 段的长度在 c 中没有对应相等的值时 说明所选的尾元素并非真正 的尾元素 此时返回第二步 经过上述四步处理后 SPDP 的原模型已被标准化 对此时的第一组数据 b 重新按递增排序 并重新给予脚标 将重值赋予同样的脚标 这样就可以得到新 的 2 21 L bbb l 并记录有重值的 b 仍用 i k b 这样一组数来表示 由 定理三说明中的分析知道 b 若有重值最多只有两个元素等相等 而对于第二组数 据 c 也同样重新赋予脚标并排序得到 m ccc 21 并用 m pppp 321 DNA 限制性图谱绘制 SPDP 问题的解决算法 第 14 页 共 41 页 记录每一个 c 值重复的个数 通过上面五步的操作 我们得到标准化的 SPDP 问题 为了保持定理的习惯 以及后面算法设计的方便 我们对于第一组数据 b 不去处首尾元素 则 1 b为首元 素 2 b为尾元素 b 数据满足 2 21 L bbb l 而在 c 数据中我们却已经 把首尾元素对应相等的值已经去除 则对于标准化问题 我们要做的事情就是要 确定 l bbb 43 的状态组合 判定每个 i b属于前半段还是后半段 而我们的 数据结构与算法就需要针对这样的标准 SPDP 问题进行选取与设计 3 3 23 3 23 3 23 3 2SPDPSPDPSPDPSPDP 数据结构的选取 利用二叉树 数据结构的选取 利用二叉树 数据结构的选取 利用二叉树 数据结构的选取 利用二叉树 当我们已经将原模型转化为 SPDP 的标准问题后 我们就开始需要对 l bbb 43 的 状 态 进行确定 因为在确定 它们的状态的时候是 逐一进行的 因此每轮 到确定某个 i b 它就有 两个可能的选择 属于前半段或者属于后半段 根据这样的一个特点我们选取 二叉树作为 SPDP 标准问题的主体数据结构 接下来的问题就是要确定我们如何的逐一的对 i b进行选择和建树 这里 我 们选择的顺序是从 3 b开始从小到大的对 b 数据进行判定并建立二叉树 我们以 3 b 为例来看下如何建树 如图 7 所示 3 b要不然在前半段 要不然在后半段 并且 我们考察 13 bb 与 23 bb 这两个差值之中至少有一个可以与 c 中的某个元素 c 相等 其原因为 1 b是首元素 2 b为尾元素 并且 3 b是数据 b 中除了 1 b 2 b最 小的元素 它所决定的位点应该是距离前半段第一个位点或者后半段第一个位点 距离最近的点 21 aa或者一定是 c 中若干片段中的一个 不然在这种首尾元素组 合下没有合理解 这样 我们就可以通过判定能否在 c 中找到 c 13 bb 或者 图 7 DNA 限制性图谱绘制 SPDP 问题的解决算法 第 15 页 共 41 页 c 23 bb 而判定 3 b状态的可能性 倘若 c 13 bb 那么 3 b就有可能在前半段 建立二叉树时现在所处在的结点就有左树枝 而左树枝结点的数据中 c 中的数 据就要去除 c 当 c 23 bb 则现在所处的结点有右树枝 并且对右树枝所在 的结点做同样的处理 如果 c 23 bb 则右树枝为空 并且不再被考虑 因为 那是一条不可能的路径 依次类推 我们从小到大依次考虑每一个 i b 并通过上 述的判定来建立二叉树 最后需要对重值的 b 做一个解释 如果 i b有重值 当考 虑到 i b时 应该对两边同时进行判断 是否两个 i b能同时在两段都成立 若有其 中一边不成立则说明这条支路无解 如此运行 直到所有的 i b都被考虑完 循环 停止并将最后合理的组合所确定的 DNA 顺序输出 关于这个数据结构的流程如图 8 所示 否 判断该段 b 能 否放入后半段 DNA 图谱 判断该段 b 能 否放入前半段 DNA 图谱 否 开始 是 进 入 下 一 个 节 点 进 行 搜 索 是 该节点子树 没有解 搜 索其他节点 图 8 DNA 限制性图谱绘制 SPDP 问题的解决算法 第 16 页 共 41 页 3 43 43 43 4 对对对对 SPDPSPDPSPDPSPDP 算法进行进一步的优化 建立算法进行进一步的优化 建立算法进行进一步的优化 建立算法进行进一步的优化 建立 b bb bb bb b 表表表表与与与与 b cb cb cb c 表表表表 我们建立二叉树数据结构的思想来源于 3 1 2 的数学模型 而这个数学模型 建立的立足点是通过对第一组数据 b 进行组合 而拿第二组数据 c 来进行检验 不论是最初的穷举法还是二叉树数据结构的算法都体现了第一组数据与第二组 数据这样的一种关系 然而这样的关系并非完美 因为尽管 c 数据比 b 数据包含 的信息要少 但对 b 进行组合的时候 数据 c 仍然是非常重要的一个约束 并且 时刻的在约束着 b 的每一步组合 基于这样的想法 我们希望在二叉树的结点计 算时可以加入 c 对 b 的约束 为了实现这样的想法 我们在 SPDP 的标准问题中 建立了 b b 表与 b c 表 3 4 13 4 13 4 13 4 1b bb bb bb b 表的建立表的建立表的建立表的建立 首先我们建立 b b 表 在二叉树数据结构算法中 我们每步对结点树枝的是 否存在的判断都是通过两个 b 数的差 ji bb 是否在这个结点中数据 c 可以将它 看作一个集合 中 因此判断 ji bb 是否等于 k c至关重要 由此 我们就对数据 b 的所有元素两两作差 建立 b b 表 我们可以让横坐标表示被减数 i b的脚标 i 而纵坐标表示减数 j j m c 则在 i j 的位置记为 1 这样区分的好处在后面的算法里可以 体现 那么 二叉树结构中每步 ji bb k c的判断就转变成为判断 b b 表 i j 位置上的值 3 4 23 4 23 4 23 4 2b cb cb cb c 表的建立与表的建立与表的建立与表的建立与 b cb cb cb c 表约束表约束表约束表约束 b b 表是等式 ji bb k c中 i 与 j 之间的关系 而下面我们建立的 b c 表是 j 与 k 之间的关系 如表 3 所示 表 3 是最基本 b c 表 横坐标为 c 的脚标 k 而 纵坐标是被减数 j b的脚标 j 如果 ji bb k c 那么在 k j 的位置记 i 若 ji bb k c 则在 k j 的位置记 0 这样 这张 b c 表就有了它自身的含义 它表示着对于每一个 k c 有可能组合出这个 k c的两个 b 数的差的所有可能情况 这里就有一个非常重要的约束 对于每一个 k c 两个 b 数相减可以等于 k c的所 有的组合的个数 k n与数据 c 中 k c的个数 k p满足 k n k p 1 这里要注意 k p之 所以要加 1 是因为 中间元素 并非为两个 b 值相减而得到的 所以有可能在这 里 k c的个数 k p比 k n可以小 1 但一旦在 k c出现了这种情况 在别的 c 数据的列 中就不能出现这种情况 即对于其它的 c 数据要求 n p 倘若出现了与约束 相矛盾的情况时 再往后计算肯定得不到合理解了 需要换下一个可能的尾元素 DNA 限制性图谱绘制 SPDP 问题的解决算法 第 18 页 共 41 页 b50000 b45000 b30455 b20304 b13003 c1c2c3c4 p1p2p3p4 表3 b c初始表 得到了 b c 表的这个约束后 下一步需要解决的就是如何在二叉树建立的过程中 在不改变开始时候做的 b c 表而对每个结点的 k n进行计算并与该节点的 k p相比 较 首先 我们发现 k p在每次节点中的变化是因为每次计算需要除去 c 数据中 的一个值而导致 k p的变化 对于每个节点 都需要记录所有的 k p的值 然而 对于 k n 我们并不需要每次都改变 b c 表 而是直接从 b c 表中计算出当前情况 k n的值 这样 我们就需要对 b c 表进行一个补充 如表 4 所示 对于每一列 k c 我们又增加了两个子列 一列为状态数 J 函数 另一列为排序 R 函数 我 们现在来考察二叉树在建立过程中其中的一个节点的情况 如表 4 所示 假设该 J函数 被减数R函数J函数 被减数R函数 J函数 被减数R函数J函数 被减数R函数 b5002002001003 b4152002001003 b3001142151153 b2001131000142 b1131000000131 表4 完整b c表 c1c2c3c4 节点的前半段已经考虑到 i b 后半段已经考虑到 j b 当前需要考虑 b到底属于 前半段还是属于后半段 倘若 b被放到了前半段 生成该节点的左树枝及其节 点 我们发现 对于这个新生成的节点 对于任何 b i b在这里已经是 不可能的组合 同理我们发现 纵坐标比 i 小的与 i j 之间的那些可能与 c 相等 的 b 的差值的组合在这里已经没有意义了 需要在所有初始时 b 的差的组合总数 中减去这些在这个状态下没有意义的组合个数 因此我们这样来定义我们的 J 函数与 R 函数 由于在 3 3 1 标准化 SPDP 问题的过程中应用了定理六 相邻重 DNA 限制性图谱绘制 SPDP 问题的解决算法 第 19 页 共 41 页 值等效方法 如果对于某个 k c所对应的一列 若 j k 上的值不为 0 即 ji bb k c 那么 J j 1 否则为 0 而 R j 1 1 j s sJ 那么 R j 表示以从 1 b到 1 j b中为被减数的所有有可能被别的 b 相减等于这个 k c的个数 那么很容易 对 于新生成的节点 k n jJRlR 对这个公式举一个具体的实例加以说 明 如表 4 当我们已经计算到前半段考虑到 b4 后半段考虑到 b3 时 1122 3 4 5 1 JRRn 这表示当前情况下只有一种情况可以得到 c1 即 b5 b4 c1 经过上述的改进 我们就可以通过一个静态的 b c 表对 c 中所有的元素在建 立树的过程中方便的检查它的约束 如果与约束矛盾的情形前面已经讨论过 而 b c 表还有非常好的一个特性就是它在某些情况会有 临界 发生 比如对于 k c 所对应的一列 当在某个计算过程中 发现 kk np 或者1 kk np 中间元素 的情况 说明可以组合出 k c的 b 的差值的个数已经和 k c的个数相等 那么这时 已经发生了 临界 的情况 要求对于当前考虑建立树的节点 b以及它以后的 s b 中凡是满足 J s 1 s s b与 s k 所对应的 b一定要在同侧 而 121 bbb ss 一定要在 s b与 b的另一侧 这样大大的提高了计算的速度 我 们称这个约束为 b c 表约束 它的本质是数据 c 对数据 b 组合的约束 3 4 33 4 33 4 33 4 3对对对对 b bb bb bb b 表 表 表 表 b cb cb cb c 表的进一步讨论表的进一步讨论表的进一步讨论表的进一步讨论 在 3 4 1 与 3 4 2 我们分别建立 了b b表 b c表这两张非常有用的表 对于b c表的约束与作用在3 4 1中已 经做了详细的说明 我们发现 其实 b b 表 b c 表本质上是等价的 它们 都来自于 ji bb 是否等于 k c这个逻辑 关系 而从 b b 表中 我们可以从图的 图 9 DNA 限制性图谱绘制 SPDP 问题的解决算法 第 20 页 共 41 页 角度发现对这个问题更深刻的理解 我们将一个充满了数据的问题由此全部转化 成为一个图的问题 通过对这个图的逻辑关系的分析与讨论 可以得到更加好的 优化方法以及解决带有误差问题的思路 在 2 2 的问题分析中所举出的那么一组 合理解具有指数个数的特例也是通过对 b b 表的图的关系分析所构造出来的 下 面就先着重对 b b 表的图的逻辑关系进行一个分析 在 b b 表中 每一个点 i j 都表示一个 ji bb 的操作 而 i j 上所记 录的值是 ji bb 这个操作与 k c的逻辑关系 而这于前面我们所讲的二叉树结构的 建立是完全一样的 那么我们就尝试将二叉树建立的过程就放到 b b 表中 使 b b 表中的每一个路径都对应二叉树中的一个分支 下面我们就以一个简单的例 子来看看 b b 表中的路径是如何的与二叉树中的分支相对应 如图 9 与图 10 首 先为了看两个图的对应关系 我们先不考虑二叉树建立过程中每步对 c 的判断 也不考虑 b b 表中每个点 i j 上记录的值 那么在图 9 中 我们可以看到二 叉树的一个分支 A D E G 而 b b 表中的 A D E G 刚好与之完全对应 我们来看 这个过程 在初始状态 21 bb 分别是首元素与尾元素 3 b有两个选择 一个是放 在 1 b一边 而另一个选择是放在 2 b一边 在 b b 表中 它的选择就是 A 点 A 点 在图中表示 3 1 点 与 B 点 而对于我们这个分支它选择了 A 点 下一个考 虑的是 4 b 同样道理它也有两个选择 D 点与 F 点 容易的看出 每次选择时 b b 表中的图的这一列的最上面的点 如点 B D F G 都是可以选择的一个路径 而对于另一个路径在取决于前面的形成过程 比如考虑 4 b时 由于 B 点是上一次 的一个选择确没有选择 则将 B 点平移到了 C 点 成为了这次考虑的一个路径的 选择 同样的 4 b在这个分支选择了 D 点 当考虑 5 b时 它的选择就有 E 与 F 当考虑 6 b时 它的选择有 G 与 H 而最后选择了 G 最后形成了 A D E G 这个路 图 10 A A A A D D D D E E E E G G G G DNA 限制性图谱绘制 SPDP 问题的解决算法 第 21 页 共 41 页 径 而在实际建立二叉树时的每一步都需要检 验 ji bb 是否等于 k c 则在 b b 表中就需要经 过的点 i j 上记录的值不能是 0 必须为 某一个 k 并且还要要求这个 k c在已经到达这 个点时仍然在数据 c 之中 c 中的元素是不断 减少的 这样一来 建立二叉树的过程就全 部可以在 b b 表的图的关系中得以表现 下面 我们再来观察 b b 表具有的更多的特性 首 先 如果 b b 表中每一点 的值均记为 ji bb 则我们 发现在同一列中 下面的 点的值比上面的大 同一 行中 右边的点的值比左 边的大 则我们用箭头表 示值增大的方向 我们可 以得出图 11 这是点的值 的大小分布图 下面我们 就用这样的关系来构造一 组合理解的个数在 3 2 N 个 以上的数据 即问题分析 中所举出的实例 首先我 们希望构造一组数据 使得 1 b为首元素一定在前半段 2 b为尾元素一定在后半段 而 3 b一定可以既能在前半段也能在后半段 4 b在前半段 5 b在后半段 6 b一定 既能在前半段又能在后半段 如此一直类推下去 如果能构造出这样的解 它解 的个数一定不少于 3 2 N 而我们现在将刚才所说的规律所要求经过的点画在 b b 图上 得到图 12 这样我们就发现了规律 它很有规律的六个一组的进行重复 现在的任务就是需要对这些点赋上 c 的值 使上述对 b b 表的点的值的分布可以 图 11 图 12 DNA 限制性图谱绘制 SPDP 问题的解决算法 第 22 页 共 41 页 看出 如果我们规定了 200 时 深度算法的内存使用量为 608kb 是广度算法的千分 之一 因此深度搜索的适用范围几乎不受硬件限制 时间复杂度 理论上 深度回溯算法与广度算法接近 但是在实现算法中 递归结构深度算法返回上一个节点需要很多的时间开销 不如广度算法计算高 效 而非递归结构的深度算法返回一个节点的时间远远小于递归结构的深度算 法 接近于广度算法的执行效率 利用非递归深度算法在 Celeron1 7GHz 的 cpu 上一分钟可以搜索 8 105 2 个节点 DNA 限制性图谱绘制 SPDP 问题的解决算法 第 27 页 共 41 页 5 5 5 5 算法评估算法评估算法评估算法评估 5 15 15 15 1 对于算法复杂度的估计对于算法复杂度的估计对于算法复杂度的估计对于算法复杂度的估计 表1中的实验数据表明 在最坏情况该问的解的复杂性至少达到 N 2 表1中 的数据进行拟合基本符合 N 2 当N 20时 实验结果也符合 N 2 的判断 而任一个 SPDP问题的算法时间复杂性不会低于解的复杂性 所以最坏情况下标准SPDP问题 的时间复杂性会高于 N 2 无论使用何种搜索方法 都需要记录给定的所有DNA片段的长度 所以空间 复杂度至少N 对于不同搜索方法的具体空间复杂度 前文已经讨论不再赘述 如果利用BC表和BB表 那么空间复杂度将提高到 2 N 5 25 25 25 2 对对对对 SPDPSPDPSPDPSPDP 二叉树数据结构进行分析二叉树数据结构进行分析二叉树数据结构进行分析二叉树数据结构进行分析 现在我们来分析采取这样的二叉树数据结构的优缺点 与 3 1 2 的数学模型 的穷举算法相比 利用这个二叉树的结构利用了数据中所有的特点 可以避免很 多不必要的计算 因为当这个二叉树在建立过程中出现了这个结点即没有左枝也 没有右枝时 这个结点就不会再被考虑 它已经是一个 死胡同 而对这个结 点之后可能还能衍伸出的情况就不会被计算 而原始的穷举法不能避免这一点 从而与 3 1 2 的穷举法相比二叉树数据结构有比较大的优势 而它的缺点也非常 的明显 首先 它仍然是一个穷举的算法 而且并不能保证每次 死胡同 的情 形都出现在前面 往往会出现算到了最后一层结点才发现是不可能的情形 这样 复杂度仍然很高 其次 如果利用广度算法来实现这样的数据结构 当数据规模 变的庞大的时候 结点数就要成指数的增长 每个结点还需要存储当前结点 c 的信息 每个结点的 c 数据都是不一样的 以及已考虑过的数据 b 的分布 哪些 在前段哪些在后段 因此空间复杂度将大大的增加 使得计算机的内存难以承 受 若采取深度算法来实现 递归算法 则每次调用函数还需要花费相当的时 间 也增加了时间复杂度 关于这个问题我们做了很多的努力 在 5 2 有详细的 讨论 DNA 限制性图谱绘制 SPDP 问题的解决算法 第 28 页 共 41 页 但还是不得不承认二叉树数据结构的建立已经比前面的算法要好很多了 在 Construction of DNA restriction maps based on a simplified experiment 1 中 其作者也采取了类似的做法 但是他并没有将 SPDP 问题化成我们现在所处 理的标准问题 因此那篇论文所建立的树并非二叉树 而是允许很多树叉 使它 的复杂性增大不少 在 5 3 1 中我们对这个事实进行了实验与对比 有详细的数 据来说明这个问题 对于这种复杂度为指数的搜索 在数据结构中还有一种遗传算法来解决这类 问题特别有效 这种算法的主要思想是将一种情况或者组合用一个数来表示 对 于我们这个问题来说就可以用一个长度为 n 的二进制数来表示 b 的组合 并给定 一个淘汰函数 fitness function 来确定某一个物种有多好 对于这个问题就 是确定这个二进制数有与数据 c 的匹配程度 然后通过一个初始的种群 一组二 进制数 进行遗传 变异 繁殖 淘汰来形成新的种群 直到种群中出现满足最 终约束条件的个体或者是最好的个体为止 这是一种仿生学的算法 以很优秀的 平均复杂度解决了不少 NPH 问题 然而 非常遗憾的是对于 SPDP 问题 这个算 法并不合适 因为 SPDP 是为了重构基因的序列 我们需要根据已知的数据计算 出来所有有可能的合理的解 即解必须做到不漏 然而遗传算法可能很快的能出 现满足条件的一个个体 但无法辨识什么时候所有的解才被找出来 因此我们选 择了二叉