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

我是 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 在相反的方向

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

你能帮忙吗？

请您参考如下方法:

从算法的角度来看，您可能应该看看 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']) 
# [] 

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