Motif 寻找

快速概览

Motif 寻找是在多条序列中发现反复出现且具有生物学意义的统计模式：这些模式不是完全一致的字符串，而是带有位置偏好的概率模型。

核心是从观测数据中提取位置相关的统计偏好
PFM、PWM 和共识序列是三种经典的表示方法
穷举搜索、贪心搜索和期望最大化（EM）是常用的算法策略
它是 motif discovery 的概念基础，后续算法都基于此表示

所属板块 核心方法

索引、比对、组装与概率模型构成的核心算法主轴。

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

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

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

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

是什么

motif 寻找关注的是：在多条序列中是否存在某种反复出现、具有生物学意义的模式。

这个模式不一定完全一致，它可能是：

一个短而保守的 DNA 片段；
一个蛋白质中的保守结构域信号；
某类调控元件的偏好序列。

因此，motif 通常不是”精确相同的字符串”，而更像”带有统计偏好的局部模式”。

要解决什么生物信息学问题

很多关键生物学问题都可以转化为 motif 寻找：

转录因子结合位点在哪里？
一组共表达基因是否共享调控信号？
蛋白家族中是否有保守功能位点？
多条序列里是否隐藏了某种结构相关模式？

motif 寻找的难点在于：

背景噪声大；
motif 可能很短；
各位置可能允许不同程度的变异；
真实数据里往往混有大量无关序列。

数学模型

位置频率矩阵（PFM）

给定 N 个长度为 L 的 motif 实例，PFM 记录每个位置上各字符出现的次数：

\text\{PFM\}[i][c] = \text\{count of character \} c \text\{ at position \} i

其中 $i \in \{1, 2, ..., L\}$ ， $c \in \{A, C, G, T\}$ 。

转换为频率：

f_\{i,c\} = \frac\{\text\{PFM\}[i][c]\}\{N\}

位置权重矩阵（PWM）

PWM 通过对数比值将频率转换为权重：

w_\{i,c\} = \log_2\left(\frac\{f_\{i,c\} + \alpha\}\{b_c\}\right)

其中：

$f_{i,c}$ 是位置 $i$ 上字符 $c$ 的频率
$b_c$ 是背景频率（通常为 0.25 或根据背景序列估计）
$\alpha$ 是伪计数（pseudocount），用于避免零概率

共识序列（Consensus Sequence）

共识序列是每个位置最频繁的字符：

\text\{consensus\}[i] = \arg\max_c \text\{PFM\}[i][c]

也可以使用简并碱基表示（如 R = A/G, Y = C/T）来表示位置上的变异。

信息含量

信息含量衡量每个位置的保守程度：

I_i = \sum_\{c \in \\{A,C,G,T\\}\} f_\{i,c\} \log_2\left(\frac\{f_\{i,c\}\}\{b_c\}\right)

信息含量越高，说明该位置越保守。

4. Motif 寻找与中值字符串的对偶性

Motif 寻找问题（寻找最优起始位置）与中值字符串问题（Median String Problem） 在数学上是完全等价的对偶问题。

核心直觉

Motif Finding：目标是找到起始位置 $s$ ，使得共识得分 $Score(s)$ 最大化。
Median String：目标是找到一个长度为 $l$ 的字符串 $v$ ，使得它到所有序列的距离总和 $TotalDistance(v, DNA)$ 最小化。

数学等价性

对于任何起始位置 $s$ 和由其产生的共识序列 $w$ ，它们之间满足： $TotalDistance(w, DNA) = l \cdot t - Score(s, DNA)$ 其中 $l$ 是 Motif 长度， $t$ 是序列条数。

这意味着：

解决了一个问题，就自动解决了另一个。
搜索空间差异：Motif Finding 的搜索空间是 $(n-l+1)^t$ （取决于序列条数和长度），而 Median String 的搜索空间是 $4^l$ （仅取决于 Motif 长度）。当序列很多时，从 Median String 入手往往更高效。

5. 贪心 Motif 搜索（Greedy Motif Search）

由于穷举搜索速度较慢，实际常用贪心策略（如 CONSENSUS 算法）。它逐个扫描序列，每步选择能使当前 Profile 得分最大化的 $l$ -mer。

GREEDYMOTIFSEARCH(DNA, t, n, l)
1  bestMotif ← (1, 1, ..., 1)
2  for s1 ← 1 to n-l+1
3      for s2 ← 1 to n-l+1
4          if Score(s, 2, DNA) > Score(bestMotif, 2, DNA)
5              // 更新最佳起始位置...
6  for i ← 3 to t
7      // 贪心选择第 i 条序列的最佳位置

注意：贪心算法虽然快，但可能陷入局部最优，错过全局最强的模式。

从实例构建 PFM

算法1：构建位置频率矩阵

输入：N 个长度为 L 的 motif 实例 S = \{s₁, s₂, ..., s_N\}
输出：位置频率矩阵 PFM

1. 初始化 PFM 为 L × 4 的零矩阵
2. for i = 1 to L:
     for j = 1 to N:
        c = s_j[i]  // 第 j 个序列的第 i 位字符
        PFM[i][c] += 1
3. return PFM

时间复杂度：O(N·L)

从 PFM 构建 PWM

算法2：构建位置权重矩阵

输入：PFM，背景频率 b_c，伪计数 α
输出：位置权重矩阵 PWM

1. for i = 1 to L:
     for each character c ∈ \{A, C, G, T\}:
        f_ic = PFM[i][c] / N
        PWM[i][c] = log₂((f_ic + α) / b_c)
