2026年4月24日 研究日志

今日主题：整理相关文献，准备样本汇总表。搞生信啊，我总得自己整理一下材料吧。今天的工作内容都没什么成型的东西，给大家随便聊聊之前学的Boyer-Moore算法吧。

注意：Boyer-Moore算法属于一个相当原始的算法（当然还是比朴素对比要强的），所以学习该算法大概并不会真的对于你的研究有什么帮助。就当是周末临近的放松就好。

Boyer–Moore 算法在生信数据中的价值：从经典字符串匹配到现代序列搜索引擎

在生物信息学中，我们每天都在处理字符串：DNA、RNA、蛋白序列、barcode、UMI、motif、k-mer……
这些序列本质上都是 字符串（string），而“在海量文本中查找模式”正是字符串算法的核心任务。

---

为什么生物信息学研究者应该知道 Boyer–Moore？

因为它提供了三个关键启发：

1. “跳跃式搜索”思想是所有高效比对算法的基础

BM 的核心是：

不需要检查文本的每一个字符，可以跳跃式前进。

这正是 FM-index、suffix array、k-mer hashing 的精神内核。

---

2. “从右向左匹配”启发了 seed-based alignment

BM 不是从模式串开头比，而是从 末尾 开始比。
这与现代比对工具的 “seed-first” 思路高度一致：

• Bowtie：先找短种子，再延伸
• BLAST：先找 word，再扩展
• minimap2：先找 minimizer，再 chaining

---

3. “坏字符 / 好后缀规则”是现代 mismatch 处理的雏形

BM 的两个跳跃规则：

• Bad Character Rule
• Good Suffix Rule

本质上是对 mismatch 的结构化利用。
这与现代算法中：

• seed mismatch
• spaced seed
• adaptive seeding

等思想高度相似。

---

Boyer–Moore 的核心思想

Boyer–Moore 通过 预处理模式串 P，也就是建表，在搜索文本 T 时跳过大量不可能匹配的位置。

它的两个关键规则：

---

1. Bad Character Rule（坏字符规则）

当从右向左比较时遇到 mismatch：

• 看 mismatch 字符是否在模式串左侧出现过
• 如果出现过 → 把模式串移动到那个位置
• 如果没出现过 → 整个模式串跳过 m 个字符（m = 模式长度）

这允许 大步跳跃。

---

2. Good Suffix Rule（好后缀规则）

如果已经匹配了一段后缀 t：

• 尝试在模式串中找到另一个 t′
• 如果找到 → 对齐 t′
• 如果找不到 → 对齐模式串的前缀与 t 的后缀

这是 BM 最强大的部分，说真的这玩意想讲清楚对我还有点困难，给大家看个例子吧：

Boyer–Moore（坏字符规则）

def build_bad_character_table(pattern):
    """
    构建坏字符表：记录每个字符在模式串中最后出现的位置
    """
    table = {}
    for i, ch in enumerate(pattern):
        table[ch] = i
    return table


def boyer_moore_search(text, pattern):
    """
    Boyer–Moore 字符串查找（仅使用坏字符规则）
    返回所有匹配起始位置
    """
    m = len(pattern)
    n = len(text)

    if m == 0:
        return []

    bad_char = build_bad_character_table(pattern)
    matches = []

    i = 0  # text 指针

    while i <= n - m:
        j = m - 1  # pattern 从右向左比较

        # 从右向左比较字符
        while j >= 0 and pattern[j] == text[i + j]:
            j -= 1

        if j < 0:
            # 完全匹配
            matches.append(i)
            i += m  # 可以直接跳过整个模式串长度
        else:
            # 坏字符规则跳跃
            bad_char_index = bad_char.get(text[i + j], -1)
            shift = max(1, j - bad_char_index)
            i += shift

    return matches

genome = "ATGCGTAGGCTAGGACCGTAGGTTAG"
motif = "AGG"

result = boyer_moore_search(genome, motif)
print("匹配位置:", result)

