限制性图谱构建

快速概览

限制性图谱（restriction mapping）是通过限制性酶切实验确定 DNA 分子上酶切位点位置的技术。核心计算问题是根据片段长度数据推断酶切位点的顺序和位置。

• 理解部分消化问题（Partial Digest Problem, PDP）的数学形式
• 掌握穷举算法和分支定界策略（Branch-and-Bound）
• 了解双消化问题（Double Digest Problem, DDP）和探针部分消化问题（PPDP）

前置知识

• 穷举搜索
• 算法复杂度

所属板块 基础与数学

对象层、坐标系统、coverage 与概率图模型的共同语言。

阅读目标 帮助建立阅读上下文

先判断这页与你当前问题的关系，再决定是否深入展开。

建议前置 先建立相关基础对象与方法直觉

建议先建立相关基础对象与方法直觉，再进入本页。

生物学背景

限制性酶

限制性内切酶（restriction endonucleases） 是一类能够识别特定DNA序列并在特定位点切割DNA链的酶。

• 每种酶识别特定的短序列（通常4-8个碱基）
• 例如：EcoRI 识别 GAATTC 并在 G 和 A 之间切割
• 切割后产生DNA片段

限制性图谱

限制性图谱显示限制性酶切位点在DNA分子上的相对位置。

应用：

• 基因组作图（在测序时代之前非常重要）
• 基因克隆和载体构建
• 基因组结构分析
• 遗传疾病研究

实验方法

主要有两种实验方法：

1. 完全消化（complete digestion）：用限制性酶完全消化DNA，产生所有可能的片段
2. 部分消化（partial digestion）：控制酶切时间，产生部分片段

通过凝胶电泳可以测量这些片段的长度，但无法知道它们的顺序。

部分消化问题（PDP）

问题定义

给定一组切割位点 $X = \{x_1, x_2, \ldots, x_n\}$（假设在一条直线上，$x_1 = 0$），定义所有点对之间的距离集合：

ΔX = \{|xᵢ - xⱼ| : 1 ≤ i < j ≤ n\}

部分消化问题（Partial Digest Problem, PDP）：

• 输入：距离多重集 L = ΔX
• 输出：还原位点集合 X

示例： 如果 X = {0, 2, 4, 7} 则 ΔX = {2, 4, 7, 2, 5, 3} = {2, 2, 3, 4, 5, 7}

给定 L = {2, 2, 3, 4, 5, 7}，需要找出 X = {0, 2, 4, 7}

Brute Force PDP (穷举法)

穷举算法通过枚举所有可能的位点组合来寻找解。对于长度为 $L_{max}$，含有 $n$ 个位点的图谱：

BRUTEFORCEPDP(L, n)
1  M ← max(L)
2  for every subset X = {0, x2, ..., xn-1, M} from {1, ..., M-1}
3      if ΔX = L
4          return X

缺点：搜索空间为 $\binom{M-1}{n-2}$，当 $M$ 较大时极度低效。

Practical PDP (分支定界算法)

PDP 可以用分支定界（branch-and-bound）策略高效求解。

关键观察：

• 最大距离一定是某个点到最远点的距离
• 可以递归地构建解

算法思路：

1. 从最大距离开始，确定最远的两个点
2. 递归地在中间插入新点
3. 使用距离约束进行剪枝

PARTIALDIGEST(L)
1 X ← \{0, max(L)\}
2 L ← L \ \{max(L)\}
3 return PLACEPOINTS(L, X)

PLACEPOINTS(L, X)
4 if L is empty
5   return X
6 y ← max(L)
7 // 尝试在 X 的最右侧添加 y
8 if CONSISTENT(y, X, L)
9   X' ← X ∪ \{y\}
10  L' ← L \ DISTANCES(y, X)
11  result ← PLACEPOINTS(L', X')
12  if result ≠ failure
13    return result
14 // 尝试在 X 的最左侧添加 max(X) - y
15 if CONSISTENT(max(X) - y, X, L)
16  X' ← X ∪ \{max(X) - y\}
17  L' ← L \ DISTANCES(max(X) - y, X)
18  result ← PLACEPOINTS(L', X')
19  if result ≠ failure
20    return result
21 return failure

CONSISTENT 函数检查添加新点后是否与距离集合一致。

示例

给定 L = {2, 2, 3, 4, 5, 7}：

1. 最大距离 7，设 X = {0, 7}
2. 剩余 L = {2, 2, 3, 4, 5}
3. 最大距离 5：
   • 尝试在右侧添加 5：X = {0, 5, 7}
   • 检查距离：|5-0|=5, |5-7|=2, 符合
   • 剩余 L = {2, 3, 4}
