Wie optimiert man ein Python-Skript, das 4 ** k mal läuft?

Question

Programmiersprache: Python 3.4

Ich habe ein Programm für den Kurs Bioinformatik 1 von Coursera geschrieben. Das Programm funktioniert in Ordnung, aber ist sehr langsam für große Datensätze. Ich schätze, das liegt daran, dass die Schleife 4 x k mal läuft, wobei k die Länge der Teilzeichenfolge ist, die an die Funktion übergeben wird. Eingabe: Strings Text und Muster zusammen mit einer ganzen Zahl d. Ausgabe: Alle Anfangspositionen, bei denen Muster als Teilzeichenfolge von Text mit höchstens d Mismatches angezeigt wird.

Dies ist mein Code:

def MotifCount(string1, substring, d): 
    k = 4 ** (len(substring)) 
    codeArray = list(itertools.product(['A', 'C', 'G', 'T'], repeat=len(substring))) 
    for i in range(k): 
     codeArray2 = ''.join(list(codeArray[i])) 
     HammingValue = HammingDistance(codeArray2, substring) 
     if HammingValue <= d: 
      for j in range(len(string1)): 
       if(string1.find(codeArray2, j) == j): 
        print(j) 



def HammingDistance(string_1, string_2): 
    length_1 = len(string_1) 
    length_2 = len(string_2) 
    count = 0 
    for i in range(length_1): 
     if string_1[i] != string_2[i]: 
      count += 1 
    return count 

Probe Input:

CGCCCGAATCCAGAACGCATTCCCATATTTCGGGACCACTGGCCTCCACGGTACGGACGTCAATCAAAT 
ATTCTGGA 
3 

Ausgang:

6 7 26 27 

Ich möchte diesen Code für größere Datenmengen optimieren. Gibt es eine Möglichkeit, die Laufzeit des Codes zu reduzieren?

Answer 1

import itertools 

def HammingDistance(string_1, string_2): 
    assert len(string_1) == len(string_2) 
    return sum(c1 != c2 for c1, c2 in zip(string_1, string_2)) 

def MotifCount(string1, substring, d): 
    for i in range(len(string1) - len(substring) + 1): 
     if HammingDistance(string1[i:i+len(substring)], substring) <= d: 
      print(i) 

MotifCount("CGCCCGAATCCAGAACGCATTCCCATATTTCGGGACCACTGGCCTCCACGGTACGGACGTCAATCAAAT", "ATTCTGGA", 3) 

Es gibt:

6 
7 
26 
27 

schnell.