Python - 通过键中的汉明距离对 defaultdict 值进行分组

Question

我有一个约 700 个键的默认字典。 key 采用 A_B_STRING 等格式。我需要做的是用“_”拆分 key ，如果 A 和 B 相同，则比较每个 key 的“STRING”之间的距离。如果距离 <= 2，我想将这些键的列表分组到一个 defaultdict key:value 组中。将有多个键应该匹配并分组。我还想保留在新的组合 defaultdict 中，所有没有进入组的键:值对。

输入文件在FASTA格式，其中标题是键，值是序列(使用 defaultdict 是因为基于原始 fasta 文件的 blast 报告，多个序列具有相同的标题)。

这是我目前所拥有的:

!/usr/bin/env python

import sys
from collections import defaultdict
import itertools

inp = sys.argv[1]                                                       # input fasta file; format '>header'\n'sequence'

with open(inp, 'r') as f:
        h = []
        s = []
        for line in f:
                if line.startswith(">"):
                        h.append(line.strip().split('>')[1])            # append headers to list
                else:
                        s.append(line.strip())                          # append sequences to list

seqs = dict(zip(h,s))                                                   # create dictionary of headers:sequence

print 'Total Sequences: ' + str(len(seqs))                              # Numb. total sequences in input file

groups = defaultdict(list)

for i in seqs:
        groups['_'.join(i.split('_')[1:])].append(seqs[i])                      # Create defaultdict with sequences in lists with identical headers

def hamming(str1, str2):
        """ Simple hamming distance calculator """
        if len(str1) == len(str2):
                diffs = 0
                for ch1, ch2 in zip(str1,str2):
                        if ch1 != ch2:
                                diffs += 1
                return diff

keys = [x for x in groups]

combos = list(itertools.combinations(keys,2))                           # Create tupled list with all comparison combinations

combined = defaultdict(list)                                            # Defaultdict in which to place groups

for i in combos:                                                        # Combo = (A1_B1_STRING2, A2_B2_STRING2)
        a1 = i[0].split('_')[0]
        a2 = i[1].split('_')[0]

        b1 = i[0].split('_')[1]                                         # Get A's, B's, C's
        b2 = i[1].split('_')[1]

        c1 = i[0].split('_')[2]
        c2 = i[1].split('_')[2]

        if a1 == a2 and b1 == b2:                                       # If A1 is equal to A2 and B1 is equal to B2
                d = hamming(c1, c2)                                     # Get distance of STRING1 vs STRING2
                if d <= 2:                                              # If distance is less than or equal to 2
                        combined[i[0]].append(groups[i[0]] + groups[i[1]])      # Add to defaultdict by combo 1 key

print len(combined)
for c in sorted(combined):
        print c, '\t', len(combined[c])

问题是这段代码没有按预期工作。在组合的 defaultdict 中打印键时；我清楚地看到有很多可以组合的。但是，合并后的 defaultdict 的长度大约是原始长度的一半。

编辑

替代方案没有 itertools.combinations:

for a in keys:
        tocombine = []
        tocombine.append(a)
        tocheck = [x for x in keys if x != a]
        for b in tocheck:
                i = (a,b)                                               # Combo = (A1_B1_STRING2, A2_B2_STRING2)
                a1 = i[0].split('_')[0]
                a2 = i[1].split('_')[0]

                b1 = i[0].split('_')[1]                                         # Get A's, B's, C's
                b2 = i[1].split('_')[1]

                c1 = i[0].split('_')[2]
                c2 = i[1].split('_')[2]

                if a1 == a2 and b1 == b2:                                       # If A1 is equal to A2 and B1 is equal to B2
                        if len(c1) == len(c2):                                          # If length of STRING1 is equal to STRING2
                                d = hamming(c1, c2)                                     # Get distance of STRING1 vs STRING2
                                if d <= 2:
                                        tocombine.append(b)
        for n in range(len(tocombine[1:])):
                keys.remove(tocombine[n])
                combined[tocombine[0]].append(groups[tocombine[n]])

final = defaultdict(list)
for i in combined:
        final[i] = list(itertools.chain.from_iterable(combined[i]))

但是，使用这些方法，我仍然遗漏了一些与其他方法不匹配的内容。

Answer 1

考虑到这种情况，我想我发现您的代码存在一个问题:

0: A_B_DATA1 
1: A_B_DATA2    
2: A_B_DATA3 

All the valid comparisons are:  
0 -> 1 * Combines under key 'A_B_DATA1' 
0 -> 2 * Combines under key 'A_B_DATA1'
1 -> 2 * Combines under key 'A_B_DATA2' **opps

我想您会希望将所有这三个组合在一个键下。但是请考虑这种情况:

0: A_B_DATA111
1: A_B_DATA122    
2: A_B_DATA223 

All the valid comparisons are:  
0 -> 1 * Combines under key 'A_B_DATA111' 
0 -> 2 * Combines under key 'A_B_DATA111'
1 -> 2 * Combines under key 'A_B_DATA122'

现在它变得有点棘手，因为第 0 行与第 1 行的距离为 2，第 1 行与第 2 行的距离为 2，但您可能不希望它们都放在一起，因为第 0 行与第 2 行的距离为 3!

这是一个可行的解决方案示例，假设这是您希望输出的样子:

def unpack_key(key):
    data = key.split('_')
    return '_'.join(data[:2]), '_'.join(data[2:])

combined = defaultdict(list)
for key1 in groups:
    combined[key1] = []
    key1_ab, key1_string = unpack_key(key1)
    for key2 in groups:
        if key1 != key2:
            key2_ab, key2_string = unpack_key(key2)
            if key1_ab == key2_ab and len(key1_string) == len(key2_string):
               if hamming(key1_string, key2_string) <= 2:
                   combined[key1].append(key2)

在我们的第二个示例中，这将产生以下字典，如果这不是您要查找的答案，您能否准确输入此示例的最终字典应该是什么？

A_B_DATA111: ['A_B_DATA122']
A_B_DATA122: ['A_B_DATA111', 'A_B_DATA223']
A_B_DATA223: ['A_B_DATA122']

请记住，这是一个复杂度为 O(n^2) 的算法，这意味着当您的 key 集变大时它不可扩展。