python

在defaultdict中使用levenshtein距離我正在做一些測序分析，我試圖根據一些標識符創建基因序列的默認字典。所以，在看下面的例子中，我創建了一個字典，並把兩個序列AGAGAG和ATATAT在同一個列表中，因爲他們有CCCCCC相同的標識符：python

輸入：

CCCCCCAGAGAG 
CCCCCCATATAT

代碼：

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

我的問題是，如果密鑰序列是1:1的Levenshtein距離內我希望它被視爲相同的密鑰。所以，如果我碰到過，看起來像這樣的順序：

CCCCCTACACAC

我想通過字典來看看，看看有CCCCCC，看到distance('CCCCCC', 'CCCCCT') < 2所以也許改變CCCCCA到CCCCCC，然後添加到同一列表，以上。

希望有這樣做的好方法。謝謝。

來源

2015-08-19 The Nightman

對於你的例子，你的意思是'距離（'CCCCCC'，'CCCCCT'）<2'？ – Kasramvd

你是說前六個字是鑰匙？字符串也可以是字母的任意組合嗎？ –

如果你考慮每個字符串的每個字符串在LD方面，那麼你將會做太多的計算。最重要的是首先排序所有鏈接。您應該對'CCCCCC'長度字符串的每個索引進行排序，然後比較幾個附近的字符串（如果我們談論的是數百萬個字符串）。「一對夫婦」的定義取決於你的組合的大小。無論如何，在這種情況下，你只需要做比較少的比較。 – PascalVKooten

可以使用difflib.SequenceMatcher這對於等於序列返回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']}) 
>>>

來源

2015-08-19 16:38:28 Kasramvd

不要以爲OP是在問如何計算，他們會問如何使用一個單一的鍵爲多個相似的字符串 –

@PadraicCunningham是的，完成！ – Kasramvd

如果輸入過大，則無法進行所有Levenshtein距離計算。（1000x1000比較需要0.6秒，10k乘10k需要一分鐘....） – PascalVKooten

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（局部敏感哈希）。也許有人可以進一步幫助。

來源

2015-08-19 17:06:16 PascalVKooten

回答

相關問題