python - 提高列表中子字符串搜索的速度

Question

我是 Python 的新手，我正在努力提高一段代码的速度。

我有一本包含 500k DNA 序列的字典。作为键，我有序列的标识符，而作为值，我有相应的 DNA 序列。这些序列的长度可变(它只是一个包含 CTACTA 的字符串...)，可能有 200 到 60k 个核苷酸。我需要删除作为较大序列子串的 DNA 序列。

我是这样写的:

def remove_subs():

    #Create a list of values based on reversed lenght
    LISTA=sorted(list(x for x in finaldic.values()), key=len, reverse=True)

    LISTA2=[]

    for a in range(len(LISTA)):
        #run the same list but in opposite direction 
        for b in range(len(sorted(LISTA,key=len))):
            if len(LISTA[b])<len(LISTA[a]):
                if LISTA[a].find(LISTA[b])!=-1 or Bio.Seq.reverse_complement(LISTA[a]).find(LISTA[b])!=-1 and LISTA[b]!=LISTA[a]:
                    LISTA2.append(LISTA[a])

我试图通过在两个 for 循环中运行来识别那些子字符串序列，一个仅包含 DNA 序列(按长度排序)的列表，使用内置的 .find 在相反的方向

此代码运行完美，但需要很长时间才能运行如此大量的信息。我很确定存在一些更快的选择。

你能帮忙吗？

Answer 1

从算法的角度来看，您可能应该看看 suffix trees .首先，您从要查找的字符串构建一个广义后缀树，其构建时间复杂度为 O(n)(其中 n = 要搜索的所有字符串中的字符数)。然后，您可以查询该树，如果其中包含子字符串，则可以查询该树，其时间复杂度为 O(m)，其中 m 是子字符串的长度。从本质上讲，这是尽可能快的速度。

---

描述几个后缀树库的堆栈溢出问题:

python: library for generalized suffix trees

不幸的是，这里的示例不是非常成熟的代码库...有一些 C 库更侧重于优化等等。尽管如此，像这样的东西suffix tree algorithm应该是您代码的简单替代品:

import SubstringDict
d = SubstringDict.SubstringDict()
d['foobar'] = 1  
d['barfoo'] = 2
d['forget'] = 3
d['arfbag'] = 4

print(d['a'])
# [1, 2, 4]
print(d['arf'])
# [2, 4]
print (d['oo'])
# [1, 2]
print(d['food'])
# []

搜索和匹配字符串是生物信息学中一个相当大且活跃的领域，并且有大量关于这个问题的文献。