7

我认为我的代码效率太低了。我猜这与使用字符串有关，但我不确定。这是代码：

genome = FASTAdata[1]
genomeLength = len(genome);

# Hash table holding all the k-mers we will come across
kmers = dict()

# We go through all the possible k-mers by index
for outer in range (0, genomeLength-1):
    for inner in range (outer+2, outer+22):
        substring = genome[outer:inner]
        if substring in kmers:              # if we already have this substring on record, increase its value (count of num of appearances) by 1
            kmers[substring] += 1
        else:
            kmers[substring] = 1            # otherwise record that it's here once

这是搜索长度最多为 20 的所有子字符串。现在这段代码似乎很长时间并且永远不会终止，所以这里一定有问题。在字符串上使用 [:] 会导致巨大的开销吗？如果是这样，我可以用什么代替它？

为了清楚起见，有问题的文件将近 200mb，非常大。

4

2 回答 2

1

我建议使用动态编程算法。问题是对于所有inner未找到的字符串，您正在重新搜索那些附加了额外字符的字符串，因此当然也不会找到这些字符串。我没有想到一个特定的算法，但这肯定是动态编程的一个例子，你记得你已经搜索过什么。作为一个非常糟糕的例子，记住所有substrings长度 1,2,3,... 没有找到，并且永远不要在字符串更长的下一次迭代中扩展这些碱基。

于 2013-11-07T22:34:24.343 回答
1

您应该使用memoryview来避免创建子字符串，[:]然后返回“视图”而不是副本，但是您必须使用 Python 3.3 或更高版本（在此之前，它们不可散列）。

此外，计数器将简化您的代码。

from collections import Counter

genome = memoryview("abcdefghijkrhirejtvejtijvioecjtiovjitrejabababcd".encode('ascii'))
genomeLength = len(genome)

minlen, maxlen = 2, 22

def fragments():
    for start in range (0, genomeLength-minlen):
        for finish in range (start+minlen, start+maxlen):
            if finish <= genomeLength:
                yield genome[start:finish]

count = Counter(fragments())
for (mv, n) in count.most_common(3):
    print(n, mv.tobytes())

产生：

4 b'ab'
3 b'jt'
3 b'ej'

一个 1,000,000 字节的随机数组在我的笔记本电脑上需要 45 秒，但 2,000,000 会导致交换（超过 8GB 内存使用）。但是，由于您的片段很小，您可以轻松地将问题分解为数百万长的子序列，然后在最后组合结果（请注意重叠）。运气好的话，这将使 200MB 阵列的总运行时间约为 3 小时。

PS为了清楚起见，通过“最后合并结果”，我假设您只需要为每个 1M 子序列保存最流行的，例如，将它们写入文件。您不能将计数器保存在内存中 - 这就是使用 8GB 的​​原因。如果您有发生数千次的片段，那很好，但显然不适用于较小的数字（例如，您可能在 200 个 1M 子序列中的每个子序列中只看到一次片段，因此永远不要保存它）。换句话说，结果将是不完整的下限，特别是在较低频率下（仅当在每个子序列中找到并记录片段时，值才是完整的）。如果你需要一个准确的结果，这是不合适的。

于 2013-11-08T02:24:33.567 回答