Ottenere tutte le combinazioni di stringhe in base alla distanza massima di Hamming (numero di disallineamenti) in Java

Question

Esiste un algoritmo per generare tutte le possibili combinazioni di stringhe di una stringa (sequenza DNA) con un numero determinato di posizioni massime consentite che possono variare (errore massimo , massima distanza di Hamming)?

L'alfabeto è {A, C, T, G}.

Esempio per una stringa AGCC e il numero massimo dei disallineamenti 2:

Hamming distance is 0 
    {AGCC} 
Hamming distance is 1 
    {CGCC, TGCC, GGCC, AACC, ACCC, ATCC, AGAC, AGTC, ..., AGCG} 
Hamming distance is 2 
    {?} 

Un possibile approccio sarebbe quello di generare un insieme di tutte le permutazioni di una stringa, scorrere su di essi e rimuovere tutte le stringhe con maggiore Hamming distanza che dovrebbe essere.

Questo approccio è molto ressource-mangiare, da una data stringa di 20 caratteri e la massima distanza di Hamming di 5.

c'è un altro, più efficienti approcahes/implementazioni per questo?

Answer 1

Basta usare un algoritmo di generazione di permutazione normale, tranne che si passa intorno alla distanza, diminuendo quando si ha un carattere diverso.

static void permute(char[] arr, int pos, int distance, char[] candidates) 
{ 
    if (pos == arr.length) 
    { 
     System.out.println(new String(arr)); 
     return; 
    } 
    // distance > 0 means we can change the current character, 
    // so go through the candidates 
    if (distance > 0) 
    { 
     char temp = arr[pos]; 
     for (int i = 0; i < candidates.length; i++) 
     { 
     arr[pos] = candidates[i]; 
     int distanceOffset = 0; 
     // different character, thus decrement distance 
     if (temp != arr[pos]) 
      distanceOffset = -1; 
     permute(arr, pos+1, distance + distanceOffset, candidates); 
     } 
     arr[pos] = temp; 
    } 
    // otherwise just stick to the same character 
    else 
     permute(arr, pos+1, distance, candidates); 
} 

chiamata con:

permute("AGCC".toCharArray(), 0, 1, "ACTG".toCharArray()); 

Prestazioni nota:

Per una lunghezza di stringa di 20, la distanza di 5 e un alfabeto 5 caratteri, ci sono già più di 17 milioni di candidati (supponendo che il mio codice sia corretto).

Il codice precedente impiega meno di un secondo per passare attraverso di essi sulla mia macchina (senza stampa), ma non aspettatevi che un generatore sia in grado di generare molto più di quello in un ragionevole lasso di tempo, poiché ci sono semplicemente troppe possibilità.