基于朴素模式匹配算法实现模式匹配次数统计（字典方案）

基于字典的改造方案 #

你可以直接在现有匹配逻辑基础上引入字典记录每个模式的匹配次数，无需大幅修改原有代码：

def count_motifs(patterns, txt):
    count_dict = {}
    # 初始化所有目标基序的计数为0
    for pat in patterns:
        count_dict[pat] = 0
        M = len(pat)
        N = len(txt)
        for i in range(N - M + 1):
            j = 0
            while j < M:
                if txt[i + j] != pat[j]:
                    break
                j += 1
            if j == M:
                count_dict[pat] += 1
    # 统一输出统计结果
    for pat, count in count_dict.items():
        print(f"{pat} found {count} times")

# 使用示例
genome_sequence = "你的基因组序列内容"
target_motifs = ["GAATC", "GAGTC"]
count_motifs(target_motifs, genome_sequence)

逻辑说明 #

• 先通过字典初始化所有目标基序的计数为0
• 沿用原有的朴素匹配逻辑，每找到一次匹配就给对应字典项加1
• 最后遍历字典输出汇总后的统计结果

更高效的正则表达式方案 #

如果处理的基因组序列较长，朴素匹配的效率会明显不足，推荐使用Python内置的re模块，其底层实现更高效，代码也更简洁：

import re

def count_motifs_re(patterns, txt):
    for pat in patterns:
        # 查找所有非重叠匹配，直接通过长度获取次数
        match_count = len(re.findall(pat, txt))
        print(f"{pat} found {match_count} times")

# 使用示例
genome_sequence = "你的基因组序列内容"
target_motifs = ["GAATC", "GAGTC"]
count_motifs_re(target_motifs, genome_sequence)

重叠匹配处理（可选） #

如果你的研究场景需要统计重叠的基序（比如序列AAAA中统计AA，重叠计数应为3次而非2次），可以用re.finditer来逐个处理匹配位置：

import re

def count_overlapping_motifs(patterns, txt):
    for pat in patterns:
        count = 0
        start_pos = 0
        motif_len = len(pat)
        while True:
            match_result = re.search(pat, txt[start_pos:])
            if not match_result:
                break
            count += 1
            # 每次匹配后移动1位起始位置，允许重叠匹配
            start_pos += match_result.start() + 1
        print(f"{pat} found {count} times")

内容的提问来源于stack exchange，提问作者Iacopo Passeri