2. return PWM

时间复杂度：O(L·4) = O(L)

使用 PWM 扫描序列

算法3：PWM 扫描

输入：PWM，序列 seq，motif 长度 L
输出：每个起始位置的得分

1. for pos = 1 to (|seq| - L + 1):
     score = 0
     for i = 1 to L:
        c = seq[pos + i - 1]
        score += PWM[i][c]
     output score at position pos

时间复杂度：O((|seq| - L + 1) · L) ≈ O(|seq| · L)

示例

假设我们观察到 4 个转录因子结合位点实例：

序列 1: T A T A A A
序列 2: T A T G A A
序列 3: T A T A A T
序列 4: T A T C A A

步骤 1：构建 PFM

统计每个位置上各碱基的出现次数：

位置	A	C	T	总计
1	0	0	4	4
2	4	0	0	4
3	0	0	4	4
4	3	1	0	4
5	4	0	0	4
6	3	0	1	4

步骤 2：转换为频率矩阵

使用伪计数 α = 1（拉普拉斯平滑）：

f_\{i,c\} = \frac\{\text\{PFM\}[i][c] + \alpha\}\{N + 4\alpha\}

对于位置 1，碱基 T：

f_\{1,T\} = \frac\{4 + 1\}\{4 + 4\} = \frac\{5\}\{8\} = 0.625

步骤 3：构建 PWM

假设背景频率 $b_A = b_C = b_G = b_T = 0.25$ ，使用伪计数 α = 0.5：

w_\{i,c\} = \log_2\left(\frac\{f_\{i,c\} + \alpha\}\{b_c\}\right)

对于位置 1，碱基 T：

w_\{1,T\} = \log_2\left(\frac\{0.625 + 0.5\}\{0.25\}\right) = \log_2(4.5) \approx 2.17

对于位置 1，碱基 A：

w_\{1,A\} = \log_2\left(\frac\{0 + 0.5\}\{0.25\}\right) = \log_2(2) = 1.00

完整 PWM（示例）：

位置	A	C	G	T
1	1.00	1.00	1.00	2.17
2	2.17	1.00	1.00	1.00
3	1.00	1.00	1.00	2.17
4	1.42	0.58	1.00	1.00
5	2.17	1.00	1.00	1.00
6	1.42	1.00	1.00	0.58

步骤 4：扫描新序列

给定候选序列 TATAAA，计算得分：

位置 1 (T): 2.17
位置 2 (A): 2.17
位置 3 (T): 2.17
位置 4 (A): 1.42
位置 5 (A): 2.17
位置 6 (A): 1.42

总分：2.17 + 2.17 + 2.17 + 1.42 + 2.17 + 1.42 = 11.52

给定候选序列 CGCGCG，计算得分：

位置 1 (C): 1.00
位置 2 (G): 1.00
位置 3 (C): 1.00
位置 4 (G): 1.00
位置 5 (C): 1.00
位置 6 (G): 1.00

总分：6.00

显然 TATAAA 得分更高，更像该 motif。

步骤 5：计算信息含量

对于位置 1：

I_1 = 0.625 \log_2(0.625/0.25) + 0.125 \log_2(0.125/0.25) \times 3 \approx 0.42

信息含量越高，说明该位置越保守，对 motif 识别贡献越大。

复杂度分析

空间复杂度

PFM 存储：O(L·4) = O(L)，其中 L 是 motif 长度
PWM 存储：O(L·4) = O(L)
扫描时临时空间：O(L)

时间复杂度

构建 PFM：O(N·L)，N 是实例数量
构建 PWM：O(L)
扫描序列：O(|seq|·L)，对于长度为 M 的基因组，总复杂度为 O(M·L)

三种表示方法的对比

特性	共识序列	PFM	PWM
表示精度	低	中	高
计算复杂度	O(L)	O(N·L)	O(N·L)
扫描速度	快	中	快
变异表示	有限	频率	概率权重
是否需要背景	否	否	是
信息含量	低	中	高

共识序列最简单但信息量最少，PWM 最灵活但需要背景模型。PFM 介于两者之间，是构建 PWM 的基础。

伪计数的选择

伪计数（pseudocount）用于处理零概率问题：

拉普拉斯平滑：α = 1，相当于在所有位置添加一个虚拟观测
小伪计数：α = 0.5 或更小，减少对真实数据的干扰
基于背景的伪计数：α = k·b_c，其中 k 是缩放因子

伪计数过大会过度平滑，过小则可能遇到数值问题。实践中常用 α = 0.5 或 α = 1。

与概率模型的关系

motif 寻找常常和概率模型联系非常紧密，因为我们需要区分：

某个片段只是背景随机出现；
还是更像由 motif 生成。

因此，很多 motif 方法会借助：

PWM / profile
背景碱基分布
HMM 或类似状态模型
EM 等参数估计方法

与 HMM 的关系

如果一个问题不只是”找到一个短模式”，而是要在整条序列上区分 motif 区域和背景区域，那么 HMM 就会变得很自然。

从这个角度说：

motif 寻找偏向”找局部模式”；
HMM 更偏向”对整条序列做状态建模”。

两者有交集，但并不完全等价。

与真实工具或流程的连接

motif 寻找与以下场景高度相关：

转录因子结合位点分析
调控元件发现
蛋白家族保守位点分析
上游序列扫描与富集分析

在真实流程里，motif 结果通常还要结合：

进化保守性
表达数据
ChIP-seq 或实验验证

共同解释。

参考资料

Biological Sequence Analysis
motif discovery 相关教材与综述