python - 在Python中的defaultdict中使用levenshtein距离作为键

Question

我正在做一些测序分析，我正在尝试根据一些标识符创建一个默认的基因序列字典。所以看下面的例子，我创建了一个字典，并将两个序列 AGAGAG和ATATAT在同一个列表中，因为它们具有相同的标识符 CCCCCC :

输入:

CCCCCCAGAGAG
CCCCCCATATAT

代码:

from collections import defaultdict
d = defaultdict(list)
d['CCCCCC'].append('AGAGAG')
d['CCCCCC'].append('ATATAT')

我遇到的问题是，如果按键序列在编辑距离 1 之内，我希望将其视为相同的按键。因此，如果我遇到如下所示的序列:

CCCCCTACACAC

我想查看字典，看到有 CCCCCC看到 distance('CCCCCC', 'CCCCCT') < 2所以也许改变CCCCCA至CCCCCC然后附加到与上面相同的列表。

希望有一个好的方法可以做到这一点。谢谢。

Answer 1

import numpy
biginput = [''.join([chr(y) for y in numpy.random.randint(65, 90, 6)]) 
            for x in range(100000)]
biginput[0]
'VSNRGF'

我认为您必须以某种方式创建 ~6 种排序，这样对于每个键您只需进行几次比较。这是可能的，因为编辑只需要考虑几个变体。

事实上，您需要某种形式的 LSH(位置敏感哈希)。也许有人可以提供进一步的帮助。