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

我正在做一些测序分析，并且我正在尝试根据一些标识符创建默认的遗传序列字典。因此，请看下面的示例，我创建了一个字典，并将两个序列AGAGAG和ATATAT放在同一列表中，因为它们具有相同的标识符CCCCCC：

输入：

CCCCCCAGAGAG
CCCCCCATATAT

码：

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

我的问题是，如果键序列在levenshtein距离1之内，我希望将其视为相同的键。所以，如果我遇到一个看起来像这样的序列：

CCCCCTACACAC

我想浏览一下字典，看是否有CCCCCC并看到distance('CCCCCC', 'CCCCCT') < 2，所以也许将CCCCCA更改为CCCCCC，然后追加到上述相同的列表中。

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

最佳答案

您可以使用difflib.SequenceMatcher返回相等序列的1，也可以将其差值用于compare：

在这种情况下 ：

>>> 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']})
>>>