高效地在大型列表中查找字符串不匹配

Question

我正在迭代遍历大量字符串列表以查找相似字符串（有几个不匹配）。以下代码有效，但需要约20分钟的时间，而我的目标是在5分钟内完成。有没有更有效的方法来完成这个任务？哪一部分代码最具限制性？

我有 k=10，mism=3，seq 是由字符 A、T、C 和 G 组成的字符串。每个 pattern 和 kmer 都是 k 个字符长。

我已经生成了长度为 4**k（约100万）的 pattern 列表和长度为 len(seq)-k+1（约300）的 kmer 列表。frequent 是一个字典。

测试迭代仅需不到一分钟：

for i in range (0,4**k):
    for j in range(0,len(kmers)):
        pass

这是我需要更高效计算的实际内容：

for pattern in patterns:
    for kmer in kmers:
        mism_counter=0
        for j in range(0,k):
            if not kmer[j]==pattern[j] : mism_counter+=1
        if mism_counter <= mism :
            if pattern in frequent:
                frequent[pattern] += 1
            else:
                frequent[pattern] = 1

我尝试使用维基百科的hamming_distance函数代替每个字符的比较，并且尝试删除字典，只将pattern放入列表进行进一步处理。但这些都没有改善循环的性能。如有帮助，请提供！

- Sebastian K

---

你有第三个循环：for j in range(k)；这会使每个外部循环额外增加10个循环。10次“不到一分钟”仍然接近10分钟，再加上if测试和字典访问。 - Martijn Pieters

@MartijnPieters，去掉那个for循环不会将时间复杂度从O(n^3)降低到O(n^2)吗？ - Dunno

@Dunno：第三个循环：k=10；第一个循环：4**k（约1e6） - jfs

代码中 seq 在哪里？ - jfs

另外，最后一个 if 可以移动到第一个循环中（在 for kmer 结束后）吗？ - Dunno

感谢大家提供的有用想法。最终我重新思考了算法，因此能够避免这些大规模迭代。 - Sebastian K

Answer 1

这将节省一半的时间;-)

for pattern in patterns:
    for kmer in kmers:
        mism_counter=0
        for j in range(0,k):
            if kmer[j] != pattern[j] : 
                mism_counter+=1
                if mism_counter > misn:
                    break
        else:
            if pattern in frequent:
                frequent[pattern] += 1
            else:
                frequent[pattern] = 1

要想真正加快速度，你需要做两件事情：

• 压缩数据以减少程序的工作量。你不必将GTAC表示为ASCII字母（每个字母7个位），使用每个字母2位即可。
• 构建一个搜索Trie以加快比较速度。允许匹配错误的搜索会使你拥有大量的模式。你可以有一个包含额外边缘的Trie来允许一定数量的匹配错误，但这实际上会使你的搜索集变得巨大。

- Jochen Ritzel