在 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

您可以使用 difflib.SequenceMatcher which returns 1 来表示相同的序列，您可以使用您的差异来进行比较：

在这种情况下：

>>> import difflib
>>> difflib.SequenceMatcher(None,'CCCCCC', 'CCCCCT').ratio()
0.8333333333333334

演示：

>>> from itertools import combinations
>>> import difflib

>>> li=['AAAAAAACDCBA', 'CCCCCCATATAT', 'CCCCCCAGAGAG', 'CCCCCTACACAC', 'AAAAAAACACAC']
>>> d = defaultdict(list)
>>> for i in li:
...     d[i[:6]].append(i[6:])
... 
>>> keys=d.keys()
>>> for i,j in combinations(keys,2):
...      if difflib.SequenceMatcher(None,i, j).ratio()>0.8:
...         d[i].extend(d[j])
...         del d[j]
... 
>>> d
defaultdict(<type 'list'>, {'AAAAAA': ['ACDCBA', 'ACACAC'], 'CCCCCC': ['ATATAT', 'AGAGAG', 'ACACAC']})
>>>

Answer 2

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

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

事实上，您需要某种形式的 LSH（局部敏感哈希）。也许有人可以进一步提供帮助。

在 python 中对 defaultdict 中的键使用 levenshtein 距离

Use levenshtein distance for keys in defaultdict in python

python

dictionary

levenshtein-distance