Come ottimizzare uno script python che viene eseguito per 4 ** volte k?

Question

Linguaggio di programmazione: Python 3.4

Ho scritto un programma per il corso Bioinformatica 1 da Coursera. Il programma funziona correttamente, ma è molto lento per per dataset di grandi dimensioni. Immagino, è perché il ciclo è in esecuzione per 4 ** k volte, dove k è la lunghezza della sottostringa che viene passata nella funzione. Immissione: stringhe Testo e Modello insieme a un numero intero d. Output: tutte le posizioni iniziali in cui Pattern viene visualizzato come sottostringa di testo con al massimo d disallineamenti.

Questo è il mio codice:

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 

Esempio Ingresso:

CGCCCGAATCCAGAACGCATTCCCATATTTCGGGACCACTGGCCTCCACGGTACGGACGTCAATCAAAT 
ATTCTGGA 
3 

uscita:

6 7 26 27 

voglio per ottimizzare il codice per i set di dati più grandi. C'è un modo per ridurre il tempo di esecuzione del codice?

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) 

Dà:

6 
7 
26 
27 

rapidamente.