Algoritmo di allineamento dei caratteri Java

Question

Ho due array di 100 caratteri (massimo, potrebbe essere inferiore o inferiore alle stesse dimensioni) che desidero allineare. Voglio aggiungere un "-" quando c'è un personaggio diverso dall'altro. Ho trovato l'algoritmo Needleman–Wunsch, che si basa sulla programmazione dinamica, e l'algoritmo Smith–Waterman che è un metodo di allineamento locale generale basato anch'esso sulla programmazione dinamica ma che sembra troppo complesso per quello che voglio fare. Ho solo bisogno di un semplice algoritmo in Java forse su meno di 50 righe, questo codice sarà tradotto in linguaggio assembly dopo, quindi perché ho bisogno di un algoritmo semplice.

C'è un modo per eseguire questo tipo di allineamento con un algoritmo diff? Se sì, qualcuno può indicarmi come farlo? Ho cercato nella sezione di biostar, ma sembra che ho bisogno di usare i due algoritmi che ho citato.

L'inglese non è la mia lingua madre, quindi ho cercato le parole chiave sbagliate.

Il mio programma funziona già con l'algoritmo di Needleman e le sue circa 200 righe (ish) di codice.

Esempio di ingresso/uscita desiderato:

Input 
Array 1 : MKNLASREVNIYVNGKLV 
Array 2 : QMASREVNIYVNGKL 


Output 
Array 1 (or a simple print) : -MKNLASREVNIYVNGKLV 
Array 2 (or a simple print) : QM---ASREVNIYVNGKL- 

Grazie

Answer 1

Utilizzando una variazione di Levenshtein distanza che fa esattamente ciò che si vuole:

uscita

-MKNLASREVNIYVNGKLV 
QM---ASREVNIYVNGKL- 

Codice:

public class Main { 
    public static void main(String[] args) { 
     String[] aligned = align("MKNLASREVNIYVNGKLV", "QMASREVNIYVNGKL"); 
     System.out.println(aligned[0]); 
     System.out.println(aligned[1]); 
    } 

    public static String[] align(String a, String b) { 
     int[][] T = new int[a.length() + 1][b.length() + 1]; 

     for (int i = 0; i <= a.length(); i++) 
      T[i][0] = i; 

     for (int i = 0; i <= b.length(); i++) 
      T[0][i] = i; 

     for (int i = 1; i <= a.length(); i++) { 
      for (int j = 1; j <= b.length(); j++) { 
       if (a.charAt(i - 1) == b.charAt(j - 1)) 
        T[i][j] = T[i - 1][j - 1]; 
       else 
        T[i][j] = Math.min(T[i - 1][j], T[i][j - 1]) + 1; 
      } 
     } 

     StringBuilder aa = new StringBuilder(), bb = new StringBuilder(); 

     for (int i = a.length(), j = b.length(); i > 0 || j > 0;) { 
      if (i > 0 && T[i][j] == T[i - 1][j] + 1) { 
       aa.append(a.charAt(--i)); 
       bb.append("-"); 
      } else if (j > 0 && T[i][j] == T[i][j - 1] + 1) { 
       bb.append(b.charAt(--j)); 
       aa.append("-"); 
      } else if (i > 0 && j > 0 && T[i][j] == T[i - 1][j - 1]) { 
       aa.append(a.charAt(--i)); 
       bb.append(b.charAt(--j)); 
      } 
     } 

     return new String[]{aa.reverse().toString(), bb.reverse().toString()}; 
    } 
} 

Answer 2

La descrizione del problema fa immediatamente pensare del Levenshtein distance ed il suo algoritmo relativo, che è semplice (sicuramente meno di 50 righe) ma si basa anche sulla programmazione dinamica.

L'algoritmo originale calcola semplicemente il numero di modifiche richieste, ma può essere facilmente modificato per trovare gli inserimenti, le eliminazioni e le sostituzioni richieste. In realtà non sono sicuro che tu voglia gestire le sostituzioni, come ti allinei ad esempio ABC e ADC?