3

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

我有k=10, mism=3,seq是一个由字符 A、T、C 和 G 组成的字符串。每个pattern和kmer是 k 个字符长。我生成了patterns长度为 4**k（~100 万）和kmers长度为 len(seq)-k+1（~300）的列表。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

我尝试了 wikipedia 的hamming_distance功能而不是我的每个字符比较，并且还尝试删除字典并将pattern's 转储到列表中以供进一步处理。这些都没有提高循环的性能。任何帮助，将不胜感激！

4

1 回答 1

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 位就足够了。
  • 从模式中构建搜索尝试以加快比较速度。您对允许不匹配的搜索基本上会炸毁您拥有的模式数量。您可以尝试使用额外的边缘来允许许多不匹配，但这实质上会使您的搜索集变得巨大。
于 2013-11-11T00:39:26.743 回答