二、模体从头发现（De Novo Motif Finding）

1. 基于共有序列的穷举方法
- 遍历所有可能的k-mer序列（4^k种组合）
- 统计每个k-mer在输入序列集中的出现频率
- 筛选在多数序列中均有出现的显著模式
- 计算复杂度：O(4^k)，适用于k≤10的情况
2. 基于EM算法的模体发现（以MEME为代表）
EM算法包含两个迭代步骤：
E-step（期望步骤）：假设当前位置频率矩阵为θ，对每条序列中每个可能的结合位点位置计算似然比：
$$LR = \frac{P(\text{sequence}|\theta)}{P(\text{sequence}|\theta_0)}$$
其中θ_0为背景碱基频率模型。
M-step（最大化步骤）：以E-step得到的似然比为权重，重新计算位置频率矩阵，最大化观测数据的似然函数。
迭代直至收敛，最终得到最优的位置频率矩阵。
MEME算法改进：先遍历所有可能的起始矩阵，筛选具有统计学显著性的矩阵作为EM的输入，避免陷入局部最优。
3. 基于Gibbs抽样的模体发现
Gibbs抽样是一种马尔可夫链蒙特卡罗（MCMC）方法：
1. 从N条序列中随机选择一条序列S_i
2. 从剩余N-1条序列中随机提取长度为n的片段，构建初始位置频率矩阵
3. 基于该矩阵对S_i中每个可能的n长度片段计算似然比
4. 根据似然比概率随机选择一个片段作为S_i上的结合位点
5. 用选中的片段更新位置频率矩阵
6. 重复步骤1-5，遍历所有序列，完成一轮迭代
7. 多轮迭代直至矩阵收敛
Gibbs抽样的优势：随机化策略可以跳出局部最优，探索更广泛的可能性空间。