4. 最大距离 4：
   • 尝试在右侧添加 4：X = {0, 4, 5, 7}
   • 距离 |4-0|=4, |4-5|=1（不在L中），不一致
   • 尝试在左侧添加 7-4=3：X = {0, 3, 5, 7}
   • 距离 |3-0|=3, |3-5|=2, |3-7|=4，符合
   • 剩余 L = {2}
5. 最大距离 2：
   • 尝试添加 2：X = {0, 2, 3, 5, 7}
   • 距离 |2-0|=2, 符合
   • L 为空，返回 X = {0, 2, 3, 5, 7}

计算复杂性

PDP 是 NP-困难的，但分支定界算法在实践中通常可以高效求解，因为距离约束提供了很强的剪枝能力。

双消化问题（DDP）

问题定义

**双消化问题（Double Digest Problem, DDP）**使用两种不同的限制性酶。

给定：

• 酶 A 单独消化的片段长度集合 A
• 酶 B 单独消化的片段长度集合 B
• 酶 A 和 B 同时消化的片段长度集合 A + B

需要重构两种酶的切割位点顺序。

示例

假设酶 A 的切割位点产生片段 {1, 2, 4, 5, 6} 酶 B 的切割位点产生片段 {1, 3, 3, 3, 8} 双消化产生片段 {1, 1, 1, 1, 2, 2, 2, 3, 5}

需要找到一种排列使得：

• 单独 A 消化得到 {1, 2, 4, 5, 6}
• 单独 B 消化得到 {1, 3, 3, 3, 8}
• 双消化得到 {1, 1, 1, 1, 2, 2, 2, 3, 5}

算法

DDP 也可以用分支定界策略求解：

BRUTEFORCEDDP(A, B, AB)
1 for each possible ordering of A cuts
2   for each possible ordering of B cuts
3     if combined digestion matches AB
4       return the ordering

由于搜索空间很大，需要更强的剪枝策略。

难度

DDP 通常比 PDP 更难，因为需要同时考虑两种酶的切割位点。

探针部分消化问题（PPDP）

问题定义

**探针部分消化问题（Probed Partial Digest Problem, PPDP）**使用标记探针。

给定：

• 一个标记探针的位置（设为 0）
• 部分消化实验测量的距离（包含探针的片段）

需要重构切割位点 A（负坐标）和 B（正坐标）。

形式化

输入：多重集 $\{b - a : a \in A, b \in B\}$ 输出：集合 $A$ 和 $B$

算法

PPDP 可以分解为两个独立的 PDP：

1. 重构 A
2. 重构 B

实际考虑

实验误差

实际实验中存在测量误差，算法需要：

• 容忍小的距离误差
• 处理缺失或额外的片段

计算方法

现代方法包括：

• 整数线性规划
• 约束满足
• 启发式搜索

与测序的关系

在下一代测序时代，限制性图谱的重要性有所下降，但：

• 仍用于验证组装结果
• 用于研究结构变异
• 在某些应用中作为补充方法

相关页面

穷举搜索

穷举搜索的基本原理和复杂度分析

延伸阅读

算法复杂度

理解算法效率的理论框架

延伸阅读

分支定界

穷举搜索与剪枝策略

延伸阅读

常见误区

• 部分消化问题（PDP）的解总是唯一的：
• PDP 可能存在多个解——不同的位点集合可能产生相同的距离多重集。即使分支定界找到了一个解，也不能保证它是唯一的。在实验中，测量误差会进一步增加解的不唯一性。实际应用中通常需要结合其他实验证据来消歧。
• 凝胶电泳可以精确测量所有片段长度：
• 凝胶电泳的分辨率有限，特别是对于长度接近的片段，区分能力下降。短片段（< 50 bp）和长片段（> 20 kb）的测量误差更大。PDP 算法假设输入的距离集合是精确的，但实际实验数据必然带有噪声，需要算法能够容忍一定程度的误差。
• 分支定界一定能高效求解 PDP：
• 虽然 PDP 的距离约束提供了很强的剪枝能力，但在某些精心构造的输入上，分支定界仍可能退化为接近穷举搜索。剪枝效果依赖于距离约束的"紧度"——如果很多位点之间的距离相同，剪枝效果就会大打折扣。

穷举搜索

延伸阅读

换钱问题

另一个动态规划入门案例

延伸阅读

基因组组装

大规模图谱构建的现代方法

延伸阅读