for pos in result:
    print(f"位置 {pos}: {genome[pos:pos+len(motif)]}")

匹配位置: [6, 11, 19]
位置 6: AGG
位置 11: AGG
位置 19: AGG

好后缀规则

构建好后缀表（Good Suffix Table）

好后缀规则的核心是两个表：

• suffix：记录每个后缀在模式串中再次出现的位置
• prefix：记录某个后缀是否同时是模式串的前缀

def build_good_suffix_table(pattern):
    """
    构建好后缀表：suffix 和 prefix
    suffix[k] = 模式串中长度为 k 的后缀在前面再次出现的位置
    prefix[k] = 长度为 k 的后缀是否同时是模式串的前缀
    """
    m = len(pattern)
    suffix = [-1] * m
    prefix = [False] * m

    for i in range(m - 1):
        j = i
        k = 0  # 公共后缀长度

        # 从 pattern[i] 向左，与 pattern 末尾向左比较
        while j >= 0 and pattern[j] == pattern[m - 1 - k]:
            j -= 1
            k += 1
            suffix[k] = j + 1  # 记录公共后缀的起始位置

        if j == -1:
            prefix[k] = True  # 如果公共后缀也是前缀

    return suffix, prefix

好后缀规则的跳跃计算

def move_by_good_suffix(j, m, suffix, prefix):
    """
    根据好后缀规则计算跳跃距离
    j: mismatch 发生的位置
    m: 模式串长度
    """
    k = m - 1 - j  # 好后缀长度

    # 情况 1：在前面找到另一个匹配的子串
    if suffix[k] != -1:
        return j - suffix[k] + 1

    # 情况 2：找不到匹配子串，但好后缀的某个后缀是前缀
    for r in range(j + 2, m):
        if prefix[m - r]:
            return r

    # 情况 3：完全没有匹配，整体右移 m
    return m

完整 Boyer–Moore 搜索（坏字符 + 好后缀）

def boyer_moore(text, pattern):
    m = len(pattern)
    n = len(text)

    # 坏字符表
    bad_char = {ch: i for i, ch in enumerate(pattern)}

    # 好后缀表
    suffix, prefix = build_good_suffix_table(pattern)

    matches = []
    i = 0  # text 指针

    while i <= n - m:
        j = m - 1

        # 从右向左比较
        while j >= 0 and text[i + j] == pattern[j]:
            j -= 1

        if j < 0:
            matches.append(i)
            i += m  # 完全匹配，整体右移
        else:
            # 坏字符跳跃
            bad_char_index = bad_char.get(text[i + j], -1)
            bc_shift = j - bad_char_index

            # 好后缀跳跃
            gs_shift = move_by_good_suffix(j, m, suffix, prefix)

            # 取最大跳跃
            i += max(bc_shift, gs_shift)

    return matches

---

在基因组序列中测试（示例：查找 PAM 序列）

genome = "ATGCGTAGGCTAGGACCGTAGGTTAG"
motif = "AGG"

result = boyer_moore(genome, motif)
print("匹配位置:", result)

for pos in result:
    print(f"{pos}: {genome[pos:pos+len(motif)]}")

匹配位置: [11]
11: AGG

---

好后缀规则（Good Suffix Rule）解释

当从右向左比较时出现 mismatch，如果右侧已经匹配了一段后缀 t（称为“好后缀”），我们可以利用它来跳跃：

1. 如果 t 在模式串前面再次出现
   → 将前面的 t 与文本中的 t 对齐

2. 如果 t 不再出现，但 t 的某个后缀是模式串的前缀
   → 将前缀与 t 的后缀对齐

3. 如果都没有
   → 整体右移模式串长度 m

好后缀规则能在 mismatch 时利用“已经匹配的结构”进行更大的跳跃，是 Boyer–Moore 最强大的部分。

---

说实话有没有讲清楚呢……恐怕是没有的（笑）我自己也稀里糊涂的，不管怎么说，周末要来了，今天就休息了，下个工作日见！