用O（k*N+k*Q）计算kmer的有效方法？

Question

我有一串小写字母。我需要找出每个k-mer问的问题出现了多少次。关键是我需要按问题所要求的k-mers顺序输出计数。另一个问题是，我可能需要多次输出同一k-mer的计数。我需要在O（kN+kQ）中完成这一点，其中k是k-mer的长度，N是DNA串的长度，Q是感兴趣的特定k-mers的数量

例如，对于以下输入，其中N=7，k=2，q=3，aaabaab是DNA字符串，接下来的5行是我感兴趣的k-mers：

7 3 5
aaabaab
aaa
aab
aaa
baa
xyz

我希望输出以下内容：

aaa 1
aab 2
aaa 1
baa 1
xyz 0

注意aaa被询问了两次

我有一份Q k-mers的名单。我有一本带计数的k-mers字典（一本字典的长度可能小于Q）。使用for循环，我遍历DNA和每个字符，同时跟踪当前的k-mero（N）。在下一次迭代中，我通过删除第一个字母并附加当前字符来更新当前k-mer。为了输出答案，我迭代qk-mers列表并在字典中搜索其计数

l, n , k, q = [int(x) for x in sys.stdin.readline().strip('\n').split(' ')]

dna = ''

for i in range(l):
    dna += sys.stdin.readline().strip('\n')

mykmer =[]
mycount = {}

for i in range(q):
    kmer = sys.stdin.readline().strip('\n')
    mykmer.append(kmer)   
    mycount[kmer]=0


current = dna[0:k]

for j in range(k-1,len(dna)): 

    if j != k-1:
        current = current[1:]+str(dna[j]) 

    if current in mykmer:
        mycount[current] += 1



for x in mykmer:
    print(str(x)+' '+str(mycount[x]))

我得到了正确的答案，但我超时了

Answer 1

我会改进你的内环：

for j in range(len(dna) - (len(dna) % k)):
    current = dna[j:j+k]
    if current in mycount:
        mycount[current] += 1

一次切片的成本低于重复切片和附加current = current[1:]+str(dna[j])成本高于dna[j:j+k]。因为它会导致3个字符串分配，而因为切片会导致一个字符串分配

使用您已有的词典而不是列表来进行成员资格测试。这就去掉了Q的因子

range(len(dna) - (len(dna) % k))确保循环不会不必要地考虑最后几个索引