Python - Gruppierung defaultdict Werte durch Hamming Abstand in Tasten

Question

Ich habe ein Standard-Diktat mit ~ 700 Tasten. Die Schlüssel haben ein Format wie A_B_STRING. Was ich tun muss, ist, den Schlüssel durch '_' zu teilen und den Abstand zwischen 'STRING' für jeden Schlüssel zu vergleichen, wenn A und B identisch sind. Wenn der Abstand < = 2 ist, möchte ich die Listen für diese Schlüssel in einem einzigen Standardschlüssel gruppieren: Wertgruppe. Es wird mehrere Schlüssel geben, die übereinstimmen und gruppiert werden sollen. Ich möchte auch in dem neuen kombinierten Standarddict alle Schlüssel: Wert-Paare behalten, die es nicht zu einer Gruppe gemacht haben.

Die Eingabedatei befindet sich im Format FASTA, wobei die Header die Schlüssel und die Werte die Sequenzen sind (defaultdict wird verwendet, da mehrere Sequenzen basierend auf einem Explosionsbericht aus einer ursprünglichen Fasta-Datei denselben Header haben). Diese

ist das, was ich bisher:

!/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]) 

Das Problem ist, dass dieser Code nicht wie erwartet funktioniert. Beim Drucken der Schlüssel im kombinierten Standarddict; Ich sehe deutlich, dass es viele gibt, die kombiniert werden können. Die Länge des kombinierten Standarddiktions ist jedoch etwa halb so groß wie das Original.

bearbeiten

Alternative keine 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])) 

jedoch mit diesen Verfahren, bin ich immer noch ein paar aus, dass fehlende passen nicht alle anderen zu.

Answer 1

Ich glaube, ich ein Problem mit Ihrem Code finden Sie in diesem Szenario vor:

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 

Ich könnte mir vorstellen, Sie alle drei von ihnen wollen würde unter 1 Schlüssel zu kombinieren. Allerdings betrachten dieses Szenario:

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' 

Jetzt wird es ein bisschen schwierig, da die Zeile 0 ist Abstand 2 von Zeile 1 und Zeile 1 Abstand 2 von Reihe 2, aber Sie könnten sie alle zusammen nicht wollen als Zeile 0 ist Abstand 3 weg von Reihe 2! Hier

ist ein Beispiel einer Arbeitslösung, vorausgesetzt, dies ist das, was man die Ausgabe aussehen soll:

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) 

In unserem zweiten Beispiel, das im folgende Wörterbuch ergeben würde, wenn das nicht der ist Antwort, nach der Sie suchen, könnten Sie genau angeben, was das endgültige Wörterbuch für dieses Beispiel sein soll?

Beachten Sie, dass dies ein O (n^2) -Algorithmus ist, was bedeutet, dass er nicht skalierbar ist, wenn Ihr Schlüsselsatz größer wird.