Javaキャラクタのアライメントアルゴリズム

Question

私は、整列させたい100文字の2つの配列を持っています（最大、それ以下でも同じでもないかもしれません）。他の文字と異なる文字がある場合は、「 - 」を追加します。ダイナミックプログラミングに基づいたNeedleman–Wunschアルゴリズムと、動的プログラミングに基づいた一般的なローカルアライメントメソッドであるSmith–Watermanアルゴリズムが見つかりましたが、それらは私がやりたいことに対しては複雑すぎます。私はちょうど50行未満のJavaの単純なアルゴリズムを必要とするだけで、このコードはアセンブリ言語に翻訳されるので、単純なアルゴリズムが必要なのです。

diffアルゴリズムとのこの種のアラインメントはありますか？はいの場合、誰かが私にこれを行う方法を教えることができますか？私はbiostarセクションを検索しましたが、私が言及した2つのアルゴリズムを使用する必要があるようです。

英語は母国語ではないため、間違ったキーワードを検索してしまう可能性があります。

私のプログラムは、すでにNeedlemanアルゴリズムと約200行（ish）のコードで動作します。所望の入力/出力の

例：

Input 
Array 1 : MKNLASREVNIYVNGKLV 
Array 2 : QMASREVNIYVNGKL 


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

おかげ

Answer 1

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

あなたの問題の説明がすぐに私はLevenshtein distanceを思わせると簡単ですその関連アルゴリズム、（間違いなく未満50行）動的プログラミングにも基づいています。

元のアルゴリズムは必要な変更の数を計算するだけですが、必要な挿入、削除、および置換を見つけるために簡単に変更できます。実際には、置換を処理したいと思っているのかどうか分からない、たとえばABCとADCのためにどうやって整列させるのだろうか？

出力

-MKNLASREVNIYVNGKLV 
QM---ASREVNIYVNGKL- 

コード：正確に何をしたいんレーベンシュタイン距離の変化を使用して