Java字符對齊算法

我有兩個我想要對齊的100個字符（最大，可能更小或不是相同大小）的數組。當有一個字符與另一個字符不同時，我想添加一個「 - 」。我發現基於動態編程的Needleman–Wunsch算法和基於動態編程的一般局部對齊方法，但它們似乎對於我想要做的事情來說太複雜。我只需要在Java中使用簡單的算法，大概少於50行，此代碼將在之後被翻譯爲彙編語言，以便我需要一個簡單的算法。Java字符對齊算法

有沒有辦法做這種對比與差異算法？如果是的話，有人可以指出我該怎麼做？我在biostar部分搜索，但似乎非常需要使用我提到的兩種算法。

英語不是我的母語，所以我可能搜索了錯誤的關鍵字。

我的程序已經與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-

由於

來源

2013-02-23 metraon

是輸出是否正確？ 'IY'消失了，而'Q'仍然存在？數組2的順序是相關的，還是僅僅遵循數組1的順序？ – 2013-02-23 17:10:32

我修改了輸入輸出以使問題更清楚，並且順序是相關的。 – metraon 2013-02-23 17:20:48

在維基百科文章http://en.wikipedia.org/wiki/Sequence_alignment中，這些基本上是列出的唯一算法。互聯網不太可能想出更好的東西。此外，您的問題情況如何比通用序列比對案例更簡單？ – 2013-02-23 17:34:58

使用萊文斯坦距離不正是你想要的變化：

輸出

-MKNLASREVNIYVNGKLV 
QM---ASREVNIYVNGKL-

代碼：

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()}; 
    } 
}

來源

2013-02-23 17:36:36

太棒了！更簡單，更清潔！ – metraon 2013-02-23 17:48:36

記住添加一些解釋說明你的算法與通用序列比對相比不能做什麼？ – 2013-02-23 17:50:45

它不能根據操作本身或它們在字符串上的位置爲「編輯操作」分配權重。當然，修改它很容易。這種算法有一個更加通用的版本叫做[Smith-Waterman]（http://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorithm）。 – 2013-02-23 17:57:21

您的問題的描述，立即使我認爲Levenshtein distance及其相關算法，這是簡單的（絕對小於50行）但也基於動態編程。

原始算法僅計算所需更改的數量，但可以輕鬆修改它以找到所需的插入，刪除和替換。其實我不確定你是否想要處理替換，你會如何對準例如ABC和ADC？

來源

2013-02-23 17:14:17 aditsu

Java字符對齊算法

回答

相關問題